PaperlayerView exact revision on arXiv

Source-linked AI summary

Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization

Alekh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, Martin J. Wainwright

arXiv:1009.0571v3stat.MLeess.SYmath.OC

TL;DR

The paper asks how to characterize the fundamental oracle complexity of stochastic convex optimization, motivated by its role in large-scale learning and estimation. It uses information-theoretic reductions from parameter estimation to optimization and derives lower bounds for several function classes, generally matching known algorithmic upper bounds. The results clarify dimension, geometry, curvature, and sparsity effects, with stated qualifications for small dimensions and certain norm regimes.

  • Problem

    The paper addresses limited study of the inherent complexity of convex optimization despite its extensive use in statistical learning and estimation.

  • Method

    The paper constructs difficult hypercube-indexed function subclasses and reduces accurate optimization to statistical hypothesis testing using Fano’s inequality or Le Cam’s bound.

  • Results

    The paper derives lower bounds for convex, strongly convex, and sparse-optimizer classes that are sharp in general, with matching upper bounds from known stochastic algorithms.

  • Takeaways & Limitations

    The results reveal dimension-dependent and geometric complexity effects, while strong convexity and structured sparse optima can reduce fundamental optimization complexity.

  • Takeaways & Limitations

    The Fano-based lower bound requires sufficiently large dimension, so smaller dimensions require a separate one-dimensional coin-bias argument.

Abstract

from arXiv · show

Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight minimax complexity estimates for various function classes.

1 Introduction

The paper addresses the underexplored fundamental complexity of stochastic convex optimization through an oracle model, complementing extensive algorithm-specific upper-bound analyses. It develops improved lower bounds and tight minimax estimates across several function classes.

  • Motivation: Stochastic convex optimization is important because convex optimization underlies many large-scale statistical learning and estimation algorithms.Stochastic methods can produce moderately accurate solutions relatively quickly.
  • Related work: Prior work primarily analyzed convergence rates and error upper bounds for specific optimization procedures.Examples include gradient descent, mirror descent, interior point programming, and stochastic gradient descent.
  • Oracle complexity: The oracle model measures complexity through repeated queries that return noiseless or noisy information about the optimized function.This framework avoids the difficulty of casting convex optimization directly in a Turing Machine model.
  • Contributions: The paper improves prior stochastic lower bounds through better dimension dependence and sharper results for simpler function classes.The analysis concerns how parameter dimension affects statistical estimation difficulty.
  • Contributions: Optimization complexity is smaller for strongly convex losses than for convex Lipschitz losses, and can be significantly smaller when optimizers are sparse.The proofs reduce statistical parameter estimation to stochastic optimization and apply information-theoretic lower bounds.
  • Organization: The paper organizes its results around oracle-complexity formulation, main theorems and consequences, a common four-step proof framework, and appendices for technical details.The technical aspects of the proofs are deferred to the appendices.

2 Background and problem formulation

The paper formulates stochastic convex optimization in a noisy first-order oracle model and studies lower bounds over convex, strongly convex, and sparse-optimizer function classes. Its framework specifies the optimization error, oracle randomness, geometric assumptions, and function-class constraints.

  • 2.1 Convex optimization in the oracle model: Convex optimization minimizes a convex function over a convex set, with computational cost measured by noisy function and subgradient evaluations needed for an ǫ-optimal solution.The target is a minimizer x*_f in the feasible set.
  • 2.1 Convex optimization in the oracle model: An oracle maps each query point to information about the function, while an optimization method uses observed answers to choose subsequent queries.For stochastic first-order oracles, function values and subgradients are corrupted by zero-mean noise with bounded variance.
  • 2.1 Convex optimization in the oracle model: With stochastic oracles, optimization error is random and accuracy is evaluated by its expectation over oracle randomness.The method’s final query is random because it depends on the oracle’s random responses.
  • 2.2 Stochastic first-order oracles: The stochastic first-order oracle returns noisy function and subgradient estimates that are unbiased, with subgradient noise controlled in the ℓp-norm.For differentiable functions, the subgradient estimate becomes an unbiased gradient estimate.
  • 2.2 Stochastic first-order oracles: For separable statistical losses, sampling one component uniformly yields unbiased estimates of the full function and gradient.This provides the oracle interpretation of a standard stochastic gradient method.
  • 2.3 Function classes of interest: The studied function classes are real-valued convex functions on convex sets containing an open neighborhood of zero, with geometry characterized partly by the set radius r(S).The paper uses ℓp and conjugate ℓq norms to state Lipschitz and oracle conditions.
  • 2.3 Function classes of interest: Strongly convex functions impose ℓ2 strong convexity alongside Lipschitzness, with the Lipschitz and strong-convexity constants interacting through the domain geometry.The paper restricts its main treatment to strong convexity with respect to the ℓ2-norm.
  • 2.3 Function classes of interest: Sparse-optimizer functions are convex Lipschitz functions with at least one k-sparse optimizer, motivated by statistical settings where ambient dimension often enters logarithmically.The paper investigates whether sparsity similarly reduces optimization complexity’s dependence on ambient dimension.

