mlsanityData to 14 Oct 2026

Multi-scale exploration of convex functions and bandit convex optimization

arXiv 1507.06580 ↗First posted 23 Jul 2015math.MG cs.LG math.OCcited by 20

Not on the map. Why?

Abstract (arXiv)

We construct a new map from a convex function to a distribution on its domain, with the property that this distribution is a multi-scale exploration of the function. We use this map to solve a decade-old open problem in adversarial bandit convex optimization by showing that the minimax regret for this problem is tildeO(poly(n) √T), where n is the dimension and T the number of rounds. This bound is obtained by studying the dual Bayesian maximin regret via the information ratio analysis of Russo and Van Roy, and then using the multi-scale exploration to solve the Bayesian problem.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 6; 2022: 3; 2023: 4; 2024: 3; 2025: 1; 2026: 2.

20 papers.

Sort:

By area:

  1. 2021Reinforcement Learning, Bit by Bitcited by 59
  2. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  3. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  4. 2021No Weighted-Regret Learning in Adversarial Bandits with Delayscited by 12
  5. 2023An Information-Theoretic Analysis of Nonstationary Bandit Learningcited by 11
  6. 2022An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regretcited by 10
  7. 2024Improved Regret for Bandit Convex Optimization with Delayed Feedbackcited by 8
  8. 2023Statistical Complexity and Optimal Algorithms for Non-linear Ridge Banditscited by 7
  9. 2021From the Greene--Wu Convolution to Gradient Estimation over Riemannian Manifoldscited by 6
  10. 2021Zeroth-order non-convex learning via hierarchical dual averagingcited by 6
  11. 2022Gaussian Imagination in Bandit Learningcited by 5
  12. 2021Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimizationcited by 3
8 more
  1. 2026A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guaranteescited by 3
  2. 2022Adaptive Bandit Convex Optimization with Heterogeneous Curvaturecited by 2
  3. 2023Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatmentscited by 2
  4. 2020Distilled Thompson Sampling: Practical and Efficient Thompson Sampling via Imitation Learningcited by 1
  5. 2024A Bayesian Approach to Online Planningcited by 1
  6. 2025Multi-Agent Stage-wise Conservative Linear Banditscited by 1
  7. 2026Capacity-Constrained Online Convex Optimization with Delayed Feedbackcited by 1
  8. 2024Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regretcited by 0