Estimating Barycenters of Measures in High Dimensions
- URL: http://arxiv.org/abs/2007.07105v2
- Date: Sun, 14 Feb 2021 09:00:46 GMT
- Title: Estimating Barycenters of Measures in High Dimensions
- Authors: Samuel Cohen, Michael Arbel, Marc Peter Deisenroth
- Abstract summary: We propose a scalable and general algorithm for estimating barycenters of measures in high dimensions.
We prove local convergence under mild assumptions on the discrepancy showing that the approach is well-posed.
Our approach is the first to be used to estimate barycenters in thousands of dimensions.
- Score: 30.563217903502807
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Barycentric averaging is a principled way of summarizing populations of
measures. Existing algorithms for estimating barycenters typically parametrize
them as weighted sums of Diracs and optimize their weights and/or locations.
However, these approaches do not scale to high-dimensional settings due to the
curse of dimensionality. In this paper, we propose a scalable and general
algorithm for estimating barycenters of measures in high dimensions. The key
idea is to turn the optimization over measures into an optimization over
generative models, introducing inductive biases that allow the method to scale
while still accurately estimating barycenters. We prove local convergence under
mild assumptions on the discrepancy showing that the approach is well-posed. We
demonstrate that our method is fast, achieves good performance on
low-dimensional problems, and scales to high-dimensional settings. In
particular, our approach is the first to be used to estimate barycenters in
thousands of dimensions.
Related papers
- A Bayesian Approach Toward Robust Multidimensional Ellipsoid-Specific Fitting [0.0]
This work presents a novel and effective method for fitting multidimensional ellipsoids to scattered data in the contamination of noise and outliers.
We incorporate a uniform prior distribution to constrain the search for primitive parameters within an ellipsoidal domain.
We apply it to a wide range of practical applications such as microscopy cell counting, 3D reconstruction, geometric shape approximation, and magnetometer calibration tasks.
arXiv Detail & Related papers (2024-07-27T14:31:51Z) - Estimating Barycenters of Distributions with Neural Optimal Transport [93.28746685008093]
We propose a new scalable approach for solving the Wasserstein barycenter problem.
Our methodology is based on the recent Neural OT solver.
We also establish theoretical error bounds for our proposed approach.
arXiv Detail & Related papers (2024-02-06T09:17:07Z) - LIDL: Local Intrinsic Dimension Estimation Using Approximate Likelihood [10.35315334180936]
We propose a novel approach to the problem: Local Intrinsic Dimension estimation using approximate Likelihood (LIDL)
Our method relies on an arbitrary density estimation method as its subroutine and hence tries to sidestep the dimensionality challenge.
We show that LIDL yields competitive results on the standard benchmarks for this problem and that it scales to thousands of dimensions.
arXiv Detail & Related papers (2022-06-29T19:47:46Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
We consider distributed optimization methods for problems where forming the Hessian is computationally challenging.
We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
arXiv Detail & Related papers (2022-03-18T05:49:13Z) - Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
We present an algorithm to approximate the Wasserstein-2 barycenters of continuous measures via a generative model.
Based on the celebrity faces dataset, we construct Ave, celeba! dataset which can be used for quantitative evaluation of barycenter algorithms.
arXiv Detail & Related papers (2022-01-28T16:59:47Z) - Learning to Estimate Without Bias [57.82628598276623]
Gauss theorem states that the weighted least squares estimator is a linear minimum variance unbiased estimation (MVUE) in linear models.
In this paper, we take a first step towards extending this result to non linear settings via deep learning with bias constraints.
A second motivation to BCE is in applications where multiple estimates of the same unknown are averaged for improved performance.
arXiv Detail & Related papers (2021-10-24T10:23:51Z) - Streaming computation of optimal weak transport barycenters [13.664682865991255]
We provide a theoretical analysis of the weak barycenter and its relationship to the classic Wasserstein barycenter.
We provide iterative algorithms to compute a weak barycenter for either finite or infinite families of arbitrary measures.
arXiv Detail & Related papers (2021-02-26T10:08:02Z) - Continuous Wasserstein-2 Barycenter Estimation without Minimax
Optimization [94.18714844247766]
Wasserstein barycenters provide a geometric notion of the weighted average of probability measures based on optimal transport.
We present a scalable algorithm to compute Wasserstein-2 barycenters given sample access to the input measures.
arXiv Detail & Related papers (2021-02-02T21:01:13Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck.
We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian.
We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
arXiv Detail & Related papers (2020-02-16T09:01:18Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.