Local convergence of tensor methods

Nikita Doikov, Yurii E. NesterovMath. Program 2022 · DOI

TL;DR

This paper introduces and analyzes "Tensor Methods" for solving a specific class of optimization problems (composite convex optimization). The key contribution is proving that these high-order methods can achieve "local superlinear convergence," meaning they get very close to the optimal solution very quickly once they are near it. This is significant because it offers a theoretical foundation for why these complex methods can be efficient in practice.

What Problem Does This Paper Address?

In optimization, we often want to find the minimum of a function. For complex problems, especially those involving a "smooth" part and a "simple but possibly non-smooth" part (composite optimization), finding the absolute best solution can be computationally expensive. Traditional methods like Newton's method offer good convergence rates (quadratic), but they rely on second-order derivatives (Hessian). Higher-order methods, using derivatives up to degree $p$, promise even faster convergence but come with increased complexity in computation and analysis. A major challenge has been to rigorously prove that these high-order methods can indeed achieve faster-than-quadratic convergence (superlinear) and to understand the conditions under which this happens, especially for composite objectives.

Methods

The paper focuses on a specific high-order method called the "Regularized Composite Tensor Method" (RCTM). The core idea is to use Taylor approximations of the objective function up to a certain degree $p$ (where $p \ge 2$) and combine them with a regularization term (a term involving the Euclidean norm) to ensure convexity of the subproblem. This allows for efficient minimization of the approximate objective. The analysis then delves into proving local superlinear convergence. This involves:

  • High-Order Taylor Approximations: Using approximations of the objective function that go beyond the standard quadratic (second-order) Taylor expansion.
  • Composite Objective Handling: Developing methods that can handle objectives composed of a smooth function and a simple, non-smooth function (like indicator functions for constraints).
  • Uniform Convexity Assumption: Assuming the smooth part of the objective is "uniformly convex" of a certain degree $q$. This property is crucial for guaranteeing fast convergence.
  • Local Convergence Analysis: Proving that once the method is close enough to the optimal solution, the error decreases at a superlinear rate. This is done by analyzing the properties of the gradient and function value at successive iterations.
  • Global Convergence Bounds: Extending the analysis to provide bounds on the total number of iterations needed to reach a certain level of accuracy, even from an arbitrary starting point.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and does not present experimental results on specific datasets.

Key Insights and Ideas

  • High-Order Methods Can Be Efficient: The paper provides theoretical backing for the intuition that using higher-order derivatives (beyond second-order) can lead to significantly faster convergence, especially in the local region around the optimum.
  • Uniform Convexity is Key: The assumption of uniform convexity of the smooth component is critical for achieving superlinear convergence rates. The degree of this uniform convexity ($q$) plays a role in determining the convergence rate.
  • Composite Structure is Manageable: The methods developed can effectively handle optimization problems that are a sum of a smooth and a simple non-smooth function, which is a common structure in many real-world applications.
  • Local Convergence Guarantees Global Performance: The paper shows how fast local convergence can be leveraged to design algorithms that achieve good global performance, particularly when combined with inexact proximal steps.

Key Results

  • Local Superlinear Convergence: The paper proves that the RCTM achieves local superlinear convergence for composite convex optimization problems under uniform convexity assumptions. The rate depends on the order of the method ($p$) and the degree of uniform convexity ($q$).
  • Convergence in Function Value and Gradient Norm: The analysis establishes convergence guarantees for both the function value and the norm of the minimal subgradient.
  • Global Complexity Bounds: The paper provides bounds on the total number of iterations required to reach a desired accuracy, showing sublinear convergence rates for convex objectives and linear rates for uniformly convex objectives.
  • Application to Proximal Methods: A novel approach is presented where the local convergence of RCTM is used to accelerate inexact proximal methods, leading to improved global convergence rates.

Limitations and Future Work

  • Computational Complexity: While the paper proves theoretical convergence, the practical implementation of high-order tensor methods can be computationally expensive due to the calculation and manipulation of higher-order derivatives. The paper acknowledges this by discussing the "prohibiting complexity" of high-order Taylor approximations.
  • Assumptions: The analysis relies on strong assumptions, such as uniform convexity and Lipschitz continuity of higher-order derivatives. The behavior of the methods under weaker assumptions might be an area for future research.
  • Practical Implementation Details: The paper focuses on theoretical guarantees. Further research could explore practical implementation strategies, including efficient computation of derivatives and robust handling of numerical precision.
  • Relation to Other High-Order Methods: The paper mentions recent results on third-order schemes and their potential acceleration. Investigating the precise relationship between the proposed tensor methods and these other advanced techniques could be a fruitful direction.

Summary updated

BibTeX
@article{doikov2022local,
  author = {Nikita Doikov and Yurii E. Nesterov},
  title = {{Local convergence of tensor methods}},
  journal = {Math. Program.},
  year = {2022},
  doi = {10.1007/s10107-020-01606-x},
}
Figure