Contracting proximal methods for smooth convex optimization. (English) Zbl 1454.90052

Doikov, Nikita; Nesterov, Yurii

SIAM J. Optim. 30, No. 4, 3146-3169 (2020).

Summary: In this paper, we propose new accelerated methods for smooth convex optimization, called contracting proximal methods. At every step of these methods, we need to minimize a contracted version of the objective function augmented by a regularization term in the form of Bregman divergence. We provide global convergence analysis for a general scheme admitting inexactness in solving the auxiliary subproblem. In the case of using for this purpose high-order tensor methods, we demonstrate an acceleration effect for both convex and uniformly convex composite objective functions. Thus, our construction explains acceleration for methods of any order starting from one. The augmentation of the number of calls of oracle due to computing the contracted proximal steps is limited by the logarithmic factor in the worst-case complexity bound.

MSC:

90C25	Convex programming
90C30	Nonlinear programming
65K05	Numerical mathematical programming methods

Keywords:

convex optimization; proximal method; accelerated methods; global complexity bounds; high-order algorithms

References:

[1]	Y. Arjevani, O. Shamir, and R. Shiff, Oracle complexity of second-order methods for smooth convex optimization, Math. Program., 178 (2019), pp. 327-360. · Zbl 1430.90460
[2]	M. Baes, Estimate Sequence Methods: Extensions and Approximations, Institute for Operations Research, ETH, Zürich, Switzerland, 2009.
[3]	H. H. Bauschke, J. Bolte, and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Math. Oper. Res., 42 (2016), pp. 330-348. · Zbl 1364.90251
[4]	N. Doikov and Y. Nesterov, Local Convergence of Tensor Methods, CORE Discussion Paper 2019/21, 2019.
[5]	N. Doikov and Y. Nesterov, Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Method, preprint, arXiv:1905.02671, 2019.
[6]	N. Doikov and P. Richtárik, Randomized block cubic Newton method, in Proceedings of the International Conference on Machine Learning, 2018, pp. 1289-1297.
[7]	A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck, J. Qijia, Y. T. Lee, L. Yuanzhi, and S. Aaron, Near optimal methods for minimizing convex functions with Lipschitz \(p\)-th derivatives, in Proceedings of the Conference on Learning Theory, 2019, pp. 1392-1393.
[8]	A. Gasnikov and Y. Nesterov, Universal method for stochastic composite optimization problems, Comput. Math. Math. Phys., 58 (2018), pp. 48-64. · Zbl 1457.90099
[9]	G. N. Grapiglia and Y. Nesterov, Accelerated regularized Newton methods for minimizing composite convex functions, SIAM J. Optim., 29 (2019), pp. 77-99. · Zbl 1406.49030
[10]	O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), pp. 403-419. · Zbl 0737.90047
[11]	O. Güler, New proximal point algorithms for convex minimization, SIAM J. Optim., 2 (1992), pp. 649-664. · Zbl 0778.90052
[12]	A. Ivanova, D. Grishchenko, A. Gasnikov, and E. Shulgin, Adaptive Catalyst for Smooth Convex Optimization, preprint, arXiv:1911.11271, 2019.
[13]	H. Lin, J. Mairal, and Z. Harchaoui, A universal catalyst for first-order optimization, in Proceedings of Advances in Neural Information Processing Systems, 2015, pp. 3384-3392.
[14]	H. Lin, J. Mairal, and Z. Harchaoui, Catalyst acceleration for first-order convex optimization: From theory to practice, J. Mach. Learn. Res., 18 (2018), pp. 1-54. · Zbl 1469.68101
[15]	H. Lu, R. M. Freund, and Y. Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim., 28 (2018), pp. 333-354. · Zbl 1392.90090
[16]	R. D. Monteiro and B. F. Svaiter, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIAM J. Optim., 23 (2013), pp. 1092-1125. · Zbl 1298.90071
[17]	A. Nemirovskii and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley, New York, 1983. · Zbl 0501.90062
[18]	Y. Nesterov, A method for solving the convex programming problem with convergence rate \(O(1/k^2)\), Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543-547.
[19]	Y. Nesterov, Accelerating the cubic regularization of Newton’s method on convex problems, Math. Program., 112 (2008), pp. 159-181. · Zbl 1167.90013
[20]	Y. Nesterov, Gradient methods for minimizing composite functions, Math. Program., 140 (2013), pp. 125-161. · Zbl 1287.90067
[21]	Y. Nesterov, Lectures on Convex Optimization, Springer Optim. Appl. 137, Springer, New York, 2018. · Zbl 1427.90003
[22]	Y. Nesterov, Implementable tensor methods in unconstrained convex optimization, Math. Program., 2019, https://doi.org/10.1007/s10107-019-01449-1. · Zbl 1459.90157
[23]	Y. Nesterov and B. T. Polyak, Cubic regularization of Newton’s method and its global performance, Math. Program., 108 (2006), pp. 177-205. · Zbl 1142.90500
[24]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), pp. 877-898. · Zbl 0358.90053
[25]	S. Salzo and S. Villa, Inexact and accelerated proximal point algorithms, J. Convex Anal., 19 (2012), pp. 1167-1192. · Zbl 1283.90030
[26]	M. Schmidt, N. L. Roux, and F. R. Bach, Convergence rates of inexact proximal-gradient methods for convex optimization, in Proceedings of Advances in Neural Information Processing Systems, 2011, pp. 1458-1466.
[27]	M. V. Solodov and B. F. Svaiter, A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optim., 22 (2001), pp. 1013-1035. · Zbl 1052.49013
[28]	Q. Van Nguyen, Forward-backward splitting with Bregman distances, Vietnam J. Math., 45 (2017), pp. 519-539. · Zbl 1371.90106