Online Convex Optimization with Sublinear Noisy Probes

Résumé Technique : Optimisation Convexe en Ligne avec Sondes Bruyantes Sous-linéaires

Formulation du Problème
Cet article étudie l'optimisation convexe en ligne (OCO) sur un ensemble convexe $K \subseteq \mathbb{R}^d$. Dans le cadre standard, un apprenant choisit une décision $x_t \in K$ à chaque tour $t$, subit une perte convexe $f_t(x_t)$ choisie de manière adversarielle, et reçoit un retour complet (la fonction $f_t$ ou ses sous-gradients). L'objectif est de minimiser le regret par rapport à la meilleure décision fixe a posteriori.

Les auteurs introduisent un modèle de sondage (probing) unifié qui généralise deux lignes de travaux récentes : les requêtes de meilleur expert sous-linéaires dans le cadre des experts [Russo et al., 2024] et le retour par comparaison de paires dans l'OCO [Bhaskara et al., 2023b]. Dans ce cadre, l'apprenant dispose d'un budget de $k \le T$ sondes par paires. Lors d'un tour de sondage, avant de sélectionner $x_t$, l'apprenant peut interroger deux points $\{y_{t,1}, y_{t,2}\} \subseteq K$ et reçoit une indication sur le point qui présente la perte la plus faible. Crucialement, ces sondes sont bruyantes : avec une probabilité $\delta$, l'oracle renvoie le point ayant la perte la plus élevée (la "mauvaise" réponse), et avec une probabilité $1-\delta$, il renvoie le minimiseur correct. Le paramètre de bruit $\delta \in [0, 1]$ est inconnu de l'apprenant.

Le protocole suppose un adversaire oublieux (oblivious adversary) qui s'engage à l'avance sur la séquence des fonctions de perte $\{f_t\}_{t=1}^T$ avant que l'apprenant ne décide de sonder à un tour spécifique. Cette contrainte est vitale ; si l'adversaire pouvait s'adapter à la décision de sondage, la sonde pourrait être rendue inutile (par exemple, en fixant les pertes à 0 lors des tours de sondage), dégradant la borne de regret à $\Theta(\sqrt{T-k})$.

Méthodologie
L'algorithme proposé est une version augmentée par sondage et adaptative de la méthode des Poids Exponentiels Continus (CEW). L'intuition technique centrale repose sur un effet de réduction de la variance combiné à une analyse de second ordre (basée sur la variance) de l'algorithme CEW.

1. Réduction de la Variance via le Sondage :
   Lors d'un tour de sondage, l'algorithme échantillonne deux points indépendamment de la distribution de densité actuelle $p_t$. En jouant le point présentant la perte observée la plus faible (ou celui suggéré par la sonde), la perte attendue diminue d'un montant proportionnel à la variance de la fonction de perte sous $p_t$, notée $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Spécifiquement, pour des sondes sans bruit, la perte attendue est réduite par $v_t$.

2. Gestion des Sondes Bruyantes (Méta-Apprenant) :
   Puisque $\delta$ est inconnu, l'algorithme emploie un Méta-Apprenant léger (spécifiquement AdaHedge) pour décider s'il doit "suivre" la suggestion de la sonde ou l'"inverser". Le Méta-Apprenant opère sur deux actions : $F$ (suivre) et $I$ (inverser). Il met à jour ses poids en fonction des pertes subies par ces deux actions hypothétiques lors des tours de sondage. Cela permet à l'algorithme de faire confiance de manière adaptative à la sonde lorsqu'elle est informative ($\delta$ éloigné de $1/2$) et de l'ignorer lorsqu'elle ne l'est pas.

3. Décomposition du Regret :
   L'analyse du regret décompose la perte totale en deux composantes :

   • Tours sans sondage : L'algorithme suit la mise à jour CEW standard. Le regret est borné en utilisant une analyse de second ordre (suivant de Rooij et al., 2014) qui relie le regret de base à la variance cumulée $V_T = \sum v_t$.
   • Tours de sondage : La perte est bornée par la perte de la meilleure des deux actions du Méta-Apprenant ($F$ ou $I$), plus un terme de regret pour le Méta-Apprenant lui-même. L'analyse montre que la "meilleure" action atteint une réduction de perte proportionnelle à $|1-2\delta|v_t$.

Résultats Clés
L'article établit qu'un budget sous-linéaire de sondes par paires bruyantes peut améliorer de manière prouvable le regret dans le pire des cas dans le régime de retour complet de l'OCO.

• Pertes Convexes Générales : Pour des pertes convexes générales bornées dans $[0, 1]$ sur un ensemble convexe $K$, le regret attendu est :
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  Cette borne est serrée (à un facteur logarithmique près en $T$) par rapport à l'horizon $T$, le budget de sondage $k$ et le paramètre de bruit $\delta$. Le regret se dégrade de manière fluide lorsque $\delta \to 1/2$ (pile ou face).

• Prédiction avec Experts : Dans le cas particulier du cadre des experts (pertes linéaires sur les sommets du simplexe $\Delta^{d-1}$), la borne s'améliore pour devenir :
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  Ces taux sont complètement serrés pour tous les paramètres, y compris la dimension $d$.

Signification et Contributions
Les auteurs revendiquent plusieurs contributions significatives :

1. Unification : Ce travail unifie le modèle de sondage discret du "meilleur expert" et le modèle continu de "comparaison par paires" en un cadre unique, démontant que les sondes par paires sont aussi informatives que les sondes du meilleur expert pour atteindre des taux de regret optimaux.
2. Robustesse au Bruit : Contra-rément aux travaux précédents qui supposent souvent des modèles sans bruit ou des bruits spécifiques, ce cadre gère des niveaux de bruit inconnus $\delta$ et atteint une dépendance optimale en $|1-2\delta|$.
3. Nouveauté Technique : L'analyse évite la machinerie de la confidentialité différentielle et les hypothèses concernant les normes de gradient ou la courbure (qui étaient requises dans des travaux antérieurs comme Bhaskara et al., 2023b). Au lieu de cela, elle exploite un argument de réduction basé sur la variance.
4. Optimalité : L'article fournit des bornes inférieures correspondantes (dans l'Appendice A) montrant que les taux dérivés sont serrés pour le cadre des experts et serrés en $T, k, \delta$ pour les ensembles convexes généraux.

Les auteurs notent que bien que les garanties théoriques soient fortes, l'algorithme principal nécessite le calcul d'intégrales sur des ensembles convexes, ce qui peut être numériquement difficile en général. Ils identifient le développement d'algorithmes efficaces atteignant des garanties comparables comme une direction de recherche ouverte.