PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization

Ohad Shamir

arXiv:1209.2388v3cs.LGmath.OCstat.ML

TL;DR

The paper addresses the limited understanding of complexity in stochastic convex optimization with bandit or derivative-free feedback. It develops upper and lower bounds in dimension d and query count T, finding sharp behavior for strongly-convex and smooth functions and a fast rate for quadratic functions.

  • Problem

    The complexity of stochastic convex optimization with bandit or derivative-free feedback, especially for nonlinear functions, is much less understood than its algorithms and upper bounds.

  • Method

    The paper derives upper and lower bounds for bandit and derivative-free stochastic convex optimization as functions of dimension d and query count T, analyzing strongly-convex, smooth, and quadratic functions.

  • Results

    Quadratic functions admit a sharp Θ(d2/T) optimization-error rate and, under more restrictive noise assumptions, an O(d/T) rate in T.

  • Takeaways & Limitations

    The results establish quadratic dimension dependence for strongly-convex and smooth problems and demonstrate a fast O(1/T) derivative-free stochastic rate for quadratic functions.

  • Takeaways & Limitations

    The paper leaves high-probability guarantees and the attainable performance for general convex and strongly-convex possibly non-smooth functions unresolved.

Abstract

from arXiv · show

The problem of stochastic convex optimization with bandit feedback (in the learning community) or without knowledge of gradients (in the optimization community) has received much attention in recent years, in the form of algorithms and performance upper bounds. However, much less is known about the inherent complexity of these problems, and there are few lower bounds in the literature, especially for nonlinear functions. In this paper, we investigate the attainable error/regret in the bandit and derivative-free settings, as a function of the dimension d and the available number of queries T. We provide a precise characterization of the attainable performance for strongly-convex and smooth functions, which also imply a non-trivial lower bound for more general problems. Moreover, we prove that in both the bandit and derivative-free setting, the required number of queries must scale at least quadratically with the dimension. Finally, we show that on the natural class of quadratic functions, it is possible to obtain a "fast" O(1/T) error rate in terms of T, under mild assumptions, even without having access to gradients. To the best of our knowledge, this is the first such rate in a derivative-free stochastic setting, and holds despite previous results which seem to imply the contrary.

1. Introduction

The paper studies how query-limited stochastic convex optimization performs without gradient information, focusing on complexity in dimension d and queries T. It gives sharp results for strongly-convex and smooth functions, establishes quadratic dimension dependence, and identifies a fast rate for quadratic functions.

  • The paper asks how to optimize an unknown convex function using as few noisy value queries as possible.The derivative-free setting uses function values rather than gradients or higher-order information.
  • Bandit stochastic convex optimization minimizes average regret, whereas derivative-free optimization returns a point with small optimization error.Small average regret can be converted into an algorithm with the same optimization error, so bandit SCO is harder.
  • Prior complexity results leave nonlinear convex optimization insufficiently understood and often concern regret, non-convex domains, artificial domains, or implicit bounds.The paper instead focuses on simple, natural domains and convex problems.
  • The paper proves a sharp Θ(d2/T) characterization for strongly-convex and smooth functions, implying that query requirements scale at least quadratically with dimension.This contrasts with linear settings that often allow linear dimension dependence and yields a lower bound for more general convex problems.
  • For quadratic functions, the attainable optimization error is Θ(d2/T), while under more restrictive noise assumptions it can improve to O(d/T).The paper presents the Θ(d2/T) rate as sharp on a fixed domain and identifies the improved rate for specific natural noise processes.
  • Average regret for quadratic functions is Θ(d2/T), revealing a gap between bandit and derivative-free stochastic convex optimization.The discussion emphasizes this as a qualitative difference from settings such as multi-armed bandits.

2. Preliminaries

The preliminaries define the convex optimization setting, curvature assumptions, noisy value-query process, and the distinction between optimization error and average regret. They also state the expectation-based performance focus and the reduction from bandit regret to derivative-free error.

  • The objective F is convex on a closed convex domain W ⊆ R^d, with strong convexity and smoothness specified through quadratic lower and upper bounds.Strong convexity uses parameter λ, while smoothness uses parameter µ.
  • The minimizer w* is assumed to lie in a bounded domain, and F is Lipschitz there, even when the overall domain W is unrestricted.The setup allows W = R^d while controlling the location of the optimum.
  • Each of T rounds queries w_t ∈ W and observes an independent noisy realization of F(w_t) + ξ_w, where the noise has zero mean.The noise assumptions are adjusted to support unrestricted domains as well as bounded ones.
  • Derivative-free SCO seeks a point with low expected optimization error, while bandit SCO seeks low expected average regret over the queried points.The derivative-free output is computed from the queried points and observed values.
  • A bandit algorithm with a regret bound yields a derivative-free algorithm with the same optimization-error bound by returning the average of its queried points.Jensen’s inequality supplies the reduction.
  • The paper focuses on bounds in expectation, leaving high-probability error and regret guarantees for further research.

