PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower Bounds for Non-Convex Stochastic Optimization

Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, Blake Woodworth

arXiv:1912.02365v2math.OCcs.ITcs.LGstat.ML

TL;DR

The paper studies fundamental performance limits for stochastic first-order methods on non-convex optimization problems. It constructs worst-case instances and proves ε^-4 and ε^-3 lower bounds in bounded-variance and mean-squared-smooth settings, respectively, matching SGD and recent variance-reduction rates.

  • Problem

    The paper asks what complexity guarantees are fundamentally possible for stochastic-gradient methods on smooth, potentially non-convex problems.

  • Method

    The paper constructs distributions over stochastic first-order instances and proves query lower bounds for randomized algorithms, including settings with function-gradient oracles and batch queries.

  • Results

    The lower bounds are ε^-4 under bounded variance and ε^-3 under mean-squared smoothness, matching the rates of SGD and recent variance-reduction schemes.

  • Takeaways & Limitations

    SGD is minimax optimal in the bounded-variance model, while SPIDER and SNVRG are optimal under mean-squared smoothness.

  • Takeaways & Limitations

    Whether ε^-3 complexity is achievable with a single query remains open in the mean-squared-smooth setting.

Abstract

from arXiv · show

We lower bound the complexity of finding $ε$-stationary points (with gradient norm at most $ε$) using stochastic first-order methods. In a well-studied model where algorithms access smooth, potentially non-convex functions through queries to an unbiased stochastic gradient oracle with bounded variance, we prove that (in the worst case) any algorithm requires at least $ε^{-4}$ queries to find an $ε$ stationary point. The lower bound is tight, and establishes that stochastic gradient descent is minimax optimal in this model. In a more restrictive model where the noisy gradient estimates satisfy a mean-squared smoothness property, we prove a lower bound of $ε^{-3}$ queries, establishing the optimality of recently proposed variance reduction techniques.

1 Introduction

The paper studies fundamental limits for finding ε-stationary points in smooth, potentially non-convex stochastic optimization. It formalizes the stochastic-gradient oracle setting and relates existing SGD rates to the lower-bound questions it addresses.

  • Finding approximate global minima or testing local minima and high-order saddles is intractable in general non-convex optimization.
  • ε-approximate stationarity provides an alternative convergence criterion for non-convex optimization.
  • The oracle returns an unbiased stochastic gradient estimate while the objective has bounded initial suboptimality and L-Lipschitz gradients.
  • SGD finds an ε-stationary point using O(∆Lε^-2(1 + σ^2ε^-2)) oracle queries under these assumptions.In the regime ε ≤ σ, this becomes O(∆Lσ^2ε^-4).

1. The stochastic gradient g satisfies a mean-squared smoothness property

The paper establishes lower bounds for stochastic first-order methods under mean-squared smoothness and contrasts them with the bounded-variance setting. Its constructions explain why the ε^-4 and ε^-3 rates arise and extend to broad algorithm and oracle classes.

  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: Both lower bounds hold for any number K of simultaneous queries, with dimension depending polynomially on K and ε^-1.
  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: Under mean-squared smoothness, SPIDER and SNVRG with K = 2 queries achieve O(∆L̄σε^-3 + σ^2ε^-2), while the paper settles further improvement questions negatively.
  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: The proof handles arbitrary randomized algorithms through random rotations and extends to gradient-of-function, statistical-learning, and active-oracle settings.
  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: The lower bounds match SGD’s ε^-4 rate without mean-squared smoothness and match variance-reduction methods’ ε^-3 rate with it.
  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: The bounded-variance lower bound amplifies a noiseless coordinate-progress bound by revealing relevant coordinates only with probability p = Θ(ε^2/σ^2).The resulting factor 1/p = Θ(σ^2ε^-2) yields the ε^-4 lower bound.
  • 1. The stochastic gradient g satisfies a mean-squared smoothness property: The constructions are high-dimensional, with the required dimension depending on the number of simultaneous queries and the progress probability.The authors note that polynomial dependence on ε^-1 is common in high-dimensional lower-bound constructions.

2 Setup

The setup defines stochastic first-order optimization through batch oracle interactions with smooth functions and specifies bounded-variance and mean-squared-smooth oracle classes. Complexity is measured distributionally, yielding minimax lower bounds.

  • The task is to find an ε-stationary point of an unknown function through a stochastic first-order oracle.
  • The framework permits algorithms to observe exact function values for each query and explicitly tracks the dimension required by each lower-bound construction.
  • Each round allows a batch of K queries, and the oracle returns stochastic responses generated from its distribution over seeds.
  • When K = 1 the model is classical stochastic optimization, while K = 2 captures the query structure of SPIDER and SNVRG.
  • The bounded-variance oracle requires unbiased stochastic gradients with bounded variance, whereas the mean-squared-smooth class additionally imposes mean-squared smoothness.
  • Distributional lower bounds imply minimax lower bounds over the corresponding oracle and function classes.

