Résumé technique : Approximation gaussienne et bootstrap multiplicateur pour l'approximation stochastique linéaire fédérée

Énoncé du problème

L'article aborde le défi de l'inférence statistique dans le cadre de l'approximation stochastique linéaire fédérée (FedLSA). Bien que l'algorithme de moyenne fédérée (FedAvg) soit la méthode standard pour l'entraînement collaboratif de modèles à travers des agents distribués, la littérature théorique existante se concentre principalement sur les taux de convergence de l'optimisation. Il existe un écart significatif dans la fourniture de garanties non asymptotiques pour l'inférence statistique, spécifiquement pour la construction d'intervalles de confiance pour les paramètres du modèle.

Les approches actuelles pour l'inférence dans les environnements fédérés reposent souvent sur la convergence asymptotique vers une distribution gaussienne limite ou nécessitent une estimation explicite de la matrice de covariance asymptotique ($\Sigma_\infty$), ce qui est coûteux en calcul et difficile à estimer avec précision dans les régimes à échantillons finis. De plus, les résultats existants d'approximation gaussienne non asymptotique pour l'approximation stochastique (SA) et la descente de gradient stochastique (SGD) ne capturent pas entièrement les complexités introduites par l'hétérogénéité (différences dans les distributions de données locales) et les compromis spécifiques entre communication et calcul inhérents à l'apprentissage fédéré, en particulier lorsque le nombre d'itérations locales varie dans le temps.

Méthodologie

Les auteurs développent un cadre théorique rigoureux pour analyser la dernière itérée de FedLSA dans un régime de tailles de pas décroissantes et un nombre croissant d'itérations locales. La méthodologie procède en trois étapes principales :

1. Bornes de moments d'ordre supérieur et décomposition de l'erreur :
   Les auteurs étendent le cadre de décomposition de l'erreur pour accommoder des tailles de pas non constantes et des nombres variables de mises à jour locales. Ils décomposent l'erreur d'estimation $\theta_t - \theta^\star$ en quatre composantes :

   • Un terme transitoire décroissant depuis l'initialisation.
   • Un terme de biais résultant de l'hétérogénéité statistique.
   • Un terme de fluctuation dû à l'hétérogénéité.
   • Un terme de fluctuation dû au bruit stochastique.
     Crucialement, ils établissent des bornes de moments d'ordre supérieur (pour $p \ge 2$) pour ces composantes d'erreur. Il s'agit d'une contribution novatrice, car la littérature précédente se concentrait largement sur les moments d'ordre deux. Ces bornes quantifient explicitement les effets des tailles de pas locales, du nombre de mises à jour locales et de l'hétérogénéité des données.

2. Approximation gaussienne non asymptotique (GAR) :
   En utilisant les bornes de moments dérivées, l'article établit une borne de type Berry-Esseen pour la dernière itérée de FedLSA. L'analyse emploie une décomposition de l'erreur normalisée en une statistique linéaire $W_t$ et un terme de reste $D_t$. En appliquant des inégalités de concentration et des outils issus de la théorie des statistiques non linéaires (spécifiquement Shao et Zhang [2022]), les auteurs bornent la distance convexe entre la distribution de la dernière itérée normalisée et une distribution gaussienne.

   • L'analyse suit l'interdépendance entre le taux de décroissance de la taille de pas ($\gamma_\eta$) et le taux de croissance des itérations locales ($\gamma_H$).
   • Elle prend explicitement en compte le taux de convergence de la matrice de covariance empirique $\Sigma_t$ vers la covariance asymptotique $\Sigma_\infty$, montrant que l'approximation directe de $\Sigma_\infty$ peut introduire des taux de convergence plus lents.

3. Bootstrap multiplicateur en ligne :
   Pour faciliter l'inférence pratique sans estimer $\Sigma_\infty$, les auteurs proposent une procédure de bootstrap multiplicateur en ligne. Cette méthode génère des itérées de bootstrap en introduisant des poids multiplicatifs aléatoires dans les mises à jour locales.

   • La procédure est entièrement en ligne et pilotée par les données.
   • La validité théorique est prouvée en montrant que la distribution conditionnelle de la statistique de bootstrap approxime la distribution d'échantillonnage de l'erreur d'estimation normalisée avec un taux comparable au taux d'approximation gaussienne, contournant efficacement la nécessité d'estimer la matrice de covariance asymptotique.

Contributions clés

L'article apporte les contributions spécifiques suivantes :

