Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization

Résumé Technique : Bornes de Regret à Haute Probabilité Adaptatives au Bruit pour l'Optimisation Convexe en Ligne

Énoncé du Problème
Ce travail traite du problème de l'Optimisation Convexe en Ligne (OCO) sous trois défis distincts mais interconnectés : (1) l'obtention de bornes de regret à haute probabilité adaptatives au bruit pour les pertes fortement convexes dans le cadre de l'information complète ; (2) la détermination du coût de confiance fondamental (dépendance vis-à-vis de la probabilité d'échec $\delta$) lors du passage de l'information complète au feedback de type bandit ; et (3) l'établissement de garanties simultanées à haute probabilité pour le regret cumulé et la violation de contraintes à long terme dans l'OCO contraint avec des contraintes stochastiques.

Alors que les résultats classiques établissent que la Descente de Gradient en Ligne (OGD) atteint un regret attendu de $O(\frac{G^2}{\alpha} \log T)$ pour des pertes $\alpha$-fortement convexes (où $G$ borne les normes des gradients), les garanties à haute probabilité sont souvent insuffisamment serrées pour les applications critiques de sécurité. Les approches standards reposent sur l'inégalité d'Azuma-Hoeffding, qui produit un terme de déviation de martingale dépendant de la borne de gradient la plus défavorable $G$ et du diamètre du domaine $D$ (spécifiquement $GD\sqrt{2T \log(1/\delta)}$). Cette borne est lâche lorsque le niveau de bruit stochastique réel $\sigma$ est nettement inférieur à $G$, un régime courant dans la minimisation du risque empirique régularisé. De plus, la littérature existante manque d'un traitement unifié de l'adaptativité au bruit, des différences de structure de feedback et de la satisfaction de contraintes à haute probabilité.

Méthodologie et Contributions Clés

L'article résout trois questions ouvertes grâce à de nouveaux arguments de concentration et des constructions de bornes inférieures :

1. Bornes à Haute Probabilité Adaptatives au Bruit (Information Complète) :
   Les auteurs prouvent que l'OGD projetée avec un pas $\eta_t = 1/(\alpha t)$ atteint une borne de regret à haute probabilité où la déviation de la martingale dépend du niveau de bruit $\sigma$ plutôt que de la borne du gradient $G$.

   • Méthodologie : L'analyse introduit un argument de supermartingale exponentielle adapté aux séquences conditionnellement sub-gaussiennes. Cette technique contourne l'exigence de différence bornée inhérente à l'inégalité de Freedman, qui nécessite généralement la troncature de bruits sub-gaussiens non bornés. En évitant la troncature, les auteurs préservent la propriété de martingale et dérivent une borne où le terme de déviation est $O(\sigma D \sqrt{T \log(1/\delta)})$.
   • Résultat : La borne de regret est $O(\frac{G^2}{\alpha} \log T + \sigma D \sqrt{T \log(1/\delta)})$. Cela produit une amélioration multiplicative de $G/\sigma$ par rapport à la référence classique d'Azuma-Hoeffding lorsque $\sigma \ll G$. La preuve utilise des budgets de probabilité indépendants pour séparer la troncature des normes de gradient de la concentration de la queue de la martingale.

2. Séparation du Coût de Confiance (Bandit vs Information Complète) :
   L'article établit une borne inférieure minimax démontrant une séparation fondamentale dans le coût de confiance entre les contextes de feedback d'information complète et de bandit pour l'OCO fortement convexe.

   • Méthodologie : En utilisant une construction basée sur des époques avec un bruit gaussien additif, les auteurs appliquent le lemme de Bretagnolle-Huber et des arguments de couplage conditionnel pour construire un cas difficile.
   • Résultat : Dans le cadre de l'information complète, le regret à haute probabilité évolue en $\sqrt{\log(1/\delta)}$. En revanche, sous un feedback de type bandit (où seules les valeurs scalaires de perte sont observées), le regret évolue linéairement en $\log(1/\delta)$. Cela constitue la première preuve formelle que le coût informationnel de la confiance est strictement plus élevé dans le cadre bandit pour les problèmes fortement convexes.

3. Garanties Simultanées à Haute Probabilité (OCO Contraint) :
   Les auteurs fournissent le premier algorithme permettant de contrôler simultanément, à haute probabilité, le regret cumulé et la violation de contraintes à long terme sous des contraintes stochastiques satisfaisant une condition de Slater.

   • Méthodologie : L'analyse emploie un cadre OGD primal-dual. La borne de regret exploite l'inégalité de Freedman (applicable en raison du caractère presque sûrement borné du bruit de contrainte). L'analyse de la violation de contrainte décompose la violation cumulée en une composante attendue et une composante de martingale stochastique. La composante attendue est bornée via un argument de point de selle et l'inégalité de Markov, tandis que la composante stochastique est contrôlée via l'inégalité de Freedman.
   • Résultat : L'algorithme atteint un regret de $O(\sqrt{T \log(m/\delta)})$ et une violation de contrainte à long terme de $O(\frac{\sqrt{T}}{\zeta \delta_1} + m\sqrt{T \log(m/\delta_2)})$. Notamment, la borne de violation conserve un facteur $1/\delta$ pour la composante attendue (via l'inégalité de Markov), tandis que la déviation stochastique évolue en $\sqrt{\log(1/\delta)}$.

Validation Expérimentale
Des expériences synthétiques corroborent les prédictions théoriques :

• Adaptativité au Bruit : Les statistiques de queue empiriques confirment que les quantiles de regret suivent la borne adaptative au bruit ($\sigma$-dépendante) et restent bien en dessous de la référence d'Azuma-Hoeffding ($G$-dépendante) lorsque $\sigma \ll G$.
• Coût de Confiance : Des expériences sur des problèmes fortement convexes en 1D démontrent que le regret d'information complète croît en $\sqrt{\log(1/\delta)}$, tandis que le regret de bandit croît linéairement en $\log(1/\delta)$, validant la séparation informationnelle.
• OCO Contraint : Les distributions conjointes de regret et de violation confirment le budget de probabilité indépendant et l'évolution inversement linéaire de la violation avec le gap de Slater $\zeta$.

Signification et Revendications
L'article affirme résoudre trois questions ouvertes spécifiques à l'intersection de l'adaptativité au bruit, de la structure de feedback et de la satisfaction de contraintes dans l'OCO fortement convexe.

• Il fournit un affinement de l'adaptativité au bruit des bornes à haute probabilité, montrant que le "prix de la confiance" peut être découplé de la magnitude de la norme de gradient la plus défavorable et lié au niveau de bruit réel.
• Il établit une séparation formelle dans les coûts de confiance, prouant que le feedback de type bandit incorpore une pénalité linéaire $\log(1/\delta)$ comparée à la pénalité de racine carrée $\sqrt{\log(1/\delta)}$ de l'information complète.
• Il offre les premières garanties simultanées à haute probabilité pour le regret et la violation de contrainte dans le cadre stochastique contraint, clarifiant les mécanismes statistiques (Markov vs Freedman) régissant chaque composante.

Les auteurs notent que la dépendance en $1/\delta$ dans la borne de violation de contrainte est serrée pour la technique de preuve actuelle (reposant sur l'inégalité de Markov pour la composante attendue), et que l'amélioration de celle-ci en $\log(1/\delta)$ reste un problème ouvert nécessitant un contrôle par chemin de l'inégalité de point de selle primal-dual. De même, l'extension de l'adaptativité au bruit aux contextes bandit avec des interactions biais-supermartingale non triviales est identifiée comme une direction pour les travaux futurs.