3 Lower bounds for zero-respecting algorithms

The paper develops probabilistic zero-chain constructions to lower bound how quickly zero-respecting algorithms can activate relevant coordinates. These constructions yield tight lower bounds matching SGD in the bounded-variance setting and matching variance-reduction rates under mean-squared smoothness.

  • Zero-respecting algorithms: Zero-respecting algorithms restrict each query’s support to coordinates appearing in previous oracle responses.This class generalizes the linear span assumption and includes many standard optimization algorithms.
  • Zero-chain construction: A first-order zero-chain lets each noiseless query reveal at most one new coordinate, while an ε-stationary point requires progress across many coordinates.The construction uses Carmon et al.’s function, whose gradient remains large until sufficient coordinate progress occurs.
  • Probabilistic zero-chains: Probabilistic zero-chains make each coordinate activation occur with probability at most p, forcing zero-respecting algorithms to wait Ω(T/p) rounds to achieve high coordinate progress.The increment in progress is either 0 or 1, with conditional probability at most p for an increment of 1.
  • Bounded-variance setting: The stochastic estimator g_T is unbiased, forms a probability-p zero-chain, and has bounded variance in the bounded-variance construction.The construction’s central technical challenge is keeping variance bounded independently of dimension T.
  • Bounded-variance setting: The resulting ε^-4 lower bound matches SGD’s convergence rate up to constants, establishing SGD’s optimality in the bounded-variance model.The lower bound also remains unchanged by additional batch queries, although general algorithms require sufficiently large dimension in the full argument.
  • Mean-squared smooth setting: Under mean-squared smoothness, the construction yields an ε^-3 lower bound matching the upper bounds of SPIDER and SNVRG up to constants.The stochastic estimator in this construction is again unbiased and a probability-p zero-chain.

4 Lower bounds for randomized algorithms

The paper extends its lower-bound construction from zero-respecting methods to arbitrary randomized algorithms by combining probabilistic zero-chains with random rotations, high dimension, and soft projection. The resulting constructions establish the main minimax lower bounds under bounded-variance and mean-squared-smoothness assumptions.

  • Main result: Theorem 3 provides optimal lower bounds for arbitrary, potentially randomized algorithms in both bounded-variance and mean-squared-smooth settings.The theorem realizes the corresponding lower bounds with high-dimensional constructions.
  • Randomized lower-bound construction: Random rotations make arbitrary algorithms behave essentially like zero-respecting algorithms in the hidden coordinate system.For sufficiently large dimension, significantly nonzero rotated coordinates must lie in the support of previous oracle responses.
  • Randomized lower-bound construction: Lemma 5 bounds progress for norm-bounded randomized algorithms with dimension d ≥ ⌈18R^2KT/(pδ)⌉.With probability at least 1 − δ, progress remains below T through the stated number of queries.
  • Final hard instance: Soft projection handles unbounded iterates while regularization prevents algorithms from reducing the gradient merely by increasing their norm.The construction combines bounded-query progress control with a norm-dependent term that preserves gradient hardness.
  • Verification: The final rotated and projected instances satisfy the required smoothness and boundedness properties.Lemma 7 establishes Lipschitz-continuity bounds for the hard function and its derivatives.

5 Extensions

The paper shows that its lower bounds persist for statistical-learning-type gradient oracles and active finite-sum oracles. These extensions preserve the same hardness while exposing open questions about oracle structure and seed-space size.

  • 5.1 Statistical learning oracles: Gradient estimators of the form g(x,z) = ∇_x f(x,z) do not improve worst-case stochastic optimization complexity.The construction makes F(x) = E[f(x,z)] while preserving the zero-chain, unbiasedness, and smoothness properties needed for the lower bound.
  • 5.1 Statistical learning oracles: Theorem 3 continues to hold for statistical-learning-type stochastic gradient functions.This includes gradient estimators arising in empirical-risk-minimization settings.
  • 5.2 Active oracles: Random permutations preserve unbiasedness and the variance bound while yielding an analogous progress limitation for active-oracle queries.The algorithm’s previous queries reveal little information about the next coordinate bit, limiting progress.
  • 5.2 Active oracles: The active-oracle lower bound uses a distribution over oracles rather than a single fixed oracle.Accordingly, the complexity measure takes a supremum over oracle distributions and expectation over the sampled oracle.
  • 5.2 Active oracles: The ε^-4 lower bound extends to active oracles, including finite-sum settings with finite seed space and uniform seed distribution.The active construction uses independent randomness across chain coordinates to prevent repeated queries to one informative seed from bypassing the lower bound.
  • Open limitations: The constructed seed space is super-exponential in 1/ε, and reducing its cardinality remains an open problem.Because N scales as σ^2/ε^2 and T is polynomial in 1/ε, |Z| = NT is super-exponential in 1/ε.

