Built on

R.T. Rockafellar, Monotone operators and the proximal point algorithm , SIAM journal on control and optimization 14 (1976), pp. 877–898
1976
Earlier work this paper cites.
A.S. Nemirovsky and D.B. Yudin, Problem Complexity and Method Efficiency in Optimization , A Wiley-Interscience publication, Wiley, 1983
1983
Earlier work this paper cites.
B.T. Polyak, Introduction to optimization , Optimization Software, 1987
1987
Earlier work this paper cites.
Y. Hu, Y. Koren, and C. Volinsky, Collaborative filtering for implicit feedback datasets , in 2008 Eighth IEEE International Conference on Data Mining . Ieee, 2008, pp. 263–272
2008
Earlier work this paper cites.
Y. Nesterov and J.P. Vial, Confidence level solutions for stochastic programming , Automatica 44 (2008), pp. 1559–1568
2008
Earlier work this paper cites.
C.C. Chang and C.J. Lin, Libsvm: a library for support vector machines , ACM Transactions on Intelligent Systems and Technology (TIST) 2 (2011), p. 27
2011
Earlier work this paper cites.
Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM Journal on Optimization 22 (2012), pp. 341–362
2012
Earlier work this paper cites.
R.D. Monteiro and B.F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods , SIAM Journal on Optimization 23 (2013), pp. 1092–1125
2013
Earlier work this paper cites.
N. Parikh, S. Boyd, et al. , Proximal algorithms , Foundations and Trends® in Optimization 1 (2014), pp. 127–239
2014
Earlier work this paper cites.
S. Shalev-Shwartz and T. Zhang, Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization , in International conference on machine learning . 2014, pp. 64–72
2014
Earlier work this paper cites.
S. Bubeck, Convex optimization: Algorithms and complexity , Foundations and Trends® in Machine Learning 8 (2015), pp. 231–357
2015
Earlier work this paper cites.
J.C. Duchi, M.I. Jordan, M.J. Wainwright, and A. Wibisono, Optimal rates for zero-order convex optimization: The power of two function evaluations , IEEE Trans. Information Theory 61 (2015), pp. 2788–2806
2015
Earlier work this paper cites.
H. Lin, J. Mairal, and Z. Harchaoui, A universal catalyst for first-order optimization , in Advances in neural information processing systems . 2015, pp. 3384–3392
2015
Earlier work this paper cites.
S.J. Wright, Coordinate descent algorithms , Mathematical Programming 151 (2015), pp. 3–34
2015
Earlier work this paper cites.
Z. Allen-Zhu and E. Hazan, Optimal black-box reductions between optimization objectives , arXiv preprint arXiv:1603.05642 (2016)
Original
2016
Earlier work this paper cites.
A. Gasnikov, P. Dvurechensky, and I. Usmanova, On accelerated randomized methods , Proceedings of Moscow Institute of Physics and Technology 8 (2016), pp. 67–100. In Russian, first appeared in arXiv:1508.02182
Original
2016
Earlier work this paper cites.
H. Karimi, J. Nutini, and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition , in Joint European Conference on Machine Learning and Knowledge Discovery in Databases . Springer, 2016, pp. 795–811
2016
Earlier work this paper cites.
B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems , in Advances in Neural Information Processing Systems . 2016, pp. 1416–1424
2016
Earlier work this paper cites.
A. Beck, First-order methods in optimization , Vol. 25, SIAM, 2017
2017
Earlier work this paper cites.
E. De Klerk, F. Glineur, and A.B. Taylor, On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions , Optimization Letters 11 (2017), pp. 1185–1199
2017
Earlier work this paper cites.
A. Gasnikov, Universal gradient descent , arXiv preprint arXiv:1711.00394 (2017)
Original
2017
Earlier work this paper cites.
Y. Nesterov and S.U. Stich, Efficiency of the accelerated coordinate descent method on structured optimization problems , SIAM Journal on Optimization 27 (2017), pp. 110–123
2017
Earlier work this paper cites.
C. Paquette, H. Lin, D. Drusvyatskiy, J. Mairal, and Z. Harchaoui, Catalyst acceleration for gradient-based non-convex optimization , arXiv preprint arXiv:1703.10993 (2017)
Original
2017
Earlier work this paper cites.

Similar