3 Main results and their consequences

The paper develops lower bounds for stochastic convex optimization that improve dimension dependence, expose the role of constraint-set geometry, and are generally minimax-tight across convex, strongly convex, and sparse-optimum classes.

  • Convex Lipschitz functions: Theorem 1 gives lower bounds for bounded convex Lipschitz functions over sets containing an ℓ∞ ball, with rates scaling naturally with the ball radius r.The bounds use σ=L and apply to Fcv(S, L, p).
  • Convex Lipschitz functions: The analysis improves prior stochastic lower bounds by allowing arbitrary constraint-set geometry through the largest inscribed ℓ∞ ball, rather than requiring dual norms.This yields sharper dimension dependence and highlights geometry as a determinant of oracle complexity.
  • Convex Lipschitz functions: The convex lower bounds are generally optimal, with matching rates achieved by stochastic gradient descent or mirror descent in the relevant norm regimes.For p ∈[1,2], stochastic gradient descent matches the bounds; for p>2 and S=B∞(1), mirror descent with the dual norm achieves them up to constants.
  • Convex Lipschitz functions: Higher-order gradient information cannot improve worst-case convergence rates, even under an oracle returning a noisy realization of the entire function.The result applies when derivative estimates are unbiased with appropriately bounded second moments.
  • Strongly convex Lipschitz functions: Theorem 2 establishes sharp lower bounds for strongly convex Lipschitz functions on B∞(r), with a phase transition between strong-convexity and convex-objective regimes.For sufficiently large γ and large T, the Ω(1/T) term dominates; when γ≈0, the convex-rate term dominates.
  • Strongly convex Lipschitz functions: The strongly convex result is limited to B∞(r); extending it to arbitrary convex compact sets remains open.This scope boundary does not apply to the general convex result in Theorem 1.
  • Sparse optima: Theorem 3 gives a tight lower bound for convex Lipschitz functions with k-sparse optimizers when k=O(d^(1−δ)), matching mirror-descent rates up to constants.The paper identifies this as its first tight lower bound for sparse optimization.

4 Proofs of results

The proofs reduce stochastic convex optimization to identifying a hidden vertex encoding Bernoulli biases, then use function packings and testing lower bounds to control oracle complexity.

  • Proof framework: The common proof framework embeds convex optimization into estimating the biases of d independent Bernoulli variables.A hypercube subset indexes Bernoulli parameter vectors and difficult functions.
  • Testing lower bounds: Fano’s inequality and Le Cam’s bound convert the resulting multiway or binary testing problem into lower bounds on the probability of misidentification.The information supplied by T stochastic-oracle queries is bounded through the revealed coin tosses and mutual information.
  • Constructing hard instances: A d/4-separated hypercube packing supplies a difficult subclass G ⊆ F whose functions preserve the target regularity properties.The base functions and scaling factor are chosen so minimizers remain in S and the functions satisfy Lipschitz or strong-convexity conditions.
  • Optimization and identification: Optimizing a packed function to sufficiently small error identifies its hidden hypercube vertex, because one point cannot approximately minimize two separated functions.The discrepancy premetric ρ measures separation through behavior near the functions’ minima.
  • Stochastic oracles: Oracle A reveals one randomly selected coin flip per round, while Oracle B reveals d-dimensional unbiased gradients linked to all coin tosses.Both oracle constructions return unbiased function-value or gradient information, with bounded moments under the stated base-function conditions.
  • Information bounds: For δ ≤ 1/4, the information bound for ℓ revealed coins per round is I((U, Y); α∗) ≤ 16ℓδ2.When the packing is too small for a nontrivial Fano bound, the proof reduces to estimating a single coin bias using Le Cam’s method.

4.2 Proof of Theorem 1

