REVIEW 26 cited by
Online convex optimization in the bandit setting: gradient descent without a gradient
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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).
Forward citations
Cited by 26 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.
-
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...
-
Efficient Controllable Diffusion via Optimal Classifier Guidance
SLCD provably converges, under no-regret learning and a strong score-estimation assumption, to the KL-regularized optimal distribution using only supervised classification oracles.
-
Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
A continuized zeroth-order Nesterov method achieves O(d/√ε) function-evaluation complexity for smooth quasar-convex minimization, with improved dimension dependence under a 1-norm mirror step when the solution is sparse.
-
Leveraging Similarities in Multi-Armed Bandits
Impossibility result for one-point feedback in tree-structured bandits plus algorithms for multi-point feedback achieving best-of-both-worlds regret with effective action count K_eff, including √T regret for d≤2 Lipsc...
-
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Establishes a noise-adaptive high-probability regret bound scaling with noise level σ for full-info OCO, a linear log(1/δ) lower bound for bandit feedback, and joint regret-violation bounds for constrained OCO.
-
Double Preconditioning (DoPr): Optimization for Test-Time Performance, not Validation Loss
Double preconditioning (DoPr) improves downstream task performance in test-time feedback settings without consistent gains in validation loss.
-
ZOAF: Towards Efficient Zeroth-Order Optimization for Analog/RF Circuit Design
ZOAF recovers gradient-descent directions from few black-box simulations via hybrid scheduling and multi-start, outperforming baselines on three schematics with 1.3-3.8x fewer calls.
-
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.
-
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.
-
Rewriting the Budget: A General Framework for Black-Box Attacks Under Cost Asymmetry
A framework that adapts the search and gradient-estimation steps of decision-based attacks to minimize total cost under arbitrary ratios of high-cost to low-cost queries.
-
Estimating the Effects of Sample Training Orders for Large Language Models without Retraining
A framework using Taylor expansions and random projections estimates LLM performance under arbitrary training batch orders from one reference run.
-
Coreset-Based Task Selection for Sample-Efficient Meta-Reinforcement Learning
A derivative-free coreset task-selection algorithm for MAML-RL trains on a small weighted task subset and provably reduces sample complexity by O(1/epsilon), provided the task-selection bias is small.
-
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.
-
Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning
AdaNAGED combines zeroth-order gradient-free training, automatic parameter adaptation, and LMO-based non-Euclidean geometry with claimed convergence guarantees, demonstrated on OPT-1.3B fine-tuning.
-
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.
-
A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
POEM is a parameter-free stochastic zeroth-order method that adapts both step size and smoothing automatically and reaches near-optimal oracle complexity.
-
Refining Adaptive Zeroth-Order Optimization at Ease
R-AdaZO changes the second-moment update of adaptive zeroth-order optimization to use the smoothed first moment instead of the raw gradient estimate, with a new variance-aware convergence analysis and faster empirical...
-
Accelerated zero-order SGD under high-order smoothness and overparameterized regime
A kernel-based accelerated zero-order SGD method is introduced for convex stochastic optimization under higher-order smoothness and overparameterization, with convergence guarantees under deterministic and stochastic ...
-
DistZO2: High-Throughput and Memory-Efficient Zeroth-Order Fine-tuning LLMs with Distributed Parallel Computing
DistZO2 distributes ZO2's dual perturbed forward passes and scalar gradients across GPUs, achieving up to 3x throughput over ZO2 on OPT-175B while keeping per-GPU memory near 19GB.
-
What Makes Local Updates Effective: The Role of Data Heterogeneity and Smoothness
Under bounded second-order heterogeneity, local updates are shown to achieve faster convergence than mini-batch SGD in several convex and non-convex regimes, with matching lower bounds.
Discussion (0). Continue with ORCID to comment.