O. Shamir, An optimal algorithm for bandit and zero-order convex optimization with two-point feedback , Journal of Machine Learning Research 18 (2017), pp. 52:1–52:11
2017
Cited alongside, same era.
A. Bayandina, A. Gasnikov, and A. Lagunovskaya, Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise , Automation and remote control 79 (2018). arXiv:1701.03821
Original
2018
Cited alongside, same era.
J. Diakonikolas and L. Orecchia, Alternating randomized block coordinate descent , arXiv preprint arXiv:1805.09185 (2018)
Original
2018
Cited alongside, same era.
P. Dvurechensky, A. Gasnikov, and E. Gorbunov, An accelerated directional derivative method for smooth stochastic convex optimization , arXiv:1804.02394 (2018)
Original
2018
Cited alongside, same era.

Then

A. Kulunchakov and J. Mairal, A generic acceleration framework for stochastic composite optimization , arXiv preprint arXiv:1906.01164 (2019)
Original
2019
Closest in time.
A. Ogaltsov, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, and V. Spokoiny, Adaptive gradient descent for convex and non-convex stochastic optimization , arXiv preprint arXiv:1911.08380 (2019)
Original
2019
Closest in time.
N. Tupitsa, P. Dvurechensky, and A. Gasnikov, Alternating minimization methods for strongly convex optimization , arXiv preprint arXiv:1911.08987 (2019)
Original
2019
Closest in time.
A.C. Wilson, L. Mackey, and A. Wibisono, Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions , in Advances in Neural Information Processing Systems . 2019, pp. 13533–13543
2019
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…

2019

Adaptive Catalyst for Smooth Convex Optimization

Ivanova, Anastasiya, Pasechnyuk, Dmitry, Grishchenko, Dmitry et al.

Understand

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 main approach of our envelope is the same as in Catalyst (Lin et al., 2015): an accelerated proximal outer gradient method, which is used as an envelope for a non-accelerated inner method for the $\ell_2$ regularized auxiliary problem.
Our algorithm has two key differences: 1) easily verifiable stopping criteria for inner algorithm; 2) the regularization parameter can be tunned along the way.
As a result, the main contribution of our work is a new framework that applies to adaptive inner algorithms: Steepest Descent, Adaptive Coordinate Descent, Alternating Minimization.

Built on

R.T. Rockafellar, Monotone operators and the proximal point algorithm , SIAM journal on control and optimization 14 (1976), pp. 877–898
1976
Earlier work this paper cites.
A.S. Nemirovsky and D.B. Yudin, Problem Complexity and Method Efficiency in Optimization , A Wiley-Interscience publication, Wiley, 1983
1983
Earlier work this paper cites.
B.T. Polyak, Introduction to optimization , Optimization Software, 1987
1987
Earlier work this paper cites.
Y. Hu, Y. Koren, and C. Volinsky, Collaborative filtering for implicit feedback datasets , in 2008 Eighth IEEE International Conference on Data Mining . Ieee, 2008, pp. 263–272
2008
Earlier work this paper cites.
Y. Nesterov and J.P. Vial, Confidence level solutions for stochastic programming , Automatica 44 (2008), pp. 1559–1568
2008
Earlier work this paper cites.
C.C. Chang and C.J. Lin, Libsvm: a library for support vector machines , ACM Transactions on Intelligent Systems and Technology (TIST) 2 (2011), p. 27
2011
Earlier work this paper cites.
Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems , SIAM Journal on Optimization 22 (2012), pp. 341–362
2012
Earlier work this paper cites.
R.D. Monteiro and B.F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods , SIAM Journal on Optimization 23 (2013), pp. 1092–1125
2013
Earlier work this paper cites.
N. Parikh, S. Boyd, et al. , Proximal algorithms , Foundations and Trends® in Optimization 1 (2014), pp. 127–239
2014
Earlier work this paper cites.
S. Shalev-Shwartz and T. Zhang, Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization , in International conference on machine learning . 2014, pp. 64–72
2014
Earlier work this paper cites.
S. Bubeck, Convex optimization: Algorithms and complexity , Foundations and Trends® in Machine Learning 8 (2015), pp. 231–357
2015
Earlier work this paper cites.
J.C. Duchi, M.I. Jordan, M.J. Wainwright, and A. Wibisono, Optimal rates for zero-order convex optimization: The power of two function evaluations , IEEE Trans. Information Theory 61 (2015), pp. 2788–2806
2015
Earlier work this paper cites.
H. Lin, J. Mairal, and Z. Harchaoui, A universal catalyst for first-order optimization , in Advances in neural information processing systems . 2015, pp. 3384–3392
2015
Earlier work this paper cites.
S.J. Wright, Coordinate descent algorithms , Mathematical Programming 151 (2015), pp. 3–34
2015
Earlier work this paper cites.
Z. Allen-Zhu and E. Hazan, Optimal black-box reductions between optimization objectives , arXiv preprint arXiv:1603.05642 (2016)
Original
2016
Earlier work this paper cites.
A. Gasnikov, P. Dvurechensky, and I. Usmanova, On accelerated randomized methods , Proceedings of Moscow Institute of Physics and Technology 8 (2016), pp. 67–100. In Russian, first appeared in arXiv:1508.02182
Original
2016
Earlier work this paper cites.
H. Karimi, J. Nutini, and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition , in Joint European Conference on Machine Learning and Knowledge Discovery in Databases . Springer, 2016, pp. 795–811
2016
Earlier work this paper cites.
B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems , in Advances in Neural Information Processing Systems . 2016, pp. 1416–1424
2016
Earlier work this paper cites.
A. Beck, First-order methods in optimization , Vol. 25, SIAM, 2017
2017
Earlier work this paper cites.
E. De Klerk, F. Glineur, and A.B. Taylor, On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions , Optimization Letters 11 (2017), pp. 1185–1199
2017
Earlier work this paper cites.
A. Gasnikov, Universal gradient descent , arXiv preprint arXiv:1711.00394 (2017)
Original
2017
Earlier work this paper cites.
Y. Nesterov and S.U. Stich, Efficiency of the accelerated coordinate descent method on structured optimization problems , SIAM Journal on Optimization 27 (2017), pp. 110–123
2017
Earlier work this paper cites.
C. Paquette, H. Lin, D. Drusvyatskiy, J. Mairal, and Z. Harchaoui, Catalyst acceleration for gradient-based non-convex optimization , arXiv preprint arXiv:1703.10993 (2017)
Original
2017
Earlier work this paper cites.

