KERDREUX Thomas

Les algorithmes de bandits linéaires produisent des limites de pseudo-retour de $\tilde{\mathcal{O}}(n\sqrt{T})$ sur des ensembles d'action convexes compacts $\mathcal{K}\subset\mathbb{R}^n$ et deux types d'hypothèses structurelles conduisent à de meilleures limites de pseudo-retour. Lorsque $\mathcal{K}$ est le simplexe ou une boule $\ell_p$ avec $p\in]1,2]$, il existe des algorithmes de bandits avec des limites de pseudo-retour de $\tilde{\mathcal{O}}(\sqrt{nT})$. Ici, nous dérivons des algorithmes de bandits pour certains ensembles fortement convexes au-delà de $\ell_p$ boules qui bénéficient de limites de pseudo-regret de $\tilde{\mathcal{O}}(\sqrt{nT})$, ce qui répond à une question ouverte de [BCB12, \S 5.5.]. Il est intéressant de noter que lorsque l'ensemble d'actions est uniformément convexe mais pas nécessairement fortement convexe, nous obtenons des bornes de pseudo-regret avec une dépendance de dimension plus petite que $\mathcal{O}(\sqrt{n})$. Cependant, cela se fait au détriment de taux asymptotiques en $T$ variant entre $\tilde{\mathcal{O}}(\sqrt{T})$ et $\tilde{\mathcal{O}}(T)$.

Nous passons en revue diverses caractérisations de la convexité uniforme et du lissage sur les boules de normes dans les espaces de dimension finie et nous connectons les résultats issus de la géométrie des espaces de Banach avec les \textit{inégalités d'échelle} utilisées dans l'analyse de la convergence des méthodes d'optimisation. En particulier, nous établissons des versions locales de ces conditions afin de fournir un aperçu plus précis d'un ensemble récent de résultats de complexité en théorie de l'apprentissage, en apprentissage en ligne ou en optimisation hors ligne, qui reposent sur la forte convexité de l'ensemble réalisable. Bien qu'elles aient un impact significatif sur la complexité, ces propriétés de forte convexité ou de convexité uniforme des ensembles réalisables ne sont pas exploitées de manière aussi approfondie que leurs équivalents fonctionnels, et ce travail est un effort pour corriger ce déséquilibre. Nous concluons par quelques exemples pratiques en optimisation et en apprentissage automatique où l'exploitation de ces conditions et des hypothèses localisées conduit à de nouveaux résultats de complexité.

Les algorithmes de Frank-Wolfe sont des méthodes d’optimisation de problèmes sous contraintes. Elles décomposent un problème non-linéaire en une série de problèmes linéaires. Cela en fait des méthodes de choix pour l’optimisation en grande dimension et notamment explique leur utilisation dans de nombreux domaines appliqués. Ici nous proposons de nouveaux algorithmes de Frank-Wolfe qui convergent plus rapidement vers la solution du problème d’optimisation sous certaines hypothèses structurelles assez génériques. Nous montrons en particulier, que contrairement à d’autres types d’algorithmes, cette famille s’adapte à ces hypothèses sans avoir à spécifier les paramètres qui les contrôlent.

Les algorithmes de Frank-Wolfe, aussi appelés algorithmes de gradient conditionnel, résolvent des problèmes d'optimisation sous contraintes. Ils décomposent un problème non linéaire en une série de minimisations linéaires sur l'ensemble des contraintes. Ceci contribue à leur récent renouveau dans de nombreux domaines appliqués, en particulier ceux impliquant des problèmes d'optimisation à grande échelle. Dans cette thèse, nous concevons et analysons des versions des algorithmes de Frank-Wolfe. Nous montrons notamment que, contrairement à d'autres types d'algorithmes, cette famille est adaptative à un large spectre d'hypothèses structurelles, sans qu'il soit nécessaire de connaître et de spécifier les paramètres contrôlant ces hypothèses.