### ?

## Proceedings of Machine Learning Research

Vol. 80: Proceedings of the International Conference on Machine Learning (ICML 2018).
PMLR, 2018.

Under the general editorship: Dy J., Krause A.

In press

Volume 80 is assigned to the 2018 International Conference on Machine Learning (ICML 2018)

Language:
English

Tupitsa N., Gasnikov A., Dvurechensky P. et al., , in: Mathematical Optimization Theory and Operations Research. MOTOR 2020. Communications in Computer and Information Science. Vol. 1275.: Springer, 2020.. P. 192-204.

In this paper we experimentally check a hypothesis, that dual problem to discrete entropy regularized optimal transport problem possesses strong convexity on a certain compact set. We present a numerical estimation technique of parameter of strong convexity and show that such an estimate increases the performance of an accelerated alternating minimization algorithm for strongly convex ...

Added: October 28, 2020

Kroshnin A., Dvinskikh D., Dvurechensky P. et al., , in: Proceedings of Machine Learning Research. Vol. 97: International Conference on Machine Learning, 9-15 June 2019, Long Beach, California, USA.: PMLR, 2019.. P. 3530-3540.

We study the complexity of approximating the Wasserstein barycenter of m discrete measures, or histograms of size n, by contrasting two alternative approaches that use entropic regularization. The first approach is based on the Iterative Bregman Projections (IBP) algorithm for which our novel analysis gives a complexity bound proportional to $m n^2 / \epsilon^2$ to approximate the original non-regularized barycenter. ...

Added: June 11, 2019

Le Gouic T., Paris Q., Rigollet P. et al., Working papers by Cornell University. Series math "arxiv.org" 2019 P. 1-17

This work establishes fast rates of convergence for empirical barycenters over a large class of geodesic spaces with curvature bounds in the sense of Alexandrov. More specifically, we show that parametric rates of convergence are achievable under natural conditions that characterize the bi-extendibility of geodesics emanating from a barycenter. These results largely advance the state-of-the-art ...

Added: November 14, 2019

Kroshnin A., Journal of Convex Analysis 2018 Vol. 25 No. 4 P. 1371-1395

We consider the space P(X) of probability measures on arbitrary Radon space X endowed with a transportation cost J(μ, ν) generated by a nonnegative continuous cost function. For a probability distribution on P(X) we formulate a notion of average with respect to this transportation cost, called here the Fréchet barycenter, prove a version of the law ...

Added: November 23, 2018

Kroshnin A., Spokoiny V., Suvorikova A., Annals of Applied Probability 2021 Vol. 31 No. 3 P. 1264-1298

n this work we introduce the concept of Bures-Wasserstein barycenter $Q_*$, that is essentially a Fr\'echet mean of some distribution $P$ supported on a subspace of positive semi-definite Hermitian operators $\mathbb{H}_{+}(d)$.
We allow a barycenter to be constrained to some affine subspace of $\mathbb{H}_{+}(d)$ and provide conditions ensuring its existence and uniqueness.
We also investigate convergence and concentration properties ...

Added: October 30, 2020

Гуминов С. В., Dvurechensky P., Tupitsa N. et al., Proceedings of Machine Learning Research 2021 Vol. 139 P. 3886-3898

Alternating minimization (AM) procedures are practically efficient in many applications for solving convex and non-convex optimization problems. On the other hand, Nesterov's accelerated gradient is theoretically optimal first-order method for convex optimization. In this paper we combine AM and Nesterov's acceleration to propose an accelerated alternating minimization algorithm. We prove $1/k^2$ convergence rate in terms ...

Added: September 29, 2021

Annales de l'institut Henri Poincare (B) Probability and Statistics 2017 Vol. 53 No. 4 P. 1719-1746

Nous relions les inégalités de transport-entropie à l'étude des points critiques de la fonction. Cette approche conduit en particulier à une nouvelle preuve du résultat de Otto et Villani 2000 montrant que le droit logarithmique de Sobolev implique l'inégalité des transports chez Talagrand. ...

Added: June 7, 2018

Kolesnikov A., Tikhonov S. Y., Regularity of the Monge-Ampère equation in Besov's space / Cornell University. Series math "arxiv.org". 2012. No. 1203.3457.

Let $\mu = e^{-V} \ dx$ be a probability measure and $T = \nabla \Phi$ be the optimal transportation mapping pushing forward $\mu$ onto a log-concave compactly supported measure $\nu = e^{-W} \ dx$. In this paper, we introduce a new approach to the regularity problem for the corresponding Monge--Amp{\`e}re equation $e^{-V} = \det D^2 ...

Added: March 28, 2013

Delon J., Salomon J., Sobolevski A., SIAM Journal of Discrete Mathematics 2012 Vol. 26 No. 2 P. 801-827

In this paper, we introduce a class of local indicators that enable us to compute efficiently optimal transport plans associated with arbitrary weighted distributions of N demands and M supplies in R in the case where the cost function is concave. Indeed, whereas this problem can be solved linearly when the cost is a convex ...

Added: May 30, 2012

Dvurechensky P., Gasnikov A., Gasnikova E. et al., В кн.: Proceedings of DOOR 2016 Conference, special issue of CEUR Workshop Proceedings. Vol. 1623.: CEUR Workshop Proceedings, 2016.. С. 584-595.

In this paper, we consider a large class of hierarchical congestion population games. One can show that the equilibrium in a game of such type can be described as a minimum point in a properly constructed multi-level convex optimization problem. We propose a fast primal-dual composite gradient method and apply it to the problem, which ...

Added: November 17, 2017

Tupitsa N., Dvurechensky P., Gasnikov A. et al., , in: 2020 IEEE 59th Conference on Decision and Control (CDC). .: IEEE, 2020.. P. 6132-6137.

We study multimarginal optimal transport (MOT) problems, which include, as a particular case, the Wasserstein barycenter problem. In MOT problems, one has to find an optimal coupling between m probability measures, which amounts to finding a tensor of order m. We propose a method based on accelerated alternating minimization and estimate the complexity to find ...

Added: February 5, 2021

Ahidar-Coutrix A., Le Gouic T., Paris Q., Probability Theory and Related Fields 2020

This paper provides rates of convergence for empirical (generalised) barycenters on compact geodesic metric spaces under general conditions using empirical processes techniques. Our main assumption is termed a variance inequality and provides a strong connection between usual assumptions in the field of empirical processes and central concepts of metric geometry. We study the validity of ...

Added: November 14, 2019