PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds for Finding Stationary Points II: First-Order Methods

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

arXiv:1711.00841v1math.OC

TL;DR

The paper studies the complexity of finding approximate stationary points, using zero-respecting first-order algorithms and zero-chain constructions to establish lower bounds. It shows that deterministic first-order methods face near-matching lower bounds across smoothness classes, while convexity makes finding stationary points fundamentally easier, and it identifies gaps for tighter and randomized-algorithm lower bounds.

  • Problem

    The paper studies the complexity of finding approximate stationary points of smooth functions, including the contrast between convex and non-convex optimization.

  • Method

    The analysis uses zero-respecting first-order algorithms and zero-chain constructions to build and analyze lower-bound instances.

  • Results

    Deterministic first-order methods require at least ϵ^-8/5 iterations for arbitrarily smooth functions and ϵ^-12/7 when first and second derivatives are Lipschitz, while convexity makes the task fundamentally easier.

  • Takeaways & Limitations

    The results establish a strict separation between deterministic second-order and first-order methods and characterize first-order rates as near-optimal, though possibly slightly loose.

  • Takeaways & Limitations

    The lower bounds remain potentially loose relative to known upper bounds, and extending them to randomized algorithms is left as an open direction.

Abstract

from arXiv · show

We establish lower bounds on the complexity of finding $ε$-stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic first-order methods, even applied to arbitrarily smooth functions, cannot achieve convergence rates in $ε$ better than $ε^{-8/5}$, which is within $ε^{-1/15}\log\frac{1}ε$ of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove no deterministic first-order method can achieve convergence rates better than $ε^{-12/7}$, while $ε^{-2}$ is a lower bound for functions with only Lipschitz gradient. For convex functions with Lipschitz gradient, accelerated gradient descent achieves the rate $ε^{-1}\log\frac{1}ε$, showing that finding stationary points is easier given convexity.

1 Introduction

The paper studies dimension-free oracle lower bounds for finding ε-stationary points with first-order methods, contrasting these limits across smooth non-convex and convex settings. It asks how far ε-dependence can improve under increasingly strong Lipschitz-derivative assumptions.

  • 1 Introduction: The framework studies high-dimensional functions through function-value and gradient queries, with complexity measured by the first iterate that is ε-stationary.The paper also situates first-order methods as attractive because iterations are often inexpensive and dimension-free.
  • 1.1 Our contributions: Deterministic first-order methods require at least ε^-8/5 iterations on functions with Lipschitz derivatives through order p, and at least ε^-12/7 when p = 2.These lower bounds are described as almost tight relative to known first-order upper bounds.
  • 1.1 Our contributions: First-order methods cannot match Newton’s ε^-3/2 rate, and the ε^-5/3 log 1/ε rate requires Lipschitz third derivatives.With only Lipschitz Hessian, first-order methods require at least ε^-12/7 function values and gradients.
  • 1.1 Our contributions: For convex functions with bounded initial value and Lipschitz gradient, the optimal stationary-point rate is eΘ(√L1∆ε^-1), making the problem fundamentally easier.The introduction contrasts this convex result with non-convex lower bounds.
  • 1 Introduction: The analysis builds on Nesterov’s chain-structured worst function and augments it with a carefully chosen separable non-convex term.This construction is intended to strengthen the gradient lower bound for first-order methods.

2 A framework for lower bounds

The lower-bound framework reduces deterministic first-order analysis to structured zero-chain instances under orthogonal invariance. A resisting-oracle argument then transfers bounds from zero-respecting algorithms to all deterministic algorithms.

  • 2 A framework for lower bounds: The function classes impose Lipschitz derivative and bounded-initial-value conditions, include all dimensions, and are orthogonally invariant.These assumptions support dimension-free lower-bound constructions.
  • 2 A framework for lower bounds: The analyzed algorithms are deterministic first-order procedures whose iterates are measurable functions of prior queried values and gradients.The paper separately identifies the zero-respecting subclass used directly in the chain argument.
  • 2 A framework for lower bounds: The framework defines complexity as the first iterate that is ε-stationary and takes the worst case over functions, then the best case over algorithms.Table 1 summarizes this quantity for different oracle and function classes.
  • 2 A framework for lower bounds: A first-order zero-chain reveals derivative information one coordinate at a time, forcing zero-respecting algorithms to discover coordinates sequentially.Its defining support condition restricts the gradient to the current and previously revealed coordinates.
  • 2 A framework for lower bounds: Orthogonal invariance and a resisting oracle extend lower bounds for zero-respecting algorithms to all deterministic algorithms.The resisting oracle adversarially rotates the hard function while preserving membership in the function class.
  • 2 A framework for lower bounds: To prove a lower bound, construct a first-order zero-chain in the function class whose gradient remains larger than ε whenever the final coordinate is zero.After T iterations, the algorithm has not reached that coordinate, so every iterate remains non-stationary.

