Stochastic simultaneous optimistic optimization
arXiv:2604.24537
Abstract
We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
Published in International Conference on Machine Learning (ICML 2013)
References in corpus (1)
Cited by in corpus (28)
- Bayesian Multi-Scale Optimistic Optimization
- Global optimization of Lipschitz functions
- Black-box optimization of noisy functions with unknown smoothness
- Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem
- Online Stochastic Optimization under Correlated Bandit Feedback
- Adaptive-treed bandits
- On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization
- Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?
- Learning to Optimize Via Posterior Sampling
- Discrepancy-Based Active Learning for Domain Adaptation
- Copeland Dueling Bandits
- Exploiting correlation and budget constraints in Bayesian multi-armed bandit optimization
- X-Armed Bandits: Optimizing Quantiles, CVaR and Other Risks
- Global Continuous Optimization with Error Bound and Fast Convergence
- Adaptive Block Coordinate DIRECT algorithm
- Provably adaptive reinforcement learning in metric spaces
- A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
- Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization
- Derivative-Free & Order-Robust Optimisation
- Multi-Objective Simultaneous Optimistic Optimization
- On Regret with Multiple Best Arms
- Best Arm Identification with Safety Constraints
- Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
- Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach
- Fast Rate Learning in Stochastic First Price Bidding
- A Simple Heuristic for Bayesian Optimization with A Low Budget
- Verification and Parameter Synthesis for Stochastic Systems using Optimistic Optimization
- Bayesian Optimistic Optimisation with Exponentially Decaying Regret