Similar

O. Shamir, An optimal algorithm for bandit and zero-order convex optimization with two-point feedback , Journal of Machine Learning Research 18 (2017), pp. 52:1–52:11
2017
Cited alongside, same era.
A. Bayandina, A. Gasnikov, and A. Lagunovskaya, Gradient-free two-points optimal method for non smooth stochastic convex optimization problem with additional small noise , Automation and remote control 79 (2018). arXiv:1701.03821
Original
2018
Cited alongside, same era.
J. Diakonikolas and L. Orecchia, Alternating randomized block coordinate descent , arXiv preprint arXiv:1805.09185 (2018)
Original
2018
Cited alongside, same era.
P. Dvurechensky, A. Gasnikov, and E. Gorbunov, An accelerated directional derivative method for smooth stochastic convex optimization , arXiv:1804.02394 (2018)
Original
2018
Cited alongside, same era.

Then

A. Kulunchakov and J. Mairal, A generic acceleration framework for stochastic composite optimization , arXiv preprint arXiv:1906.01164 (2019)
Original
2019
Closest in time.
A. Ogaltsov, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, and V. Spokoiny, Adaptive gradient descent for convex and non-convex stochastic optimization , arXiv preprint arXiv:1911.08380 (2019)
Original
2019
Closest in time.
N. Tupitsa, P. Dvurechensky, and A. Gasnikov, Alternating minimization methods for strongly convex optimization , arXiv preprint arXiv:1911.08987 (2019)
Original
2019
Closest in time.
A.C. Wilson, L. Mackey, and A. Wibisono, Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions , in Advances in Neural Information Processing Systems . 2019, pp. 13533–13543
2019
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…

P. Dvurechensky, A. Gasnikov, and E. Gorbunov, An accelerated method for derivative-free smooth stochastic convex optimization , arXiv:1802.09022 (2018)

Original

2018

Cited alongside, same era.

P. Dvurechensky, A. Gasnikov, and A. Lagunovskaya, Parallel algorithms and probability of large deviation for stochastic convex optimization problems , Numerical Analysis and Applications 11 (2018), pp. 33–37

2018

Cited alongside, same era.

H. Lin, J. Mairal, and Z. Harchaoui, Catalyst acceleration for first-order convex optimization: from theory to practice , arXiv preprint arXiv:1712.05654 (2018)

Original

2018

Cited alongside, same era.

K. Mishchenko, F. Iutzeler, J. Malick, and M.R. Amini, A delay-tolerant proximal-gradient algorithm for distributed learning , in International Conference on Machine Learning . 2018, pp. 3587–3595

2018

Cited alongside, same era.

Y. Nesterov, Lectures on convex optimization , Vol. 137, Springer, 2018

2018

Cited alongside, same era.

Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky, Primal-dual accelerated gradient descent with line search for convex and nonconvex optimization problems , arXiv preprint arXiv:1809.05895 (2018)

Original

2018

Cited alongside, same era.

S.U. Stich, Local sgd converges fast and communicates little , arXiv preprint arXiv:1805.09767 (2018)