3. Quadratic Functions

For strongly convex quadratic functions, derivative-free stochastic optimization achieves a sharp Θ(d^2/T) error rate under mild query-access assumptions. The matching lower bound also shows that both optimization and bandit regret require quadratically many queries in dimension.

  • Upper bounds: O(d^2/T) optimization error is achievable for strongly convex quadratic functions under a mild assumption on the optimum or query domain.The algorithm may query points slightly outside the domain, or the optimum may lie at least ϵ from the boundary.
  • Lower bounds: The quadratic-function upper bound scales as d^2/(ϵ^2T), and for fixed ϵ it is essentially tight.The lower bound applies even to very well-behaved strongly convex functions and domains.
  • Comparison with prior work: The apparent conflict with a prior Ω(d/T) quadratic lower bound disappears because that construction uses a domain whose diameter, and hence ϵ, decreases with T.The present O(d^2/T) result assumes fixed ϵ.
  • Upper bounds: A one-point random query provides an unbiased gradient estimate, allowing the method to perform stochastic gradient descent with bounded second moments.Quadratic structure permits queries at a non-vanishing distance from the iterate; suffix-averaging avoids logarithmic factors.
  • Lower bounds: The required number of queries to reach fixed accuracy must scale quadratically with dimension, unlike settings where linear dependence on dimension can suffice.This conclusion follows from the matching derivative-free lower bound for quadratic functions.
  • Bandit regret: For bandit SCO, average regret also has a Θ(d^2/T) minimax rate on strongly convex and smooth functions, even with an unrestricted query domain.The lower bound matches a known regret upper bound and extends the d^2/T barrier to more general convex bandit problems.

4. Strongly Convex and Smooth Functions

The paper extends its lower-bound analysis from quadratics to general strongly convex and smooth functions. A carefully designed family remains hard to distinguish from noisy function queries, yielding a d^2/T error barrier.

  • Main result: An existing O(d^2/T) average-regret upper bound for strongly convex and smooth functions is matched by a lower bound in the easier derivative-free setting.Thus the attainable error for strongly convex and smooth functions is of order d^2/T.
  • Main result: There exists a function that is 0.5-strongly convex, 3.5-smooth, 4-Lipschitz on the unit ball, and minimized within that ball, yet remains hard to optimize.The lower-bound construction is valid over R^d and uses a global minimum in the unit Euclidean ball.
  • Lower-bound construction: The lower-bound proof uses a more intricate family parameterized by µ, with e uniformly distributed over {−µ,+µ}^d.The construction is designed so that function differences remain small across queried points, hindering identification of the optimum.
  • Lower-bound construction: Unlike the quadratic construction, querying far from the optimum does not create a much larger signal for distinguishing the hidden parameter.This preserves the d^2/T lower bound for general strongly convex and smooth functions.

5. Discussion

The discussion highlights fast rates for quadratic functions and qualitative separations from prior linear-function results, while identifying unresolved generalizations and parameter-scaling questions.

  • O(1/T) error is possible for stochastic quadratic functions without derivative information.
  • The analysis leaves open settings where Lipschitz and strong-convexity parameters scale with dimension.
  • The attainable performance for general convex and strongly-convex nonsmooth functions remains unresolved.
  • The lower bound and existing upper bounds for strongly-convex functions are not known to be tight.

Appendix A. Improved Results for Quadratic Functions

The appendix develops improved derivative-free stochastic optimization results for decomposable quadratic objectives, exploiting structured noise to improve the generic quadratic rate in suitable settings.

  • Motivation and scope: Θ(d2/T) is tight for quadratic functions under the generic noise model, but more specific noise structure can permit better algorithms.The appendix emphasizes that the generic noise assumption is important for the lower bound.
  • Improved rate: O(d/T) error is attainable for ridge regression when the stochastic quadratic term has dimension-independent structure.The key example assumes bounded feature norms, making the relevant matrix quantity independent of dimension.
  • Problem formulation: The generalized setting writes F(w) as E[ˆF(w)], decomposing each stochastic quadratic realization into a deterministic term R(w) and random quadratic coefficients.The queried value is generated from a random realization of the quadratic coefficients.
  • Algorithm: Algorithm 2 uses a random sign vector, queries at a displaced point, subtracts the deterministic component, and adds a subgradient of R to form an estimate.The update projects the next iterate onto the bounded feasible set.
  • Scope boundary: The O(d/T) improvement does not extend to bandit regret because the algorithm queries points far from the current iterate.The result also relies on specifically structured stochastic noise rather than the generic noise used in the quadratic lower bound.
  • Analysis: The estimated vector is an unbiased subgradient of F(w_t), and the proof obtains the theorem by combining this property with an improved moment bound.The appendix states that the proof differs from the generic analysis mainly through the sharper gradient-estimate moment bound.

