Source-linked AI summary
An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
Ohad Shamir
TL;DR
The paper addresses two-point bandit and zero-order convex optimization, where limited function evaluations replace direct gradient access. It uses mirror descent with a modified two-sided randomized gradient estimator and reports optimal guarantees for convex Lipschitz functions, with simpler analysis and non-Euclidean applicability.
Problem
Two-point bandit and zero-order convex optimization need effective guarantees when only two function evaluations per round are available, especially for non-smooth convex functions.
Method
The paper combines mirror descent with a randomized estimator that queries f at w − δu and w + δu and estimates a gradient of a smoothed function.
Results
The algorithm is optimal up to constants for smooth and non-smooth Euclidean problems, applies to non-Euclidean problems, and translates between bandit and zero-order settings.
Takeaways & Limitations
A small change to the gradient estimator yields essentially linear rather than quadratic dependence of its second moment on dimension, supporting the paper’s guarantees.
Takeaways & Limitations
The algorithm assumes function queries are possible at the specified perturbed points, potentially outside the feasible set; querying within the set requires running on a slightly smaller domain.
Abstract
from arXiv · showhide
We consider the closely related problems of bandit convex optimization with two-point feedback, and zero-order stochastic convex optimization with two function evaluations per round. We provide a simple algorithm and analysis which is optimal for convex Lipschitz functions. This improves on \cite{dujww13}, which only provides an optimal result for smooth functions; Moreover, the algorithm and analysis are simpler, and readily extend to non-Euclidean problems. The algorithm is based on a small but surprisingly powerful modification of the gradient estimator.
1 Introduction
The paper studies two-point bandit and zero-order convex optimization, presenting a simple estimator-based algorithm that closes key gaps for non-smooth and non-Euclidean settings.
- Problem: Two-point bandit optimization repeatedly selects points in a convex domain while observing function feedback at two queried locations.The learner seeks low average regret against adversarial convex losses.
- Problem: Zero-order stochastic optimization uses two function evaluations per round to minimize an expected objective when gradients are difficult or infeasible to compute.Bandit regret guarantees transfer to expected optimization-error guarantees for averaged iterates.
- Gap: Prior two-point randomized gradient methods had dimensionally suboptimal guarantees, while optimal non-smooth analyses required involved smoothing and were limited to Euclidean problems.The cited smooth-function result was optimal, but its general non-smooth extension incurred additional logarithmic dimension factors.
- Approach: The paper analyzes a simple mirror-descent algorithm using a randomized gradient estimator based on two function queries near the current point.The estimator’s expectation is a gradient of a smoothed function.
- Results: For Euclidean problems, the method is optimal up to constants for both smooth and non-smooth functions and extends readily to non-Euclidean problems.The analysis also applies to both bandit and zero-order settings and supports standard extensions such as high-probability guarantees and k > 2 observations.
- Approach: The modified estimator queries at w − δu and w + δu instead of w and w + δu, preserving gradient approximation while improving variance behavior.For non-differentiable functions, the earlier estimator can have second moment quadratic in d, whereas the modified estimator is essentially linear in d.
2 Algorithm and Main Results
The paper presents a two-point bandit algorithm using mirror descent with a modified randomized gradient estimator, and proves bounds under convexity, Lipschitzness, and regularizer assumptions. The resulting guarantees apply to Euclidean and non-Euclidean settings, match the Euclidean lower bound up to constants, and match the 1-norm lower bound up to a logarithmic factor.
- Algorithm: The algorithm performs mirror descent with a randomized estimator formed from function queries at wt + δtut and wt − δtut.The direction ut is sampled uniformly from the Euclidean unit sphere, and the estimator scales the function-value difference by d/(2δt).
- Main theorem: Theorem 1 assumes a 1-strongly convex regularizer bounded by R^2, while each ft is convex and G2-Lipschitz in the Euclidean norm.The analysis also requires additional conditions to control the estimator’s variance.
- Query feasibility: If query points leave W, running the algorithm on a slightly smaller set ensures feasible queries while adding negligible regret or error for sufficiently small exploration radii.This boundary adjustment relies on the Lipschitzness of each ft and the guarantee holding for arbitrarily small δt.
- Stochastic optimization: The regret bound immediately yields an analogous stochastic optimization error bound for the average iterate, with robustness to the step-size choice up to constants.The paper states that the same result holds when η = Θ(R/(√(dT))).
- Euclidean application: In the Euclidean setting, the resulting bound matches the lower bound in up to constants.The Euclidean specialization uses standard online gradient descent with a quadratic regularizer.
- 1-norm application: In the 1-norm setting on the simplex, the bound matches the lower bound in up to a logarithmic factor.The specialization uses an entropic regularizer whose value on the simplex is at most log(d).
3 Proof of Theorem 1
The proof combines online mirror descent with a symmetric two-point gradient estimator, whose unbiasedness and variance control yield the theorem’s guarantee.
- The proof’s key ingredient is a modified random gradient estimator with significantly lower variance than previous approaches.The improved variance behavior is established in Lemma 5.
- Online mirror descent converts the estimator’s inner-product bound into the theorem’s average-loss guarantee after taking expectations and dividing by T.
- The smoothed loss is convex, Lipschitz, and differentiable, with its gradient characterized through uniform sampling on the Euclidean unit sphere.
- Lemma 5 shows that the estimator is conditionally unbiased for the smoothed gradient and has a second moment essentially linear in dimension d.
- The variance proof uses symmetry, an elementary squared-difference inequality, Cauchy–Schwarz, and concentration for Lipschitz functions on the sphere.
A Proof of Lemma 1
Lemma 1 bounds a Gaussian-related moment using the representation of a uniform sphere vector through a normalized Gaussian vector and standard concentration and tail bounds.
- A uniformly sampled sphere vector is represented using a standard Gaussian vector normalized by its Euclidean norm.
- The proof bounds the Gaussian norm using concentration and separates events involving the infinity and Euclidean norms.
- Independence of the Gaussian coordinates enables a scalar tail-bound calculation for powers of the maximum coordinate.
- Choosing r = 4 log2(d) produces a dimension-dependent bound involving logarithmic terms in d.