Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Technische Samenvatting: Exact Optimaal en Communicatie-efficiënt Privaat Schatten via Block Designs

Probleemformulering
Het artikel behandelt het probleem van het privaat schatten van discrete distributies onder het Local Differential Privacy (LDP) raamwerk. In deze setting observeren $n$ cliënten datapunten $X_i$ die zijn getrokken uit een onbekende distributie $P$ over een domein van grootte $v$. Elke cliënt past een privacy-mechanisme $Q$ toe om een geprivatiseerde output $Y_i$ te genereren die voldoet aan $\epsilon$-LDP voordat deze naar een centrale server wordt verzonden. De server construeert vervolgens een estimator $\hat{P}_n$ om $P$ te herstellen. Het doel is om de worst-case risico (schattingsfout) te minimaliseren onder een specifieke verliesfunctie (voornamelijk $\ell_u^u$ voor $1 \le u \le 2$) terwijl tegelijkertijd de communicatiekosten worden geminimaliseerd, gedefinieerd door de grootte van het output-alfabet $b = |\mathcal{Y}|$.

Hoewel het Subset Selection (SS) schema bekend staat om het bereiken van de exact optimale privacy-utiliteit trade-off voor alle $(v, \epsilon)$, lijdt het aan prohibitief hoge communicatiekosten (exponentieel in $v$). Omgekeerd bereiken communicatie-efficiënte schema's zoals Hadamard Response (HR) en Projective Geometry Response (PGR) vaak slechts orde-optimale of bijna-optimale prestaties, waarbij de prestatiekloof aanzienlijk wordt in middelmatige privacy-regimes. Dit artikel streeft ernaar deze kloof te overbruggen door schema's te vinden die zowel exact optimaal (of bijna-optimaal) als communicatie-efficiënt zijn.

Methodologie
De auteurs stellen een nieuwe klasse LDP-schema's voor gebaseerd op combinatorische block designs en een bredere klasse genaamd Regular and Pairwise-Balanced Designs (RPBD).

1. Block Design Schema's:

   • Het mechanisme wordt geconstrueerd met behulp van een incidentiestructuur $(X, Y, I)$ waarbij $X$ het input-domein is en $Y$ het output-domein.
   • De structuur wordt gedefinieerd door parameters $(v, b, r, k, \lambda)$, representatief voor input-grootte, output-grootte, regulariteit, uniformiteit en pairwise balance, respectievelijk.
   • Het mechanisme geeft een element $y \in I_x$ uit met een waarschijnlijkheid proportioneel aan $e^\epsilon$ en een element in $Y \setminus I_x$ anders.
   • Een canonieke onbevooroordeelde estimator wordt afgeleid op basis van de tellingen van outputs die in specifieke verzamelingen vallen.
   • Kerninzicht: De auteurs stellen vast dat het risico van een block design schema voor een vaste input-grootte $v$ en privacy budget $\epsilon$ alleen afhangt van de parameter $k$ (de grootte van de intersectie tussen input- en output-verzamelingen), en niet van $b$, $r$ of $\lambda$. Specifiek zijn twee block design schema's met dezelfde $k$ "marginaal equivalent" en leveren zij identieke risico's voor decomponeerbare verliesfuncties.

2. Optimaliteitsvoorwaarden:

   • Door gebruik te maken van de bekende exacte optimaliteit van het SS-schema, bewijst het artikel dat elk block design schema met een parameter $k \in K^*_{v,\epsilon}$ (de verzameling gehele getallen die de risicofunctie minimaliseren) ook exact optimaal is.
   • Het karakteriseert $K^*_{v,\epsilon}$ precies, waarbij wordt aangetoond dat een schema exact optimaal is als $k$ specifieke grenzen voldoet die gerelateerd zijn aan $\epsilon$ en $v$.

