1. Polynomial Cost of Adaptation for X -Armed Bandits
- Author
-
Hadiji, H��di
- Subjects
FOS: Computer and information sciences ,FOS: Mathematics ,Machine Learning (stat.ML) ,Statistics Theory (math.ST) ,Machine Learning (cs.LG) - Abstract
In the context of stochastic continuum-armed bandits, we present an algorithm that adapts to the unknown smoothness of the objective function. We exhibit and compute a polynomial cost of adaptation to the H{��}lder regularity for regret minimization. To do this, we first reconsider the recent lower bound of Locatelli and Carpentier [20], and define and characterize admissible rate functions. Our new algorithm matches any of these minimal rate functions. We provide a finite-time analysis and a thorough discussion about asymptotic optimality.
- Published
- 2019
- Full Text
- View/download PDF