Résumé technique : Comptabilité de la confidentialité sans échantillonnage pour les mécanismes matriciels sous allocation aléatoire

Énoncé du problème

L'article aborde le défi du calcul de garanties de confidentialité déterministes et serrées pour l'entraînement de modèles privés par différentiellement qui utilisent des mécanismes de factorisation matricielle combinés à une allocation aléatoire (également connue sous le nom de schéma « boules dans des urnes » ou d'échantillonnage d'itération équilibré).

Bien que l'amplification de la confidentialité par échantillonnage soit une technique standard pour réduire le bruit dans la descente de gradient stochastique privée par différentiel (DP-SGD), le schéma « boules dans des urnes » est préféré à l'échantillonnage de Poisson pour l'entraînement à grande échelle en raison de son efficacité computationnelle et de sa couverture uniforme des données. Cependant, lorsqu'il est combiné à une factorisation matricielle (qui introduit un bruit corrélé à travers les itérations pour améliorer l'utilité), les méthodes existantes de comptabilité de la confidentialité présentent des limitations significatives :

1. Dépendance aux méthodes de Monte Carlo : Les approches récentes (par exemple, Choquette-Choo et al., 2025) reposent sur un échantillonnage de Monte Carlo pour estimer les paramètres d'amplification. Cette approche est coûteuse en calcul, en particulier dans les régimes de haute confidentialité où le nombre d'échantillons requis évolue inversement avec $\delta$ (par exemple, montrer une confidentialité $(\epsilon, 10^{-8})$-DP est $10^5$ fois plus coûteux que $(\epsilon, 10^{-3})$-DP).
2. Garanties probabilistes : Ces méthodes basées sur l'échantillonnage produisent souvent des garanties qui ne tiennent qu'avec une forte probabilité ou nécessitent que le mécanisme emploie une abstention aléatoire, plutôt que de fournir des bornes déterministes de confidentialité $(\epsilon, \delta)$-DP.
3. Intrabilité computationnelle : La distribution de la perte de confidentialité pour les mécanismes matriciels sous allocation aléatoire implique des mélanges de haute dimension, rendant l'évaluation exacte de la divergence en forme de bâton de hockey intraitable sans échantillonnage.

Méthodologie

Les auteurs proposent deux procédures de comptabilité distinctes, sans échantillonnage, qui calculent des bornes déterministes explicitement, en exploitant la structure du schéma d'allocation aléatoire et les corrélations introduites par la factorisation matricielle.

1. Compteur de divergence de Rényi (Programmation dynamique)

Cette méthode calcule une borne supérieure sur la divergence de Rényi, qui est ensuite convertie en confidentialité $(\epsilon, \delta)$-DP en utilisant des théorèmes de conversion standard.

• Idée centrale : La distribution de la perte de confidentialité pour la direction « suppression » (où un point de données est retiré de l'ensemble de données) peut être exprimée comme une somme sur une matrice de Gram $G$ dérivée de la matrice de stratégie $C$.
• Réduction de complexité : Pour les matrices générales, le calcul de cette somme est prouvé comme étant #P-complet. Cependant, pour les matrices structurées (par exemple, les matrices bandées où la matrice de stratégie $C$ a une bande passante $p$), la matrice de Gram $G$ hérite d'une structure bandée cyclique.
• Algorithme : Les auteurs formulent une approche de programmation dynamique pour calculer la somme exactement pour les matrices bandées de largeur $p$.
  • Complexité : Le temps d'exécution est réduit d'une exponentielle $O(2^\alpha)$ (en fonction de l'ordre $\alpha$) à une polynomiale $O(b p \alpha^{2p})$, où $b$ est le nombre de lots par époque.
  • Troncature : Pour les matrices qui ne sont pas strictement bandées mais dont les entrées décroissent rapidement (par exemple, les matrices inverses bandées), la méthode tronque la matrice de Gram et ajoute un terme de correction additive calculable pour garantir que la borne reste valide.
• Direction « Ajout » : Une borne supérieure analytique serrée séparée est dérivée pour la direction « ajout » en utilisant l'inégalité arithmético-géométrique (AM-GM).

2. Compteur de composition conditionnelle

Cette méthode aborde le régime « petit $\epsilon$ » (haute confidentialité) où les formules de conversion de Rényi peuvent être lâches. Elle surmonte l'interdépendance des étapes causée par la corrélation du bruit et les comptes de participation fixes.

• Concept : Au lieu de supposer des étapes indépendantes, la méthode utilise une composition conditionnelle. Elle identifie des résultats « bons » où les distributions conditionnelles du mécanisme à l'étape $n$ sont dominées par une paire de distributions fixes et factorisantes $(P^{(n)}, Q^{(n)})$.
• Événements « mauvais » : La méthode prend en compte les résultats « mauvais » (où la dominance échoue) en bornant leur probabilité $\delta_E$. La perte de confidentialité totale est la composition des étapes indépendantes plus $\delta_E$.
• Critère de dominance : Les auteurs dérivent un critère basé sur les fonctions de risque inverse des poids des mélanges gaussiens. Ils montrent que si la fonction de risque inverse a posteriori est inférieure point par point à la fonction de risque inverse d'une distribution cible, la dominance est vérifiée.
• Bornes de queue : Pour déterminer les paramètres des distributions dominantes, les auteurs dérivent des bornes analytiques de queue sur la perte de confidentialité des mélanges gaussiens ternaires. Ils utilisent une famille variationnelle de distributions pour resserrer ces bornes, en optimisant les paramètres de température pour minimiser l'écart type de la borne de queue.
• Efficacité : Bien que l'évaluation initiale soit de $O(N^2 b^2)$, les évaluations ultérieures pour différents multiplicateurs de bruit $\sigma$ peuvent être amorties à $O(N b^2)$, la rendant efficace pour l'étalonnage du mécanisme.

Contributions clés

1. Comptabilité déterministe : L'article introduit les premières méthodes sans échantillonnage pour calculer des garanties déterministes $(\epsilon, \delta)$-DP pour les mécanismes matriciels sous allocation aléatoire, éliminant le besoin d'estimation par Monte Carlo.
2. Complexité améliorée pour la DP-SGD : Pour le cas particulier du bruit non corrélé (DP-SGD standard), le compteur de Rényi proposé améliore la complexité computationnelle du comptage exact sous allocation aléatoire, passant d'une exponentielle $O(2^\alpha)$ à une polynomiale $O(b \alpha^2)$, surpassant significativement les méthodes exactes précédentes.
3. Généralisation au bruit corrélé : Le cadre s'étend aux mécanismes matriciels bandés et non bandés arbitraires (incluant la racine carrée bandée, l'inverse bandé et le Toeplitz linéaire tamponné), gérant les corrélations inter-étapes complexes inhérentes à ces mécanismes.
4. Précision dual-régime : La combinaison du compteur de Rényi (fort dans le régime de faible confidentialité/grand-$\epsilon$) et du compteur de composition conditionnelle (plus serré dans le régime de haute confidentialité/petit-$\epsilon$) fournit une solution de comptabilité complète.

Résultats

Les auteurs évaluent leurs méthodes par rapport au compteur de Monte Carlo de l'état de l'art sur divers mécanismes matriciels (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) et configurations (époque unique et multi-époques).

• Précision : Dans le régime de faible confidentialité ($\epsilon \ge 2$), le compteur de Rényi correspond étroitement à la référence Monte Carlo. Dans le régime de haute confidentialité ($\epsilon \le 1$), le compteur de composition conditionnelle produit des bornes plus serrées, permettant des multiplicateurs de bruit calibrés $\sigma$ plus petits par rapport aux estimations Monte Carlo.
• Robustesse : Les performances sont maintenues à travers différentes largeurs de bande ($p$) et nombres de lots ($b$).
• Utilité : Les expériences sur CIFAR-10 démontrent que les multiplicateurs de bruit dérivés de ces garanties sans échantillonnage préservent les avantages d'utilité de l'utilisation d'un bruit corrélé par rapport à un bruit non corrélé.
• Temps d'exécution : Les méthodes surmontent la dépendance $O(\delta^{-1})$ de l'échantillonnage Monte Carlo. Bien que le compteur de composition conditionnelle ait un coût initial plus élevé pour un grand $N$, son coût amorti pour l'étalonnage est significativement inférieur à celui de Monte Carlo pour des budgets de confidentialité stricts.

Importance et affirmations

L'article revendique fournir la première comptabilité de confidentialité sans échantillonnage pour les mécanismes avec des gradients et des participations corrélés. Son importance réside dans :

• L'obtention de garanties déterministes : Il élimine la dépendance aux bornes probabilistes ou à l'abstention aléatoire, qui sont souvent peu pratiques ou théoriquement plus faibles pour les systèmes de production.
• Évolutivité : En réduisant la complexité du comptage exact de Rényi pour l'allocation aléatoire d'exponentielle à polynomiale, il rend la comptabilité de confidentialité précise réalisable pour les entraînements à grande échelle où l'échantillonnage Monte Carlo serait computationnellement prohibitif.
• Étalonnage pratique : La capacité de calculer efficacement des bornes serrées sur une large gamme de $\epsilon$ et $\delta$ facilite un meilleur étalonnage des multiplicateurs de bruit, améliorant directement le compromis utilité-confidentialité dans l'apprentissage profond privé par différentiel.

Les auteurs reconnaissent des limitations, notant que la complexité du compteur de Rényi reste exponentielle en fonction de la largeur de bande $p$ (bien que polynomiale en $\alpha$), et que la méthode de composition conditionnelle repose sur une partition grossière des résultats qui peut être pessimiste. Ils suggèrent que des travaux futurs pourraient explorer des partitions plus fines et une inférence variationnelle plus efficace pour resserrer davantage les bornes.