PaperlayerView exact revision on arXiv

Source-linked AI summary

"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Yair Carmon, Oliver Hinder, John C. Duchi, Aaron Sidford

arXiv:1705.02766v1math.OC

TL;DR

The paper addresses limited transfer of convex acceleration theory to smooth non-convex optimization, where gradients lack global information. It develops an AGD variant that either behaves as though the function were strongly convex or identifies non-convexity exploitable through negative curvature, yielding provable acceleration.

  • Problem

    Convex acceleration theory has limited known transfer to large-scale non-convex optimization, where gradients no longer provide global information and stationary-point classification is generally difficult.

  • Method

    The method runs accelerated gradient descent until non-convexity is certified, then exploits a convexity violation by stepping along a negative-curvature direction.

  • Results

    The approach provably accelerates gradient descent for a broad class of smooth non-convex functions, with negative-curvature progress and improved guarantees under third-order smoothness.

  • Takeaways & Limitations

    Acceleration and negative-curvature exploitation can be combined to obtain deterministic convergence improvements in non-convex optimization.

  • Takeaways & Limitations

    The method provides no guarantee of positive definiteness for the Hessian at its output and terminates immediately if initialized at a saddle point.

Abstract

from arXiv · show

We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our AGD variant converges quickly, as if the function was convex, or we produce a certificate that the function is "guilty" of being non-convex. This non-convexity certificate allows us to exploit negative curvature and obtain deterministic, dimension-free acceleration of convergence for non-convex functions. For a function $f$ with Lipschitz continuous gradient and Hessian, we compute a point $x$ with $\|\nabla f(x)\| \le ε$ in $O(ε^{-7/4} \log(1/ ε) )$ gradient and function evaluations. Assuming additionally that the third derivative is Lipschitz, we require only $O(ε^{-5/3} \log(1/ ε) )$ evaluations.

1 Introduction

The paper adapts accelerated gradient descent to smooth non-convex optimization by either certifying convex-like progress or exposing negative curvature. This yields deterministic, dimension-free first-order complexity improvements over gradient descent, including stronger rates under third-order smoothness.

  • Non-convex optimization is harder because gradients lack global information, but negative-curvature directions can still guarantee function-value reduction.
  • Our contributions: AGD either behaves as though the function were strongly convex or produces trajectory points certifying a violation of strong convexity.The monitoring procedure detects slow progress and finds a witness pair when the convex-like guarantee fails.
  • Our contributions: The method uses exposed negative curvature to obtain O(ε^-7/4 log 1/ε) first-order oracle complexity, improving on gradient descent’s O(ε^-2) rate.
  • Our contributions: Preliminary experiments show that a basic implementation outperforms gradient descent but not nonlinear conjugate gradient.
  • Our contributions: Under Lipschitz continuous third derivatives, the complexity improves to O(ε^-5/3 log 1/ε) while the method still uses only first-order information.The stronger smoothness assumption permits larger negative-curvature steps and greater function progress.
  • Related work: The result is dimension-free and deterministic, avoiding the dimension dependence associated with prior approaches.The method also avoids eigenvector search and Hessian-vector products.

2 Algorithm components

The method combines monitored accelerated gradient descent with a negative-curvature descent step. AGD either progresses as expected for a strongly convex function or returns a witness pair certifying non-convexity, which is then exploited for function decrease.

  • Method overview: The approach combines monitored AGD with a negative-curvature descent step to accelerate optimization of non-convex functions.The two components are introduced as the building blocks of the method.
  • Monitored AGD: AGD-until-proven-guilty optimizes an L-smooth function while testing whether gradient norms decrease exponentially as expected under strong convexity.If the test fails, Find-witness-pair returns points u and v showing that the function violates σ-strong convexity.
  • Monitored AGD: The monitor has two outcomes: successful accelerated progress under local strong-convexity conditions or a witness pair certifying non-convexity.The paper frames this as using AGD to determine whether the function is effectively strongly convex along its trajectory.
  • Implementation: The algorithm can reduce implementation overhead by checking certification conditions only every τ iterations and regenerate stored sequences using O(d) memory.The latter option increases gradient and function evaluations by at most a factor of 2.
  • Negative curvature: A convexity-violation pair u, v exposes negative curvature along the direction u−v, enabling a descent step that lowers the function value.The negative-curvature lemma first establishes curvature in this direction and then uses a step of size η in one of the two signs.
  • Negative curvature: The negative-curvature guarantee requires an L2-Lipschitz Hessian, a controlled pair distance, and a step size satisfying η ≤ α/L2.Under these conditions, the procedure finds z with a function decrease proportional to αη^2.