3 Lower bounds for finding stationary points of convex functions

The section establishes lower bounds for finding stationary points of smooth convex functions, using hard quadratic instances and zero-respecting first-order methods. It shows accelerated gradient descent is nearly optimal, while stationary-point finding is easier under convexity than in the non-convex setting.

  • 3.3 Lower bounds: Convex quadratic functions provide nearly sharp lower bounds for deterministic first-order methods, which extend immediately to broader smooth convex classes.The quadratic subclass is also identified with a restricted higher-order smoothness class.
  • 3.1 Function classes: For any deterministic zero-respecting algorithm and any requested iteration horizon, a suitable smooth convex quadratic can prevent even slight function-value improvement for arbitrarily long.This motivates focusing on stationarity rather than function-value suboptimality for these classes.
  • 3.2 The worst function in the convex world: The hard quadratic construction is a first-order zero-chain with Lipschitz gradient and a gradient bounded away from zero until the final coordinate is revealed.Its proof uses a path-Laplacian structure and a least-squares characterization of the smallest possible gradient.
  • 3.3 Lower bounds: Accelerated gradient descent attains O(√L1Dε^-1/2 log(L1D/ε)) for distance-bounded functions and O(√L1Δε^-1 log(L1Δ/ε^2)) for gap-bounded functions.These upper bounds match the corresponding lower bounds up to logarithmic factors.
  • 3.3 Lower bounds: Convexity makes finding stationary points fundamentally easier than finding them for smooth non-convex functions, even when the latter have higher-order smoothness or use higher-order methods.The section also notes that small gradients can matter for feasibility and residual certification despite being less typical in convex optimization.

4 Constructing the non-convex hard instance

The paper constructs a non-convex first-order zero-chain by augmenting a convex quadratic chain with separable non-convex terms. The added terms penalize slow transitions, producing a uniformly large gradient while preserving smoothness across derivative orders.

  • 4 Constructing the hard instance: The non-convex hard instance augments a convex zero-chain to strengthen the gradient lower bound while retaining controlled derivative smoothness.Its construction is designed specifically for first-order methods.
  • 4 Constructing the hard instance: The penalty Υr is chosen so its derivative is large away from 0 and 1, targeting the slowly varying vectors that minimize the quadratic chain’s gradient.This is the key mechanism behind the improved lower bound.
  • 4 Constructing the hard instance: For finite r, all derivatives of Υr are Lipschitz, while increasing r approaches a quartic limit and shows that smoothness beyond third order does not change the ε-dependence.The limiting quartic cannot be used directly because its first three derivatives are unbounded.
  • 4.1 Zero-chain property: The construction remains a first-order zero-chain, so first-order zero-respecting methods cannot access the final coordinates before enough iterations.It is deliberately not a second-order zero-chain, because Newton’s method has a faster ε^-3/2 rate.
  • 4.2 Large gradients: Lemma 3 obtains a gradient lower bound by splitting every transition from 1 to 0 into short and long cases: the quadratic chain handles short transitions, while Υr handles long ones.The two contributions intersect near m ≈ 1/√µ, yielding a gradient norm at least µ^3/4 up to constants.

5 Lower bounds for first-order methods

The scaling argument converts the non-convex zero-chain into hard instances in classes with Lipschitz derivatives through order p. This yields deterministic first-order lower bounds of ε^-12/7 for p=2 and ε^-8/5 for p≥3, nearly matching known upper bounds.

  • 5.2 Proof of Theorem 2: The hard function is scaled as f(x)=λσ^2 f̄T,µ,r(x/σ), with λ controlling gradient smoothness and σ controlling the gradient lower bound.Parameters are chosen simultaneously to enforce function-gap and derivative-Lipschitz constraints.
  • 5.3 Discussion: The lower bounds nearly match known deterministic upper bounds: the ε-dependent gaps are ε^-1/28 log(1/ε) for p=2 and ε^-1/15 log(1/ε) for p≥3.The comparison uses the previously proposed “convex until proven guilty” method.
  • 5.1 Distance-based bounds: Distance-based assumptions preserve the same ε-dependence, replacing the function gap with min_q∈[p] LqD^(q+1).Thus the theorem’s dependence on accuracy is unchanged under the distance-based formulation.
  • 5.2 Proof of Theorem 2: After T iterations, zero-respecting first-order iterates have unrevealed final coordinates and therefore retain gradient norm above ε.Observation 2 and Lemma 3 provide the zero-chain and gradient guarantees used in the reduction.

