Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Résumé Technique : Estimation Privée Exactement Optimale et Économe en Communication via les Plans de Blocs

Formulation du Problème
Le document traite du problème de l'estimation de distributions discrètes sous une contrainte de confidentialité dans le cadre de la Confidentialité Différentielle Locale (LDP). Dans ce contexte, $n$ clients observent des points de données $X_i$ tirés d'une distribution inconnue $P$ sur un domaine de taille $v$. Chaque client applique un mécanisme de confidentialité $Q$ pour générer un résultat privatisé $Y_i$ satisfaisant une $\epsilon$-LDP avant de l'envoyer à un serveur central. Le serveur construit ensuite un estimateur $\hat{P}_n$ pour récupérer $P$. L'objectif est de minimiser le risque de pire cas (erreur d'estimation) sous une fonction de perte spécifique (principalement $\ell_u^u$ pour $1 \le u \le 2$) tout en minimisant simultanément le coût de communication, défini par la taille de l'alphabet de sortie $b = |\mathcal{Y}|$.

Bien que le schéma de Sélection de Sous-ensembles (SS - Subset Selection) soit connu pour atteindre l'arbitrage optimal exact de confidentialité-utilité pour tous les $(v, \epsilon)$, il souffre de coûts de communication prohibitifs (exponentiels en $v$). À l'inverse, les schémas économes en communication comme la Réponse de Hadamard (HR - Hadamard Response) et la Réponse de Géométrie Projective (PGR - Projective Geometry Response) n'atteignent souvent que des performances de l'ordre de l'optimalité ou quasi-optimales, avec des écarts de performance qui deviennent significatifs dans les régimes de confidentialité moyenne. Le présent article cherche à combler ce fossé en trouvant des schémas qui sont à la fois exactement optimaux (ou quasi-optimaux) et économes en communication.

Méthodologie
Les auteurs proposent une nouvelle classe de schémas LDP basés sur les plans de blocs combinatoires et une classe plus large appelée Plans Réguliers et à Équilibre par Paires (RPBD - Regular and Pairwise-Balanced Designs).

1. Schémas de Plans de Blocs :

   • Le mécanisme est construit à l'aide d'une structure d'incidence $(X, Y, I)$ où $X$ est le domaine d'entrée et $Y$ est le domaine de sortie.
   • La structure est définie par les paramètres $(v, b, r, k, \lambda)$, représentant la taille d'entrée, la taille de sortie, la régularité, l'uniformité et l'équilibre par paires, respectivement.
   • Le mécanisme produit un élément $y \in I_x$ avec une probabilité proportionnelle à $e^\epsilon$ et un élément dans $Y \setminus I_x$ autrement.
   • Un estimateur sans biais canonique est dérivé à partir des comptages des sorties tombant dans des ensembles spécifiques.
   • Idée Clé : Les auteurs établissent que pour une taille d'entrée $v$ et un budget de confidentialité $\epsilon$ fixés, le risque d'un schéma de plan de blocs dépend uniquement du paramètre $k$ (la taille de l'intersection entre les ensembles d'entrée et de sortie), et non de $b$, $r$ ou $\lambda$. Plus précisément, deux schémas de plans de blocs ayant le même $k$ sont « marginalement équivalents » et produisent des risques identiques pour les fonctions de perte décomposables.

2. Conditions d'Optimalité :

   • En s'appuyant sur l'optimalité exacte connue du schéma SS, l'article prouve que tout schéma de plan de blocs avec un paramètre $k \in K^*_{v,\epsilon}$ (l'ensemble des entiers minimisant la fonction de risque) est également exactement optimal.
   • Les auteurs caractérisent précisément $K^*_{v,\epsilon}$, montrant qu'un schéma est exactement optimal si $k$ satisfait des bornes spécifiques liées à $\epsilon$ et $v$.

