Tight convergence rates of the gradient method on smooth hypoconvex functions

Teodor Rotaru, François Glineur, Panagiotis PatrinosarXiv 2022 · DOI · arXiv

TL;DR

This paper provides the first "tight" (exact worst-case) convergence analysis for the gradient method when applied to hypoconvex (weakly convex) functions. By leveraging the Performance Estimation Problem (PEP) framework, the authors derive explicit bounds that bridge the gap between smooth convex and general nonconvex optimization, identifying the optimal step sizes to minimize the worst-case gradient norm.

What Problem Does This Paper Address?

In the world of optimization, we usually have a clear picture of how Gradient Descent (GD) behaves on convex functions—we have tight bounds on how fast it reaches the minimum. However, most real-world machine learning problems are nonconvex.

Standard analysis for nonconvex functions often assumes the gradient is $L$-Lipschitz (meaning the curvature is bounded between $-L$ and $L$). But this is a "one-size-fits-all" approach. Many functions fall into a middle ground called hypoconvexity (or weak convexity), where the curvature is bounded by a specific interval $[\mu, L]$, with $\mu < 0$.

Until now, we lacked a tight analysis that accounted for this specific degree of nonconvexity ($\mu$). Existing bounds were either too pessimistic or didn't smoothly transition as a function became "more" or "less" convex. This paper fills that gap by providing exact worst-case rates for this specific class of functions.

Methods

The authors employ a powerful modern tool called the Performance Estimation Problem (PEP).

  1. Optimizing the Optimizer: Instead of traditional "pen-and-paper" proofs, PEP models the search for a convergence bound as an optimization problem itself: "Find the function in class $\mathcal{F}$ that makes the algorithm perform the worst."
  2. Interpolation Conditions: To make PEP work for hypoconvex functions, the authors derived new "interpolation conditions." These are mathematical rules that allow a discrete set of points (iterates) to be represented as if they came from a continuous hypoconvex function.
  3. SDP Relaxation: They transform the infinite-dimensional problem of searching over all possible functions into a finite-dimensional Semidefinite Program (SDP), which can be solved numerically to find (and then prove) analytical bounds.

Datasets

As a theoretical paper in mathematical optimization, no empirical datasets (like ImageNet or CIFAR) were used. The "data" consists of numerical solutions to the PEP semidefinite programs, which the authors used to infer and then formally prove their analytical convergence theorems.

Key Insights and Ideas

  • The "Bridge" Effect: The derived rates are not just new; they are unifying. If you set $\mu = 0$, you recover the known tight rates for convex functions. If you set $\mu = -L$, you recover the rates for standard $L$-smooth nonconvex functions.
  • Minimum Gradient Norm: In nonconvex optimization, you can't always find the global minimum, so the standard measure of success is finding a "stationary point" where the gradient is zero. The paper tracks the minimum gradient norm observed across all iterations.
  • Three Step-Size Regimes: The authors discovered that the worst-case behavior changes qualitatively across three regimes of step sizes: small ($h \in (0, 1]$), medium ($h \in [1, \bar{h}]$), and large ($h > \bar{h}$).
  • Structure of Convergence: They show that all these sublinear rates share a common structure: $\min \|\nabla f\|^2 \le \frac{2L(f(x_0) - f_*)}{q + \sum p_i}$, where $q$ and $p_i$ are constants related to the step size and curvature.

Key Results

  • Tight Bounds: The authors provide explicit upper bounds on the convergence rate and prove they are tight (cannot be improved) for step sizes $h \le 1/L$.
  • Optimal Step Size: They identify the optimal constant step size $h_*$ that minimizes the worst-case gradient norm. Interestingly, this optimal step size is a unique solution to a cubic equation involving the nonconvexity parameter $\kappa = \mu/L$.
  • Convex Case Extension: For the specific case of convex functions ($\mu=0$), they extended the range of known tight bounds for step sizes up to $3/2L$.
  • Analytical Conjectures: For very large step sizes where formal proofs are difficult, they provide partially explicit analytical expressions backed by extensive numerical PEP simulations.

Limitations and Future Work

  • Knowledge of Curvature: The proposed optimal step size requires knowing both $L$ (upper curvature) and $\mu$ (lower curvature). In practice, $\mu$ is often very difficult to estimate accurately.
  • Worst-Case Pessimism: Like all PEP-based results, these are "worst-case." An algorithm might perform much better on a "typical" problem than these bounds suggest.
  • Unproven Regimes: While the bounds for small and medium step sizes are proven, the results for the "large" step-size regime remain conjectures (though strongly supported by numerical evidence). Proving these remains an open challenge.

Summary updated

Abstract

We perform the first tight convergence analysis of the gradient method with varying step sizes when applied to smooth hypoconvex (weakly convex) functions. Hypoconvex functions are smooth nonconvex functions whose curvature is bounded and assumed to belong to the interval $[μ, L]$, with $μ&lt;0$. Our convergence rates improve and extend the existing analysis for smooth nonconvex functions with $L$-Lipschitz gradient (which corresponds to the case $μ=-L$), and smoothly interpolates between that class and the class of smooth convex functions. We obtain our results using the performance estimation framework adapted to hypoconvex functions, for which new interpolation conditions are derived. We derive explicit upper bounds on the minimum gradient norm of the iterates for a large range of step sizes, explain why all such rates share a common structure, and prove that these rates are tight when step sizes are smaller or equal to $1/L$. Finally, we identify the optimal constant step size that minimizes the worst-case of the gradient method applied to hypoconvex functions.
BibTeX
@misc{rotaru2022tight,
  author = {Teodor Rotaru and François Glineur and Panagiotis Patrinos},
  title = {{Tight convergence rates of the gradient method on smooth hypoconvex functions}},
  year = {2022},
  eprint = {2203.00775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.00775},
}
Figure