Geometric median and robust estimation in Banach spaces
Open accessAbstract
In many real-world applications, collected data are contaminated by noise with heavy-tailed distribution and might contain outliers of large magnitude. In this situation, it is necessary to apply methods which produce reliable outcomes even if the input contains corrupted measurements. We describe a general method which allows one to obtain estimators with tight concentration around the true parameter of interest taking values in a Banach space. Suggested construction relies on the fact that the geometric median of a collection of independent “weakly concentrated” estimators satisfies a much stronger deviation bound than each individual element in the collection. Our approach is illustrated through several examples, including sparse linear regression and low-rank matrix recovery problems.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Minsker (2015) established sub-Gaussian concentration for the geometric median of means, which Theorem 1 adapts to contaminated juries.
“in high dimensions, Minsker (2015) established sub-Gaussian concentration for the geometric median of means-the result Theorem 1 adapts to contaminated juries”
From RoPoLL: Robust Panel of LLM Judges (2026) · cites this paper as Minsker (2015)
If at least (1-α)k points lie within distance r of z, then any geometric median x* satisfies ||x*-z||_2 ≤ C_α r, where C_α = (1-α)/sqrt(1-2α).
“If |{j : ∥x j -z∥ 2 ≤ r}| ≥ (1 -α)k, then x * -z 2 ≤ C α r, C α ≜ 1 -α √ 1 -2α . (16”
From RoPoLL: Robust Panel of LLM Judges (2026) · cites this paper as Minsker (2015)
If at least (1-α)k points are within distance r of z, then the minimizer x* satisfies ∥x* - z∥ ≤ C_α r with C_α = (1-α)/√(1-2α).
“If |{j : ∥x j -z∥ 2 ≤ r}| ≥ (1 -α)k, then ∥x * -z∥ 2 ≤ C α r with C α = (1 -α)/ √ 1 -2α.”
From RoPoLL: Robust Panel of LLM Judges (2026) · cites this paper as Minsker (2015)
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 19
- Alon, N., Matias, Y. and Szegedy, M. (1996). The space complexity of approximating the frequency moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996) 20-29. New York: ACM. MR1427494
- Bubeck, S., Cesa-Bianchi, N. and Lugosi, G. (2013). Bandits with heavy tail. IEEE Trans. Inform. Theory 59 7711-7717. MR3124669
- Bühlmann, P. and van de Geer, S. (2011). Statistics for High-Dimensional Data. Methods, Theory and Applications. Springer Series in Statistics. Heidelberg: Springer. MR2807761
- Candès, E.J., Li, X., Ma, Y. and Wright, J. (2011). Robust principal component analysis? J. ACM 58 Art. 11, 37. MR2811000
- Candès, E.J. and Plan, Y. (2011). Tight oracle inequalities for low-rank matrix recovery from a mini- mal number of noisy random measurements. IEEE Trans. Inform. Theory 57 2342-2359. MR2809094
- Hsu, D. and Sabato, S. (2013). Loss minimization and parameter estimation with heavy tails. Preprint. Available at arXiv:1307.1827. · arXiv
- Huber, P.J. and Ronchetti, E.M. (2009). Robust Statistics, 2nd ed. Wiley Series in Probability and Statistics. Hoboken, NJ: Wiley. MR2488795
- Koltchinskii, V. (2011). Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems. Lecture Notes in Math. 2033. Lectures from the 38th Probability Summer School held in Saint-Flour 2008. École d'Été de Probabilités de Saint-Flour. Heidelberg: Springer. MR2829871
- Lerasle, M. and Oliveira, R.I. (2011). Robust empirical mean estimators. Preprint. Available at arXiv:1112.3914. · arXiv
- Minsker, S. (2013). Geometric median and robust estimation in Banach spaces. Preprint. Available at http://sminsker.wordpress.com/publications/.
- Nemirovski, A. (2000). Topics in non-parametric statistics. In Lectures on Probability Theory and Statistics (Saint-Flour, 1998). Lecture Notes in Math. 1738 85-277. Berlin: Springer. MR1775640
- Nemirovski, A. and Yudin, D. (1983). Problem Complexity and Method Efficiency in Optimization. New York: Wiley.
- Nguyen, N.H. and Tran, T.D. (2013). Robust Lasso with missing and grossly corrupted observations. IEEE Trans. Inform. Theory 59 2036-2058. MR3043781
- Pearson, K. (1901). On lines and planes of closest fit to systems of points in space. Lond. Edinb. Dubl. Phil. Mag. J. Sci. 2 559-572.
- van der Vaart, A.W. and Wellner, J.A. (1996). Weak Convergence and Empirical Processes. Springer Series in Statistics. New York: Springer. MR1385671
- Vardi, Y. and Zhang, C.-H. (2000). The multivariate L 1 -median and associated data depth. Proc. Natl. Acad. Sci. USA 97 1423-1426 (electronic). MR1740461
- Weber, A. (1929). Uber Den Standort der Industrien (Alfred Weber's Theory of the Location of Indus- tries). Chicago, IL: Univ. Chicago Press.
- Wright, J. and Ma, Y. (2010). Dense error correction via ℓ 1 -minimization. IEEE Trans. Inform. Theory 56 3540-3560. MR2799012
- Zwald, L. and Blanchard, G. (2006). On the convergence of eigenspaces in kernel principal component analysis. In Advances in Neural Information Processing Systems 18 1649-1656. Cambridge, MA: MIT Press. Received November 2013 and revised May 2014
Cited by
Sorted by citations
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154503 · Cited by 390 · see citing works
RoPoLL: Robust Panel of LLM Judges
Acharya, A., Pan, K. W., & Verkhovsky, B. (2026) · arXiv · doi:10.48550/arxiv.2606.30931
- Authors
- Minsker, S.
- Affiliations
- Duke University (US)
- Corresponding author
- Minsker, Stanislav
- ORCID
- Minsker, Stanislav
- Venue
- Bernoulli
- Published
- 2015-11-01
- Volume
- 21
- Issue
- 4
- Pages
- 2308-2335
- ISSN
- 1350-7265 (ISSN-L)
- OpenAlex
- W1753414968
- Cited by
- 261
- References
- 0
- Citations by year
- 2026: 17 · 2025: 23 · 2024: 19 · 2023: 19 · 2022: 24 · 2021: 25 · 2020: 39 · 2019: 30 · 2018: 19 · 2017: 20 · 2016: 10 · 2015: 9 · 2014: 6 · 2013: 1
- FWCI
- 17.05
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Bernoulli (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0808847, 0847388)
- National Institutes of Health
- National Institute of Environmental Health Sciences
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Advanced Statistical Methods and Models
- Physical Sciences › Mathematics › Statistics and Probability › Statistical Methods and Inference
- Physical Sciences › Engineering › Computational Mechanics › Sparse and Compressive Sensing Techniques
- Keywords
- geometric median, robust estimation, Banach spaces, heavy-tailed noise, outliers, concentration bounds, sparse linear regression, low-rank matrix recovery
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
