Résumé Technique : Sur la complexité du gradient de l'optimisation privée avec des oracles privés

Énoncé du Problème

Cet article étudie la complexité d'oracle (temps d'exécution mesuré en requêtes d'oracle du premier ordre) de la minimisation du risque empirique (ERM) et de l'optimisation convexe stochastique (SCO) différentiellement privées (DP) pour des pertes convexes lipschitziennes. Les auteurs se concentrent sur deux contextes distincts :

1. Pertes non lisses avec Oracles Privés : L'optimiseur interagit avec un « oracle de substitution » qui traite un mini-lot de gradients et renvoie un message satisfaisant la confidentialité différentielle (spécifiquement la $\rho$-zCDP. Cela modélise les pratiques courantes comme le DP-SGD où les gradients sont perturbés avant la transmission.
2. Pertes lisses avec Optimiseurs Privés : L'hypothèse est assouplie pour exiger uniquement que la procédure d'optimisation finale soit $(\epsilon, \delta)$-DP, sans restreindre le mécanisme d'oracle interne à être privé.

L'objectif principal est d'établir des bornes inférieures sur le nombre de requêtes de gradient nécessaires pour atteindre un excès de risque $\alpha$, en analysant spécifiquement comment les contraintes de confidentialité et la dimension $d$ impactent le temps d'exécution par rapport aux contreparties non privées.

Méthodologie

Les auteurs emploient un hybride de « découverte de vecteurs » et de techniques de bornes inférieures de l'information théorique.

Construction du Problème Difficile

La construction de la borne inférieure centrale repose sur une construction de fonction de perte spécifique inspirée de la fonction de Nemirovski, mais augmentée d'un terme de régularisation. La perte est définie comme :
$$L(w) = \max \left\{ \max_{k \in [K]} \{ |\langle w, X_k \rangle - \alpha| \}, \| \Pi_V w \| \right\}$$
où :

• $X_1, \dots, X_K$ sont des vecteurs orthonormés aléatoires dans $\mathbb{R}^d$.
• $V$ est un sous-espace aléatoire orthogonal à l'espace engendré par $\{X_k\}$.
• $\Pi_V$ est la projection orthogonale sur $V$.
• La perte est répliquée $n$ fois pour le contexte ERM.

Analyse de l'Information Théorique

La stratégie de preuve consiste à montrer que pour minimiser cette perte, un optimiseur doit « découvrir » chaque vecteur $X_k$. Cependant, contrairement à la découverte de vecteurs standard où l'observation d'un vecteur est suffisante, ici l'optimiseur doit obtenir une information mutuelle élevée sur chaque $X_k malgré les contraintes de confidentialité.

• Suivi de l'Information Mutuelle : Les auteurs suivent la somme des informations mutuelles conditionnelles $\sum I(X_k; W | X_{\neq k}, V)$, où $W$ est la solution de sortie. Ils soutiennent que l'estimation de $X_k$ reste un problème de haute dimension même lorsque les autres vecteurs sont connus.
• Contraintes de Confidentialité : Pour les oracles privés, les auteurs bornent l'information fuitée sur $X_k$ en utilisant les propriétés de la $\rho$-zCDP et de la confidentialité de groupe. Ils démontrent que, à moins que l'optimiseur ne fasse $\Omega(d)$ requêtes pour apprendre le sous-espace $V$, il ne peut pas utiliser efficacement le sous-espace non pénalisé pour estimer $X_k$.
• Oracles à Capacité d'Information Limitée : La technique s'étend aux oracles ayant une capacité d'information $\Gamma$ (bits) bornée, montrant que l'optimiseur doit interroger l'oracle suffisamment de fois pour accumuler suffisamment d'information sur les gradients.

Contributions Clés et Résultats

1. Optimisation Non Lisse avec Oracles Privés