3. Efficacité de la Communication :

   • L'inégalité de Fisher dicte que pour tout schéma sans biais ou cohérent, $b \ge v$.
   • Les auteurs se concentrent sur les plans de blocs symétriques où $b = v$, atteignant le coût de communication théorique minimum pour les schémas sans biais.
   • Lorsqu'un plan de blocs symétrique avec le $k$ optimal n'existe pas pour un $(v, \epsilon)$ donné, l'article utilise des plans de blocs dérivés et résiduels pour construire des schémas non symétriques qui restent exactement optimaux ou quasi-optimaux avec un faible $b$.

4. Schémas RPBD :

   • Pour répondre à l'« existence parcellaire » des plans de blocs pour des paramètres arbitraires, les auteurs relâchent la contrainte d'uniformité, proposant des Plans Réguliers et à Équilibre par Paires (RPBD).
   • Les schémas RPBD abandonnent l'exigence que $|I_y| = k$ pour tout $y$, tout en conservant la régularité ($r$) et l'équilibre par paires ($\lambda$).
   • Les auteurs montrent que les schémas RPBD ayant un ratio $[b:r:\lambda]$ similaire à celui du schéma SS optimal atteignent un risque quasi-optimal. Ceux-ci peuvent être construits en tronquant des plans de blocs symétriques existants.

Résultats Clés

• Optimalité Exacte avec Faible Coût : L'article identifie de nombreux nouveaux schémas LDP qui atteignent l'arbitrage exact de confidentialité-utilité (correspondant à la borne inférieure $M_{v,u,\epsilon}$) avec le coût de communication minimum ($b=v$) pour une gamme plus large de paires $(v, \epsilon)$ que ce qui était connu précédemment.
• Unification : Le cadre unifie les schémas existants (Réponse Aléatoire, Sélection de Sous-ensembles, Réponse de Hadamard, Réponse de Géométrie Projective) sous l'égide unique des plans de blocs.
• Quasi-Optimalité via la Troncature : Pour les cas où les plans de blocs exacts optimaux n'existent pas, l'article démontre que la troncature de plans de blocs symétriques pour former des schémas RPBD produit des performances quasi-optimales avec des coûts de communication nettement inférieurs aux méthodes de pointe précédentes (ex: PGR).
  • Exemple : Pour $v=100, \epsilon=1$, un schéma RPBD tronqué basé sur un ensemble de différence de résidus quartiques atteint une erreur d'estimation plus faible et nécessite environ 6,66 bits par client, contre environ 8,41 bits pour un schéma PGR tronqué.
• Connexion avec la Conjecture de Hadamard : L'article lie l'existence de schémas exactement optimaux avec un coût de communication minimum dans le régime de haute confidentialité ($\epsilon \approx 0$) à la conjecture de Hadamard. Si la conjecture est vérifiée, des schémas exactement optimaux avec $b=v$ (ou $b=2v$) existent pour tout $v$.

Signification
L'article affirme fournir un nouveau cadre unifié pour découvrir des schémas LDP qui surmontent le compromis traditionnel entre l'optimalité exacte et l'efficacité de la communication. En déplaçant l'attention des constructions ad hoc spécifiques vers les propriétés combinatoires des plans de blocs, les auteurs démontrent que :

1. De nombreux schémas proposés précédemment (HR, PGR) sont en réalité exactement optimaux pour des régimes spécifiques, un fait qui n'était pas établi auparavant.
2. De nouveaux schémas peuvent être générés systématiquement pour atteindre l'optimalité exacte avec des coûts de communication minimaux pour un ensemble plus large de paramètres.
3. Le passage aux schémas RPBD permet d'obtenir des performances quasi-optimales avec de faibles coûts de communication dans les scénarios où la construction de plans de blocs exacts optimaux est mathématiquement impossible.

Le travail souligne que l'analyse de l'arbitrage exact de confidentialité-utilité (incluant les facteurs constants) est cruciale pour un déploiement pratique, et que l'approche par plans de blocs proposée offre une voie rigoureuse pour y parvenir sans sacrifier l'efficacité de la communication.