Online convex optimization in the bandit setting: gradient descent without a gradient
read the original abstract
We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a signle point (from some feasible set) and pay a cost equal to the value of the next function on our chosen point. Zinkevich shows that, if the each function is revealed after the choice is made, then one can achieve vanishingly small regret relative the best single decision chosen in hindsight. We extend this to the bandit setting where we do not find out the entire functions but rather just their value at our chosen point. We show how to get vanishingly small regret in this setting. Our approach uses a simple approximation of the gradient that is computed from evaluating a function at a single (random) point. We show that this estimate is sufficient to mimic Zinkevich's gradient descent online analysis, with access to the gradient (only being able to evaluate the function at a single point).
This paper has not been read by Pith yet.
Forward citations
Cited by 14 Pith papers
-
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
Prudent-Banker achieves pseudo-regret Õ(√T + √D) and Õ(1) regret vs. safe comparator in adversarial bandits both with and without delays, matching new lower bounds up to logs.
-
Bandit Convex Optimization with Gradient Prediction Adaptivity
TP-VR-OPT achieves O(√(d E[S_T])) prediction-adaptive regret in two-point bandit convex optimization, with a matching Ω(√E[S_T]) lower bound up to √d, while single-point feedback cannot benefit from predictions.
-
Online Conformal Prediction with Corrupted Feedback
Develops robust online conformal prediction schemes that provide explicit miscoverage guarantees under feedback modeled as arbitrary binary flips or bounded-memory errors.
-
Select-then-differentiate: Solving Bilevel Optimization with Manifold Lower-level Solution Sets
Optimistic bilevel optimization with manifold lower-level minimizers is differentiable if the optimistic selection is unique, yielding a pseudoinverse hyper-gradient and a convergent HG-MS algorithm whose rate depends...
-
NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning
NePPO learns a player-independent potential function via a novel objective whose minimization yields an approximate Nash equilibrium for general-sum multi-agent games.
-
Baryon-antibaryon photoproduction cross sections off the proton
GlueX measured total and differential cross sections for baryon-antibaryon photoproduction, finding forward-peaked distributions consistent with t-channel exchange, a phenomenological double-exchange model fit, and no...
-
Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise
RSC-ZO achieves high-probability ε-stationary points for stochastic ZO optimization under weak-L_p heavy-tailed noise with Õ(d^{p/2(p-1)} ε^{-(3p-2)/(p-1)}) function queries.
-
Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing
Recasts sampling-based nonconvex optimization as smoothed gradient descent to obtain non-asymptotic convergence guarantees and introduces the DIDA annealed algorithm that converges to the global optimum.
-
Ensemble Distributionally Robust Bayesian Optimisation
A tractable ensemble distributionally robust Bayesian optimization method achieves improved sublinear regret bounds under context uncertainty.
-
OGPO: Sample Efficient Full-Finetuning of Generative Control Policies
OGPO is a sample-efficient off-policy method for full finetuning of generative control policies that reaches SOTA on robotic manipulation tasks and can recover from poor behavior-cloning initializations without expert data.
-
Policy Optimization for Unknown Systems using Differentiable Model Predictive Control
Hybrid differentiable-plus-zeroth-order policy optimization for MPC yields faster transients than pure data-driven methods while retaining convergence guarantees under model mismatch, demonstrated on a 12D quadcopter.
-
Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Introduces a novel search direction enabling sublinear stochastic bilevel regret guarantees for first- and zeroth-order online bilevel optimization algorithms without relying on window smoothing.
-
Inference-Time Scaling for Diffusion Models beyond Scaling Denoising Steps
Diffusion models improve generation quality via inference-time search over noise candidates guided by verifiers and algorithms, yielding gains beyond denoising step scaling on class- and text-conditioned benchmarks.
-
Position: Zeroth-Order Optimization in Deep Learning Is Underexplored, Not Underpowered
Zeroth-order optimization is underexplored rather than underpowered in deep learning, with limitations stemming from full-space designs that can be addressed via subspace, spectral, and systems-aware approaches.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.