Theorem 1 constructs packed Lipschitz convex functions on ℓ∞-balls and combines discrepancy separation with Oracle A or B to derive dimension- and norm-dependent lower bounds.

  • Construction: The proof begins with S = B∞(1/2), where packed functions have minimizers xα = −α/2 and satisfy the required Lipschitz constraints.The general-radius argument rescales the construction so minimizers become xα = −rα/2.
  • Case 1 ≤ p ≤ 2: For 1 ≤ p ≤ 2, Oracle A reveals at most one coin flip per round, producing the corresponding information lower bound.The resulting testing inequality is combined with the optimization-to-identification reduction and extended to all dimensions.
  • Discrepancy separation: Each differing coordinate contributes 2cδ/d to ρ under the packing, yielding ψ(δ) ≥ cδ.This separation lets optimization accuracy imply successful identification of the packed function.
  • Case p > 2: For p > 2, Oracle B reveals all d coin tosses per round, and scaling c = Ld1−1/p yields the stronger theorem-specific lower bound.The d-dimensional gradient norm is controlled by cd1/p−1 before setting the Lipschitz scale.
  • General domains: For a general domain containing B∞(r), the lower bound scales with r because the hard-instance minimizers and discrepancy scale with the inscribed-ball radius.The proof otherwise remains unchanged and holds for all dimensions after the stated reduction.

4.3 Proof of Theorem 2

Theorem 2 applies the same identification framework to strongly convex Lipschitz functions, using a parameterized quadratic-like ensemble and separate regimes for the strong-convexity parameter.

  • Construction: The strongly convex construction uses base functions parameterized by θ, with strong convexity constant (1−θ)c/(4d).For the p = 1 proof, the functions are cr-Lipschitz and their stochastic gradients have bounded second moments.
  • Discrepancy regimes: The proof relies on a uniform lower bound for the discrepancy ρ between distinct packed functions.The lower bound changes according to whether 1−θ is above or below 4δ/(1+2δ).
  • Second regime: When 1−θ ≤ 4δ/(1+2δ), the discrepancy instead satisfies ρ(gα, gβ) ≥ cδr2/4 for distinct packed functions.The proof sets ε := Lδr/36 and follows the Theorem 1 identification argument.
  • Case p > 2: For p > 2, Oracle B reveals d-dimensional gradients and uses c = Ld1−1/p/r to control the oracle output before applying the d-coin information bound.The same two-regime discrepancy analysis yields the stated lower bound, with small dimensions handled up to constants.

4.4 Proof of Theorem 3

Theorem 3 targets convex Lipschitz functions with sparse minimizers by packing vectors with exactly k nonzero entries and applying Fano’s inequality to the resulting restricted hypothesis class.

  • Sparse packing: The construction uses vectors in {−1, 0, +1}d with exactly k nonzero entries and pairwise Hamming separation at least k.A packing set V(k) with exponentially many elements supplies the hypotheses.
  • Function class: The induced class G(δ; k) is convex and c-Lipschitz in the ℓ∞ norm.The proof controls its discrepancy ψ(δ; k) before applying the testing argument.
  • Oracle construction: Oracle B returns d-dimensional gradients generated from Bernoulli variables, with c = L/3 ensuring the returned functions are L-Lipschitz.The gradient coordinates are bounded in ℓ∞ norm by 3c.
  • Fano argument: Fano’s inequality bounds pairwise divergence by D(Pα ∥ Pβ) ≤ 32kTδ2 because each of the at most 2k differing coordinates contributes at most 16δ2.This produces a lower bound on the probability of misidentifying the sparse parameter vector.
  • Final lower bound: The optimization reduction sets ε proportional to Lkδr and combines the testing bound with the packing size to obtain the theorem’s lower bound.The proof treats k, d ≥ 11 directly and obtains the remaining cases from Theorem 1(b) with p = ∞.

5 Discussion

The paper derives stochastic first-order oracle lower bounds across several convex function classes and connects them to statistical minimax techniques. It identifies dimension-dependent and geometric aspects of complexity while outlining memory and distributed optimization as future directions.

  • Lower bounds cover convex, strongly convex, and convex functions with sparse optima.
  • The bounds are sharp in general because known stochastic gradient and mirror descent algorithms achieve matching upper bounds.
  • The proofs construct packing sets using a pre-metric that measures separation between different functions’ optima.
  • Fano’s inequality and related information-theoretic techniques establish the lower bounds.
  • Future work includes studying memory constraints and distributed optimization.

A Proof of Lemma 5

The proof evaluates single-function and joint infima over the constraint ball, splitting the calculation according to coordinate relationships and parameter regimes. These evaluations yield the discrepancy needed for the lemma.

  • Evaluating the infima: The proof computes both inf_x∈B∞(r) gα(x) and inf_x∈B∞(r){gα(x)+gβ(x)} to evaluate the discrepancy.
  • Evaluating the single function infimum: For each coordinate, the constrained minimum is found by analyzing the associated univariate function on [−r,r].
  • Evaluating the single function infimum: Summing the coordinatewise minima produces the single-function infimum over all d coordinates.
  • Evaluating the joint infimum: Coordinates where α_i ≠ β_i are minimized at x*(i)=0, with per-coordinate minimum value (1+3θ)cr^2/(2d).
  • Case analysis: The discrepancy calculation separates the cases 1−θ ≥4δ/(1+2δ) and 1−θ <4δ/(1+2δ).

