Résumé Technique : SILAGE

Énoncé du Problème

L'article traite de la minimisation de risque empirique (ERM) non convexe sur des jeux de données massifs présentant une structure de somme finie double imbriquée. La fonction objectif est formulée comme suit :
$$\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x), \quad \text{où} \quad f_i(x) := \frac{1}{m} \sum_{j=1}^m f_{i,j}(x)$$
Ici, $N = nm$ représente le nombre total d'échantillons, partitionnés en $n$ blocs (ou silos) de taille $m$. Cette structure émerge naturellement dans des contextes centralisés tels que les lacs de données mutualisés (par exemple, des dossiers de santé provenant de plusieurs hôpitaux), l'apprentissage hors mémoire (out-of-core) où les données dépassent la capacité de la mémoire, ou la stratification délibérée par partitionnement (clustering).

Les méthodes existantes de réduction de la variance (VR) sont confrontées à un compromis critique dans ce régime :

1. Estimateurs récursifs (ex. : PAGE, SARAH) : Atteignent des complexités d'oracle optimales mais nécessitent des rafraîchissements périodiques du gradient global complet sur l'ensemble des $nm$ échantillons. Ces rafraîchissements sont coûteux en termes de calcul et créent des goulots d'étranglement à l'échelle.
2. Estimateurs basés sur la mémoire (ex. : SILVER, SAGA) : Évitent les rafraîchissements globaux mais nécessitent de stocker une variable de contrôle pour chaque échantillon individuel, ce qui entraîne une empreinte mémoire $\mathcal{O}(nm)$ impraticable pour des jeux de données massifs.

L'objectif est de concevoir un algorithme qui élimine les rafraîchissements globaux périodiques tout en maintenant une empreinte mémoire proportionnelle uniquement au nombre de blocs ($\mathcal{O}(n)$), plutôt qu'au nombre total d'échantillons.

Méthodologie : SILAGE

Les auteurs proposent SILAGE (SIngle Loop Average Gradient Estimator), un algorithme de réduction de la variance à boucle unique conçu pour la structure imbriquée. SILAGE combine deux philosophies de réduction de la variance :

• Structure de mémoire de type SILVER : Maintient un estimateur de gradient (variable de contrôle) par bloc ($n$ entrées au total), plutôt que par échantillon.
• Suivi récursif de type PAGE : Met à jour ces estimateurs de manière récursive à l'aide de gradients stochastiques.

L'algorithme fonctionne différemment selon la relation entre le nombre de blocs ($n$) et la taille des blocs ($m$) :

1. Le régime $m \ge n$ (Algorithme 1)

Dans ce régime, la taille du bloc est supérieure ou égale au nombre de blocs.

• Mécanisme : Un lancer de pièce global unique détermine le type d'itération. Avec une probabilité $p$, un bloc unique $i_t$ est sélectionné uniformément au hasard et son gradient local complet $\nabla f_{i_t}(x_{t+1})$ est calculé (un « ancrage de réinitialisation »). Avec une probabilité $1-p$, aucun bloc n'est réinitialisé ; au lieu de cela, les $n$ blocs sont mis à jour de manière récursive en utilisant un seul gradient de composante échantillonné de chaque bloc.
• Couplage : La probabilité $p$ est fixée à $n/m$. Cela garantit que la probabilité marginale qu'un bloc spécifique soit rafraîchi est de $1/m$, correspondant au taux de rafraîchissement de PAGE standard sur un ensemble de données plat, tout en garantissant qu'au plus un bloc est rafraîchi par itération.
• Coût : Le coût par itération est de $\mathcal{O}(m)$ (dominé par le gradient local complet unique ou les $n$ gradients de composantes).

2. Le régime $n > m$ (Algorithme 2)

Dans ce régime, le nombre de blocs dépasse la taille des blocs.

• Mécanisme : Calculer le gradient complet pour même un seul bloc est coûteux par rapport au budget total si de nombreux blocs doivent être mis à jour. SILAGE sélectionne un bloc d'ancrage $i_t$ pour une réinitialisation complète et un petit sous-ensemble actif $\Omega_t$ de taille $b_{grp}-1$ pour les mises à jour récursives.
• Dérive partagée (Shared Drift) : Pour les $n - b_{grp}$ blocs restants qui ne sont pas échantillonnés, l'algorithme ne calcule pas de nouveaux gradients. Au lieu de cela, il applique une dérive partagée $d_t$, calculée comme la moyenne des différences stochastiques du sous-ensemble actif, pour mettre à jour leurs estimateurs.
• Efficacité d'implémentation : Pour éviter le coût de $\mathcal{O}(n)$ d'une mise à jour explicite de tous les $n$ estimateurs avec la dérive, les auteurs proposent une forme d'implémentation efficace (Algorithme 3) utilisant un accumulateur partagé $q_t$, réduisant le coût de gestion comptable à $\mathcal{O}(b_{grp})$.

