Source-linked AI summary
Lower Bounds for Finding Stationary Points I
Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford
TL;DR
The paper asks how difficult it is to find ε-stationary points of smooth, high-dimensional, potentially non-convex functions under a full-derivative oracle. It constructs hard functions and proves lower bounds for randomized algorithms, showing rates that match known upper bounds up to constants while identifying scope limits for higher-order first-order methods.
Problem
The paper addresses the lack of tight, dimension-free complexity limits for finding ε-stationary points of smooth, potentially non-convex functions.
Method
The authors construct high-dimensional hard instances with Lipschitz pth derivatives and analyze algorithms accessing function values and all derivatives through oracle queries.
Results
The lower bound scales as ε^-(p+1)/p queries and matches known upper bounds up to constants, establishing optimality for gradient descent, cubic-regularized Newton, and generalized pth-order regularization.
Takeaways & Limitations
The results characterize optimal dimension-free rates for ε-stationarity under the full-derivative oracle model and natural smoothness classes.
Takeaways & Limitations
The results say little about first-order methods on functions with higher-order Lipschitz derivatives, and higher-order methods can be impractical in large-scale settings.
Abstract
from arXiv · showhide
We prove lower bounds on the complexity of finding $ε$-stationary points (points $x$ such that $\|\nabla f(x)\| \le ε$) of smooth, high-dimensional, and potentially non-convex functions $f$. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of $f$ at a query point $x$. We show that for any (potentially randomized) algorithm $\mathsf{A}$, there exists a function $f$ with Lipschitz $p$th order derivatives such that $\mathsf{A}$ requires at least $ε^{-(p+1)/p}$ queries to find an $ε$-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton's method, and generalized $p$th order regularization are worst-case optimal within their natural function classes.
1 Introduction
The paper studies dimension-free lower bounds for finding ε-stationary points of smooth, potentially non-convex functions. Its bounds match known upper rates up to constants and establish optimality for several methods, while leaving higher-order first-order methods to companion work.
- Research focus: Oracle complexity counts function and derivative evaluations required to find a point satisfying the ε-stationarity condition.The oracle model may provide function values and derivatives at queried points.
- Known rates: Known methods achieve ε^-(p+1)/p iteration rates: gradient descent for p=1, cubic-regularized Newton for p=2, and pth-order regularization generally.Higher-order methods can improve ε dependence but may have expensive iterations in high dimensions.
- Research focus: The paper asks for dimension-free complexity lower bounds for finding ε-stationary points of smooth, potentially non-convex functions.An ε-stationary point has gradient norm at most ε.
- Motivation: Globally finding ε-suboptimal points for smooth non-convex functions has complexity scaling at least as (1/ε)^(d/p), ruling out dimension-free near-optimality guarantees.The paper therefore studies stationarity rather than global near-optimality.
- Main contribution: The main result gives randomized-algorithm lower bounds for functions with Lipschitz pth derivatives, with the hard domain dimension polynomial in 1/ε.The oracle returns the function value, gradient, Hessian, and all higher-order derivatives.
- Main contribution: For every p, the lower bound matches known upper bounds up to constants, making gradient descent, cubic-regularized Newton, and pth-order Taylor methods worst-case optimal in their natural classes.The paper notes that its results say little about first-order methods on functions with higher-order Lipschitz derivatives.
2 Preliminaries
The preliminaries define the smooth function classes, derivative-based deterministic and randomized algorithm classes, zero-respecting structure, and oracle-query complexity used in the lower-bound analysis.
- Function classes: The paper studies function classes with Lipschitzian derivative regularity and bounded initial function-value suboptimality.The classes include C∞ functions over finite-dimensional spaces, with dimension allowed to vary.
- Function classes: The function classes are orthogonally invariant, preserving initial suboptimality and derivative Lipschitz constants under orthogonal transformations.This invariance supports rotated hard-instance constructions.
- Algorithm classes: Each iterate is treated as a query to an information oracle, whose returned derivative order determines the algorithm's information model.For p=∞, the oracle reveals all derivatives at the query point.
- Algorithm classes: Deterministic algorithms generate iterates through measurable mappings of the available derivative information, while randomized algorithms are distributions over such deterministic procedures.Randomized algorithms draw randomness independently of the function.
- Algorithm classes: Zero-respecting algorithms never explore coordinates whose function derivatives have remained zero; common gradient, Newton, quasi-Newton, and trust-region methods satisfy this property when initialized at the origin.This structural restriction is central to the lower-bound strategy.
- Complexity measures: Complexity is the number of iterations, equivalently oracle queries, needed to reach a point with gradient norm at most ε.The framework evaluates the best worst-case performance over an algorithm class and a function class.
- Complexity measures: The paper proves that the ε^-(p+1)/p rates are sharp up to constants, using lower bounds that apply to deterministic and randomized algorithms.Randomized lower bounds use distributional complexity and a shared hard-function vulnerability.
3 Anatomy of a lower bound
The paper abstracts the zero-chain and resisting-oracle techniques into a general framework for proving lower bounds, including for high-order methods and non-convex optimization. Zero-chains restrict how quickly zero-respecting algorithms discover coordinates, while orthogonal transformations extend the resulting bounds to deterministic and randomized algorithms under different constructions.
- Zero-chains: Zero-chains generalize Nesterov’s chain-like quadratic structure to higher-order derivatives and broader optimization goals.They are designed to support lower bounds for high-order methods, non-convex functions, ε-stationarity, and ε-optimality.
- Zero-chains: A zero-chain appears locally constant in undiscovered coordinates, so zero-respecting iterates acquire derivative information only progressively.For the classical chain, querying points with trailing zero coordinates reveals at most one new coordinate; Observation 1 formalizes the corresponding support restriction.
- Lower-bound strategy: A function with large gradient whenever its final coordinate is zero yields a query lower bound once it is scaled to meet the function-class and termination conditions.The construction chooses the chain length, multiplier, and scale so that the lower-bound dimension grows as ε decreases.
- Deterministic reduction: Orthogonal invariance and resisting-oracle rotations convert lower bounds for zero-respecting algorithms into bounds for deterministic algorithms.The adversary constructs an orthogonal transformation so the algorithm’s rotated iterates behave as a zero-respecting sequence; the dimensional variant uses dimension d+T.
- Randomized reduction: The reduction applies broadly to complexity measures such as ε-optimality and second-order stationarity, but its adversarial simulation does not directly handle randomized algorithms.Randomized algorithms instead use robust zero-chains, a uniformly random orthogonal rotation, and an approximate information-discovery argument under bounded iterates.
4 Lower bounds for zero-respecting and deterministic algorithms
The paper constructs a smooth hard instance whose zero-chain structure delays progress through coordinates, then uses its large-gradient property to establish deterministic lower bounds. The resulting lower bound matches pth-order regularization rates up to polynomial factors in p and transfers from zero-respecting to all deterministic algorithms.
- Hard-instance structure: The hard instance is a zero-chain, so zero-respecting methods cannot make the Tth coordinate nonzero before T + 1 iterations.Its robust zero-chain property follows from local independence when consecutive coordinates are small.
- Hard-instance structure: If any coordinate among the first T has magnitude below 1, the construction guarantees a large gradient in an earlier coordinate.This large-gradient property prevents stationary points until the coordinate sequence has sufficiently progressed.
- Smoothness properties: The functions Ψ and Φ are infinitely differentiable with bounded nonnegative functions and derivatives, while the resulting hard instance has Lipschitz pth-order derivatives.The pth-derivative Lipschitz constant is bounded through the smoothness properties established for the construction.
- Lower-bound theorem: Theorem 1 gives a deterministic lower bound for pth-order smooth functions, even with access to all derivatives, and Proposition 1 transfers the zero-respecting bound to all deterministic algorithms.The hard function can be embedded through an orthogonal transformation, with dimension sufficient to establish the lower bound.
- Lower-bound theorem: The lower bound matches known pth-order regularization upper bounds up to a factor polynomial in p, so only the first p derivatives are needed for minimax-optimal scaling.This comparison applies despite the lower-bound oracle exposing derivatives of every order.
- Lower-bound construction: The construction's smoothness, boundedness, and gradient properties allow an appropriately scaled version to belong to Fp(∆, Lp) while keeping gradients above ε for T iterations.The scaling choice σ = (ℓpε/Lp)^(1/p) ensures the gradient lower bound and the required pth-order smoothness.
5 Lower bounds for randomized algorithms
The randomized lower-bound construction uses random rotations, bounded iterates, and concentration to hide undiscovered directions from any all-derivatives oracle algorithm. It yields lower bounds for broad randomized algorithms under smoothness and dimension conditions.
- Randomized construction: Random orthogonal rotations make undiscovered directions statistically hidden from randomized iterates, so information beyond the revealed coordinates is effectively a shot in the dark.The proof combines sequential conditioning, rotational symmetry, and concentration of measure.
- Bounded iterates: A smooth projection forces queried points into a bounded ball, preventing unbounded iterates from escaping the hard instance’s dead zone.A quadratic term additionally gives large gradients beyond a certain norm.
- Regularity: The constructed hard functions have Lipschitz pth-order derivatives, with smoothness constants bounded by exp(c p log p + c).The required regularity is established in Lemma 6, whose proof is deferred to an appendix.
- Final lower bound: Theorem 2 extends the lower bound to all randomized algorithms with access to all derivatives, while restricting the domain dimension to 1 + c2q.The theorem’s quantitative query bound is stated in the supplied theorem passages, with the scaling completed in the surrounding proof.
- Final lower bound: A randomized procedure generates hard instances without knowing the algorithm, and the proof establishes the theorem for probability levels δ ≥ 1/2.The construction is distributional and succeeds with high probability.
6 Distance-based lower bounds
The paper extends its stationary-point lower bounds to functions whose global minima lie within a bounded distance of the origin. Non-convexity permits nearby minima that remain difficult to locate through local access.
- Function class: The distance-based class restricts global minima to lie within distance D of the origin while maintaining Lp-Lipschitz pth-order derivatives.The class is defined using smooth C∞ functions and a positive smoothness parameter Lp.
- Distance-based lower bounds: Distance-bounded non-convex functions receive a lower bound with the same ϵ dependence as the value-gap class.The section contrasts this with convex optimization, where distance-bounded functions can have better ϵ dependence.
- Interpretation: Non-convexity allows global minima to be hidden close to the origin, making them difficult to find using local function access.This explains why a distance restriction does not yield the same improvement seen in convex optimization.
- Construction: A lower-dimensional construction suffices for the deterministic distance-based lower bound.The section explicitly notes this parallels the deterministic construction used for the earlier theorem.
- Relation to value-gap bounds: For Lipschitz-gradient functions, bounded distance to a global minimizer implies a bounded function gap, embedding the distance-based class into the value-gap class.The supplied passages give the relation ∆ := 1/2 L1D^2.
7 Conclusion
The paper establishes algorithm-independent, tight dimension-free lower bounds for finding stationary points with all-derivatives oracles. It characterizes optimal ϵ-stationarity rates while identifying high-order methods’ impracticality as an unresolved scope boundary.
- Conclusion: This work provides the first algorithm-independent and tight lower bounds on the dimension-free complexity of finding stationary points.The result applies to smooth, high-dimensional settings with an oracle returning all derivatives.
- Conclusion: The lower bounds characterize optimal convergence rates to ϵ-stationarity under the high-dimensional, all-derivatives-oracle assumption.The conclusion frames this as the main consequence of the paper’s results.
- Scope and continuation: High-order algorithms, including second-order methods, may be impractical at large scale, motivating sharper lower bounds for restricted first-order methods in the companion work.The companion paper addresses the incomplete picture for practical high-dimensional optimization.
A Proof of Propositions 1 and 2
The proof reduces arbitrary algorithms to zero-respecting ones under an appropriate orthogonal rotation, then constructs the rotation inductively so each iterate reveals only a controlled support.
- Transfer of hardness: If an algorithm needs at least T0 iterations on the zero-respecting problem, the rotated instance forces the same iteration count for the original algorithm.The argument uses equality of the initial iterates and invariance of gradient norms under orthogonal transformations.
- Simulator construction: A zero-respecting simulator maintains a support set and orthonormal vectors, producing iterates that match the original algorithm under a suitable rotation.The simulator’s first T0 iterates are identical to the rotated algorithm’s iterates.
- Inductive construction: The rotation is built inductively by choosing new orthonormal directions orthogonal to all past iterates, preserving the required support containment.The available orthogonal complement is shown to contain enough vectors for the induction.
- Reduction to zero-respecting algorithms: The construction uses orthogonal invariance to rotate any function while preserving the function class and the stationarity norm.This reduction transfers lower bounds for zero-respecting algorithms to general algorithms.
- Randomized extension: The randomized extension uses rotations in a larger dimension, with the rotated functions defined as fU(x) = f(U⊤x).The construction places the original function in a dimension enlarged by T.
B.1 Proof of Lemma 1
The proof establishes derivative bounds for the auxiliary functions Ψ and Φ, showing that both are infinitely differentiable with controlled, nonnegative, bounded derivatives.
- Derivative bounds: Ψ and Φ are infinitely differentiable, and their derivatives admit bounds for every order k.The proof obtains these bounds by induction and estimates Gaussian-weighted terms after a change of variables.
- Basic properties: The functions and derivatives Ψ, Ψ′, Φ, and Φ′ are non-negative and bounded.These properties provide the basic regularity and boundedness conditions needed for the constructed functions.
- Inductive proof: The induction begins with explicit first-derivative formulas and extends the bounds from order k to order k + 1.The recursive estimates control coefficients and polynomial factors appearing in higher derivatives.
B.2 Proof of Lemma 3
The proof bounds the derivatives of the one-dimensional zero-chain function ¯fT by exploiting locality, directional projections, and derivative estimates for its building blocks.
- Auxiliary-function estimates: The auxiliary functions Ψ and Φ supply the derivative estimates used in the bound for ¯fT.The proof invokes their smoothness and bounded derivative properties from the preceding lemma.
- Smoothness bound: The p-th order derivatives of ¯fT are ℓp-Lipschitz continuous, with ℓp bounded by an exponential in p log p.The proof defines ℓp using the derivative estimates and obtains ℓp ≤ exp(2.5p log p + 5p + 10).
- Locality structure: A (p + 1)-fold derivative of ¯fT is nonzero only when all involved indices differ pairwise by at most one.This locality lets the derivative sum be rearranged into products involving neighboring coordinates.
- Directional control: Directional derivative terms are bounded using that v is a unit vector and neighboring-coordinate products remain at most one.These estimates control every summand in the directional derivative expansion.
B.3 Proof of Lemma 4
The proof shows that random orthogonal embeddings preserve the zero-chain’s hidden-coordinate structure with high probability, using projection geometry and rotational invariance.
- Dimension requirement: The construction assumes bounded iterates and sufficiently large dimension, including d ≥ 52TR^2 log 2T^2 in the stated condition.The dimension requirement supports the probabilistic projection argument.
- Good-event geometry: With probability at least 1 − δ, the iterates have inner products below 1/2 with all unrevealed directions across every time step.Lemma 4a derives this from the good events G≤t and the projection inequalities.
- Information restriction: Before time i, the iterate x(i) depends on the random orthogonal matrix only through its first i − 1 columns.The robust zero-chain property recursively limits which directions can influence the derivatives and iterates.
- Rotational invariance: Conditioned on earlier columns and the good event, each later embedded direction’s projected component is uniformly distributed on the relevant orthogonal subspace.Rotational invariance establishes the conditional distribution despite conditioning on the preceding iterates.
- Concentration: The relevant projection subspace has dimension at least d − 2(t − 1), enabling concentration bounds for inner products with uniformly random unit vectors.This dimension estimate is combined with spherical concentration to control failure probabilities.
B.4 Proof of Lemma 6
The proof establishes smoothness and bounded function gap for the transformed construction ˆfT;U by combining chain-rule derivative estimates with properties of the base function and the radial map.
- Smoothness bound: The p-th order derivatives of ˆfT;U are ˆℓp-Lipschitz continuous, with ˆℓp bounded by exp(cp log p + c).Faà di Bruno’s formula and partition-counting bounds control the derivatives of the composition.
- Function gap: The transformed function preserves the base function’s value at the origin and has function gap at most 12T.The proof uses ˆfT;U(0) = ¯fT(0), the pointwise lower bound, and Lemma 3.i.
- Construction: The radial map ρ and the quadratic regularizer define the transformed construction used in the smoothness analysis.The quadratic term contributes a 1/5-Lipschitz first derivative and zero higher-order derivatives.
- Chain-rule expansion: The derivative calculation expands composition derivatives over partitions of the index set using Faà di Bruno’s formula.Bell-number bounds control the number of partitions, while the radial-map derivatives provide the remaining factors.
C Proof of Theorem 3
The proof constructs a localized negative bump near the origin whose exponentially small volume makes it difficult to discover locally, then establishes the smoothness properties needed for the lower bound.
- Bump construction: The proof introduces a negative bump designed to be difficult to find while remaining close to the origin.The construction uses the bump function h̄T: R^T → R.
- Bump construction: The bump has a unit-height peak centered at 4/5e(T) and vanishes when points are more than distance 1 from that peak.Its support is therefore localized around a specific point in R^T.
- Bump construction: The bump’s peak volume vanishes exponentially with T, making local queries unlikely to find it.This property is identified as necessary for the subsequent lower-bound analysis.
- Smoothness analysis: For every p ≥ 1, the bump has Lipschitz pth-order derivatives with constant bounded by e^(3p log p + cp).Lemma 10 supplies the smoothness property used in the theorem proof.
- Smoothness analysis: The smoothness proof analyzes one-dimensional directional projections and applies Faà di Bruno’s formula to bound higher derivatives.The argument reduces the required derivative bound to directional derivatives along unit vectors.
C.2 Proof of Theorem 3
The theorem embeds the localized bump into a randomized, rotated hard instance with controlled smoothness and shows that algorithms fail to find a sufficiently small gradient within T iterations with high probability.
- Hard-instance construction: The hard instance fU is indexed by a uniformly random orthogonal matrix U and constructed from the randomized bump-based function.Its pth-order derivative Lipschitz constant is Lp, with the construction using ℓ′p = ĥℓp + h̃ℓp.
- Query lower bound: When the hidden bump is absent near each query, its gradient contribution vanishes, while the constructed function retains gradient norm greater than 1/2 before scaling.This prevents the iterates from being ε-stationary for the selected scaling.
- Hard-instance construction: The construction belongs to the constrained function class when σ ≤ D, after ensuring that its global minimizers have norm at most D.The proof checks the minimizer norm using the bump’s properties and the underlying randomized construction.
- Query lower bound: For iterates generated through T steps, a random-rotation argument keeps the final hidden direction nearly orthogonal to the queried points with high probability.The proof tracks the events G≤t and bounds the directional inner products by 1/2.
- Query lower bound: The resulting lower bound is obtained after choosing σ appropriately, while the σ > D regime is vacuous because every method requires at least one step.The proof explicitly separates the nontrivial σ ≤ D case from this boundary regime.