# Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 17 Jun 2021.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption](https://mlsanity.com/paper/1810.00997/) (2018)
- [Online Forgetting Process for Linear Regression Models](https://mlsanity.com/paper/2012.01668/) (2020)
- [Residual Bootstrap Exploration for Bandit Algorithms](https://mlsanity.com/paper/2002.08436/) (2020)
- [Online Stochastic Optimization under Correlated Bandit Feedback](https://mlsanity.com/paper/1402.0562/) (2014)
- [Global Continuous Optimization with Error Bound and Fast Convergence](https://mlsanity.com/paper/1607.04817/) (2016)
- [Online Batch Decision-Making with High-Dimensional Covariates](https://mlsanity.com/paper/2002.09438/) (2020)

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

- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Federated X-Armed Bandit](https://mlsanity.com/paper/2205.15268/) (2022)
- [PyXAB -- A Python Library for X-Armed Bandit and Online Blackbox Optimization Algorithms](https://mlsanity.com/paper/2303.04030/) (2023)
- [Federated Online Sparse Decision Making](https://mlsanity.com/paper/2202.13448/) (2022)
- [Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributions](https://mlsanity.com/paper/2402.15188/) (2024)
- [Personalized Federated X -armed Bandit](https://mlsanity.com/paper/2310.16323/) (2023)

## Abstract (arXiv)

In this paper, we make the key delineation on the roles of resolution and statistical uncertainty in hierarchical bandits-based black-box optimization algorithms, guiding a more general analysis and a more efficient algorithm design. We introduce the textitoptimum-statistical collaboration, an algorithm framework of managing the interaction between optimization error flux and statistical error flux evolving in the optimization process. We provide a general analysis of this framework without specifying the forms of statistical error and uncertainty quantifier. Our framework and its analysis, due to their generality, can be applied to a large family of functions and partitions that satisfy different local smoothness assumptions and have different numbers of local optimums, which is much richer than the class of functions studied in prior works. Our framework also inspires us to propose a better measure of the statistical uncertainty and consequently a variance-adaptive algorithm textttVHCT. In theory, we prove the algorithm enjoys rate-optimal regret bounds under different local smoothness assumptions; in experiments, we show the algorithm outperforms prior efforts in different settings.