A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption

Abstract

We study the problem of optimizing a function under a \emph{budgeted number of evaluations}. We only assume that the function is \emph{locally} smooth around one of its global optima. The difficulty of optimization is measured in terms of 1) the amount of \emph{noise} $b$ of the function evaluation and 2) the local smoothness, $d$, of the function. A smaller $d$ results in smaller optimization error. We come with a new, simple, and parameter-free approach. First, for all values of $b$ and $d$, this approach recovers at least the state-of-the-art regret guarantees. Second, our approach additionally obtains these results while being \textit{agnostic} to the values of both $b$ and $d$. This leads to the first algorithm that naturally adapts to an \textit{unknown} range of noise $b$ and leads to significant improvements in a moderate and low-noise regime. Third, our approach also obtains a remarkable improvement over the state-of-the-art SOO algorithm when the noise is very low which includes the case of optimization under deterministic feedback ($b=0$). There, under our minimal local smoothness assumption, this improvement is of exponential magnitude and holds for a class of functions that covers the vast majority of functions that practitioners optimize ($d=0$). We show that our algorithmic improvement is borne out in experiments as we empirically show faster convergence on common benchmarks.

References in corpus (12)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Bandit Algorithms for Tree Search
• The best of both worlds: stochastic and adversarial bandits
• Follow the Leader If You Can, Hedge If You Must
• Stochastic simultaneous optimistic optimization
• Bayesian Optimization with Exponential Convergence
• Bayesian Multi-Scale Optimistic Optimization
• Black-box optimization of noisy functions with unknown smoothness
• Exponential Regret Bounds for Gaussian Process Bandits with Deterministic Observations
• Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and Holder constants
• Online Stochastic Optimization under Correlated Bandit Feedback
• Infinite dimensional optimistic optimisation with applications on physical systems

Cited by in corpus (2)

• On Regret with Multiple Best Arms
• Pareto Optimal Model Selection in Linear Bandits