# Optimal Stochastic Nonconvex Optimization with Bandit Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 38 references that are in the map.
- First posted on arXiv 30 Mar 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Kernel-based methods for bandit convex optimization](https://mlsanity.com/paper/1607.03084/) (2016)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Optimization of Smooth Functions with Noisy Observations: Local Minimax Rates](https://mlsanity.com/paper/1803.08586/) (2018)
- [On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits](https://mlsanity.com/paper/1609.02606/) (2016)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense](https://mlsanity.com/paper/2002.08000/) (2020)
- [Adaptive-treed bandits](https://mlsanity.com/paper/1302.2489/) (2013)
- [Cost-aware Cascading Bandits](https://mlsanity.com/paper/1805.08638/) (2018)

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

- [Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms](https://mlsanity.com/paper/2306.12383/) (2023)

## Abstract (arXiv)

In this paper, we analyze the continuous armed bandit problems for nonconvex cost functions under certain smoothness and sublevel set assumptions. We first derive an upper bound on the expected cumulative regret of a simple bin splitting method. We then propose an adaptive bin splitting method, which can significantly improve the performance. Furthermore, a minimax lower bound is derived, which shows that our new adaptive method achieves locally minimax optimal expected cumulative regret.