Contributions Clés

1. Efficacité de la mémoire via la structure imbriquée

SILAGE ne nécessite que $\mathcal{O}(n)$ de mémoire (stockant un vecteur de dimension $d$ par bloc plus quelques vecteurs auxiliaires). Il s'agit d'une réduction substantielle par rapport aux méthodes aplaties comme SILVER, qui nécessitent $\mathcal{O}(nm)$ de mémoire.

2. Élimination des rafraîchissements globaux périodiques

Contrairement à PAGE et ses variantes, SILAGE ne réalise jamais de passage de gradient complet global sur l'ensemble des $nm$ composantes. Il évalue au plus un gradient de groupe local $\nabla f_i$ par itération (à un coût de $\mathcal{O}(m)$). L'initialisation peut être arbitraire (par exemple, zéro), évitant ainsi le besoin d'un calcul de gradient global initial.

3. Exploitation de la similitude imbriquée

L'analyse de convergence introduit une nouvelle dépendance à deux niveaux de la géométrie des données, évitant les constantes de Lipschitz maximales ($L_{\max}$) pessimistes :

• Similitude inter-groupes ($\delta_1$) : Mesure l'écart des gradients de groupe par rapport au gradient global.
• Similitude intra-groupe ($\delta_2$) : Mesure l'écart des gradients d'échantillons par rapport à leurs moyennes de groupe locales.
  Les taux de convergence dépendent explicitement de ces constantes. Dans le régime $m \ge n$, le taux dépend principalement de $\delta_2$. Dans le régime $n > m$, $\delta_1$ et $\delta_2$ influencent tous deux la complexité, mais l'algorithme les découple selon le régime opérationnel.

4. Unification des méthodes existantes

SILAGE unifie les approches existantes en tant que cas limites :

• Lorsque $n=1$ (bloc unique), SILile réduit à PAGE.
• Lorsque $m=1$ (échantillon unique par bloc), SILAGE se réduit à SILVER.

Résultats et Convergence

L'article fournit des garanties de convergence non convexe serrées pour trouver un point stationnaire $\epsilon$-approximatif ($\mathbb{E}[\|\nabla f(\tilde{x})\|^2] \le \epsilon$).

• Régime $m \ge n$ :
  La complexité du gradient est de $\mathcal{O}\left(nm + \frac{(nL + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$ (en supposant une initialisation exacte). Crucialement, le terme principal dépend de $\delta_2$ (variance intra-groupe) plutôt que de la similitude globale plate ou de $L_{\max}$.
• Régime $n > m$ :
  La complexité est de $\mathcal{O}\left(nm + \frac{(mL + m\sqrt{n-m}\delta_1 + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$.
  Ici, l'algorithme équilibre le coût de l'hétérogénéité inter-groupes ($\delta_1$) et de l'hétérogénéité intra-groupe ($\delta_2$).

Comparé aux bases de référence :

• Vs. ZeroSARAH : SILAGE remplace le pire cas $L_{\max}$ par une structure $L, \delta_1, \delta_2$, offrant des améliorations significatives dans les régimes hétérogènes.
• Vs. SILVER : SILAGE atteint une complexité de gradient similaire ou meilleure tout en réduisant la mémoire de $\mathcal{O}(nm)$ à $\mathcal{O}(n)$.
• Vs. D-PAGE : Bien que D-PAGE offre une complexité compétitive, il nécessite des rafraîchissements globaux périodiques. SILAGE élimine totalement ces rafraîchissements, échangeant une légère augmentation de la mémoire (de $\mathcal{O}(1)$ à $\mathcal{O}(n)$) contre l'élimination de l'opération la plus coûteuse dans l'entraînement à grande échelle centralisé.

Signification et Revendications

Les auteurs affirment que SILAGE répond à un goulot d'étranglement fondamental de la mise à l'échelle de l'optimisation centralisée à grande échelle. En exploitant activement la structure de somme double imbriquée, SILAGE atteint un scénario de « meilleur des deux mondes » :

1. Il évite le goulot d'étranglement de calcul des rafraîchissements périodiques de gradient complet global requis par les estimateurs récursifs.
2. Il évite le goulot d'étranglement de la mémoire lié au stockage des variables de contrôle pour chaque échantillon requis par les estimateurs basés sur la mémoire.

L'article souligne que les taux théoriques sont structurellement plus serrés que les bornes existantes car ils reposent sur des constantes de similitude imbriquées ($\delta_1, \delta_2$) qui peuvent être nettement plus petites que les constantes de similitude aplaties ou les paramètres de lissage du pire cas, particulièrement dans les régimes de blocs redondants ou de silos homogènes. Les résultats expérimentaux sur des tâches de régression logistique non convexe synthétiques confirment que les performances de SILAGE suivent ces prédictions théoriques, convergeant plus rapidement que les bases de référence lorsque la structure de similitude imbriquée est favorable.