3 Accelerating non-convex optimization

Guarded-non-convex-AGD applies monitored AGD to a proximal regularization and chooses either an accelerated iterate or a negative-curvature step. Under Lipschitz-gradient and Lipschitz-Hessian assumptions, it reaches an ε-stationary point with the paper’s improved complexity bound, subject to stated accuracy conditions.

  • Algorithm: Guarded-non-convex-AGD applies AGD-until-proven-guilty to a proximal regularization around the current iterate.If no convexity violation is detected, the next iterate is the monitored AGD output; otherwise, the method exploits the witness pair.
  • Algorithm: When no violation is detected, proximal-point arguments provide progress because the regularized objective behaves effectively as strongly convex.The method terminates when the resulting point has sufficiently small gradient for the original objective.
  • Algorithm: When a violation is detected, the method certifies negative curvature and uses Exploit-NC-pair to produce a lower-valued candidate.The next iterate is selected as the best among AGD iterates, the witness point, and the negative-curvature candidate.
  • Complexity: Ω(ε^3/2) progress is obtained per outer iteration when α = √ε, yielding O(ε^-3/2) outer iterations.The complexity follows by combining this progress guarantee with the cost of each monitored AGD call.
  • Complexity: ∥∇f(pK)∥ ≤ ε is guaranteed under the theorem’s smoothness, Hessian-Lipschitz, bounded-suboptimality, and accuracy assumptions.The theorem counts gradient evaluations and gives a corresponding function-evaluation bound of the same order.
  • Scope and comparison: The stated bound is intended for the nontrivial accuracy regime; when ε ≥ L2^2/L1, gradient descent can provide better guarantees.The paper also notes that the theorem’s bounds remain formally valid outside this regime, although the algorithm may halt after one iteration.

4 Incorporating third-order smoothness

Under Lipschitz third derivatives, the method modifies negative-curvature exploitation and iterate selection to obtain greater progress while preserving the second-order guarantees. These changes yield an improved convergence complexity.

  • 4.1 Making better use of negative curvature: Third-order smoothness permits larger negative-curvature steps and greater function-value decrease without accessing higher-order derivatives.The improvement follows from the antisymmetry of odd-order Taylor terms, whereas symmetric fourth-order terms prevent the same extension to higher orders.
  • 4.1 Making better use of negative curvature: The modified Exploit-NC-pair3 handles cases where negative curvature cannot be guaranteed at either endpoint of the relevant pair.Its guarantee improves the larger of the two endpoint function values rather than necessarily improving f(u).
  • 4.2 Bounding the function values of the iterates using cubic interpolation: Find-best-iterate3 uses cubic interpolation points to bound potentially large intermediate function values along the AGD trajectory.The construction evaluates y0 through yt together with cj, qj, and u, then returns the lowest-function-value point among them.
  • 4.3 An improved rate of convergence: The enhanced algorithm combines Exploit-NC-pair3 and Find-best-iterate3 while retaining the original guarantees under only second-order smoothness.Algorithm 3 transitions between smoothness regimes by changing the scaling of α and η with ε.
  • 4.3 An improved rate of convergence: O(ε^-5/3 log(1/ε)) evaluations are sufficient to find pK with ||∇f(pK)|| ≤ ε under Lipschitz third derivatives.The theorem assumes Lipschitz gradient and third-order derivatives, with parameter conditions stated in the theorem.

5 Preliminary experiments

