2017

Adaptive Similar Triangles Method: a Stable Alternative to Sinkhorn's Algorithm for Regularized Optimal Transport

Dvurechensky, Pavel, Gasnikov, Alexander, Omelchenko, Sergey et al.

Understand

In this paper, we are motivated by two important applications: entropy-regularized optimal transport problem and road or IP traffic demand matrix estimation by entropy model.

Both of them include solving a special type of optimization problem with linear equality constraints and objective given as a sum of an entropy regularizer and a linear function.
It is known that the state-of-the-art solvers for this problem, which are based on Sinkhorn's method (also known as RSA or balancing method), can fail to work, when the entropy-regularization parameter is small.
We consider the above optimization problem as a particular instance of a general strongly convex optimization problem with linear constraints.

Built on

Distributed optimization and statistical learning via the alternating direction method of multipliers
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein · 1935
Earlier work this paper cites.
On the translocation of masses
Leonid Kantorovich · 1942
Earlier work this paper cites.
Proof of the convergence of sheleikhovskii’s method for a problem with transportation constraints
L.M. Bregman · 1967
Earlier work this paper cites.
Diagonal equivalence to matrices with prescribed row and column sums. II
Richard Sinkhorn · 1974
Earlier work this paper cites.
On the scaling of multidimensional matrices
Joel Franklin and Jens Lorenz · 1989
Earlier work this paper cites.
Maximum – entropy models in science and engineering
J. Kapur · 1989
Earlier work this paper cites.
On the rate of convergence of deterministic and randomized ras matrix scaling algorithms
Bahman Kalantari and Leonid Khachiyan · 1993
Earlier work this paper cites.
Maximum entropy econometrics: Robust estimation with limited data
A. Golan, G. Judge, and D. Miller · 1996
Earlier work this paper cites.
Entropy optimization and mathematical programming
S.-C. Fang, Rajasekera J., and Tsao H.-S · 1997
Earlier work this paper cites.
The Elements of Statistical Learning
Trevor Hastie, Robert Tibshirani, and Jerome Friedman · 2001
Earlier work this paper cites.
Mathematical modeling of traffic flows
V. I. Shvetsov · 2003
Earlier work this paper cites.
Introductory Lectures on Convex Optimization: a basic course
Yurii Nesterov · 2004
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Yurii Nesterov · 2005
Earlier work this paper cites.

Similar

Estimating point-to-point and point-to-multipoint traffic matrices: An information-theoretic approach
Yin Zhang, Matthew Roughan, Carsten Lund, and David L. Donoho · 2005
Cited alongside, same era.
Regularization and variable selection via the elastic net
Hui Zou and Trevor Hastie · 2005
Cited alongside, same era.
Cubic regularization of newton method and its global performance
Yurii Nesterov and Boris Polyak · 2006
Cited alongside, same era.
A first-order primal-dual algorithm for convex problems with applications to imaging
Antonin Chambolle and Thomas Pock · 2011
Cited alongside, same era.
Entropy in Urban and Regional Modelling
A.G. Wilson · 2011
Cited alongside, same era.
A fast dual proximal gradient algorithm for convex minimization and applications
Amir Beck and Marc Teboulle · 2013
Cited alongside, same era.
Sinkhorn distances: Lightspeed computation of optimal transport
Marco Cuturi · 2013
Cited alongside, same era.
Fast alternating direction optimization methods
Tom Goldstein, Brendan O’Donoghue, Simon Setzer, and Richard Baraniuk · 2014
Cited alongside, same era.
Constrained convex minimization via model-based excessive gap
Quoc Tran-Dinh and Volkan Cevher · 2014
Cited alongside, same era.
Lectures on Modern Convex Optimization (Lecture Notes)
Aaron Ben-Tal and Arkadi Nemirovski · 2015
Cited alongside, same era.
Iterative bregman projections for regularized transportation problems
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré · 2015
Cited alongside, same era.
An accelerated linearized alternating direction method of multipliers
Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Jr. Eduardo Pasiliao · 2015
Cited alongside, same era.

Then

A smooth primal-dual optimization framework for nonsmooth composite convex minimization
Original
Quoc Tran-Dinh, Olivier Fercoq, and Volkan Cevher · 2015
Later among the works it cites.
A universal primal-dual convex optimization framework
Alp Yurtsever, Quoc Tran-Dinh, and Volkan Cevher · 2015
Later among the works it cites.
Fast Primal-Dual Gradient Method for Strongly Convex Minimization Problems with Linear Constraints , pages 391–403
Alexey Chernov, Pavel Dvurechensky, and Alexander Gasnikov · 2016
Later among the works it cites.
Scaling algorithms for unbalanced transport problems
Original
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard · 2016
Later among the works it cites.
A smoothed dual approach for variational wasserstein problems
Marco Cuturi and Gabriel Peyré · 2016
Later among the works it cites.
Primal-dual rates and certificates
Celestine Dünner, Simone Forte, Martin Takáč, and Martin Jaggi · 2016
Later among the works it cites.
Universal fast gradient method for stochastic composit optimization problems
Original
Alexander Gasnikov and Yurii Nesterov · 2016
Later among the works it cites.
An inexact dual fast gradient-projection method for separable convex optimization with linear coupled constraints
Jueyou Li, Zhiyou Wu, Changzhi Wu, Qiang Long, and Xiangyu Wang · 2016
Later among the works it cites.
A first-order primal-dual algorithm with linesearch
Original
Yura Malitsky and Thomas Pock · 2016
Later among the works it cites.
Stabilized sparse scaling algorithms for entropy regularized transport problems
Original
Bernhard Schmitzer · 2016
Later among the works it cites.
Much faster algorithms for matrix scaling
Original
Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson · 2017
Closest in time.
Near-linear time approximation algorithms for optimal transport via sinkhorn iteration
Original
Jason Altschuler, Jonathan Weed, and Philippe Rigollet · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…