# Kernel-based methods for bandit convex optimization

arXiv: https://arxiv.org/abs/1607.03084 · HTML: https://mlsanity.com/paper/1607.03084/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2016.

## Built on by (most cited first, 30 of 63)

- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression](https://mlsanity.com/paper/2211.07484/) (2022)
- [Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2301.08215/) (2023)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games](https://mlsanity.com/paper/2103.04539/) (2021)
- [No Weighted-Regret Learning in Adversarial Bandits with Delays](https://mlsanity.com/paper/2103.04550/) (2021)
- [Online Newton Method for Bandit Convex Optimisation](https://mlsanity.com/paper/2406.06506/) (2024)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [On Adaptivity in Non-stationary Stochastic Optimization With Bandit Feedback](https://mlsanity.com/paper/2210.05584/) (2022)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret](https://mlsanity.com/paper/2209.11817/) (2022)
- [A Second-Order Method for Stochastic Bandit Convex Optimisation](https://mlsanity.com/paper/2302.05371/) (2023)
- [Building Robust Ensembles via Margin Boosting](https://mlsanity.com/paper/2206.03362/) (2022)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [A gradient estimator via L1-randomization for online zero-order optimization with two point feedback](https://mlsanity.com/paper/2205.13910/) (2022)
- [Statistical Complexity and Optimal Algorithms for Non-linear Ridge Bandits](https://mlsanity.com/paper/2302.06025/) (2023)
- [Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability](https://mlsanity.com/paper/2506.10616/) (2025)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Online Convex Optimization with Unbounded Memory](https://mlsanity.com/paper/2210.09903/) (2022)
- [Anytime Model Selection in Linear Bandits](https://mlsanity.com/paper/2307.12897/) (2023)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization](https://mlsanity.com/paper/2102.07387/) (2021)
- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)

## Abstract (arXiv)

We consider the adversarial convex bandit problem and we build the first poly(T)-time algorithm with poly(n) √T-regret for this problem. To do so we introduce three new ideas in the derivative-free optimization literature: (i) kernel methods, (ii) a generalization of Bernoulli convolutions, and (iii) a new annealing schedule for exponential weights (with increasing learning rate). The basic version of our algorithm achieves tildeO(n9.5 √T)-regret, and we show that a simple variant of this algorithm can be run in poly(n log(T))-time per step at the cost of an additional poly(n) To(1) factor in the regret. These results improve upon the tildeO(n11 √T)-regret and exp(poly(T))-time result of the first two authors, and the log(T)poly(n) √T-regret and log(T)poly(n)-time result of Hazan and Li. Furthermore we conjecture that another variant of the algorithm could achieve tildeO(n1.5 √T)-regret, and moreover that this regret is unimprovable (the current best lower bound being Omega(n √T) and it is achieved with linear functions). For the simpler situation of zeroth order stochastic convex optimization this corresponds to the conjecture that the optimal query complexity is of order n3 / ε2.