Geometric median in nearly linear time

By Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub W. Pachocki, Aaron Sidford. 2016

189 citations recorded by the source corpus.

In this paper we provide faster algorithms for solving the geometric median problem: given n points in d compute a point that minimizes the sum of Euclidean distances to the points. This is one of the oldest non-trivial problems in computational geometry yet despite a long history of research the previous fastest running times for computing a (1+є)-approximate geometric median were O(d· n4/3є−8/3) by Chin et. al, Õ(dexpє−4logє−1) by Badoiu et. al, O(nd+poly(d,є−1)) by Feldman and Langberg, and the polynomial running time of O((nd)O(1)log1/є) by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute such an approximate geometric median in time O(ndlog3n/є) and O(dє−2). While our O(dє−2) is a fairly straightforward application of stochastic subgradient descent, our O(ndlog3n/є) time algorithm is a novel long step interior point method. We start with a simple O((nd)O(1)log1/є) time interior point method and show how to improve it, ultimately building an algorithm that is quite non-standard from the perspective of interior point literature. Our result is one of few cases of outperforming standard interior point theory. Furthermore, it is the only case we know of where interior point methods yield a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Graphics and Computer-Aided Design

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Robust Aggregation for Federated Learning (2019, background): “A theoretical proposal of a near-linear time algorithm for the geometric median was recently explored in [27].”
The Hidden Vulnerability of Distributed Learning in Byzantium (2018, background): “The exact geometric median is known to suffer from computational issues but can be approximated (Cohen et al., 2016).”
Distributed Statistical Machine Learning in Adversarial Settings (2017, methodology): “The parameter server computes the geometric median of means of gradients, which takes O(md + kd log(3)(N)), as the geometric median can be computed in O(kd log(3)(N)) [9].”
Generalized Byzantine-tolerant SGD (2018, methodology): “Geometric median has nearly linear (approximately O(nd)) time complexity (Cohen et al., 2016).”
Convolution-Weight-Distribution Assumption: Rethinking the Criteria of Channel Pruning (2020, methodology): “, geometric median (Cohen et al., 2016)), We call it Fermat .”
Filter Pruning via Geometric Median for Deep Convolutional Neural Networks Acceleration (2018, background): “As geometric median is a non-trivial problem in computational geometry, the previous fastest running times for computing a (1 + ✏)-approximate geometric median were e O(dn4/3 · ✏ 8/3) by [2], O(nd log(3)(n/✏)) by [3].”
Sub-Gaussian estimators of the mean of a random vector (2017, background): “Thus, the geometric median may be approximated efficiently, see [5] for the most recent result and for the rich history of the problem.”
Pruning Filter via Geometric Median for Deep Convolutional Neural Networks Acceleration (2018, background): “As geometric median is a non-trivial problem in computational geometry, the previous fastest running times for computing a (1 + )-approximate geometric median were Õ(dn · −8/3) by [2], O(nd log(3)(n/ )) by [3].”
Solving linear programs in the current matrix multiplication time (2018, background): “As for many important linear programs (and convex programs), the number of iterations has been decreased, including maximum ﬂow [Mad13, Mad16], minimum cost ﬂow [CMSV17], geometric median [CLM + 16], matrix scaling and balancing [CMTV17], and (cid:96) p regression [BCLL18].”
Mean Estimation and Regression Under Heavy-Tailed Distributions: A Survey (2019, unknown): “[20] for the most recent result and for the rich history of the problem.”
Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent (2017, background): “However, no closed form nor an exact algorithm to compute the geometric median is known (only approximations are available [5] and their Byzantine resilience is an open problem.).”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, background): “One way to boost the probability to 1 − δ, for someδ > 0, is to runO (log 1/δ) copies of the algorithm, each with 3/4 success probability and then output the geometric median of the solutions, which can be done in nearly linear time [17].”