# Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 21 Jun 2023.

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

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [Stochastic Rank-1 Bandits](https://mlsanity.com/paper/1608.03023/) (2016)
- [Stochastic Linear Bandits with Hidden Low Rank Structure](https://mlsanity.com/paper/1901.09490/) (2019)
- [Optimal Gradient-based Algorithms for Non-concave Bandit Optimization](https://mlsanity.com/paper/2107.04518/) (2021)
- [Low-rank Bandits with Latent Mixtures](https://mlsanity.com/paper/1609.01508/) (2016)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Bandit Principal Component Analysis](https://mlsanity.com/paper/1902.03035/) (2019)
- [Structured Stochastic Linear Bandits](https://mlsanity.com/paper/1606.05693/) (2016)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)

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

- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity](https://mlsanity.com/paper/2406.19617/) (2024)

## Abstract (arXiv)

In stochastic zeroth-order optimization, a problem of practical relevance is understanding how to fully exploit the local geometry of the underlying objective function. We consider a fundamental setting in which the objective function is quadratic, and provide the first tight characterization of the optimal Hessian-dependent sample complexity. Our contribution is twofold. First, from an information-theoretic point of view, we prove tight lower bounds on Hessian-dependent complexities by introducing a concept called energy allocation, which captures the interaction between the searching algorithm and the geometry of objective functions. A matching upper bound is obtained by solving the optimal energy spectrum. Then, algorithmically, we show the existence of a Hessian-independent algorithm that universally achieves the asymptotic optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions, which are enabled by a truncation method.