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

Dmitry Kamzolov, Alexander GasnikovarXiv 2020 · DOI · arXiv

Abstract

In this paper, we present a new Hyperfast Second-Order Method with a convergence rate of $O(N^{-5})$ up to a logarithmic factor for convex functions with a Lipschitz third derivative. This method is based on two primary ideas. The first stems from the superfast second-order scheme of Yu. Nesterov (2020), which allows implementing a third-order scheme by solving subproblems using only a second-order oracle, achieving a rate of $O(N^{-4})$. The second idea is derived from the work of Kamzolov et al. (2020) regarding the inexact near-optimal third-order method. In this work, we improve its convergence and merge it with the scheme of solving subproblems using only the second-order oracle. As a result, we achieve a convergence rate of $O(N^{-5})$ up to a logarithmic factor. This convergence rate is near-optimal and the best known to date. Furthermore, we investigate the case of a sum of two functions and improve the sliding framework for second-order methods.

Introduction

In convex optimization, a fundamental trade-off exists between the computational cost of a single iteration and the total number of iterations required to reach a target accuracy $\epsilon$. First-order methods, such as Gradient Descent, are computationally inexpensive per step but converge slowly. Conversely, second-order methods like Newton’s method converge in fewer iterations but require the computation and inversion of Hessians.

Recent theoretical advancements by Yurii Nesterov demonstrated that if a function possesses "extra smoothness"—specifically, a Lipschitz continuous third derivative—it is possible to surpass classical lower bounds for second-order methods. While Nesterov achieved a rate of $O(N^{-4})$, this paper explores whether a near-optimal rate of $O(N^{-5})$ is attainable using only a second-order oracle. Additionally, we address the challenge of composite functions (sums of two functions) where one component may be significantly more expensive to compute than the other.

Methodology

The proposed "Hyperfast" method integrates and enhances several sophisticated algorithmic components to push the boundaries of second-order optimization.

1. NATMI: Inexact Near-optimal Accelerated Tensor Method

The authors propose a generalized version of an accelerated tensor method designed to accommodate inexact solutions to internal subproblems. Solving a third-order Taylor approximation perfectly is computationally prohibitive; NATMI allows for a controlled level of error, which is essential for practical implementation.

2. BDGM: Bregman-Distance Gradient Method

To solve the subproblems generated by NATMI, the authors employ the Bregman-Distance Gradient Method. This approach approximates the third-order step using only first and second-order information (gradients and Hessians). By leveraging the second-order oracle to simulate a third-order step, the method avoids the direct calculation of the third derivative while maintaining high-order convergence properties.

3. Hyperfast Second-Order Sliding

For objective functions structured as a sum $f(x) = g(x) + h(x)$, the authors introduce a "sliding" framework. This technique allows the algorithm to skip unnecessary derivative computations for the "easier" or smoother component of the function. By effectively separating the oracle complexities, the algorithm ensures that the total computational burden is not dictated solely by the most expensive component.

Key Insights

  • The "Superfast" Loophole: By assuming higher-order smoothness (Lipschitz third derivatives), the method bypasses traditional second-order limits. It effectively uses second-order data to simulate the performance of a third-order method.
  • Sufficiency of Inexactness: A critical finding is that the complex Taylor-approximation subproblems do not require perfect solutions. As long as the BDGM solves these subproblems to a specific relative accuracy, the global $O(N^{-5})$ convergence rate remains preserved.
  • Efficiency through Sliding: The sliding framework provides a robust mechanism for handling composite objectives, allowing each function in a sum to be sampled according to its specific smoothness properties rather than a "worst-case" global assumption.

Theoretical Results

The primary contribution of this work is the achievement of a near-optimal convergence rate of $O(N^{-5})$ (up to a logarithmic factor). This represents the current state-of-the-art for this class of smooth convex problems.

In terms of oracle complexity, for a target accuracy $\epsilon$, the method requires approximately $O(\epsilon^{-1/5})$ Hessian evaluations. When compared to Stochastic Gradient Descent (SGD) in the context of large-scale machine learning (e.g., click prediction models), the authors demonstrate that if the required accuracy $\epsilon$ is sufficiently small—specifically $\epsilon = O(m^{-5/9})$ where $m$ is the number of data points—this hyperfast second-order approach theoretically outperforms SGD.

Discussion and Limitations

While the theoretical results are significant, several practical considerations remain:

  1. Accuracy Requirements: The threshold $\epsilon$ at which this method outperforms simpler first-order methods is quite small. In many machine learning applications, where low-precision solutions are often sufficient, the benefits of this method may not be immediately realized.
  2. Smoothness Assumptions: The reliance on Lipschitz continuity of the third derivative is a strong assumption. Verifying this property or adapting the method for functions that lack such smoothness is an area for future research.
  3. Computational Overhead: Although the iteration count is low, each iteration involves an inner loop (BDGM) to solve the subproblem. Managing the constant-factor overhead of these inner iterations is crucial for real-world performance.
  4. Non-Convexity: The current proofs are limited to the convex case. While there is potential for adapting these techniques to find stationary points in non-convex optimization, this remains to be formally established.

Summary updated

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.
BibTeX
@misc{kamzolov2020near,
  author = {Dmitry Kamzolov and Alexander Gasnikov},
  title = {{Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding}},
  year = {2020},
  eprint = {2002.09050},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.09050},
}
Figure