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

Peter Bartlett 1 Victor Gabillon 2 Michal Valko 3
3 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We study the problem of optimizing a function under a budgeted number of evaluations. We only assume that the function is locally smooth around one of its global optima. The difficulty of optimization is measured in terms of 1) the amount of 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 agnostic to the values of both b and d. This leads to the first algorithm that naturally adapts to an 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 deter-ministic 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 algo-rithmic improvement is also borne out in the numerical experiments, where we empirically show faster convergence on common benchmark functions.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01885368
Contributor : Michal Valko <>
Submitted on : Monday, October 1, 2018 - 6:14:01 PM
Last modification on : Friday, June 28, 2019 - 3:01:16 PM
Long-term archiving on : Wednesday, January 2, 2019 - 3:37:58 PM

File

sequool.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01885368, version 1

Collections

Citation

Peter Bartlett, Victor Gabillon, Michal Valko. A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. Algorithmic Learning Theory, Mar 2019, Chicago, United States. ⟨hal-01885368v1⟩

Share

Metrics

Record views

101

Files downloads

70