Concentration of empirical barycenters in metric spaces

Victor-Emmanuel Brunel, Jordan Serres
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:337-361, 2024.

Abstract

Barycenters (aka Fréchet means) were introduced in statistics in the 1940’s and popularized in the fields of shape statistics and, later, in optimal transport and matrix analysis. They provide the most natural extension of linear averaging to non-Euclidean geometries, which is perhaps the most basic and widely used tool in data science. In various setups, their asymptotic properties, such as laws of large numbers and central limit theorems, have been established, but their non-asymptotic behaviour is still not well understood. In this work, we prove finite sample concentration inequalities (namely, generalizations of Hoeffding’s and Bernstein’s inequalities) for barycenters of i.i.d. random variables in metric spaces with non-positive curvature in Alexandrov’s sense. As a byproduct, we also obtain PAC guarantees for a stochastic online algorithm that computes the barycenter of a finite collection of points in a non-positively curved space. We also discuss extensions of our results to spaces with possibly positive curvature.

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-brunel24a, title = {Concentration of empirical barycenters in metric spaces}, author = {Brunel, Victor-Emmanuel and Serres, Jordan}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {337--361}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/brunel24a/brunel24a.pdf}, url = {https://proceedings.mlr.press/v237/brunel24a.html}, abstract = {Barycenters (aka Fréchet means) were introduced in statistics in the 1940’s and popularized in the fields of shape statistics and, later, in optimal transport and matrix analysis. They provide the most natural extension of linear averaging to non-Euclidean geometries, which is perhaps the most basic and widely used tool in data science. In various setups, their asymptotic properties, such as laws of large numbers and central limit theorems, have been established, but their non-asymptotic behaviour is still not well understood. In this work, we prove finite sample concentration inequalities (namely, generalizations of Hoeffding’s and Bernstein’s inequalities) for barycenters of i.i.d. random variables in metric spaces with non-positive curvature in Alexandrov’s sense. As a byproduct, we also obtain PAC guarantees for a stochastic online algorithm that computes the barycenter of a finite collection of points in a non-positively curved space. We also discuss extensions of our results to spaces with possibly positive curvature.} }
Endnote
%0 Conference Paper %T Concentration of empirical barycenters in metric spaces %A Victor-Emmanuel Brunel %A Jordan Serres %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-brunel24a %I PMLR %P 337--361 %U https://proceedings.mlr.press/v237/brunel24a.html %V 237 %X Barycenters (aka Fréchet means) were introduced in statistics in the 1940’s and popularized in the fields of shape statistics and, later, in optimal transport and matrix analysis. They provide the most natural extension of linear averaging to non-Euclidean geometries, which is perhaps the most basic and widely used tool in data science. In various setups, their asymptotic properties, such as laws of large numbers and central limit theorems, have been established, but their non-asymptotic behaviour is still not well understood. In this work, we prove finite sample concentration inequalities (namely, generalizations of Hoeffding’s and Bernstein’s inequalities) for barycenters of i.i.d. random variables in metric spaces with non-positive curvature in Alexandrov’s sense. As a byproduct, we also obtain PAC guarantees for a stochastic online algorithm that computes the barycenter of a finite collection of points in a non-positively curved space. We also discuss extensions of our results to spaces with possibly positive curvature.
APA
Brunel, V. & Serres, J.. (2024). Concentration of empirical barycenters in metric spaces. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:337-361 Available from https://proceedings.mlr.press/v237/brunel24a.html.

Related Material