6 The challenge of strengthening Theorem 2

The paper identifies two unresolved challenges: closing the remaining gaps to known upper bounds and extending the non-convex first-order lower bounds to randomized algorithms. Its construction-based analysis explains why both extensions are difficult.

  • 6.1 Strengthening Theorem 2: For constructions of the current form, Lemma 5 finds points with gradient norm at most proportional to µ^3/4, limiting how much the lower bound can be strengthened.The limitation applies under explicit conditions on the linking and non-convex terms.
  • 6.1 Strengthening Theorem 2: Tightening the bounds appears to require constructions beyond the current additive linking form, although the transition-region proof offers sanity checks for alternatives.More general non-convex interactions remain possible in principle.
  • 6.2 Randomized algorithms: Extending the results to randomized first-order methods is unresolved because robust zero-chain techniques would also constrain higher-order algorithms, where faster rates are achievable.The authors relate the obstacle to the open problem of lower-bounding randomized optimization of convex quadratics.

7 Concluding remarks

The paper’s lower bounds clarify how smoothness, convexity, and derivative access govern stationary-point complexity, while leaving a polynomial gap for some first-order methods. The concluding discussion also identifies open extensions to finite-sum, stochastic, and second-order stationarity problems.

  • First-order methods vs. high-order methods: With Lipschitz higher derivatives, cubic-regularized Newton achieves ϵ^-3/2 under Lipschitz Hessians, whereas deterministic first-order methods cannot beat ϵ^-8/5.This establishes a strict separation between deterministic second-order and first-order methods.
  • The effect of high-order smoothness on first-order methods: First-order lower bounds are ϵ^-12/7 with Lipschitz gradient and Hessian, while known methods achieve ϵ^-5/3 log 1/ϵ with Lipschitz third derivatives.Thus, the optimal first-order rates differ between second- and third-order smoothness assumptions.
  • The effect of high-order smoothness on first-order methods: For all smoothness orders p ≥3, the lower bound remains ϵ^-8/5, because the hard instance approaches a quartic polynomial as its construction parameter grows.Fourth-order smoothness cannot improve the dependence because of symmetries in the fourth-order Taylor expansion.
  • Convex vs. non-convex functions: Convexity makes stationary-point finding fundamentally easier: first-order methods achieve ϵ^-1 log 1/ϵ for bounded initial sub-optimality, unlike the non-convex ϵ^-8/5 lower bound.Convex analyses can exploit function gaps or distance to an optimum, rather than only function-progress arguments.
  • Further research: The lower bounds leave a polynomial ϵ-dependence gap from the best known first-order upper bounds, and lower bounds for finite-sum, stochastic, and second-order stationarity remain open directions.The paper also notes dimension dependence for randomized methods targeting second-order stationarity.

A.1 An upper bound for finding stationary points of value-bounded functions

This section presents a proximal accelerated-gradient method for finding stationary points of value-bounded functions, then proves its complexity using a resisting quadratic-chain instance.

  • A.1 An upper bound for finding stationary points of value-bounded functions: The method applies Nesterov’s accelerated gradient descent to f plus a standard quadratic regularizer.The regularized objective is made strongly convex, enabling the use of accelerated gradient descent for strongly convex functions.
  • A.1 An upper bound for finding stationary points of value-bounded functions: For convex functions with Lipschitz gradient, a suitable proximal parameter yields the desired accelerated upper bound.The construction chooses σ as a function of ε and Δ before applying the strongly convex accelerated-gradient guarantee.
  • A.1 An upper bound for finding stationary points of value-bounded functions: The lower-bound construction uses a first-order zero-chain so that iterates cannot reveal the final coordinate within the prescribed query budget.The hard instance is scaled to have Lipschitz gradient and bounded initial suboptimality while preserving the zero-chain property.
  • A.1 An upper bound for finding stationary points of value-bounded functions: If the final coordinate remains zero, the construction ensures the queried point is still more than ε above the global minimum.An inductive chain of coordinate bounds shows that near-optimality would require nonzero coordinates through the chain.

B.1 Proof of Lemma 2