3. Communicatie-efficiëntie:

   • Fisher's ongelijkheid dicteert dat voor elk onbevooroordeeld of consistent schema, $b \ge v$.
   • De auteurs richten zich op symmetrische block designs waar $b = v$, waarmee de theoretische minimale communicatiekosten worden bereikt voor onbevooroordeelde schema's.
   • Wanneer een symmetrisch block design met de optimale $k$ niet bestaat voor een gegeven $(v, \epsilon)$, maakt het artikel gebruik van afgeleide (derived) en residuele (residual) block designs om niet-symmetrische schema's te construeren die toch exact optimaal of bijna-optimaal blijven met een lage $b$.

4. RPBD Schema's:

   • Om de "ijle existentie" van block designs voor willekeurige parameters aan te pakken, versoepelen de auteurs de uniformiteitsvereiste door Regular and Pairwise-Balanced Designs (RPBD) voor te stellen.
   • RPBD-schema's laten de eis los dat $|I_y| = k$ voor alle $y$, maar behouden enkel regulariteit ($r$) en pairwise balance ($\lambda$).
   • De auteurs tonen aan dat RPBD-schema's met een ratio $[b:r:\lambda]$ die vergelijkbaar is met die van het optimale SS-schema, bijna-optimale risico's bereiken. Deze kunnen worden geconstrueerd door bestaande symmetrische block designs te trunceren.

Belangrijkste Resultaten

• Exacte Optimaliteit met Lage Kosten: Het artikel identificeert talrijke nieuwe LDP-schema's die de exact optimale privacy-utiliteit trade-off bereiken (overeenkomend met de ondergrens $M_{v,u,\epsilon}$) met de minimale mogelijke communicatiekosten ($b=v$) voor een breder bereik van $(v, \epsilon)$-paren dan voorheen bekend.
• Unificatie: Het raamwerk verenigt bestaande schema's (Randomized Response, Subset Selection, Hadamard Response, Projective Geometry Response) onder de enkele paraplu van block designs.
• Nabij-optimaliteit via Truncatie: Voor gevallen waarin exact optimale block designs niet bestaan, demonstreert het artikel dat het trunceren van symmetrische block designs om RPBD-schema's te vormen, nabij-optimale prestaties oplevert met aanzienlijk lagere communicatiekosten dan eerdere state-of-the-art methoden (bijv. PGR).
  • Voorbeeld: Voor $v=100, \epsilon=1$ levert een getrunceerd RPBD-schema gebaseerd op een quartic residue difference set een lagere schattingsfout en vereist het ~6,66 bits per cliënt, vergeleken met ~8,41 bits voor een getrunceerd PGR-schema.
• Verbinding met de Hadamard Vermoeden: Het artikel koppelt de existentie van exact optimale schema's met minimale communicatiekosten in het hoge privacy-regime ($\epsilon \approx 0$) aan het Hadamard vermoeden. Als het vermoeden standhoudt, bestaan er exact optimale schema's met $b=v$ (of $b=2v$) voor alle $v$.

Betekenis
Het artikel beweert een nieuw, verenigd raamwerk te bieden voor het ontdekken van LDP-schema's die de traditionele trade-off tussen exact optimaliteit en communicatie-efficiëntie overwinnen. Door de focus te verschuiven van specifieke ad-hoc constructies naar de combinatorische eigenschappen van block designs, demonstreren de auteurs dat:

1. Veel eerder voorgestelde schema's (HR, PGR) feitelijk exact optimaal zijn voor specifieke regimes, een feit dat voorheen niet was vastgesteld.
2. Nieuwe schema's systematisch gegenereerd kunnen worden om exact optimaliteit te bereiken met minimale communicatiekosten voor een breder scala aan parameters.
3. De versoepeling naar RPBD-schema's nabij-optimale prestaties mogelijk maakt met lage communicatiekosten in scenario's waarin de constructie van exact optimale block designs mathematisch onmogelijk is.

Het werk benadrukt dat het analyseren van de exacte privacy-utiliteit trade-off (inclusief constante factoren) cruciaal is voor praktische implementatie, en dat de voorgestelde block design-benadering een rigoureuze weg biedt om dit te bereiken zonder communicatie-efficiëntie op te offeren.