Source-linked AI summary
Optimal rates for zero-order convex optimization: the power of two function evaluations
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, Andre Wibisono
TL;DR
The paper asks how well stochastic and non-stochastic convex optimization can be performed using only function values rather than gradients. It develops multi-point random-perturbation gradient estimators and proves convergence results for smooth and non-smooth settings, together with minimax lower bounds. With paired evaluations, the resulting rates are at most a √d factor worse than full-gradient stochastic methods, and the achievable rates are sharp up to constant or sometimes logarithmic factors.
Problem
The convergence behavior of derivative-free convex optimization using only function values remains insufficiently understood, especially for multi-point observations and across smooth and non-smooth settings.
Method
The paper analyzes stochastic gradient and mirror-descent methods using random-perturbation estimators from paired and m ≥ 2 function evaluations, and proves information-theoretic minimax lower bounds.
Results
With paired evaluations, convergence rates are roughly a factor of √d worse than full-gradient stochastic methods, while the rates are sharp up to constant or sometimes logarithmic factors.
Takeaways & Limitations
The results provide sharp convergence guarantees for smooth, non-smooth, non-stochastic, and multi-point bandit convex optimization problems.
Takeaways & Limitations
High-probability guarantees require additional tail conditions, such as bounded dual-norm subgradients, and sharp dimension dependence requires care.
Abstract
from arXiv · showhide
We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for $d$-dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most $\sqrt{d}$ in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and non-smooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple ($m \ge 2$) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.
1 Introduction
The paper studies convex optimization when only function values are available, focusing on the convergence behavior of stochastic and non-stochastic derivative-free algorithms. It develops multi-point gradient estimators and establishes achievable rates, lower bounds, and applications across smooth, non-smooth, and bandit settings.
- Derivative-free methods are useful when explicit gradient calculations are computationally infeasible, expensive, or impossible.
- Two-point evaluations alleviate difficulties of single-evaluation optimization by estimating directional derivatives from paired function values.For perturbation uZ, the difference quotient (F(θ+uZ; x)−F(θ; x))/u approximates a directional derivative.
- The paper analyzes stochastic gradient and mirror-descent procedures that construct gradient estimators from paired observations and extends the framework to m ≥ 2 evaluations.
- The resulting convergence rates are roughly a factor of √d worse than methods observing full gradients and a factor of √d better than rates in past work.
- The algorithms cover smooth, non-smooth, and non-stochastic problems, with sharp rates also obtained for bandit online convex optimization with multi-point feedback.
- Information-theoretic minimax lower bounds show that the achievable rates are sharp up to constant factors, or factors at most logarithmic in dimension in some cases.
2 Algorithms
The paper develops two-point and multi-point function-value gradient estimators for mirror descent, covering smooth, non-smooth, stochastic, and non-stochastic convex optimization. Its rates improve dimension dependence over earlier methods, while lower bounds establish sharpness up to logarithmic factors.
- Smooth case: Two function values yield nearly unbiased gradient estimators under smoothness, with optimal dependence on dimension d.The estimator's bias is controlled by the smoothing parameter, which can be taken arbitrarily close to zero.
- Smooth case: The smooth two-point method attains the fastest previously derived rate for zero-order stochastic optimization using two evaluations.Earlier analyses achieved rates with worse dimension dependence, whereas this construction improves the dependence to the sharp rate described by the corollaries.
- Multiple evaluations: Multiple evaluations improve convergence because averaging more function-based estimates produces more accurate instantaneous-gradient estimates.The extension samples m independent perturbations and averages their corresponding estimators.
- Examples and corollaries: With evaluations linear in d, the method can attain the standard full-information convergence rate using only function values.At this evaluation budget, the gradient is essentially estimable from function values.
- Lower bounds: The additional dimension dependence is sharp up to logarithmic factors: two-point methods require O(d/ε^2) iterations for ε-accuracy, versus O(1/ε^2) for mirror descent with full gradients.The lower-bound argument shows that no function-evaluation algorithm can improve the dependence, including the problem-dependent constants R and G.
- Non-smooth case: For non-smooth objectives, the estimator's squared norm incurs a d log d factor, producing a convergence rate at worst √log d worse than in the smooth case.The extra logarithmic penalty arises from non-smoothness, while the resulting dimension dependence remains better than previously known results.
3 Lower bounds on zero-order optimization
The section establishes information-theoretic lower bounds for zero-order convex optimization and compares them with achievable rates, full-gradient methods, and single-evaluation schemes. These bounds show when paired or multiple evaluations are optimal and when evaluation cost favors gradients.
- The lower bounds show that the achievable rates are unimprovable by more than constant factors, or logarithmic factors in some settings.The paper states that no oracle-model algorithm can achieve faster rates than the presented procedures, up to these factors.
- For multiple evaluations, the minimax rate approaches the full-information rate as m approaches d.The lower-bound discussion states that the rate with m evaluations converges toward RG/√k as m → d.
- Two function evaluations create a phase transition for general nonsmooth convex optimization: single evaluations require d^2/ε^2 iterations, whereas paired evaluations require d/ε^2.The comparison is stated for 1-Lipschitz convex functions over the ℓ2-ball with unit observation variance.
- For linear losses, single and multiple function evaluations generally do not exhibit the same phase transition seen for general convex losses.The paper reports comparable rates up to logarithmic factors in the Euclidean and simplex cases.
- Zero-order methods necessarily incur an additional O(√d) convergence-rate penalty relative to full-gradient methods, and the proposed algorithms attain it optimally.When function evaluations are substantially more expensive than gradient computation, the paper notes that full gradients may be preferable.
4 Convergence proofs
The convergence proofs analyze mirror-descent methods using randomized directional estimates, smoothing, and multiple perturbations. They control estimator bias and moments to derive rates for smooth and nonsmooth objectives.
- Smooth and nonsmooth convergence analysis: The proofs begin from a standard mirror-descent iterate bound and apply it to the randomized gradient estimates.The analysis conditions on the history of samples and perturbations before bounding the resulting terms.
- Smooth and nonsmooth convergence analysis: The directional estimator has controlled bias because smoothing produces a differentiable objective whose expected gradient matches the gradient of the smoothed population objective.The proof uses Lipschitzness, smoothing, independence, and the isotropic condition E[ZZ⊤] = I.
- Multiple evaluations: Averaging m directional estimates reduces the estimator’s expected squared norm by a factor of m relative to one directional vector.This variance reduction supplies the key multiple-evaluation improvement in the convergence analysis.
- Nonsmooth objectives: The nonsmooth proof smooths the objective with two perturbation scales and bounds the resulting smoothing penalties, moments, and directional-gradient terms.The technical estimates use Gaussian or ball-based perturbations and dimension-dependent moment inequalities.
5 Proofs of lower bounds
The lower-bound proofs construct hard stochastic optimization instances and reduce accurate optimization to identifying hidden binary coordinates. Testing inequalities and covariance bounds then produce minimax lower bounds for paired and multiple evaluations.
- Reduction to testing: The proofs construct separated linear objectives indexed by Boolean vectors so that optimization error reveals coordinate-sign errors.A wrong sign incurs an additive objective penalty, enabling a reduction from optimization to binary testing.
- Reduction to testing: Le Cam and Assouad arguments convert testing difficulty into lower bounds on optimization error under paired function-value observations.The proof bounds total variation between conditional observation distributions and combines it with the coordinate-wise penalties.
- Hard-instance construction: The same construction extends to d0-dimensional subproblems embedded in d dimensions, allowing the lower bounds to use d0 ≤ d active coordinates.Choosing d0 = min{d, k} completes one of the propositions.
- Multiple evaluations: For m evaluations per iteration, covariance bounds extend the testing argument and yield lower bounds that improve with m toward the full-information regime.The multiple-query proof replaces the two-point covariance calculation with an m-point analogue.
6 Discussion
The paper establishes minimax-optimal convergence rates for optimization using random function values, including smooth and non-smooth settings. Paired evaluations require at least Ω(d/ε^2) observations, while single evaluations require at least Ω(d^2/ε^2).
- The algorithms achieve convergence rates that cannot be improved by more than numerical constant factors in the minimax sense.
- Non-smooth optimization is no more difficult than smooth optimization in iteration complexity, although it requires more carefully constructed randomization schemes.
- Paired function evaluations require at least Ω(d/ε^2) observations, while gradient methods require O(1/ε^2) gradient observations.
- Single function evaluations require at least Ω(d^2/ε^2) observations.
- The results also establish sharp rates for bandit online convex optimization with multi-point feedback.
A Technical results for convergence arguments
This appendix collects proofs of the lemmas used in the paper’s convergence arguments.
- The appendix organizes the proofs of the various lemmas underlying the convergence arguments.
A.1 Proof of Lemma 4
The proof analyzes moments of rotationally invariant perturbation distributions used in the convergence arguments. It treats Gaussian, sphere-uniform, and ball-uniform samples separately.
- For Gaussian perturbations, χ2-distributed norm calculations establish the needed moment relations.
- For samples uniform on the unit ball, the norm has density d · t^(d−1), which yields the required moment expression.
A.2 Proof of Lemma 5
The proof of Lemma 5 controls deviations caused by random smoothing of Lipschitz convex functions. It combines concentration, rotational symmetry, one-dimensional reduction, and stochastic dominance for several perturbation distributions.
- Concentration and smoothing: Rotationally invariant sub-Gaussian concentration shows that the perturbed function is close to the unperturbed function with high probability.
- Concentration and smoothing: The smoothing difference Δ_u(θ) is nonnegative by convexity and Jensen’s inequality, and integrating out one perturbation produces a smoother deviation problem.
- Rotational reduction: Rotational averaging reduces the supremum over multidimensional Lipschitz convex functions to a one-dimensional problem involving the norms of two random vectors.
- Rotational reduction: The one-dimensional supremum is attained by step functions, reducing the bound to comparisons involving absolute-value functions.
- Distribution-specific bounds: Combining the deviation bounds with Lemma 10 yields the stated result of Lemma 5, with constants depending only on the moment order k.
- Distribution-specific bounds: For uniform-ball perturbations, density comparisons establish stochastic dominance of the perturbed norm over the original norm.
B Technical proofs associated with lower bounds
This section develops the technical results used to prove Propositions 1 and 2.
- The section establishes technical results needed for the proofs of Propositions 1 and 2.
B.1 Proof of Lemma 6
The proof uses convexity and monotonicity properties of x ↦ −x^(1+1/q), together with its derivative at x = d.
- The proof represents vectors with zeros in their first i coordinates and ones elsewhere using 1_i+1:d.
- For q ∈ [1, ∞], x ↦ −x^(1+1/q) is convex and non-increasing.
- At x = d, the derivative of x ↦ −x^(1+1/q) is −(1 − 1/q)/d^(1/q).
B.2 Proof of Lemma 7
The proof bounds KL divergences for function-evaluation observations by conditioning on coordinates, applying KL inequalities, and analyzing the Gaussian observation model.
- The proof defines P_v,+j and P_v,−j by forcing coordinate v_j to +1 or −1, respectively.
- By the KL chain rule, the proof decomposes divergences across conditional observation distributions.
- For query pair W = [θ τ], observations are Gaussian with mean δW^⊤v and covariance Σ = σ²W^⊤W.
- When vectors differ only at coordinate j, their query means differ through (v_j − w_j)θ_j, enabling a coordinate-specific divergence bound.
- The argument combines conditional KL bounds, including the analogous bound for P_v,+j, and integrates over observations to prove inequality (33).