# Geometric Median in Nearly Linear Time

arXiv: https://arxiv.org/abs/1606.05225 · HTML: https://mlsanity.com/paper/1606.05225/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2016.

## Built on by (most cited first, 30 of 39)

- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning](https://mlsanity.com/paper/2302.07173/) (2023)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Robust Training in High Dimensions via Block Coordinate Geometric Median Descent](https://mlsanity.com/paper/2106.08882/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [A Huber Loss Minimization Approach to Byzantine Robust Federated Learning](https://mlsanity.com/paper/2308.12581/) (2023)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)
- [Improved Learning-augmented Algorithms for k-means and k-medians Clustering](https://mlsanity.com/paper/2210.17028/) (2022)
- [Provably Robust Federated Reinforcement Learning](https://mlsanity.com/paper/2502.08123/) (2025)
- [Byzantine Fault-Tolerance in Federated Local SGD under 2f-Redundancy](https://mlsanity.com/paper/2108.11769/) (2021)
- [Global Convergence Guarantees for Federated Policy Gradient Methods with Adversaries](https://mlsanity.com/paper/2403.09940/) (2024)
- [Robust Principal Component Analysis: A Median of Means Approach](https://mlsanity.com/paper/2102.03403/) (2021)
- [Adversarially robust clustering with optimality guarantees](https://mlsanity.com/paper/2306.09977/) (2023)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Private Geometric Median](https://mlsanity.com/paper/2406.07407/) (2024)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [Enriching Disentanglement: From Logical Definitions to Quantitative Metrics](https://mlsanity.com/paper/2305.11512/) (2023)
- [Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients](https://mlsanity.com/paper/2408.09539/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence](https://mlsanity.com/paper/2106.14588/) (2021)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)
- [Robust empirical risk minimization via Newton's method](https://mlsanity.com/paper/2301.13192/) (2023)
- [Balancing Privacy, Robustness, and Efficiency in Machine Learning](https://mlsanity.com/paper/2312.14712/) (2023)
- [Geometric Median (GM) Matching for Robust Data Pruning](https://mlsanity.com/paper/2406.17188/) (2024)
- [Geometric Median Matching for Robust k-Subset Selection from Noisy Data](https://mlsanity.com/paper/2504.00564/) (2025)
- [Private Geometric Median in Nearly-Linear Time](https://mlsanity.com/paper/2505.20189/) (2025)
- [H+: An Efficient Similarity-Aware Aggregation for Byzantine Resilient Federated Learning](https://mlsanity.com/paper/2509.24330/) (2025)
- [Robust learning with anytime-guaranteed feedback](https://mlsanity.com/paper/2105.11135/) (2021)
- [Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensing](https://mlsanity.com/paper/2309.14512/) (2023)

## Abstract (arXiv)

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 an abundance of research the previous fastest algorithms for computing a (1+ε)-approximate geometric median were O(d· n4/3ε-8/3) by Chin et. al, tildeO(dexpε-4logε-1) by Badoiu et. al, O(nd+poly(d,ε-1) by Feldman and Langberg, and O((nd)O(1)logfrac1ε) by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute a (1+ε)-approximate geometric median in time O(ndlog3frac1ε) and O(dε-2). While our O(dε-2) is a fairly straightforward application of stochastic subgradient descent, our O(ndlog3frac1ε) time algorithm is a novel long step interior point method. To achieve this running time we start with a simple O((nd)O(1)logfrac1ε) 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 very few cases we are aware of outperforming traditional interior point theory and the only we are aware of using interior point methods to obtain a nearly linear time algorithm for a canonical optimization problem that traditionally requires superlinear time. We hope our work leads to further improvements in this line of research.