• Premières bornes de moments d'ordre supérieur pour FedLSA : Les auteurs fournissent les premières bornes de moments d'ordre $p \ge 2$ pour FedLSA avec des tailles de pas décroissantes et un nombre croissant d'itérations locales. Ces bornes capturent le biais d'hétérogénéité et les mises à jour bruitées, étendant les travaux antérieurs limités à des tailles de pas constantes ou à des moments d'ordre deux.
• Approximation gaussienne non asymptotique pour la dernière itérée : L'article présente la première borne d'approximation gaussienne pour la dernière itérée de FedLSA dans un cadre fédéré avec un nombre croissant d'itérations locales. La borne est exprimée en termes de distance convexe et s'échelonne jusqu'à $t^{-1/2}$ (jusqu'à des facteurs logarithmiques et des termes d'hétérogénéité), capturant explicitement les compromis entre la fréquence de communication et le calcul local.
• Bootstrap multiplicateur valide pour l'inférence fédérée : Les auteurs développent et prouvent la validité d'une procédure de bootstrap multiplicateur en ligne pour la dernière itérée. Cette méthode évite l'estimation explicite de la matrice de covariance asymptotique $\Sigma_\infty$, qui est souvent un goulot d'étranglement dans l'inférence fédérée.
• Analyse de la borne inférieure : L'article fournit une borne inférieure non asymptotique pour la distance convexe dans un cadre simplifié à une dimension, démontrant que les taux dérivés sont serrés et que la convergence de la matrice de covariance est un facteur limitant dans l'erreur d'approximation.

Résultats

Les résultats théoriques sont résumés comme suit :

• Taux de convergence : Sous le schéma de tailles de pas décroissantes ($\eta_t \propto t^{-\gamma_\eta}$) et d'itérations locales croissantes ($H_t \propto t^{\gamma_H}$), l'erreur d'approximation gaussienne pour la dernière itérée est bornée par des termes s'échelonnant comme $N^{-1/2}t^{-\gamma_\eta/2}$, $N^{1/2}t^{-\gamma}$, et $t^{-(3\gamma-\gamma_\eta)/2}$, où $\gamma = \gamma_\eta - \gamma_H$.
• Validité du bootstrap : La procédure de bootstrap multiplicateur atteint un taux de convergence du même ordre ($O(t^{-1/2})$) que l'approximation gaussienne. Cela confirme que la distribution de bootstrap approxime avec précision la vraie distribution d'échantillonnage sans nécessiter la connaissance de $\Sigma_\infty$.
• Validation numérique : Des expériences sur un environnement Garnet avec des agents hétérogènes démontrent que les intervalles de confiance basés sur le bootstrap proposé (utilisant les quantiles empiriques et l'écart-type) obtiennent une meilleure couverture que les bases de référence gaussiennes par insertion (plug-in), en particulier dans les premières itérations et les régimes avec des mises à jour locales croissantes. La méthode par insertion s'améliore à mesure que la taille de l'échantillon augmente mais accuse un retard dans les performances à échantillons finis.

Importance et affirmations

L'article prétend combler une lacune critique dans la littérature sur l'apprentissage fédéré en fournissant les premières méthodes non asymptotiques théoriquement fondées pour quantifier l'incertitude dans l'approximation stochastique linéaire fédérée.

• Conscient de l'hétérogénéité : Contrairement aux travaux antérieurs qui supposaient des agents homogènes ou des pas locaux constants, cette analyse modélise explicitement l'impact de l'hétérogénéité des données et du calendrier dynamique des mises à jour locales.
• Inférence pratique : En validant le bootstrap multiplicateur, l'article offre un outil pratique pour construire des intervalles de confiance dans des environnements fédérés sans la charge computationnelle d'estimer la matrice de covariance asymptotique.
• Confirmation d'hypothèses : Les résultats confirment l'hypothèse (précédemment conjecturée sans preuve par Bonnerjee et al. [2025]) que les procédures de bootstrap multiplicateur peuvent fournir une inférence valide pour les estimateurs fédérés, même dans des régimes complexes avec des itérations locales variables.
• Insight sur le compromis : L'analyse met en évidence un compromis fondamental : bien que l'augmentation du nombre d'itérations locales améliore l'efficacité de l'optimisation et les coûts de communication, elle peut affecter négativement le taux de convergence distributionnelle (approximation gaussienne), suggérant qu'un nombre constant de mises à jour locales pourrait être préférable pour l'inférence statistique, bien que cela ne soit pas toujours réalisable en raison des contraintes de communication.

En résumé, l'article établit une fondation rigoureuse pour l'inférence statistique dans l'apprentissage fédéré, allant au-delà des garanties asymptotiques pour fournir des bornes d'erreur non asymptotiques à échantillons finis et une procédure d'inférence validée.