B.1. Proof of Lemma 2

The proof of Lemma 2 uses the random-sign moments and the assumed bounds on the quadratic coefficients and noise to control the gradient estimate.

  • Moment calculation: Random sign vectors satisfy vanishing odd moments and identity second moments, simplifying expectations of the gradient estimator.These identities remove cross-coordinate terms in the calculation.
  • Role in the proof: The resulting bound supports the lower-bound analysis for derivative-free quadratic optimization.This role follows from the proof passages’ placement in the lemma-based lower-bound argument.
  • Moment calculation: The assumptions on A, b, c, and the noise provide the remaining moment control needed for the estimator bound.The proof combines coefficient and noise assumptions after applying the random-sign identities.

B.2. Proof of Lemma 4

The proof of Lemma 4 bounds how well an algorithm can infer hidden coordinate information from noisy observations, using conditional probabilities and KL divergence.

  • Coordinate information: The argument reduces coordinate recovery to differences between conditional probabilities given opposite signs of a hidden coordinate.The proof examines whether the output coordinate has the correct sign under the two conditions.
  • Coordinate information: A sum-of-squares inequality isolates one coordinate while controlling the aggregate contribution across d coordinates.The proof considers the first coordinate without loss of generality after applying the inequality.
  • Information bound: Pinsker’s inequality and the KL-divergence chain rule upper-bound the distinguishability of the observation distributions.The output is treated as a deterministic function of the observed values in the information-theoretic step.
  • Conclusion: Substituting the information bounds into the preceding inequality completes the lemma.The proof explicitly closes by plugging the KL-based bound back into the main expression.

B.3. Proof of Thm. 6

The proof of Theorem 6 constructs a quadratic instance and relates its expected average regret to the algorithm’s output, then chooses a parameter yielding the stated lower bound.

  • Setup: The proof assumes T≥d2 and reduces the claim to showing expected average regret at least 0.02.The restriction is justified within the theorem’s lower-bound argument.
  • Regret reduction: Jensen’s inequality converts the average of the played points into a bound involving the output point’s objective value.The proof discards the minimum while deriving the regret relation.
  • Hard instance: An arbitrary deterministic output based on the queried points is evaluated on a quadratic function selected from a parameterized family.The proof states that the same argument applies up to the referenced intermediate equation.
  • Strong-convexity step: Strong convexity supplies a lower bound that relates the objective gap to squared distances from the hidden optimum.The proof also bounds ||w_t||2 using the triangle inequality and squared-distance decomposition.
  • Parameter choice: Choosing the free parameter to make the quadratic have roots of opposite signs yields the desired lower-bound inequality.Nonnegativity of the regret quantity is used after identifying the two roots.
  • Conclusion: The final bound is expressed with the condition d2/T/2≤1/2 from the theorem statement.This is the proof’s concluding quantitative condition.

B.4. Proof of Thm. 7

The proof constructs a coordinate-separable family F_e with controlled curvature, minimizers, and hypothesis separation, then uses Gaussian-query KL bounds to derive a dimension- and query-dependent lower bound.

  • Function construction: F_e is 0.5-strongly convex and 3.5-smooth for every e ∈ {−µ, +µ}^d.The proof verifies these properties by bounding the relevant second-derivative expression within [0.5, 3.5].
  • Function construction: The global minimizer is w∗ = ce, where c = 0.3489... ≥ 1/3.After substituting x = ay, numerical minimization gives y = 0.3489..., yielding the coordinatewise minimizer.
  • Function construction: Changing one coordinate of e changes F_e(w) by at most µ^2 for every w.The bound follows from |g_µ(x) − g_−µ(x)| ≤ µ^2, using µ^2 + x^2 ≥ 2|µx|.
  • Information bound: Under Gaussian observation noise, flipping one coordinate changes the query-value means by at most µ^2, so each query contributes at most µ^4/2 to the KL divergence.The query distribution has variance 1, and the Gaussian KL bound is applied to the two coordinate hypotheses.
  • Lower-bound conclusion: The resulting lower bound is d^2/T, with a constant floor of 0.004 when T < d^2.For T ≥ d^2, the constructed functions satisfy the theorem’s Lipschitz and unit-ball minimizer requirements; smaller T cannot improve on the T = d^2 bound.
Loading 1209.2388v3…