B Proof of Lemma 6

This proof evaluates the discrepancy between functions indexed by sparse hypercube vectors by minimizing their coordinatewise terms over B∞(r). The resulting expression depends on Hamming separation within the packing set.

  • Evaluating the single function infimum: The single-function infimum is obtained coordinatewise: nonzero α_i are minimized at x(i)=−rα_i, while zero coordinates are minimized at x(i)=0.
  • Evaluating the joint infimum: For α_i ≠ β_i, the joint coordinate term has minimum value 2r, achieved at x(i)=0 when both entries are nonzero.
  • Evaluating the joint infimum: When α_i ≠ 0 and β_i=0, setting x(i)=−α_i achieves the joint-term minimum value 2r.
  • Equal-coordinate cases: For equal nonzero coordinates, the minimum occurs at x(i)=−α_ir with value 2r(1−δ), whereas equal zero coordinates contribute 2r at x(i)=0.
  • Combining the cases: The final discrepancy uses that α and β each have k nonzero elements and that the packing guarantees Δ_H(α,β)≥k/2.

C Upper bounds via mirror descent

The appendix reviews mirror descent methods and their convergence results, then shows that suitable mirror descent variants provide matching upper bounds for several lower bounds established in the paper.

  • The appendix describes the basic mirror descent algorithm and summarizes known convergence results.
  • Different mirror descent forms provide matching upper bounds for several of the paper’s lower bounds.

C.1 Background on mirror descent

Mirror descent generalizes projected stochastic gradient descent through a strongly convex proximal function and Bregman-divergence updates. Its averaged iterates provide convergence guarantees that can be related to the final iterate used in the lower-bound analysis.

  • C.1 Background on mirror descent: A 1-strongly convex proximal function Φ with respect to a chosen norm defines the mirror descent framework.The framework assumes Φ is differentiable; a Legendre-type assumption ensures differentiability of its conjugate dual.
  • C.1 Background on mirror descent: Mirror descent minimizes a convex function over S by generating iterates from a proximal-function update with stepsizes η_t.In stochastic optimization, the exact gradient is replaced by a noisy gradient estimate.
  • C.1 Background on mirror descent: Choosing Φ(x) = 1/2∥x∥_2^2 recovers projected gradient descent and, with unbiased gradient estimates, projected stochastic gradient descent.Its Bregman divergence is the squared Euclidean distance up to the factor 1/2.
  • C.1 Background on mirror descent: Under suitable convexity and Lipschitz assumptions, stochastic mirror descent yields an upper bound on optimization error for the generated sequence.The analysis assumes a bounded second moment for the noisy gradient estimates.
  • C.1 Background on mirror descent: Jensen’s inequality converts the averaged-iterate convergence guarantee into comparable bounds for the final iterate x_T.The comparison uses x_T as the average of the preceding iterates, up to constant factors.

C.2 Matching upper bounds

The paper selects mirror-descent geometries according to the norm regime and sparsity structure. These choices recover the lower bounds up to constants in the stated settings, with logarithmic qualifications in some regimes.

  • C.2 Matching upper bounds: For p ≥ 2, mirror descent chooses a = q = p/(p − 1), yielding an O(L/√T) upper bound when p = o(log d).This matches the lower bound from Equation (11) for the stated convex set and function class.
  • C.2 Matching upper bounds: For p = Ω(log d), mirror descent instead uses a = 2 log d/(2 log d − 1), with an additional logarithmic factor in the upper bound.The logarithmic qualification is explicitly noted for this regime.
  • C.2 Matching upper bounds: For the ℓ∞ ball, mirror descent uses Φ_a with a = q and exploits ∥x*∥_∞ ≤ 1 to control the proximal-function value.This condition is also assumed in the lower-bound construction.
  • C.2 Matching upper bounds: For 1 ≤ p ≤ 2, stochastic gradient descent with q = 2 matches the lower bound of Theorem 1(a).The match uses the assumed bound on the noisy-gradient second moment and a corresponding bound on ∥x*∥_2.
  • C.2 Matching upper bounds: For sparse optimization, the proximal function Φ_a with a = 2 log d/(2 log d − 1) yields an upper bound matching Theorem 3 up to constants when k = O(d^(1−δ)).Theorem 3 is described as the first tight lower bound on oracle complexity for sparse optimization.
Loading 1009.0571v3…