Efficient online algorithms for fast-rate regret bounds under sparsity - ENS - École normale supérieure Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Efficient online algorithms for fast-rate regret bounds under sparsity

Résumé

We consider the online convex optimization problem. In the setting of arbitrary sequences and finite set of parameters, we establish a new fast-rate quantile regret bound. Then we investigate the optimization into the L1-ball by discretizing the parameter space. Our algorithm is projection free and we propose an efficient solution by restarting the algorithm on adaptive discretization grids. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependences on the sparsity of the objective. In the i.i.d. setting, we establish new risk bounds that are adaptive to the sparsity of the problem and to the regularity of the risk (ranging from a rate 1 / √ T for general convex risk to 1 /T for strongly convex risk). These results generalize previous works on sparse online learning. They are obtained under a weak assumption on the risk (Łojasiewicz's assumption) that allows multiple optima which is crucial when dealing with degenerate situations.
Fichier principal
Vignette du fichier
SABOA.pdf (591.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01798201 , version 1 (23-05-2018)

Identifiants

Citer

Pierre Gaillard, Olivier Wintenberger. Efficient online algorithms for fast-rate regret bounds under sparsity. NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems, Dec 2018, Montreal, France. ⟨hal-01798201⟩
129 Consultations
60 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More