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

Technisch Samenvatting: Het Binaire Boommechanisme is Optimaal voor Benaderende Differentieel Privé Continue Telling

Probleemstelling
Het artikel behandelt het fundamentele probleem van private continue telling (private continual counting). In deze setting observeert een organisatie een binaire stroom $x \in \{0, 1\}^n$ van lengte $n$, waarbij een '1' op tijdstap $i$ een gebeurtenis aangeeft die door een enkel individu is bijgedragen. Het doel is om de lopende tellingen (prefix-sommen) $Ax$ op elk tijdstap $i \in [n]$ vrij te geven terwijl aan $(\epsilon, \delta)$-differentieel privacy (DP) wordt voldaan. Hierbij is $A$ de $n \times n$ onderste driehoeksmatrix van prefix-sommen. De primaire metriek voor nauwkeurigheid is de verwachte $\ell_\infty$-fout, gedefinieerd als $\mathbb{E}[\|M(x) - Ax\|_\infty]$, wat de fout in het slechtste geval over alle tijdstappen vertegenwoordigt.

Hoewel het binaire boommechanisme de standaardalgoritme is voor deze taak, was de optimaliteit ervan in de benaderende DP-setting ($\delta > 0$) een openstaande vraag. Eerdere analyses toonden aan dat het binaire boommechanisme een $\ell_\infty$-fout bereikt van $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$. Echter, de beste bekende ondergrens was slechts $\Omega(\log n / \epsilon)$ (specifiek voor de wortel van de verwachte kwadratische slechtste-geval-fout), waardoor een gat ontstond over de vraag of de $\log^{3/2} n$-afhankelijkheid van de stroomlengte $n$ noodzakelijk is.

Methodologie en Overzicht van het Bewijs
De auteurs bewijzen dat het binaire boommechanisme asymptotisch optimaal is door een overeenkomstige ondergrens vast te stellen van $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. Het bewijs verloopt via verschillende belangrijke technische stappen:

1. Reductie naar Oblivious Mechanismen: Volgens eerdere werken reduceren de auteurs het probleem tot het analyseren van oblivious mechanismen van de vorm $M(x) = Ax + z$, waarbij $z$ een ruisvector is die onafhankelijk is van de input $x$. Het doel wordt het ondergrenzen van $\mathbb{E}[\|z\|_\infty]$.
2. Boombasis-decompositie: In plaats van de ruis direct in de standaardbasis te analyseren, deconstrueren de auteurs de ruisvector $z$ in een basis geïnduceerd door een perfecte binaire boom. Specifiek definiëren ze vectoren $\chi_u$ die overeenkomen met subbomen (indicatoren van bladeren in een subboom). In deze basis is de ruis in elk blad $i$ de som van de coëfficiënten $b_u$ langs het pad van de wortel naar het blad $i$. Dit transformeert het probleem van het begrenzen van de maximale coördinaatfout naar het begrenzen van de accumulatie van ruis langs wortel-naar-blad paden.
3. Ruisaccumulatie en Residuele Onzekerheid: Het bewijs introduceert het concept van "residuele ruis" $\sigma_u$. De auteurs argumenteren dat als de ruis in een knoop $u$ met hoge nauwkeurigheid voorspeld kan worden vanuit de ruis in de subbomen eronder, de privacy wordt geschonden. De auteurs definiëren $\sigma_u$ als de verwachte absolute fout in het voorspellen van de ruiscoëfficiënt bij een knoop gegeven de ruis in de subbomen eronder. Ze tonen aan dat de verwachte $\ell_\infty$-fout ondergrenst wordt door een gewogen som van deze residuele onzekerheden langs willekeurige wortel-naar-blad paden.
4. Het Overwinnen van de "Voorspellings"-obstakel: Een grote uitdaging is dat een tegenstander de subboomruis niet direct kan observeren om de huidige knoopruis te voorspellen omdat de input $x$ onbekend is. Om dit te omzeilen, gebruiken de auteurs een "kleinkind"-strategie. Ze tonen aan dat door de aandacht te beperken tot specifieke subbomen en gebruik te maken van drie onafhankelijke kopieën van het mechanisme (rekening houdend met compositie-eigenschappen van DP), een tegenstander een mediaan-van-drie truc kan gebruiken om de ruisvariantie te verminderen. Dit maakt de constructie van een afgeleid mechanisme mogelijk waarbij de tegenstander lineaire metingen kan berekenen van de vorm $x_i \nu_i + q$, waarbij $q$ een gecontroleerde variantie heeft.
5. Lineaire Metingen en Haar-wavelets: De laatste stap construeert een tegenstander met lineaire metingen geïnspireerd door de Haar-waveletbasis. Door orthogonale meetvectoren te kiezen, relateren de auteurs de som van de gekwadrateerde fouten van de schattingen van de tegenstander aan de $\ell_2$-norm van de residuele ruis. Ze demonstreren dat als de residuele ruis $\sigma_u$ klein zou zijn, de tegenstander naburige inputs met een hoge waarschijnlijkheid zou kunnen onderscheiden, wat de differentiele privacy schendt. Dit dwingt de residuele ruis groot te zijn, specifiek $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$.
6. Sommatie: Het sommeren van deze residuele onzekerheden langs het pad levert de uiteindelijke $\Omega(\log^{3/2} n)$ ondergrens op.

Belangrijkste Bijdragen en Resultaten

• Optimaliteit van het Binaire Boommechanisme: Het artikel bewijst dat voor benaderende DP elk mechanisme voor continue telling een verwachte $\ell_\infty$-fout moet ondergaan van $\Omega(\log^{3//2} n / \max\{\epsilon, \delta\})$. Dit komt overeen met de bovengrens van het binaire boommechanisme (op constante factoren), waarmee het openstaande probleem wordt opgelost of de $\log^{3/2} n$-afhankelijkheid noodzakelijk is.
• Versterking van Pure DP-grenzen: Voor pure DP ($\delta = 0$) versterkt het resultaat de kloof tussen de bekende bovengrens $O(\log^2 n / \epsilon)$ en de ondergrens, door een ondergrens van $\Omega(\log^{3/2} n / \epsilon)$ aan te tonen.
• Scheiding van Hereditaire Discrepantie: Als een bijgerecht (corollary) leiden de auteurs de grootste mogelijke scheiding af tussen hereditaire discrepantie en de fout van private lineaire queries. Ze tonen aan dat de algemene bovengrens $err_{\epsilon, \delta}^\infty(A) = O(\log^{3/2} m \cdot \text{herdisc}_\infty(A))$ strikt is in zijn afhankelijkheid van het aantal queries $m$, aangezien de prefix-sommatrix een hereditaire discrepantie van 1 heeft maar een $\Omega(\log^{3/2} n)$ fout vereist.

Betekenis
Het artikel beweert een centraal openstaand probleem in differentiele privacy op te lossen door te bewijzen dat het binaire boommechanisme asymptotisch optimaal is voor continue telling in de benaderende DP-setting. De ontwikkelde technieken, met name de combinatie van boomgebaseerde ruis-decompositie, residuele ruis-analyse en het gebruik van de mediaan-van-drie truc om lineaire metingsaanvallen te hanteren, worden gepresenteerd als nieuwe ideeën die mogelijk verdere toepassingen vinden bij het bewijzen van ondergrenzen voor differentiele privacy. Het resultaat bevestigt dat de huidige state-of-the-art algoritmen niet significant verbeterd kunnen worden in termen van hun afhankelijkheid van de stroomlengte $n$.