?
Multimarginal Optimal Transport by Accelerated Alternating Minimization
P. 6132–6137.
Tupitsa, N., Dvurechensky P., Gasnikov A., Uribe C.
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 an approximate solution. We use entropic regularization with a sufficiently small regularization parameter and apply accelerated alternating minimization to the dual problem. A novel primal-dual analysis is used to reconstruct the approximately optimal coupling tensor. Our algorithm exhibits a better computational complexity than the state-of-the-art methods for some regimes of the problem parameters.
Kolesnikov A., Popova S., Математические заметки 2026 Т. 119 № 3 С. 377–390
We consider the problem of optimal exchange which can be formulated as a kind of optimal transportation problem. The existence of an optimal solution and a duality theorem for the optimal exchange problem are proved in case of completely regular topological spaces. We show the connection between the problem of optimal exchange and the optimal ...
Added: March 12, 2026
Stanislav Morozov, Zheltkov D., Osinsky A., Russian Journal on Numerical Analysis and Mathematical Modelling 2024 Vol. 39 No. 5 P. 311–328
Nowadays, low-rank approximations are a critical component of many numerical procedures. Traditionally the problem of low-rank approximation of matrices is solved in unitary invariant norms such as Frobenius or spectral norm due to the existence of efficient methods for constructing approximations. However, recent results discover the potential of low-rank approximations in the Chebyshev norm, which ...
Added: February 18, 2026
Stanislav Morozov, Smirnov M., Zamarashkin N., Linear Algebra and its Applications 2023 Vol. 679 P. 4–29
The problem of low rank approximation is ubiquitous in science. Traditionally this problem is solved in unitary invariant
norms such as Frobenius or spectral norm due to existence of efficient methods for building approximations. However, recent results reveal the potential of low rank approximations in Chebyshev norm, which naturally arises in many applications. In this paper ...
Added: April 10, 2025
Gazdieva M., Alexander Korotin, Daniil Selikhanovych et al., , in: Advances in Neural Information Processing Systems 36 (NeurIPS 2023).: Curran Associates, Inc., 2023. P. 40381–40413.
Added: January 22, 2025
Gladin E., Dvurechensky P., Mielke A. et al., , in: 38th Conference on Neural Information Processing Systems (NeurIPS 2024).: [б.и.], 2024. P. 14484–14508.
Added: November 28, 2024
Dvinskikh D., Optimization Methods and Software 2022 Vol. 37 No. 5 P. 1603–1635
In the machine learning and optimization community, there are two main approaches for the convex risk minimization problem, namely the Stochastic Approximation (SA) and the Sample Average Approximation (SAA). In terms of the oracle complexity (required number of stochastic gradient evaluations), both approaches are considered equivalent on average (up to a logarithmic factor). The total complexity depends on ...
Added: March 27, 2024
Asadulaev A., Korotin A., Vage Egiazarian et al., , in: Proceedings of the 12th International Conference on Learning Representations (ICLR 2024).: ICLR, 2024.
Added: March 5, 2024
Guminov S., Dvurechensky P., Tupitsa N. et al., , in: Proceedings of the 38th International Conference on Machine Learning (ICML 2021)Vol. 139.: PMLR, 2021. P. 3886–3898.
Added: October 30, 2022
Ivanova A., Pasechnyuk D., Grishchenko D. et al., , in: Optimization and Applications: 12th International Conference, OPTIMA 2021, Petrovac, Montenegro, September 27 – October 1, 2021, Proceedings.: Switzerland: Springer, 2021. Ch. 268319 P. 20–37.
In this paper, we present a generic framework that allows accelerating almost arbitrary non-accelerated deterministic and randomized algorithms for smooth convex optimization problems. The major approach of our envelope is the same as in Catalyst [37]: an accelerated proximal outer gradient method, which is used as an envelope for a non-accelerated inner method for the ...
Added: October 30, 2022
Tupitsa N., Dvurechensky P., Gasnikov A. et al., Journal of Inverse and Ill-posed problems 2021 Vol. 29 No. 5 P. 721–739
We consider alternating minimization procedures for convex and non-convex optimization problems with the vector of variables divided into several blocks, each block being amenable for minimization with respect to its variables while maintaining other variables' blocks constant. In the case of two blocks, we prove a linear convergence rate for alternating minimization procedure under the ...
Added: September 29, 2021
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
Tupitsa N., Gasnikov A., Dvurechensky P. et al., , in: Mathematical Optimization Theory and Operations Research. MOTOR 2020. Communications in Computer and Information ScienceVol. 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., Tupitsa Nazarii, Dvinskikh D. et al., , in: Proceedings of Machine Learning ResearchVol. 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
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