Technische Samenvatting: Sort, Partition, Randomize: Optimale Binaire Hypothesetoetsing onder Lokale Differentieel Privaatheid

1. Probleemopstelling

Het artikel behandelt het probleem van het ontwerpen van optimale $\epsilon$-lokale differentieel private (LDP) mechanismen voor binaire hypothesetoetsing. De setting betreft een observatie $X$ getrokken uit een van de twee bekende distributies, $P_0$ of $P_1$, gedefinieerd over een eindig alfabet $\mathcal{X}$ van grootte $k$. Voordat er openbaarmaking plaatsvindt, wordt elke steekproef geprivatiseerd door een kanaal $Q$ dat voldoet aan de $\epsilon$-LDP-voorwaarde:
$$Q(y|x) \leq e^\epsilon Q(y|x') \quad \forall x, x' \in \mathcal{X}, y \in \mathcal{Y}$$
Het doel is om $Q$ te ontwerpen om een nutscriterium te maximaliseren dat wordt gedefinieerd door een $f$-divergentie tussen de geïnduceerde outputdistributies $M_0 = Q^\top P_0$ en $M_1 = Q^\top P_1$. De nutfunctie is:
$$D_f(M_0 \| M_1) = \sum_{y \in \mathcal{Y}} M_1(y) f\left(\frac{M_0(y)}{M_1(y)}\right)$$
waarbij $f$ een convexe functie is met $f(1)=0$. Dit raamwerk omvat Total Variation (TV), Kullback-Leibler (KL) divergentie en $E_\gamma$ (hockey-stick) divergentie. Het probleem wordt ook beschouwd onder een communicatiebeperking, waarbij de output-alfabetgrootte beperkt is tot $\ell$ ($\ell \leq k$).

2. Methodologie en Structurele Karakterisering

Vorig werk stelde vast dat optimale mechanismen "trappenvormig" zijn (probabiliteiten nemen slechts twee waarden aan, $\theta$ en $e^\epsilon \theta$), maar vertrouwde op lineaire programma's met $2^k$ variabelen, wat computationeel onuitvoerbaar is voor een gematigde $k$. Dit artikel introduceert een scherpe structurele karakterisering om de zoekruimte te verkleinen.

De Sort-Partition-Randomize (SPR) Klasse

De auteurs bewijzen dat er, na het sorteren van het input-alfabet op basis van de likelihood ratio $r_i = P_0(x_i)/P_1(x_i)$, een optimaal mechanisme bestaat dat een specifieke driestapsstructuur volgt:

1. Sort (Sorteren): Bestel de inputs zodanig dat $r_1 < r_2 < \dots < r_k$.
2. Partition (Partitioneren): Verdeel het gesorteerde alfabet in aaneengesloten blokken (intervallen) $\pi = (B_1, \dots, B_s)$.
3. Randomize (Randomiseren): Pas $s$-aire Randomized Response (RR) toe op het bloklabel. Specifiek: als de input $x$ in blok $B_j$ valt, is de output $j$ met een waarschijnlijkheid van $\frac{e^\epsilon}{e^\epsilon + s - 1}$ en elk ander blok $j' \neq j$ met een waarschijnlijkheid van $\frac{1}{e^\epsilon + s - 1}$.

Geometrische Bewijsstrategie

De optimaliteit van SPR-mechanismen wordt afgeleid van de geometrie van de joint-range polytoop $\mathcal{R}_\ell(p, q)$, die alle haalbare paren outputdistributies $(M_0, M_1)$ representeert onder de LDP-beperking. Het bewijs verloopt in drie stappen:

1. Verfijning: Elk extreem punt van de joint range kan worden gerealiseerd door een trappenvormig kanaal waarvan de actieve kolommen LR-aaneengesloten hoge sets hebben (sets van inputs die naar een specifieke output mappen en een aaneengesloten interval vormen in de gesorteerde volgorde).
2. Convexe Decompositie: Elk dergelijk trappenvormig kanaal met LR-aaneengesloten hoge sets ligt in de convexe hull van SPR-mechanismen.
3. Niet-extremiteit van Coarsening: Het deterministisch samenvoegen van outputs van een SPR-mechanisme (tenzij dit resulteert in een enkele output) produceert geen nieuw extreem punt.

Aangezien $f$-divergenties convex zijn in het outputpaar $(M_0, M_1)$, wordt het maximum bereikt in een extreem punt van de joint range. Daarom is een optimaal mechanisme altijd een SPR-mechanisme.

3. Belangrijkste Bijdragen

1. Polynomial-Time Exact Algoritme

Het artikel biedt het eerste polynomial-time algoritme om het exacte optimale mechanisme voor elke $f$-divergentie te berekenen.

• Onbeperkte Output: Een exact dynamisch programma (DP) draait in $O(k^3)$ tijd.
• Beperkte Output ($\ell$ outputs): De DP draait in $O(\ell k^2)$ tijd.
• Mechanisme: De DP maakt gebruik van de additieve decomponeerbaarheid van $f$-divergenties over aaneengesloten blokken. Het berekent intervalscores $\mu[a:b]$ en vindt de partitie van $[1:k]$ in $s$ blokken die de totale score maximaliseert, genormaliseerd door de RR-factor.

2. Gesloten Vorm Oplossing voor $E_\gamma$ Divergentie

Voor het specifieke geval van de $E_\gamma$ divergentie (die Total Variation bevat voor $\gamma=1$), reduceert het optimale mechanisme tot een Generalized Binary Mechanism.

• De optimale strategie is om een drempelset te definiëren $S_\gamma = \{x : P_0(x) \geq \gamma P_1(x)\}$.
• Het mechanisme past binaire randomized response toe op de indicatorbit $\mathbb{1}\{X \in S_\gamma\}$.
• Dit resultaat geldt voor elke $\epsilon$ en elke alfabetgrootte $k$, en breidt eerdere bovenwaardige grenzen uit die alleen voor binaire inputs nauwkeurig waren.

3. Uitbreiding naar Andere Doelstellingen

• Rényi Divergenties: De SPR-optimaliteit en de $O(\ell k^2)$ DP zijn van toepassing op Rényi-divergenties via een monotone reductie naar $f$-divergenties.
• $\ell_r$ Afstand: Het optimale mechanisme voor de $\ell_r$ afstand wordt getoond te de binaire SPR-mechanisme te zijn (equivalent aan het TV-optimale mechanisme).

4. Resultaten en Numerieke Illustratie

De auteurs valideren hun theoretische bevindingen via numerieke experimenten:

• Kleine $k$ ($k=6$): Het SPR dynamisch programma komt overeen met de exponentiële-tijd Kairouz-Oh-Viswanath (KOV) lineaire programmering tot op machineprecisie ($\leq 6.1 \times 10^{-14}$), wat de structurele stelling empirisch bevestigt.
• Grote $k$ ($k=100$): De KOV LP is onhaalbaar (met $2^{100}$ variabelen), terwijl de SPR DP het exacte optimum berekent in minder dan 20 seconden op een standaard laptop.
• Prestaties: Het SPR-mechanisme presteert significant beter dan eenvoudige baselines zoals het binaire mechanisme (dat vroeg plateau bereikt) en $k$-aire randomized response (die oninformatief is voor kleine $\epsilon$) over het volledige privacybereik.

5. Betekenis en Claims

Het artikel claimt een langdurige computationele bottleneck in het ontwerp van lokale differentieel private mechanismen te hebben opgelost.

• Efficiëntie: Het transformeert een exponentiële-tijd zoekprobleem naar een polynomial-time exacte optimalisatie, wat het ontwerp van optimale mechanismen mogelijk maakt voor alfabetgroottes die voorheen als computationeel onhaalbaar werden beschouwd.
• Interpreteerbaarheid: De SPR-structuur biedt een eenvoudige, interpreteerbare beschrijving van optimale privatisering: "aggregeer symbolen met vergelijkbare likelihood ratios, en privatiseer vervolgens het grove label."
• Generaliteit: De resultaten zijn van toepassing op het volledige bereik van privacybudgetten $\epsilon$ en diverse nutsobjectieven, waardoor men verder gaat dan asymptotische regimes of speciale gevallen.
• Beperkingen: De auteurs merken expliciet op dat hun karakterisering specifiek is voor eenvoudige binaire hypothesetoetsing onder pure, niet-interactieve $\epsilon$-LDP op een eindig alfabet. Uitbreidingen naar multi-hypothesetoetsing, benaderde LDP of interactieve protocollen blijven openstaande. Daarnaast leunt de huidige DP op de additieve structuur van $f$-divergenties, en zijn efficiënte algoritmen voor bredere quasi-convexe doelstellingen (zoals de Chernoff-informatie) nog niet geleverd.