An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback

By Ohad Shamir. Journal of machine learning research, 2015

324 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/436445b4cf3fe25e5778b5838eb623accad428e5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, result): “These central difference estimates have similar approximation errors to the forward difference estimates [31], [34], [35].”
Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective (2019, background): “Proof [Proof of Lemma 6] From Shamir (2017), we know that g i is an unbiased estimate of the gradient of ˆ J ( θ i ), i.e. u i ∼ S d [ g i ] = ∇ ˆ J ( θ i ).”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, background): “Most works (Nesterov & Spokoiny, 2011; Ghadimi & Lan, 2013; Shamir, 2017) use the gradient of a smoothed version of the objective function through a two-point feedback in a stochastic setting.”
Fine-Tuning Language Models with Just Forward Passes (2023, background): “Zeroth-order optimization Many classical lower bounds have been derived for ZO-SGD in the strongly convex and convex settings [47, 3, 79, 32, 85, 69] as well as non-convex [101].”
A Survey of Preference-Based Reinforcement Learning Methods (2017, methodology): “Related to dueling bandits is the use of two-point feedback for online convex optimization (Agarwal et al., 2010; Shamir, 2017), which has recently been extended to structured prediction problems (Sokolov et al., 2016).”