L'article établit que pour la dimension $d \geq 1/\alpha^2$, tout optimiseur interagissant avec un oracle de substitution $\rho$-zCDP nécessite un temps d'exécution attendu de :
$$\Omega\left( \min\left\{ \frac{\sqrt{d}}{\alpha^2 \sqrt{\rho}} + \frac{d}{\bar{m}\rho}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
où $\bar{m}$ est la taille maximale du mini-lot.

• Étroitesse (Tightness) : Cette borne inférieure est montrée comme étant étroite (à un facteur logarithmique près) pour le régime $d \geq 1/\alpha^4$ via une analyse du DP-SGD.
• Impact de la Taille de Lot : Le résultat caractérise explicitement l'impact négatif des petites tailles de lots ($\bar{m}$) sur la dynamique d'apprentissage privée. Si $\bar{m} < \sqrt{d}$, la pénalité de temps d'exécution augmente.
• Corollaire pour le DP-SGD : Pour le DP-SGD avec une taille de lot $m$, le temps d'exécution est $\Omega(\min\{ \frac{\sqrt{d} + d/m}{\alpha^2}, \frac{d}{m \log(1/\alpha)} \})$.

2. Optimisation Non Lisse avec Oracles à Information Limitée

En étendant la technique de preuve, les auteurs montrent que si un oracle de substitution transmet au plus $\Gamma$ bits d'information sur les gradients, le nombre de appels d'oracle requis est de :
$$\Omega\left( \min\left\{ \frac{d}{\alpha^2 \Gamma}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
Ce résultat souligne les limitations fondamentales des techniques de quantification de gradient dans l'optimisation privée, montrant que l'optimiseur doit effectivement utiliser « l'intégralité » de l'information du gradient pour réussir.

3. Optimisation Lisse avec Optimiseurs Privés

Pour les pertes lisses, où seul l'optimiseur final est requis d'être $(\epsilon, \delta)$-DP (et non l'oracle), les auteurs prouvent une borne inférieure sur le nombre attendu d'appels d'oracle :
$$\tilde{\Omega}\left( \frac{\sqrt{d}}{\alpha} + \min\left\{ \frac{1}{\alpha^2}, n \right\} \right)$$

• Indépendance de la Confidentialité : Notamment, cette borne inférieure ne dépend pas du paramètre de confidentialité $\epsilon$ (pourvu que $\alpha$ soit fixé). Les auteurs soutiennent que des garanties de confidentialité plus fortes n'impactent que la précision minimale réalisable ($\alpha^*_{\epsilon, \delta}$), et non le coût de temps d'exécution une fois qu'une précision cible est fixée.
• Étroitesse : Des modifications d'algorithmes existants (Phased SGD) montrent que cette borne est presque étroite.

4. Réductions entre ERM et SCO

L'article démontre que le DP-SCO n'est pas plus difficile que le DP-ERM (à un facteur polylogarithmique près) via une réduction qui n'entraîne qu'un surcoût de polylog(n) en temps d'exécution et en confidentialité. Cela implique que la caractérisation de la complexité du DP-ERM est suffisante pour comprendre le DP-SCO dans la plupart des régimes.

Signification et Revendications

Les auteurs positionnent ce travail comme le premier à fournir des bornes inférieures de complexité d'oracle qui exploitent la confidentialité différentielle au-delà du modèle de confidentialité locale.

• Pénalité de Temps d'Exécution : Les résultats démontrent formellement qu'une classe d'optimiseurs privés (ceux utilisant des oracles privés) subissent une pénalité de temps d'exécution dépendant de la dimension par rapport aux optimiseurs non privés. Dans le contexte non privé, la complexité est de $\Theta(1/\alpha^2)$ pour les fonctions non lisses ; le contexte privé introduit un facteur de $\sqrt{d}$ ou $d$ selon le régime.
• Pertinence Pratique : Le modèle d'oracle privé est motivé par des scénarios pratiques tels que l'apprentissage fédéré et l'entraînement distribué, où des serveurs non approuvés interrogent les nœuds pour obtenir les gradients. Les conclusions suggèrent que les petites tailles de lots, souvent utilisées pour l'amplification de la confidentialité, dégradent fondamentalement les performances de temps d'exécution dans les hautes dimensions.
• Limites de la Quantification : Le résultat de l'oracle à information limitée fournit une justification théorique des limites de la quantification de gradient dans les contextes privés, montrant que compresser les gradients en dessous d'un certain seuil nécessite une augmentation proportionnelle du nombre de requêtes.

L'article conclut que bien que les avancées algorithmiques aient amélioré les bornes supérieures, le coût fondamental de la confidentialité en termes de complexité d'oracle est désormais mieux caractérisé, révélant un compromis entre dimensionnalité, taille de lot et confidentialité qui n'était pas pleinement compris dans le modèle de confidentialité centrale.