Source-linked AI summary
Accelerated Methods for Non-Convex Optimization
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
TL;DR
The paper studies non-convex optimization with Lipschitz-continuous gradients and Hessians, where finding global minima is intractable. It combines eigenvector estimation, regularization, and accelerated gradient methods, obtaining a faster-than-gradient-descent rate in a supported setting and second-order guarantees.
Problem
The paper seeks sufficiently small-gradient stationary points for smooth non-convex functions because finding global minima is computationally intractable without further assumptions.
Method
The approach estimates the Hessian's smallest-eigenvalue direction and either moves along it or applies accelerated gradient descent to a carefully regularized subproblem.
Results
ϵ^-16/9 is achieved in the non-accelerated eigenvector-routine setting, improving on the ϵ^-2 gradient-descent rate while retaining a second-order guarantee.
Takeaways & Limitations
The method provides a first-order route to second-order stationary points and can converge linearly to local minimizers for strict-saddle functions.
Takeaways & Limitations
Replacing accelerated gradient descent with gradient descent removes the optimal trading between convexity and convergence rate, although the second-order guarantee remains.
Abstract
from arXiv · showhide
We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time $O(ε^{-7/4} \log(1/ ε) )$ to find an $ε$-stationary point, meaning a point $x$ such that $\|\nabla f(x)\| \le ε$. The method improves upon the $O(ε^{-2} )$ complexity of gradient descent and provides the additional second-order guarantee that $\nabla^2 f(x) \succeq -O(ε^{1/2})I$ for the computed $x$. Furthermore, our method is Hessian free, i.e. it only requires gradient computations, and is therefore suitable for large scale applications.
1 Introduction
The paper studies non-convex optimization, where global minimization is intractable, and asks whether gradient-only methods can improve on gradient descent while obtaining stronger stationarity guarantees.
- Problem: Global minimization is computationally intractable without further assumptions, motivating the search for stationary points with sufficiently small gradients.The problem assumes Lipschitz continuous gradient and Hessian but permits non-convexity.
- Existing methods: O(ε^-2) iterations suffice for gradient descent to find an ε-stationary point in the non-convex setting.The bound scales with the initial optimality gap and gradient Lipschitz constant.
- Existing methods: O(ε^-3/2) iterations are achievable with cubic-regularized Newton, but naive implementations explicitly compute Hessians and solve multiple linear systems at cost eO(d^3).These iterations require both gradient and Hessian calculations.
- Contribution: The paper asks whether gradient information alone can improve on gradient descent’s ε^-2 iteration complexity.The question concerns the number of gradient calculations.
- Contribution: The proposed method provides a second-order guarantee ∇^2f(x) ⪰ −√εI and converges to second-order stationary points with polynomial accuracy and logarithmic dimension dependence.For strict-saddle functions, it converges linearly to local minimizers.
- Contribution: The approach combines almost-convex regularization with accelerated gradient descent and approximate minimum-eigenvector computations to improve running time.The method alternates between negative-curvature directions and structured nearly convex subproblems.
2 Notation and standard results
This section establishes smoothness, optimality-gap, generalized convexity, and computational conventions, then recalls accelerated gradient and approximate eigenvector guarantees used later.
- Definitions: An L1-smooth function has an L1-Lipschitz gradient, while an L2-Lipschitz Hessian controls Hessian variation.These are the principal regularity assumptions used throughout the paper.
- Definitions: An optimality gap Δf bounds the difference between the function value at a point and the global infimum.The paper assumes a finite gap at the initial search point.
- Definitions: A function may be σ1-strongly convex with negative σ1; writing γ = max{−σ1, 0} defines γ-almost convexity.This parameter measures the extent of non-convexity.
- Regularization: Adding γ∥z − z0∥^2 to a γ-almost convex function makes the regularized function γ-strongly convex.This enables the use of standard convex proximal methods on nearly convex objectives.
- Computational model: The analysis measures runtime in gradient-operation units and treats gradient, Hessian-vector, and vector-arithmetic operations as O(Tgrad).Under this convention, an algorithm is Hessian free when its basic operations cost at most O(Tgrad).
- Eigenvector computation: Accelerated approximate leading-eigenvector computation runs in O(Thess log(d/δ) ε^-1/2) time with probability at least 1 − δ.Applied to L1I − ∇^2f(x), this yields an approximate smallest Hessian eigenvector.
3 Two structured non-convex problems
The method alternates between exploiting negative curvature and solving almost-convex regularized subproblems, using accelerated procedures to find stationary points efficiently.
- Overview: The overall algorithm alternates between negative-curvature directions and nearly convex subproblems whose Hessian minimum eigenvalue is bounded below by −γ.The intended regime has γ much smaller than L1.
- Almost-convex acceleration: Regularizing a γ-almost convex function with γ∥z − zj∥^2 makes each proximal model strongly convex and suitable for accelerated gradient descent.When γ is much smaller than L1, the regularized model has better fidelity than the model associated with gradient descent.
- Almost-convex acceleration: Almost-convex-AGD returns a point with gradient norm at most ε, and its runtime improves over gradient descent whenever γ ≪ L1.The guarantee assumes smoothness and an appropriate almost-convexity parameter.
- Negative curvature: Negative-curvature descent searches for an approximate smallest Hessian eigenvector and moves along it when the Hessian has sufficiently negative curvature.The step decreases the objective substantially; otherwise, the routine identifies a nearly almost-convex region.
- Negative curvature: The negative-curvature routine terminates after a bounded number of iterations, with per-iteration cost controlled by approximate eigenvector computation.Its probabilistic guarantee accounts for failures across iterations using a union bound.
4 An accelerated gradient method for non-convex optimization
The method combines negative-curvature descent, regularization, and accelerated gradient optimization to handle smooth non-convex objectives. With an appropriate curvature parameter, it achieves an accelerated convergence rate while retaining a second-order guarantee.
- Method: The method combines Negative-curvature-descent with Almost-convex-AGD to accelerate gradient-based optimization for smooth non-convex functions.Negative-curvature-descent finds directions of negative curvature, while Almost-convex-AGD solves the resulting nearly convex subproblems.
- Convergence: eO(ε^-7/4) convergence follows by trading curvature minimization against accelerated gradient progress through the parameter α.The parameter α controls acceptable non-convexity, and its careful selection yields the stated rate.
- Regularization: Regularization transforms a locally almost convex function into a globally almost convex and smooth objective suitable for accelerated optimization.Lemma 4.1 states that fα is 3α-almost convex and 5L1-smooth under the stated smoothness and Hessian-Lipschitz assumptions.
- Guarantees: With probability at least 1 − δ, the method terminates at an ε-stationary point while maintaining λmin(∇^2f(x̂k)) ≥ −2α throughout its iterations.The guarantee applies to L1-smooth functions with L2-Lipschitz continuous Hessians and includes a high-probability iteration bound.
- Alternative complexity: Non-accelerated eigenvector routines can still achieve a total complexity of order ε^-16/9, which is faster than the ε^-2 rate of gradient descent.This alternative uses α ≍ ε^4/9 rather than α ≍ ε^1/2 and ignores other problem-dependent constants.
5 Accelerated (linear) convergence to local minimizers of strict-saddle functions
Under strict-saddle assumptions, the paper uses a two-phase accelerated method to reach local minimizers with linear convergence in the desired accuracy.
- Motivation: Strict-saddle functions ensure that sufficiently accurate second-order stationary points are local minimizers under the paper’s assumptions.The method assumes Lipschitz-continuous Hessians and excludes zero Hessian eigenvalues at approximate stationary points.
- Algorithm: The algorithm first finds a strongly convex neighborhood, then solves a regularized locally convex problem using accelerated gradient descent.The first phase uses gradient and Hessian bounds, while the second phase applies accelerated gradient descent to the resulting region.
- Guarantees: With probability at least 1 −δ, the method returns x satisfying ∥∇f(x)∥≤ϵ under L1-smoothness, Lipschitz Hessians, and σ1-strict-saddle structure.The theorem’s running-time expression depends on τ′ = 1 + L1/σ1 + 1/δ + d + L2 + ∆f.
- Guarantees: When ϵ ≤ σ2 1 16L2, the returned point is associated with a local minimizer x⋆+ of f.The proof constructs a regularized function f+ that is σ1/2-strongly convex and 5L1-smooth, then shows its minimizer lies where f+=f.
- Guarantees: The running-time guarantee is obtained by summing the costs of the two algorithmic phases.
- Proof: The constructed minimizer x⋆+ is a local minimizer of f because f+ agrees with f on a neighborhood containing x⋆+.The final accelerated-gradient point remains in this neighborhood, preserving the gradient guarantee for the original function.