General parallel optimization without a metric

Xuedong Shang 1 Emilie Kaufmann 2, 1 Michal Valko 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Hierarchical bandits are an approach for global optimization of extremely irregular functions. This paper provides new elements regarding POO, an adaptive meta-algorithm that does not require the knowledge of local smoothness of the target function. We first highlight the fact that the subroutine algorithm used in POO should have a small regret under the assumption of local smoothness with respect to the chosen partitioning, which is unknown if it is satisfied by the standard subroutine HOO. In this work, we establish such regret guarantee for HCT, which is another hierarchical optimistic optimization algorithm that needs to know the smoothness. This confirms the validity of POO. We show that POO can be used with HCT as a subroutine with a regret upper bound that matches the one of best-known algorithms using the knowledge of smoothness up to a √ log n factor. On top of that, we propose a general wrapper, called GPO, that can cope with algorithms that only have simple regret guarantees. Finally, we complement our findings with experiments on difficult functions.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-02047225
Contributor : Xuedong Shang <>
Submitted on : Tuesday, March 5, 2019 - 6:48:10 PM
Last modification on : Friday, March 22, 2019 - 1:37:20 AM
Long-term archiving on : Thursday, June 6, 2019 - 5:31:12 PM

File

shang2019general.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02047225, version 2

Collections

Citation

Xuedong Shang, Emilie Kaufmann, Michal Valko. General parallel optimization without a metric. Algorithmic Learning Theory, 2019, Chicago, United States. ⟨hal-02047225v2⟩

Share

Metrics

Record views

167

Files downloads

172