Résumé Technique : Regret Dynamique sans Paramètre avec Coûts de Mouvement Variables dans le Temps

1. Configuration du Problème

Cet article traite de l'Optimisation Convexe en Ligne (OCO) non contrainte dans des environnements non stationnaires où l'apprenant subit des coûts de mouvement variables dans le temps.

Dans le cadre standard de l'OCO, un apprenant choisit une décision $w_t$ issue d'un espace convexe $\mathcal{W}$ (spécifiquement $\mathbb{R}^n$ dans ce travail) et subit une perte convexe $f_t(w_t)$. L'objectif est de minimiser le regret dynamique par rapport à une séquence de comparateurs $(u_1, \dots, u_T)$ :
$$R_T(u_{1:T}) = \sum_{t=1}^T f_t(w_t) - \sum_{t=1}^T f_t(u_t)$$

Ce travail étend le problème en ajoutant une pénalité de coût de mouvement proportionnelle à la distance entre les décisions consécutives. Crucialement, le coefficient $\lambda_t$ régissant ce coût est variable dans le temps et arbitraire. L'objectif de l'apprenant est de minimiser le regret dynamique asymétrique :
$$R_T(u_{1:T}, \lambda_{1:T}) = \sum_{t=1}^T \left( f_t(w_t) - f_t(u_t) + \lambda_t \|w_t - w_{t-1}\| \right)$$
Notez que la séquence de comparateurs $(u_t)$ ne subit pas la pénalité de coût de mouvement dans cette formulation asymétrique, ce qui rend le problème plus difficile que la variante symétrique.

Le défi principal est de concevoir des algorithmes sans paramètre (adaptatifs aux comparateurs) qui ne nécessitent pas de connaissance préalable de :

1. La borne de norme du comparateur $M = \max_t \|u_t\|$.
2. La longueur du chemin du comparateur $P_T = \sum_{t=2}^T \|u_t - u_{t-1}\|$.
3. La séquence des normes de gradient $\|g_t\|$.
4. La séquence des coefficients de coût de mouvement $\lambda_t$.

2. Méthodologie

Les auteurs proposent un cadre algorithmique hiérarchique composé de trois composants principaux :

A. Descente de Miroir Composée avec Régularisation Variable dans le Temps (Algorithme 1)

L'algorithme de base utilise une mise à jour de Descente de Miroir Composée. À chaque tour $t$, après avoir observé le gradient $g_t$ et le coût de mouvement suivant $\lambda_{t+1}$, l'apprenant met à jour $w_{t+1}$ en minimisant :
$$w_{t+1} = \arg\min_{w} \left( \langle g_t, w \rangle + D_\psi(w | w_t) + \phi_t(w) \right)$$

• Régularisateur $\psi(w)$ : Une fonction log-linéaire conçue pour gérer les domaines non bornés.
• Terme de Correction $\phi_t(w)$ : Un terme quadratique variable dans le temps mis à l'échelle par $\beta_t^2 = (\|g_t\| + \lambda_{t+1})^2$. Ce terme agit comme une « friction dynamique », stabilisant les itérés. Lorsque les coûts de mouvement ou les gradients sont élevés, la pénalité augmente, restreignant les mises à jour ; lorsqu'ils sont faibles, la pénalité se relâche.

B. Méta-Algorithme Sans Paramètre (Algorithme 2)

Pour éliminer la nécessité de connaître $M$, $P_T$ et les échelles de gradient/mouvement, les auteurs emploient un méta-algorithme qui maintient une grille d'instances parallèles de l'Algorithme 1, chacune avec un taux d'apprentissage $\eta_i$ différent.

• L'apprenant joue la somme des décisions de toutes les instances.
• Le regret total est décomposé en le regret de la « meilleure » instance (approximant le $\eta$ optimal) plus un faible coût additif provenant des autres instances.
• Résultat : Cela produit une borne de regret de $\tilde{O}\left( \sqrt{(M + P_T) \sum_{t} (\|g_t\|^2 + \lambda_{t+1}^2) \|u_t\|} \right)$.
• Limitation : Cette borne dépend de manière quadratique des coûts de mouvement ($\lambda_{t+1}^2$), ce qui est sous-optimal lorsque les gradients sont faibles mais que les coûts de mouvement sont élevés.

C. Réduction par Premier Ordre Adaptative (Algorithme 3)

Pour améliorer la dépendance aux coûts de mouvement de quadratique à linéaire, les auteurs introduisent un mécanisme de batching adaptatif.

• Mécanisme : L'algorithme accumule les gradients dans un tampon $H_\tau$ sur une époque. Il ne déclenche une mise à jour de l'apprenant de base que lorsque la norme du gradient accumulé $\|H_\tau\|$ dépasse le coût de mouvement actuel $\lambda_{t+1}$.
• Logique : Si le coût de mouvement est élevé, l'algorithme attend que le « signal » (le gradient) soit assez fort pour justifier le « coût » du mouvement.
• Résultat : Cela réduit la dépendance du regret vis-à-vis des coûts de mouvement de $\lambda^2$ à $\lambda \|g\|$.

