Black-box optimization of noisy functions with unknown smoothness

Abstract

We study the problem of black-box optimization of a function f of any dimension, given function evaluations perturbed by noise. The function is assumed to be locally smooth around one of its global optima, but this smoothness is unknown. Our contribution is an adaptive optimization algorithm, POO or parallel optimistic optimization, that is able to deal with this setting. POO performs almost as well as the best known algorithms requiring the knowledge of the smoothness. Furthermore, POO works for a larger class of functions than what was previously considered, especially for functions that are difficult to optimize, in a very precise sense. We provide a finite-time analysis of POO's performance, which shows that its error after n evaluations is at most a factor of sqrt(ln n) away from the error of the best known optimization algorithms using the knowledge of the smoothness.

Published in Neural Information Processing Systems (NeurIPS 2015)

References in corpus (5)

• Bandit Algorithms for Tree Search
• Stochastic simultaneous optimistic optimization
• Online Stochastic Optimization under Correlated Bandit Feedback
• Adaptive-treed bandits
• Unimodal Bandits without Smoothness

Cited by in corpus (22)

• Global optimization of Lipschitz functions
• Tuning Hyperparameters without Grad Students: Scalable and Robust Bayesian Optimisation with Dragonfly
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?
• Discrepancy-Based Active Learning for Domain Adaptation
• X-Armed Bandits: Optimizing Quantiles, CVaR and Other Risks
• Efficient Contextual Bandits with Continuous Actions
• A ranking approach to global optimization
• Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence
• Optimum-statistical Collaboration Towards General and Efficient Black-box Optimization
• Online Learning Demands in Max-min Fairness
• A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption
• Continuum-Armed Bandits: A Function Space Perspective
• On Regret with Multiple Best Arms
• Derivative-Free & Order-Robust Optimisation
• High-dimensional Black-box Optimization Under Uncertainty
• Bandits with many optimal arms
• Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
• Pareto Optimal Model Selection in Linear Bandits
• Testing a Battery Management System via Criticality-based Rare Event Simulation
• The sample complexity of level set approximation
• Verification and Parameter Synthesis for Stochastic Systems using Optimistic Optimization