6 Discussion

The discussion summarizes tight lower bounds for stochastic first-order methods and identifies unresolved boundaries involving single-query variance reduction, stronger oracle assumptions, and higher-order optimization.

  • 6 Discussion: The paper establishes tight stochastic first-order lower bounds for finding stationary points with and without mean-squared smoothness.It presents these constructions as a basis for future work in non-convex stochastic optimization.
  • Open questions: Whether mean-squared-smooth oracles admit ε^-3 complexity with K = 1 remains open.Known optimal O(ε^-3) methods require K = 2 simultaneous queries, while SGD achieves O(ε^-4) with one query.
  • Open questions: The importance of stronger assumptions such as almost-sure smoothness or almost-sure bounded gradient error remains unresolved.The paper notes that no known algorithms leverage these assumptions and that extending the lower bounds to them is non-trivial.
  • Open questions: The results do not address higher-order stochastic algorithms or second-order stationary points.Tight lower bounds in those settings may require dedicated treatments despite possible extensions of the techniques.

A.1 Basic technical results

The appendix develops technical lower-bound ingredients by constructing hard stochastic instances and reducing optimization progress to statistical estimation. These constructions establish sample-complexity lower bounds under smoothness and bounded-variance conditions.

  • Lower-bound consequence: For sufficiently small tolerances, the construction yields an ε^-2 sample-complexity lower bound for finding an ε-stationary point.The stated result also handles an edge case and remains valid in dimension d=1.
  • Hard-instance construction: The construction defines functions F(x)=E_z[f(x,z)] with bounded initial suboptimality, variance, and smoothness parameters.The global stochastic model gives the algorithm the full sampled function, making it more powerful than the stochastic first-order model.
  • Hard-instance construction: The quadratic family F_s(x)=(L̄/2)||x−θ_s||^2 is L̄-smooth and has initial suboptimality at most Δ.The instance randomizes over s∈{−1,1}, with Gaussian observations whose means depend on s.
  • Statistical reduction: The proof converts difficulty in distinguishing the two underlying instances into a lower bound on the expected gradient norm at the returned iterate.It defines the instance estimate by selecting the sign with smaller gradient norm and bounds the resulting error using standard information-theoretic arguments.

A.2 Proof of Lemma 4

This proof constructs an unbiased stochastic gradient estimator whose randomness is localized to at most one coordinate. It verifies both bounded variance and mean-squared smoothness through coordinatewise and Lipschitz bounds.

  • Estimator structure: The estimator is unbiased for ∇F_T and vanishes beyond the currently revealed coordinate range.This coordinate-support property is central to the probability-p zero-chain behavior established later.
  • Zero-chain property: The estimator is a probability-p zero-chain: the next unrevealed coordinate is nonzero with probability at most p.This follows from the Bernoulli randomization at the active coordinate.
  • Estimator structure: The stochastic deviation δ(x,z)=ḡ_T(x,z)−∇F_T(x) has at most one nonzero coordinate.The proof uses this sparsity together with the coordinatewise construction to control variance and changes between query points.
  • Regularity verification: The estimator satisfies a constant bounded-variance condition, with the coordinatewise bound establishing variance parameter ς=2^3.The passage states that the relevant coordinate quantity is bounded by one for all x and i.
  • Regularity verification: The mean-squared difference is bounded by 2·(2^3·6)^2||x−y||^2+2||∇F_T(x)−∇F_T(y)||^2.Using smoothness of F_T then establishes the required mean-squared smoothness bound.

A.3 Proof of Theorem 2

The proof rescales the mean-squared-smooth hard instance so it belongs to the target oracle class while preserving the difficulty of revealing progress. It then combines the resulting bounds across parameter regimes.

  • Scaling and oracle membership: The rescaled estimator T(x,z)=(L/ℓ_1)ḡ_T(x/λ,z) is used to transfer the hard instance into the desired oracle class.The scaling is chosen analogously to the proof of Theorem 1.
  • Scaling and oracle membership: Choosing p and L appropriately guarantees the variance bound and membership in the oracle class O(K,σ^2,L̄).The proof treats the parameter constraints in separate cases.
  • Parameter regimes: The proof handles the regimes L̄Δ√p/(4ℓ̄_1Δ_0ε^2)≥3 and <3 separately.In the first regime, the floor inequality and the selected p yield the more informative lower bound.
  • Final lower bound: The two regime-specific bounds combine to give the desired lower bound, with c_0 a universal constant valid for every dimension.The edge-case argument shows that the alternate bound matches the target result up to constants.
  • K-query extension: For simultaneous-query algorithms, the argument tracks batches x(i)=(x(i,1),…,x(i,K)) and their oracle responses.This notation supports the extension from single-query to K-query settings.