The preliminary experiments compare the proposed method with gradient-based baselines on non-convex regression and small neural-network training. Results show curvature exploitation helps on the regression problem, while the neural-network loss behaves effectively convex in the tested setting.

  • Experimental setup: The experiments compare Alg. 3 with GD, NCG, RAGD, and C-Alg. 3 using gradient-step counts.C-Alg. 3 removes negative-curvature exploitation from the proposed method.
  • Non-linear regression: The regression study uses 1,000 randomly generated, substantially non-convex instances with d = 30 and m = 60.The model uses a smooth biweight loss, which is approximately quadratic for small errors and less sensitive to larger errors.
  • Non-linear regression: On regression, GD and C-Alg. 3 converge more slowly than the other methods, while Alg. 3 is faster than RAGD but slower than NCG.C-Alg. 3 stalls near saddle points when it detects negative curvature; enabling exploitation improves Alg. 3's speed.
  • Non-linear regression: Across regression instances, the methods found the best local minimum in similar fractions, despite sometimes reaching local minima with different function values.The experiment therefore found no significant difference in the ability to find good local minima in this ensemble.
  • Neural-network training: In the neural-network experiment, Alg. 3 never detects negative curvature and RAGD never restarts, suggesting the tested loss is effectively convex in large portions.The model has three fully connected hidden layers with 20, 10, and 5 units and is trained on MNIST.
  • Discussion: The authors conclude that the approach can augment AGD under negative curvature but remains less competitive with established methods such as nonlinear conjugate gradients.They identify adaptive choices for α, η, and L1 as needed for further improvement, and note that success may depend on AGD stalling in real applications.

A.1 Proof of Proposition 1

The proof establishes the monitored AGD proposition through an estimate-sequence argument adapted to avoid dependence on the global minimum. An induction maintains the required relations between the iterates and auxiliary points.

  • Proposition setup: The proposition analyzes iterates generated by AGD-until-proven-guilty under L-smoothness and a parameter σ satisfying 0 < σ ≤ L.The statement fixes an arbitrary comparison point w and imposes conditions across iterations.
  • Proof strategy: The proof follows Nesterov's estimate-sequence technique while replacing global-minimum arguments with inequalities that apply to potentially non-convex f.This adaptation is based on the cited proof of Theorem 3.18 in Bubeck (2014).
  • Inductive argument: The induction begins at s = 0 because x0 = y0 is the global minimizer of Φ0.Subsequent steps use the update definition, the induction hypothesis, and the smoothness-related assumption.
  • Proof completion: After the induction is completed, the remaining argument proceeds identically to the cited estimate-sequence proof.The text presents the continuation for completeness.
  • Inductive argument: The proof derives the relation vs − xs = √κ(xs − ys), which yields the proposition's target relation and is maintained inductively.The derivation combines the auxiliary definitions, the induction hypothesis, and the definitions of ys+1 and xs+1.

B.1 Proof of Lemma 5

The proof of Lemma 5 reduces third-order smoothness to a one-dimensional Taylor comparison and shows that one of two asymmetric endpoint steps achieves the required decrease. The construction then maps these steps back to the original function.

  • Auxiliary one-dimensional lemma: The proof begins with a normalized one-dimensional lemma for a thrice-differentiable function whose third derivative is Lipschitz.The auxiliary parameter ρ and the cubic approximation control the comparison between the function and its Taylor model.
  • Auxiliary one-dimensional lemma: Lipschitz third derivatives bound the Taylor approximation error by a term proportional to the fourth power of the scalar displacement.The proof also bounds the corresponding second-derivative approximation error before splitting into cases.
  • Case analysis: Depending on the sign condition involving the cubic term, either the left or right asymmetric step yields the required decrease bound.The two cases are represented by inequalities (35) and (36), whose disjunction implies the auxiliary result.
  • Application to Lemma 5: Exploit-NC-pair3 evaluates the two asymmetric endpoint candidates and returns the one with smaller function value, which satisfies the lemma's max-endpoint decrease guarantee.The candidates are f(v − ηδ) and f(u + η′δ).
  • Application to Lemma 5: For Lemma 5, the proof restricts f to the line through u and v and applies the auxiliary result with a normalized direction and ρ = 2η/||u − v||.The third derivative along the line is Lipschitz with a constant determined by L3 and ||u − v||.

