Geometric median in nearly linear time

DOI10.1145/2897518.2897647MaRDI QIDQ5361815zbMATH OpenOpenAlexFDO

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

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.05225

zbMATH Keywords

geometric medianinterior-point methodsstochastic gradient descent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In this paper we provide faster algorithms for solving the geometric median problem: given $n$ points in $mathbb{R}^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+epsilon)$-approximate geometric median were $O(dcdot{n}^{4/3}epsilo{n}^{-8/3})$ by Chin et. al, $ildeO(dexpepsilo{n}^{-4}logepsilo{n}^{-1})$ by Badoiu et. al, $O(nd+mathrmpoly(d,epsilo{n}^{-1})$ by Feldman and Langberg, and $O((nd{)}^{O(1)}logfrac1epsilon)$ by Parrilo and Sturmfels and Xue and Ye. In this paper we show how to compute a $(1+epsilon)$-approximate geometric median in time $O(ndlo{g}^{3}frac1epsilon)$ and $O(depsilo{n}^{-2})$. While our $O(depsilo{n}^{-2})$ is a fairly straightforward application of stochastic subgradient descent, our $O(ndlo{g}^{3}frac1epsilon)$ time algorithm is a novel long step interior point method. To achieve this running time we start with a simple $O((nd{)}^{O(1)}logfrac1epsilon)$ 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.

Recommendations

• Optimal algorithms for geometric centers and depth
• Approximation algorithms for geometric median problems
• Faster algorithms for the geometric transportation problem
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• The projection median as a weighted average

Cited in

(22)

• Computing kemeny rankings from \(d\)-Euclidean preferences
• Finding the Median (Obliviously) with Bounded Space
• Hardness results for structured linear systems
• Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
• Optimization algorithms for faster computational geometry
• Sub-Gaussian estimators of the mean of a random vector
• Approximation and complexity of the capacitated geometric median problem
• Mean estimation with sub-Gaussian rates in polynomial time
• Robust estimators in high-dimensions without the computational intractability
• Approximation algorithms for geometric median problems
• The geometric median and applications to robust mean estimation
• Active-learning a convex body in low dimensions
• Optimal algorithms for geometric centers and depth
• Preconditioning for the geometric transportation problem
• A causal filter of gradient information for enhanced robustness and resilience in distributed convex optimization
• Mean estimation in high dimension
• Mean estimation and regression under heavy-tailed distributions: A survey
• An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions
• On geometric prototype and applications
• Semi-supervised algorithms for approximately optimal and accurate clustering
• Minimizing the size of the uncertainty regions for centers of moving entities
• Medians in median graphs and their cube complexes in linear time

This page was built for publication: Geometric median in nearly linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361815)