B.1.2 Proof of the bound (44)

The proof establishes that random rotations hide unrevealed coordinates from adaptive algorithms, while soft projection preserves the required regularity properties. These facts support lower bounds for general randomized algorithms.

  • Probability control: The proof bounds failure probabilities for the events controlling all queried directions and substitutes those bounds into the target inequality.The resulting estimates include a term involving 32R^2tK.
  • Random rotation: A random orthogonal rotation makes every substantially nonzero transformed query coordinate lie in the support of a previous oracle response.The argument relies on oracle responses providing essentially no information outside their revealed support.
  • Random rotation: Conditioned on prior queries and revealed directions, the next unseen rotation vector is uniform on the orthogonal complement of their span.Rotational invariance and sphere concentration control the probability that it has a large projection onto a query.
  • Soft projection: Soft projection ρ and rotation U allow the construction to operate in higher dimensions without significantly harming regularity requirements.The proof defines compressed iterates y(i,k)=ρ(x(i,k)) and applies the rotated oracle to them.
  • Soft projection: The transformed function has Lipschitz gradient, while the transformed stochastic gradient obeys a mean-squared bound involving L̄^2+9σ^2+9.These properties verify preservation of the oracle assumptions after composition with projection and rotation.

B.4 Proof of Theorem 3

The proof handles the bounded-variance and mean-squared-smooth settings separately, using scaled hard instances and prior lemmas to derive the stated lower bounds.

  • Bounded variance setting: The bounded-variance proof defines a scaled instance whose stochastic gradient oracle has variance bounded by σ^2.The construction is parameterized by accuracy, initial suboptimality, smoothness, and variance.
  • Bounded variance setting: The proof transfers an algorithm interacting with the scaled oracle to an algorithm for the corresponding unscaled construction.This lets the lower-bound argument apply uniformly over orthogonal transformations.
  • Bounded variance setting: The resulting inequalities yield a lower bound involving L∆p/(ϵ^2) and L∆σ^2, up to numerical constants.The displayed bound combines the iteration parameter p with smoothness, initial suboptimality, accuracy, and variance terms.
  • Mean-squared smooth setting: The mean-squared-smooth proof uses scaling (60), selects p, and verifies that the resulting oracle belongs to O(K, σ^2, ¯L).Lemma 7 and the calculation from Theorem 2 establish the required class membership before applying inequality (61).
  • Mean-squared smooth setting: The proof treats both parameter regimes: when the displayed ratio is at least 4, bounds (62) and (63) imply the result; otherwise, (63) dominates (62).The floor inequality ⌊x⌋−2 ≥ x/4 for x ≥ 4 is used in the first regime.

C.1 Statistical learning oracles

This section analyzes the hard stochastic construction by establishing smoothness properties, a sparse gradient structure, variance control, and mean-squared smoothness bounds.

  • Variance and smoothness: The variance is bounded by combining the sparse support pattern with bounds on ∇Θ_i and H, while the construction also satisfies a mean-squared smoothness estimate.The proof collects separate contributions to the variance and bounds E∥∇f_T(x,z)−∇f_T(y,z)∥^2 using the error decomposition.
  • Construction regularity: The soft-indicator functions are built from Γ and have controlled regularity: Γ is 6-Lipschitz, Γ′ is 128-Lipschitz, and µ is 164-Lipschitz.These facts support differentiability and subsequent bounds for the construction.
  • Gradient structure: The gradient components decompose into neighboring terms, g_i(x, z) = −h_1(x_i−1, x_i) · ν_i(x, z) − h_2(x_i, x_i+1) · ν_i+1(x, z).This local form is used to analyze the sparse error vector and its variance.
  • Gradient structure: The stochastic gradient is unbiased, with E[∇f_T(x, z)] = ∇F(x), and exhibits a probability-p zero-chain property.Coordinates beyond the progress frontier vanish with probability one under the stated conditions.
  • Active-oracle construction: The lower-bound argument crucially uses a different random bit for every coordinate; reusing one bit would reduce the bound from Ω(NT) to Ω(N + T).With shared bits, an algorithm could find a productive coordinate and query it repeatedly.
Loading 1912.02365v2…