B.2 Proof of Lemma 6

The proof of Lemma 6 combines third-order smoothness with bounds on AGD iterates to control the function value at a selected iterate. Under a step-size condition, the resulting error terms are bounded by the target decrease scale.

  • The proof applies a one-dimensional lemma for functions whose third derivative is Lipschitz continuous.
  • Lemma 6 assumes L1-smoothness, L3-Lipschitz continuous third derivatives, and τ² ≤ α/(16L3).
  • The selected iterate satisfies f(v) − f(y0) ≤ ατ²/3 + L3∥yj − yj−1∥⁴.
  • The iterate-distance bound ∥yj − yj−1∥ ≤ 2τ converts the fourth-order remainder into a term at most ατ².
  • The remaining proof analyzes the cases where the witness iterates are available and where the best iterate does or does not achieve the required decrease.

B.4 Proof of Theorem 2

Theorem 2 derives the third-order-smoothness complexity bound by combining the iteration count with the maximum cost of each AGD call. The proof then simplifies the resulting logarithmic and parameter-dependent expressions.

  • Theorem 2 studies an L1-smooth function with L3-Lipschitz continuous third-order derivatives and seeks ∥∇f(pK)∥ ≤ ϵ.
  • The total gradient-evaluation cost is bounded by 2KT, where K counts outer iterations and T bounds steps in each AGD-until-proven-guilty call.
  • The bound on K follows by telescoping the progress inequality and substituting the theorem’s choice of α.
  • The per-call bound T uses ψ(z) ≤ ∆f and substitutes the theorem’s choices of ε, L, σ, and α.
  • The proof uses ∆fL1ϵ−2 ≥ 8 to simplify the logarithmic factor before obtaining the final complexity bound.

C Adding a second-order guarantee

The second-order extension combines approximate eigenvector computation with negative-curvature steps and the gradient method. It preserves small-gradient convergence while adding a Hessian lower-bound guarantee.

  • Approx-Eig produces a negative-curvature direction unless the Hessian is nearly positive semidefinite, using Hessian-vector products.
  • A negative-curvature direction is converted into function decrease using a step whose size depends on the smoothness regime.
  • The combined method can run only a bounded number of negative-curvature iterations because each successful step makes function progress.
  • At termination, the method guarantees ∥∇f(ẑk)∥ ≤ ϵ and, with high probability, ∇²f(ẑk) ⪰ −αI.
  • The resulting complexity is O(ϵ−5/3 log d) under third-order smoothness and O(ϵ−7/4 log d) in the second-order setting.
  • The conceptual difference from earlier approaches is that the method finds negative-curvature directions through AGD’s non-convexity certificate rather than eigenvector search.

D.1 Implementation details

The implementation adapts smoothness estimates and algorithm parameters while adding practical negative-curvature checks. Experimental cost comparisons use steps as the common axis, although the methods require different numbers of oracle evaluations.

  • Semi-adaptive gradient steps: The semi-adaptive scheme doubles L1 when gradient steps fail, starting from an underestimate of the actual smoothness.
  • Algorithm 3: The practical implementation makes ϵ′, α, and σ depend on the previous gradient norm, removing dependence on the final target accuracy ϵ.
  • Algorithm 3: A convexity-violation check returns yt immediately and substantially increases negative-curvature detection in the first experiment.
  • Negative-curvature exploitation: Negative-curvature exploitation tests candidate pairs and evaluates points displaced along their normalized difference directions.
  • Comparison of computational cost: The figures use optimization steps on the x-axis, but Algorithm 3 requires twice as many gradient evaluations per step as the other algorithms.
  • Neural network training: The neural-network experiment uses average cross-entropy loss for 10-way prediction with a three-hidden-layer tanh network.
Loading 1705.02766v1…