This proof establishes derivative and shape properties of the auxiliary function Υr, using explicit compositions and higher-order chain-rule bounds.

  • B.1 Proof of Lemma 2: Υr is nonnegative, minimized at x = 1, and bounded at the origin by 10.These properties provide the basic shape and magnitude controls used in the hard-instance analysis.
  • B.1 Proof of Lemma 2: For every r ≥ 1 and p ≥ 1, the p-th derivatives of Υr are Lipschitz with a bound that scales as r^(3-p) times a p-dependent factor.The p-dependent factor includes exponential dependence on p log p and p.
  • B.1 Proof of Lemma 2: The derivative of Υr is sufficiently negative on part of the transition range to contribute a uniform gradient signal there.The proof records |Υ′r(x)| > 1 for x in specified subintervals.
  • B.1 Proof of Lemma 2: The derivatives of Υr are bounded by analyzing the component functions ϕ1 and ϕ2 through composition and Faà di Bruno’s formula.The proof controls partition counts and derivative factors to obtain explicit higher-order bounds.

B.2 Proof of Lemma 3

This proof defines a transition region in the quadratic chain and uses its structure to lower-bound the gradient norm for every admissible sequence.

  • B.2 Proof of Lemma 3: The quadratic-chain contribution and the non-convex Υr contribution are combined after minimizing over interior coordinates to lower-bound the gradient norm.The argument uses a quadratic-form reduction involving a matrix A and a unit-norm null vector z.
  • B.2 Proof of Lemma 3: The transition region Itrans is the index interval between the last coordinate above 0.9 and the first subsequent coordinate below 0.1, augmented with a decreasing tail.Its length is m = i2 − i1, and the construction distinguishes a head, a tail, and a rapidly decreasing portion.
  • B.2 Proof of Lemma 3: Figure 3 visualizes the transition region by coloring its entries blue in vectors whose last two coordinates are zero.The illustration corresponds directly to the index interval defined in equation (27).
  • B.2 Proof of Lemma 3: The two gradient lower bounds intersect at m approximately 1/√µ, yielding a gradient norm at least µ^3/4.A direct computation of the remaining factor gives ζ(t) approximately 0.28, exceeding 1/4.
  • B.2 Proof of Lemma 3: The transition-region properties guarantee many indices with a sufficiently negative Υ′r contribution.The proof obtains N ≥ (m − 1/α) / 2 such indices.

B.3 Proof of Theorem 3

This proof extends the hard-instance construction by subtracting a scaled bump function, preserving smoothness and zero-chain behavior while controlling global minimizers.

  • B.3 Proof of Theorem 3: Theorem 3 establishes a lower bound for first-order methods on functions whose derivatives through order p have prescribed Lipschitz constants.The theorem applies for integer p ≥ 2 and positive D, L1, …, Lp, and ε.
  • B.3 Proof of Theorem 3: The hard instance is f(x) = λσ2 f̄T,µ,r(x1/σ, …, xT+1/σ) − λ̃h̄T+2(x/D), combining the original chain with a scaled bump.The bump plants a nearby global minimum while remaining essentially invisible to zero-respecting methods.
  • B.3 Proof of Theorem 3: The combined function has Lq-Lipschitz qth-order derivatives for every q ∈ [p].Each component is assigned half the target smoothness budget, so their sum satisfies the desired Lq bound.
  • B.3 Proof of Theorem 3: The bump preserves the zero-chain structure, so algorithms in the considered first-order class cannot activate the final coordinate within the hard-instance query horizon.The bump vanishes near points with final coordinate zero, leaving the relevant iterates constrained in that coordinate.
  • B.3 Proof of Theorem 3: The construction ensures every global minimizer has norm at most D by using the bump’s support and value properties.The proof combines the bump lower bound with the hard-instance objective to derive the norm constraint.

B.4 Proof of Lemma 5

Lemma 5 constructs a vector x with terminal coordinates x_T = x_{T+1} = 0 under stated assumptions on Λ and eΥ. The proof uses a piecewise construction whose entries lie in [0,1] and vanish after an index bounded by 2⌈T/3⌉+1.

  • The lemma asserts existence of x ∈ R^(T+1) satisfying x_T = x_{T+1} = 0 under the stated parameter and derivative assumptions.The assumptions include Λ′(0) = eΥ′(0) = 0, 1-Lipschitz continuity of Λ′, and a uniform bound G on eΥ′ over [0,1].
  • The proof defines x piecewise, starting with x_1 = 1 and selecting an index parameter m to control where the sequence reaches zero.The construction specifies x_0 := 1 and uses a piecewise pattern for later coordinates.
  • Every constructed coordinate lies in [0,1], and x_n = 0 for all n > 2m + 1.These properties allow the terminal-coordinate claim once 2m + 1 is shown to be smaller than T.
  • For T ≥ 8, the condition µ ≥ T^-2 yields 2m + 1 ≤ 2⌈T/3⌉ + 1 < T, so x_T and x_{T+1} vanish.The proof handles T ≤ 8 separately using µ ≥ 1/64 and the choice x = 0.
Loading 1711.00841v1…