Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding

Abstract

In this paper, we present a new Hyperfast Second-Order Method with convergence rate $O(N^{-5})$ up to a logarithmic factor for the convex function with Lipshitz the third derivative. This method based on two ideas. The first comes from the superfast second-order scheme of Yu. Nesterov (CORE Discussion Paper 2020/07, 2020). It allows implementing the third-order scheme by solving subproblem using only the second-order oracle. This method converges with rate $O(N^{-4})$. The second idea comes from the work of Kamzolov et al. (arXiv:2002.01004). It is the inexact near-optimal third-order method. In this work, we improve its convergence and merge it with the scheme of solving subproblem using only the second-order oracle. As a result, we get convergence rate $O(N^{-5})$ up to a logarithmic factor. This convergence rate is near-optimal and the best known up to this moment. Further, we investigate the situation when there is a sum of two functions and improve the sliding framework from Kamzolov et al. (arXiv:2002.01004) for the second-order methods.

References in corpus (10)

• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Solving Linear Programs with Sqrt(rank) Linear System Solves
• Contracting Proximal Methods for Smooth Convex Optimization
• Universal gradient descent
• Complexity of Highly Parallel Non-Smooth Convex Optimization
• The global rate of convergence for optimal tensor methods in smooth convex optimization
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• A Note on Inexact Condition for Cubic Regularized Newton's Method

Cited by in corpus (6)

• Accelerated meta-algorithm for convex optimization
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
• Parallel and Distributed algorithms for ML problems
• Convex optimization