2017

The proximal point method revisited

Drusvyatskiy, Dmitriy

Understand

In this short survey, I revisit the role of the proximal point method in large scale optimization.

I focus on three recent examples: a proximally guided subgradient method for weakly convex stochastic approximation, the prox-linear algorithm for minimizing compositions of convex functions and smooth maps, and Catalyst generic acceleration for regularized Empirical Risk Minimization.

Built on

A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
Monotone operators and the proximal point algorithm
R.T. Rockafellar · 1976
Earlier work this paper cites.
On a bundle algorithm for nonsmooth optimization
C. Lemarechal, J.-J. Strodiot, and A. Bihain · 1981
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
A.S. Nemirovsky and D.B. Yudin · 1983
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) O(1/k^{2})
Yu. Nesterov · 1983
Earlier work this paper cites.
New proximal point algorithms for convex minimization
O. Güler · 1992
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
B.T. Polyak and A.B. Juditsky · 1992
Earlier work this paper cites.
Weak sharp minima in mathematical programming
J.V. Burke and M.C. Ferris · 1993
Earlier work this paper cites.
Interior-point polynomial algorithms in convex programming
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
A Gauss-Newton method for convex composite optimization
J.V. Burke and M.C. Ferris · 1995
Earlier work this paper cites.
Primal-dual interior-point methods
S.J. Wright · 1997
Earlier work this paper cites.
Tilt stability of a local minimum
R.A. Poliquin and R.T. Rockafellar · 1998
Earlier work this paper cites.
Prox-method with rate of convergence O ⁡ ( 1 / t ) O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems
A. Nemirovski · 2004
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Yu. Nesterov · 2005
Earlier work this paper cites.
Convexity, classification, and risk bounds
P.L. Bartlett, M.I. Jordan, and J.D. McAuliffe · 2006
Earlier work this paper cites.
Modified Gauss-Newton scheme with worst case guarantees for global performance
Yu. Nesterov · 2007
Earlier work this paper cites.
The tradeoffs of large scale learning
L. Bottou and O. Bousquet · 2008
Earlier work this paper cites.
Robust stochastic approximation approach to stochastic programming
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro · 2008
Earlier work this paper cites.
Robust principal component analysis?
E.J. Candès, X. Li, Y. Ma, and J. Wright · 2011
Earlier work this paper cites.
On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming
C. Cartis, N.I.M. Gould, and P.L. Toint · 2011
Earlier work this paper cites.
A first-order primal-dual algorithm for convex problems with applications to imaging
A. Chambolle and T. Pock · 2011
Earlier work this paper cites.
Rank-sparsity incoherence for matrix decomposition
V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A.S. Willsky · 2011
Earlier work this paper cites.

Similar

Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization
E. Hazan and S. Kale · 2011
Cited alongside, same era.
Angular synchronization by eigenvectors and semidefinite programming
A. Singer · 2011
Cited alongside, same era.
Smoothing and first order methods: a unified framework
A. Beck and M. Teboulle · 2012
Cited alongside, same era.
A simpler approach to obtaining an O ⁡ ( 1 / t ) {O}(1/t) convergence rate for the projected stochastic subgradient method
Original
S. Lacoste-Julien, M. Schmidt, and F. Bach · 2012
Cited alongside, same era.
Making gradient descent optimal for strongly convex stochastic optimization
A. Rakhlin, O. Shamir, and K. Sridharan · 2012
Cited alongside, same era.
Proximal stochastic dual coordinate ascent
Original
S. Shalev-Shwartz and T. Zhang · 2012
Cited alongside, same era.
Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential
D. Drusvyatskiy and A.S. Lewis · 2013
Cited alongside, same era.
Stochastic first- and zeroth-order methods for nonconvex stochastic programming
S. Ghadimi and G. Lan · 2013
Cited alongside, same era.
Accelerating stochastic gradient descent using predictive variance reduction
R. Johnson and T. Zhang · 2013
Cited alongside, same era.
Gradient methods for minimizing composite functions
Yu. Nesterov · 2013
Cited alongside, same era.
Minimizing finite sums with the stochastic average gradient
Original
M. Schmidt, N. Le Roux, and F. Bach · 2013
Cited alongside, same era.
Decoding binary node labels from censored edge measurements: phase transition and efficient recovery
E. Abbe, A.S. Bandeira, A. Bracher, and A. Singer · 2014
Cited alongside, same era.

Then

Incremental majorization-minimization optimization with application to large-scale machine learning
J. Mairal · 2015
Later among the works it cites.
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
S. Shalev-Shwartz and T. Zhang · 2015
Later among the works it cites.
Katyusha: The first direct acceleration of stochastic gradient methods
Original
Z. Allen-Zhu · 2016
Later among the works it cites.
On the low-rank approach for semidefinite programs arising in synchronization and community detection
A.S. Bandeira, N. Boumal, and V. Voroninski · 2016
Later among the works it cites.
SMART: The stochastic monotone aggregated root-finding algorithm
Original
D. Davis · 2016
Later among the works it cites.
A simple practical accelerated method for finite sums
A. Defazio · 2016
Later among the works it cites.
Error bounds, quadratic growth, and linear convergence of proximal methods
Original
D. Drusvyatskiy and A.S. Lewis · 2016
Later among the works it cites.
Efficiency of minimizing compositions of convex functions and smooth maps
Original
D. Drusvyatskiy and C. Paquette · 2016
Later among the works it cites.
Tight complexity bounds for optimizing composite objectives
B.E. Woodworth and N. Srebro · 2016
Later among the works it cites.
Limitations on variance-reduction and acceleration schemes for finite sums optimization
Y. Arjevani · 2017
Closest in time.
Convex analysis and monotone operator theory in Hilbert spaces
H.H. Bauschke and P.L. Combettes · 2017
Closest in time.
“Convex until proven guilty”: Dimension-free acceleration of gradient descent on non-convex functions
Y. Carmon, J.C. Duchi, O. Hinder, and A. Sidford · 2017
Closest in time.
Lower bounds for finding stationary points i
Original
Y. Carmon, J.C. Duchi, O. Hinder, and A. Sidford · 2017
Closest in time.
Solving random quadratic systems of equations is nearly as easy as solving linear systems
Y. Chen and E.J. Candès · 2017
Closest in time.
The nonsmooth landscape of phase retrieval
Original
D. Davis, D. Drusvyatskiy, and C. Paquette · 2017
Closest in time.
Proximally guided stochastic sbgradient method for nonsmooth, nonconvex problems
Original
D. Davis and B. Grimmer · 2017
Closest in time.
Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
Original
J.C. Duchi and F. Ruan · 2017
Closest in time.
Stochastic methods for composite optimization problems
Original
J.C. Duchi and F. Ruan · 2017
Closest in time.
Phase Retrieval, What’s New?
R. Luke · 2017
Closest in time.
Catalyst acceleration for gradient-based non-convex optimization
Original
C. Paquette, H. Lin, D. Drusvyatskiy, J. Mairal, and Z. Harchaoui · 2017
Closest in time.
A geometric analysis of phase retrieval
Original
J. Sun, Q. Qu, and J. Wright · 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…