Source-linked AI summary
A geometric alternative to Nesterov's accelerated gradient descent
Sébastien Bubeck, Yin Tat Lee, Mohit Singh
TL;DR
The paper addresses unconstrained optimization for smooth, strongly convex functions by proposing a geometric alternative to accelerated gradient descent. Its ball-intersection method achieves the optimal convergence rate, while experiments provide evidence of advantages over standard methods, subject to dataset-size exclusions.
Problem
The paper seeks an intuitive accelerated method for smooth, strongly convex optimization, where Nesterov’s accelerated gradient descent is difficult to interpret.
Method
The method combines gradient information with ellipsoid-inspired intersections of balls containing the optimum and uses line searches in its more aggressive algorithm.
Results
The proposed method matches the optimal first-order convergence rate and numerical experiments report that GeoD outperforms SD, AFG, and AFGwR but remains worse than L-BFGS on one classification experiment.
Takeaways & Limitations
The algorithm does not require the smoothness parameter or iteration count, guarantees strictly decreasing function values, and may suit machine-learning applications.
Takeaways & Limitations
The binary-classification experiments omit datasets of size ≥100 MB for time considerations.
Abstract
from arXiv · showhide
We propose a new method for unconstrained optimization of a smooth and strongly convex function, which attains the optimal rate of convergence of Nesterov's accelerated gradient descent. The new algorithm has a simple geometric interpretation, loosely inspired by the ellipsoid method. We provide some numerical evidence that the new method can be superior to Nesterov's accelerated gradient descent.
1 Introduction
The paper proposes a geometric optimization method for smooth, strongly convex functions that combines gradient descent with ellipsoid-style ball intersections to achieve accelerated convergence.
- For a β-smooth, α-strongly convex function, κ = β/α is the condition number.
- Gradient descent decreases squared distance to the optimum at rate 1 − 1/κ, while the proposed method targets 1 − 1/√κ.
- Each proposed iteration requires one gradient evaluation and two line-searches while matching the optimal first-order convergence rate.
- The method maintains balls containing the optimum, uses smoothness to shrink them, and encloses their intersection with a smaller ball.
- The paper presents the geometric intuition, analyzes the optimal method, and evaluates it experimentally.
2 Intuition
The geometric intuition represents gradient information and prior iterates as balls containing the optimum; shrinking two appropriately separated balls accelerates the reduction of the enclosing radius.
- 2 Intuition: The geometric alternative combines a current ball A with a previously obtained ball B containing the optimum.
- 2 Intuition: When only one ball shrinks, the intersection contracts at the same rate, whereas shrinking two balls by the same absolute amount contracts it much faster.
- 2.1 A suboptimal algorithm: An initial guarantee x∗ ∈ B(x0, R0^2) supplies the enclosing ball used to begin the iterative construction.
- 2.1 A suboptimal algorithm: Because the two ball centers are far apart, their intersection fits inside a substantially smaller ball.
- 2.1 A suboptimal algorithm: The map T sends xk to xk+1, defining the iterative sequence used by the suboptimal algorithm.
- 2.1 A suboptimal algorithm: After 2κ log(R0/ε) gradient-oracle iterations, the suboptimal method obtains a point ε-close to the minimizer.
- 2.2 Why one can accelerate: Acceleration comes from shrinking both the current and inherited balls, but line search is needed when the accelerated center may not satisfy the next function-value condition.
- 2.2 Why one can accelerate: The line search makes ∇f(x1) perpendicular to the line through x1 and the accelerated center, allowing the geometric construction to continue.
3 An optimal algorithm
The optimal algorithm uses geometric ball intersections to maintain a shrinking region containing the optimum. Its more aggressive version uses line search and has practical parameter and monotonicity advantages.
- Geometric proof: The method applies a geometric lemma to the intersection of two balls and proves that their enclosing ball has a smaller squared radius.The proof moves the current center to the origin, scales distances by the current radius, and verifies the required geometric inequalities.
- Geometric proof: The line-search construction ensures ∇f(xk+1)ᵀ(xk+1 − ck) = 0, enabling the geometric lemma through the bound |xk+1 − ck| ≥ |∇f(xk+1)|/α.This bound supplies the lemma's required distance condition.
- Algorithm 1: Algorithm 1 computes the minimum enclosing ball of the intersection of two input balls, returning center c and radius R.The inputs are centers xA, xB and radii RA, RB.
- Algorithm 2: Algorithm 2 is more aggressive than Theorem 1 by using line search instead of a fixed step size, and its correctness follows from a similar proof.The paper explicitly presents this as the aggressive version of the algorithm.
- Practical properties: The algorithm does not require the smoothness parameter or iteration count, guarantees strictly decreasing function values, and requires only α as a given parameter.The authors identify these properties as useful for machine learning applications and emphasize its integration of zeroth- and first-order information.
4 Experiments
The experiments compare GeoD with several full-gradient and quasi-Newton methods on binary classification and a worst-case function. GeoD outperforms the accelerated gradient baselines on the classification tasks, while worst-case behavior varies by iteration regime.
- Experimental setup: GeoD is compared with SD, AFG, AFGwR, and L-BFGS using one computationally dominant calculation per iteration.The implementation includes exact line searches for some methods, while experiments report iteration counts because line-search costs are negligible relative to the dominant calculation.
- Binary classification: GeoD is better than SD, AFG, and AFGwR but worse than L-BFGS on the reported classification comparisons.Performance is summarized by the median and 90th percentile number of steps needed to reach a certain accuracy.
- Experimental scope: Datasets of size ≥100 MB are omitted from the classification experiments for time considerations.
- Worst-case experiment: After Θ(n) iterations, SD and AFG continue at the theoretically predicted rate, whereas other methods converge much faster.During the first n iterations, every method except SD has the same rate with different constants; AFGwR and GeoD are comparable despite memory size 1.