# Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 24 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [A Contextual Bandit Bake-off](https://mlsanity.com/paper/1802.04064/) (2018)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [Multi-scale exploration of convex functions and bandit convex optimization](https://mlsanity.com/paper/1507.06580/) (2015)
- [An optimal algorithm for bandit convex optimization](https://mlsanity.com/paper/1603.04350/) (2016)
- [Projection-Free Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018)
- [Towards Gradient Free and Projection Free Stochastic Optimization](https://mlsanity.com/paper/1810.03233/) (2018)
- [On the Complexity of Bandit Linear Optimization](https://mlsanity.com/paper/1408.2368/) (2014)

## Built on by (most cited first, 3 of 3)

- [Minimax Regret for Bandit Convex Optimisation of Ridge Functions](https://mlsanity.com/paper/2106.00444/) (2021)
- [Adaptive Bandit Convex Optimization with Heterogeneous Curvature](https://mlsanity.com/paper/2202.06150/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)

## Abstract (arXiv)

We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions ft admit a "pseudo-1d" structure, i.e. ft(w) = losst(predt(w)) where the output of predt is one-dimensional. At each round, the learner observes context xt, plays prediction predt(wt; xt) (e.g. predt(·)=langle xt, ·rangle) for some wt ∈ ℝd and observes loss losst(predt(wt)) where losst is a convex Lipschitz-continuous function. The goal is to minimize the standard regret metric. This pseudo-1d bandit convex optimization problem (SBCO) arises frequently in domains such as online decision-making or parameter-tuning in large systems. For this problem, we first show a lower bound of min(√dT, T3/4) for the regret of any algorithm, where T is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively, guaranteeing the em optimal regret bound mentioned above, up to additional logarithmic factors. In contrast, applying state-of-the-art online convex optimization methods leads to tildeOleft(minleft(d9.5√T,√dT3/4right)right) regret, that is significantly suboptimal in d.