An Optimal High-Order Tensor Method for Convex Optimization

References

• [1] Alves MM, Monteiro RDC, Svaiter BF (2014) Primal-dual regularized SQP and SQCQP type methods for convex programming and their complexity analysis. Preprint, submitted May, http://www.optimization-online.org/DB_HTML/2014/05/4353.html.Google Scholar
• [2] Alves MM, Monteiro RDC, Svaiter BF (2016) Iteration-complexity of a Rockafellar’s proximal method of multipliers for convex programming based on second-order approximations. Preprint, submitted February 22, https://arxiv.org/abs/1602.06794.Google Scholar
• [3] Arjevani Y, Shamir O, Shiff R (2019) Oracle complexity of second-order methods for smooth convex optimization. Math. Programming 178:327–360.Google Scholar
• [4] Baes M (2009) Estimate Sequence Methods: Extensions and Approximations. (ETH, Zurich).Google Scholar
• [5] Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• [6] Birgin EG, Gardenghi JL, Martinez JM, Santos SA, Toint PhL (2017) Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Programming 163(1-2):359–368.Crossref, Google Scholar
• [7] Bullins B (2018) Fast minimization of structured convex quartics. Preprint, submitted December 26, https://arxiv.org/abs/1812.10349.Google Scholar
• [8] Bubeck S, Lee YT, Singh M (2015) A geometric alternative to Nesterov’s accelerated gradient descent. Preprint, submitted June 26, https://arxiv.org/abs/1506.08187.Google Scholar
• [9] Bubeck S, Jiang Q, Lee YT, Li Y, Sidford A (2019) Near-optimal method for highly smooth convex optimization. Conf. Learn. Theory (COLT), 492–507.Google Scholar
• [10] Burachik RS, Iusem AN, Svaiter BF (1997) Enlargement of monotone operators with applications to variational inequalities. Set-Valued Anal. 5(2):159–180.Crossref, Google Scholar
• [11] Calatroni L, Chambolle A (2019) Backtracking strategies for accelerated descent methods with smooth composite objectives. Siam J. Optim. 29(3):1772–1798.Crossref, Google Scholar
• [12] Cartis C, Gould NIM, Toint PhL (2017) Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Preprint, submitted August 14, https://arxiv.org/abs/1708.04044.Google Scholar
• [13] Cartis C, Gould NIM, Toint PhL (2019) Universal regularization methods: Varying the power, the smoothness and the accuracy. SIAM J. Optim. 29(1):595–615.Google Scholar
• [14] Cotter A, Shamir O, Srebro N, Sridharan K (2011) Better mini-batch algorithms via accelerated gradient methods. Advances in neural information processing systems, 1647–1655.Google Scholar
• [15] Drori Y, Teboulle M (2014) Performance of first-order methods for smooth convex minimization: a novel approach. Math. Programming 145(1-2):451–482.Crossref, Google Scholar
• [16] Gasnikov A, Dvurechensky P, Gorbunov E, Vorontsova E, Selikhanovych D, Uribe CA (2018) The global rate of convergence for optimal tensor methods in smooth convex optimization. Preprint, submitted September 2, https://arxiv.org/abs/1809.00382.Google Scholar
• [17] Gasnikov A, Dvurechensky P, Gorbunov E, Vorontsova E, Selikhanovych D, Uribe CA, Jiang B, et al. (2019) Near optimal methods for minimizing convex functions with Lipschitzp-th derivatives. Conf. Learn. Theory (COLT), 1392–1393.Google Scholar
• [18] Grapiglia GN, Nesterov Y (2019) Tensor Methods for Minimizing Functions with Hölder Continuous Higher-order Derivatives. Preprint, submitted April 29, https://arxiv.org/abs/1904.12559.Google Scholar
• [19] Jiang B, Lin T, Zhang S (2020) A unified adaptive tensor approximation scheme to accelerate composite convex optimization. SIAM J. Optim. 30(4):2897–2926.Google Scholar
• [20] Lan G (2012) An optimal method for stochastic composite optimization. Math. Programming 133(1):365–397.Crossref, Google Scholar
• [21] Lin Q, Xiao L (2014) An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. Comput. Optim. Appl. 60(3):633–674.Crossref, Google Scholar
• [22] Lu H, Freund RM, Nesterov Yu (2018) Relatively smooth convex optimization by first-order methods and applications. SIAM J. Optim. 28(1):333–354.Crossref, Google Scholar
• [23] Martínez JM (2017) On high-order model regularization for constrained optimization. SIAM J. Optim. 27(4):2447–2458.Crossref, Google Scholar
• [24] Monteiro RDC, Svaiter BF (2012) Iteration-complexity of a newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM J. Optim. 22:914–935.Crossref, Google Scholar
• [25] Monteiro RDC, Svaiter BF (2013) An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23(2):1092–1125.Crossref, Google Scholar
• [26] Nesterov Y (1983) A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Soviet Math. Doklady 269:543–547.Google Scholar
• [27] Nesterov Y (2008) Accelerating the cubic regularization of Newton’s method on convex problems. Math. Programming 112(1):159–181.Crossref, Google Scholar
• [28] Nesterov Y (2018) Implementable tensor methods in unconstrained convex optimization. CORE Discussion Paper 2018/05, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, Ottignies-Louvain-la-Neuve, Belgium.Google Scholar
• [29] Rockafellar RT (1970) On the maximal monotonicity of subdifferential mappings. Pacific J. Math. 33:209–216.Crossref, Google Scholar
• [30] Scheinberg K, Goldfarb D, Bai X (2014) Fast first-order methods for composite convex optimization with backtracking. Foundations Comput. Math. 14:389–417.Crossref, Google Scholar
• [31] Shalev-Shwartz S, Zhang T (2014) Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Preprint, submitted October 8, https://arxiv.org/abs/1309.2375.Google Scholar
• [32] Su W, Boyd S, Candes EJ (2016) A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. J. Machine Learning Res. 17(153):1–43.Google Scholar
• [33] Wibisono A, Wilson AC, Jordan MI (2016) A variational perspective on accelerated methods in optimization. Proc. National Acad. Sci. 113(47):7351–7358.Google Scholar
• [34] Wilson C, Recht B, Jordan MI (2016) A Lyapunov analysis of momentum methods in optimization. Preprint, submitted November 8, https://arxiv.org/abs/1611.02635.Google Scholar