3. Contributions Clés

1. Premier Regret Dynamique Sans Paramètre avec Coûts Variables dans le Temps : L'article établit les premières bornes de regret dynamique adaptatives aux comparateurs pour l'OCO non contraint avec des coûts de mouvement arbitraires et variables dans le temps.
2. Adaptativité Optimale : Les algorithmes proposés s'adaptent simultanément à :
   • La complexité du comparateur ($M$ et $P_T$).
   • La séquence de gradient réalisée ($\|g_t\|$).
   • Les coefficients de mouvement variables dans le temps ($\lambda_t$).
3. Amélioration de la Dépendance aux Coûts de Mouvement : En introduisant la stratégie de batching adaptatif (Algorithme 3), les auteurs obtiennent une borne de regret évoluant avec $\sum (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|$. C'est une amélioration significative par rapport aux précédentes bornes de second ordre évoluant en $\lambda^2$, particulièrement dans les régimes où les gradients sont faibles.
4. Nouvelles Réductions à d'Autres Problèmes : Le cadre est présenté comme un primitif pour résoudre d'autres problèmes d'apprentissage en ligne en les traduisant en contextes de coûts de mouvement variables dans le temps :
   • OCO avec Feedback Différé : Le nombre de gradients manquants est traité comme l'échelle du coût de mouvement.
   • OCO avec Mémoire Variable dans le Temps : Les fluctuations de la longueur de la mémoire sont mappées sur des coûts de mouvement variables dans le temps.

4. Résultats Principaux

Garanties Théoriques

Pour l'Algorithme 3 (la version améliorée), l'article garantit un regret dynamique de :
$$\tilde{O}\left( (M + P_T)L + \sqrt{(M + P_T) \sum_{t=1}^T (\|g_t\|^2 + \lambda_t \|g_t\|) \|u_t\|} \right)$$
où $L$ est une constante de type Lipschitz liée à $G + \lambda_{\max}$.

Application 1 : Feedback Différé

Les auteurs réduisent l'OCO avec feedback différé à leur cadre en fixant $\lambda_t = G |m_t|$, où $|m_t|$ est le nombre de gradients manquants au temps $t$.

• Résultat : Ils obtiennent un regret dynamique sans paramètre de $\tilde{O}\left( (M + P_T)L + G\sqrt{(M^2 + MP_T)(T + d_{\text{tot}})} \right)$.
• Avantage : Cela améliore les travaux antérieurs (ex. Wan et al., 2024) en gérant des domaines non bornés et en obtenissant une dépendance plus étroite vis-à-vis du délai total $d_{\text{tot}}$ plutôt que du délai maximal $d_{\max}$, sans nécessiter l'hypothèse restrictive de feedback « dans l'ordre ».

Application 2 : Mémoire Variable dans le Temps

Les auteurs réduisent l'OCO avec mémoire variable dans le temps (où la perte dépend des $b_t$ dernières décisions) à leur cadre.

• Résultat : Ils obtiennent une borne de regret de $\tilde{O}\left( (M + P_T)L + \sqrt{M(M + P_T)(H^2 T + GH \sum b_t^2)} \right)$.
• Avantage : C'est la première garantie de regret dynamique pour l'OCO non contraint avec des longueurs de mémoire variables dans le temps. Cela améliore les travaux de Zhao et al. (2023) en supprimant l'hypothèse de domaine borné et en affinant la dépendance vis-à-vis de la séquence de longueur de mémoire.

5. Signification et Revendications

L'article affirme que ses résultats représentent une unification de plusieurs directions de recherche exigeantes dans l'apprentissage en ligne :

• Unification : Il comble le fossé entre l'optimisation non contrainte, le regret dynamique et les coûts de mouvement, une combinaison auparavant inexplorée.
• Polyvalence : Le cadre démontre que l'OCO avec coûts de mouvement est un primitif puissant. En interprétant simplement l'« information manquante » (dans le feedback différé) ou les « dépendances de mémoire » comme des pénalités de mouvement, des bornes de regret dynamique optimales peuvent être dérivées pour ces contextes complexes.
• Optimalité : Les auteurs affirment que leur dépendance vis-à-vis de la longueur du chemin $P_T$ et des normes des comparateurs est minimaxement optimale (à un facteur logarithmique près) et que la dépendance de premier ordre vis-à-vis des coûts de mouvement est un raffinement nécessaire pour atteindre l'optimalité dans les contextes avec des pénalités fluctuantes.
• Praticité : Les algorithmes sont efficaces, nécessitant $O(d \log T)$ de calcul par tour, ce qui correspond à la complexité des algorithmes standards d'OCO sans paramètre.

Le travail ne prétend pas résoudre des problèmes en dehors du champ de l'optimisation convexe ou fournir une validation expérimentale sur des jeux de données réels, se concentrant plutôt sur les garanties théoriques et les réductions.