The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

Résumé Technique : Le mécanisme de l'arbre binaire est optimal pour le comptage continu en confidentialité différentielle approximative

Énoncé du Problème
L'article traite du problème fondamental du comptage continu privé. Dans ce cadre, une organisation observe un flux binaire $x \in \{0, 1\}^n$ de longueur $n$, où un '1' à l'étape de temps $i$ indique un événement contribué par un individu unique. L'objectif est de publier les décomptes cumulés (sommes de préfixes) $Ax$ à chaque étape de temps $i \in [n]$ tout en respectant la $(\epsilon, \delta)$-confidentialité différentielle (DP). Ici, $A$ est la matrice de somme de préfixes triangulaire inférieure de taille $n \times n$. La métrique principale pour la précision est l'erreur $\ell_\infty$ attendue, définie par $\mathbb{E}[\|M(x) - Ax\|_\infty]$, qui représente l'erreur maximale sur l'ensemble des étapes de temps.

Bien que le mécanisme de l'arbre binaire soit l'algorithme standard pour cette tâche, son optimalité dans le cadre de la DP approximative ($\delta > 0$) était une question ouverte. Des analyses antérieures ont montré que le mécanisme de l'arbre binaire atteint une erreur $\ell_\infty$ de $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$. Cependant, la meilleure borne inférieure connue n'était que de $\Omega(\log n / \epsilon)$ (spécifiquement pour la racine carrée de l'erreur quadratique maximale attendue), laissant un écart quant à savoir si la dépendance en $\log^{3/2} n$ vis-à-vis de la longueur du flux $n$ est nécessaire.

Méthodologie et Aperçu de la Preuve
Les auteurs prouvent que le mécanisme de l'arbre binaire est asymptotiquement optimal en établissant une borne inférieure correspondante de $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. La preuve procède par plusieurs étapes techniques clés :

1. Réduction aux mécanismes oblitous : En suivant des travaux antérieurs, les auteurs réduisent le problème à l'analyse de mécanismes oblitous de la forme $M(x) = Ax + z$, où$z$ est un vecteur de bruit indépendant de l'entrée $x$. L'objectif devient de borner $\mathbb{E}[\|z\|_\infty]$.
2. Décomposition en base d'arbre : Au lieu d'analyser directement le bruit dans la base standard, les auteurs décomposent le vecteur de bruit $z$ dans une base induite par un arbre binaire parfait. Plus précisément, ils définissent des vecteurs $\chi_u$ correspondant à des sous-arbres (indicateurs de feuilles dans un sous-arbre). Dans cette base, le bruit à toute feuille $i$ est la somme des coefficients $b_u$ le long du chemin allant de la racine à la feuille $i$. Cela transforme le problème de la borne de l'erreur de coordonnée maximale en un problème de l'accumulation de bruit le long des chemins racine-feuille.
3. Accumulation de bruit et incertitude résiduelle : La preuve introduit le concept de « bruit résiduel » $\sigma_u$. Elle soutient que si le bruit à un nœud $u$ peut être prédit avec une grande précision à partir du bruit dans ses sous-arbres, la confidentialité est violée. Les auteurs définissent $\sigma_u$ comme l'erreur absolue attendue de la prédiction du coefficient de bruit à un nœud étant donné le bruit dans les sous-arbres situés en dessous. Ils montrent que l'erreur $\ell_\infty$ attendue est minorée par une somme pondérée de ces incertitudes résiduelles le long de chemins aléatoires racine-feuille.
4. Surmonter l'obstacle de la « prédiction » : Un défi majeur est qu'un adversaire ne peut pas observer directement le bruit du sous-arbre pour prédire le bruit du nœud actuel car l'entrée $x$ est inconnue. Pour contourner cela, les auteurs emploient une stratégie de « petits-enfants ». Ils montrent qu'en portant l'attention sur des sous-arbres spécifiques et en utilisant trois copies indépendantes du mécanisme (en exploitant les propriétés de composition de la DP), un adversaire peut utiliser une astuce de la médiane de trois pour réduire la variance du bruit. Cela permet la construction d'un mécanisme dérivé où l'adversaire peut calculer des mesures linéaires de la forme $x_i \nu_i + q$, où $q$ possède une variance contrôlée.
5. Mesures linéaires et ondelettes de Haar : L'étape finale construit un adversaire utilisant des mesures linéaires inspirées de la base des ondelettes de Haar. En choisissant des vecteurs de mesure orthogonaux, les auteurs relient la somme des erreurs quadratiques des estimations de l'adversaire à la norme $\ell_2$ du bruit résiduel. Ils démontrent que si le bruit résiduel $\sigma_u$ était faible, l'adversaire pourrait distinguer des entrées voisines avec une probabilité élevée, violant ainsi la confidentialité différentielle. Cela force le bruit résiduel à être important, spécifiquement $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$.
6. Sommation : La sommation de ces incertitudes résiduelles le long du chemin produit la borne finale de $\Omega(\log^{3/2} n)$.

Contributions Clés et Résultats

• Optimalité du Mécanisme de l'Arbre Binaire : L'article prouve que pour la DP approximative, tout mécanisme de comptage continu doit engendrer une erreur $\ell_\infty$ attendue de $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. Cela correspond à la borne supérieure du mécanisme de l'arbre binaire (à un facteur constant près), résolvant le problème ouvert de savoir si la dépendance en $\log^{3/2} n$ est nécessaire.
• Resserrement des Bornes de la DP Pure : Pour la DP pure ($\delta = 0$), le résultat resserre l'écart entre la borne supérieure connue de $O(\log^2 n / \epsilon)$ et la borne inférieure, montrant une borne inférieure de $\Omega(\log^{3/2} n / \epsilon)$.
• Séparation de la Discrépance Héréditaire : En tant que corollaire, les auteurs dérivent la plus grande séparation possible entre la discrépance héréditaire et l'erreur des requêtes linéaires privées. Ils montrent que la borne supérieure générale $err_{\epsilon, \delta}^\infty(A) = O(\log^{3/2} m \cdot \text{herdisc}_\infty(A))$ est serrée dans sa dépendance vis-à-vis du nombre de requêtes $m$, car la matrice de somme de préfixes a une discrépance héréditaire de 1 mais nécessite une erreur de $\Omega(\log^{3/2} n)$.

Signification
L'article affirme résoudre un problème central de la confidentialité différentielle en prouvant que le mécanisme de l'arbre binaire est asymptotiquement optimal pour le comptage continu dans le cadre de la DP approximative. Les techniques développées, particulièrement la combinaison de la décomposition du bruit basée sur les arbres, l'analyse du bruit résiduel et l'utilisation de l'astuce de la médiane de trois pour gérer les attaques par mesures linéaires, sont présentées comme des idées novatrices qui pourraient trouver d'autres applications dans la preuve de bornes inférieures pour la confidentialité différentielle. Le résultat confirme que les algorithmes de pointe actuels ne peuvent pas être significativement améliorés en termes de leur dépendance vis-à-vis de la longueur du flux $n$.