Original

2018

Cited alongside, same era.

B.E. Woodworth, J. Wang, A. Smith, B. McMahan, and N. Srebro, Graph oracle models, lower bounds, and gaps for parallel stochastic optimization , in Advances in neural information processing systems . 2018, pp. 8496–8506

2018

Cited alongside, same era.

N. Doikov and Y. Nesterov, Contracting proximal methods for smooth convex optimization , SIAM Journal on Optimization 30 (2020), pp. 3146–3169

2020

Closest in time.

N. Doikov and Y. Nesterov, Inexact tensor methods with dynamic accuracies , arXiv preprint arXiv:2002.09403 (2020)

Original

2020

Closest in time.

D. Dvinskikh, S. Omelchenko, A. Gasnikov, and A. Tyurin, Accelerated Gradient Sliding for Minimizing a Sum of Functions , in Doklady Mathematics , Vol. 101. Springer, 2020, pp. 244–246

2020

Closest in time.

H. Hendrikx, F. Bach, and L. Massoulié, Dual-free stochastic decentralized optimization with variance reduction , Advances in Neural Information Processing Systems 33 (2020)

2020

Closest in time.

A. Ivanova, A. Gasnikov, P. Dvurechensky, D. Dvinskikh, A. Tyurin, E. Vorontsova, and D. Pasechnyuk, Oracle complexity separation in convex optimization , arXiv preprint arXiv:2002.02706 (2020)

Original

2020

Closest in time.

D. Kamzolov, P. Dvurechensky, and A. Gasnikov, Optimal Combination of Tensor Optimization Methods , in Optimization and Applications: 11th International Conference, OPTIMA 2020, Moscow, Russia, September 28–October 2, 2020, Proceedings . Springer Nature, p. 166

2020

Closest in time.

D. Kamzolov and A. Gasnikov, Near-optimal hyperfast second-order method for convex optimization and its sliding , arXiv preprint arXiv:2002.09050 (2020)

Original

2020

Closest in time.

D. Kovalev, A. Salim, and P. Richtárik, Optimal and practical algorithms for smooth and strongly convex decentralized optimization , Advances in Neural Information Processing Systems 33 (2020)

2020

Closest in time.

H. Li and Z. Lin, Revisiting extra for smooth distributed optimization , arXiv preprint arXiv:2002.10110 (2020)

Original

2020

Closest in time.

H. Li, Z. Lin, and Y. Fang, Optimal accelerated variance reduced extra and diging for strongly convex and smooth decentralized optimization , arXiv preprint arXiv:2009.04373 (2020)

Original

2020

Closest in time.

T. Lin, C. Jin, and M. Jordan, On gradient descent ascent for nonconvex-concave minimax problems , in International Conference on Machine Learning . PMLR, 2020, pp. 6083–6093

2020

Closest in time.

N. Tupitsa, Accelerated alternating minimization and adaptability to strong convexity , arXiv preprint arXiv:2006.09097 (2020)

Original

2020

Closest in time.

B. Woodworth, K.K. Patel, S.U. Stich, Z. Dai, B. Bullins, H.B. McMahan, O. Shamir, and N. Srebro, Is local sgd better than minibatch sgd? , arXiv preprint arXiv:2002.07839 (2020)

Original

2020

Closest in time.

J. Yang, S. Zhang, N. Kiyavash, and N. He, A catalyst framework for minimax optimization , Advances in Neural Information Processing Systems 33 (2020)

2020

Closest in time.

D. Dvinskikh, D. Kamzolov, A. Gasnikov, P. Dvurechensky, D. Pasechnyk, V. Matykhin, and A. Chernov, Accelerated meta-algorithm for convex optimization , Computational Mathematica and Mathematical Physics 61 (2021)

2021

Closest in time.

A. Gasnikov, Universal gradient descent , MCCME, Moscow, 2021

2021

Closest in time.

D. Pasechnyuk, A. Anikin, and V. Matyukhin, Accelerated proximal envelopes: Application to the coordinate descent method , arXiv preprint arXiv:2101.04706 (2021)

Original

2021

Closest in time.

O. Fercoq and P. Richtárik, Accelerated, parallel, and proximal coordinate descent , SIAM Journal on Optimization 25 (2015), pp. 1997–2023

2023

Closest in time.

A. Gasnikov, A. Lagunovskaya, I. Usmanova, and F. Fedorenko, Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex , Automation and Remote Control 77 (2016), pp. 2018–2034. Available at http://dx.doi.org/10.1134/S0005117916110114 , arXiv:1412.3890

Original

2034

Closest in time.