Compoziția avansată în DP este mai proastă decât Compoziția de bază

Am probleme cu înțelegerea teoremei avansate de compoziție în DP.

Să am două mecanisme aproximative-DP ($k = 2)$ unde fiecare satisface $(\epsilon = 0,5, \delta = 0,1)$-DP. Prin compoziția de bază, știu că utilizarea a două interogări secvenţial va garanta $(2 \cdot 0,5, 2 \cdot 0,1) = (1, 0,2)$-DP.

Compoziție avansată, însă, spune că, în loc de compoziția având $\delta' = k\cdot \delta$, dacă suntem dispuși să luăm $\delta ' = k\cdot \delta + \tilde{\delta}$ pentru unii $\tilde{\delta}>0$, apoi al nostru $\epsilon'$ se îmbunătăţeşte din $2\epsilon$ la $\epsilon' = k\cdot \epsilon(\exp(\epsilon) - 1) + \epsilon\sqrt{2 \cdot k \cdot \log (1/\tilde{\delta})}$.

Acum, să presupunem că sunt mulțumit $\delta' = 0,3$ în loc de $\delta' = 0,2$. Acest lucru înseamnă $\tilde{\delta}= 0,1$. Asa de, $$\epsilon' = 2\cdot 0,5(\exp(0,5) - 1) + 0,5\sqrt{2 \cdot 2 \cdot \log (1/0,1)} = 2,16 \gg 1.$$

Nu înțeleg cum se îmbunătățește acest lucru asupra compoziției de bază, deoarece, evident, aici nu este cazul! Fac ceva greșit?

Editați | ×:

Cifrele pe care le-am fixat nu joacă niciun rol. În general, știm că putem compune $k$ mecanisme (presupunem că fiecare este $(\epsilon, \delta)$-DP) și obțineți $(k\epsilon, k\delta)$-DP doar prin compoziția de bază. Dar, prin creștere $k\delta$ un pic, primim un $\epsilon'$ care este egal cu:

$$k \epsilon \underbrace{(e^\epsilon - 1)}_{\geq 0} + \underbrace{\epsilon \sqrt{2 k \log(1 / \tilde{\delta})}}_{ \geq 0} $$ care nu este întotdeauna mai mică decât $k\epsilon$.

Mai exact, lasă-mi alocația suplimentară $\tilde{\delta} = 0,1$. Vreau să văd când compoziția avansată se îmbunătățește față de compoziția de bază. Deci, în rezumat, vreau să văd când sunt valabile următoarele:

\begin{align} & k\epsilon > k \epsilon (e^\epsilon - 1) + \epsilon \sqrt{2 k \log(1 / \tilde{\delta})} \ \iff & k > k (e^\epsilon - 1) + \sqrt{2 k \log(1 / \tilde{\delta})} \ \iff & \sqrt{k}(2 - e^\epsilon) > \sqrt{2 \log(1 / \tilde{\delta})} \ \iff & k > \frac{2 \log(1 / \tilde{\delta})}{(2 - e^\epsilon)^2} \ \iff & k > \frac{2 \log(10)}{(2 - e^\epsilon)^2}. \end{align} Acum presupune că vreau să folosesc $2$ mecanisme. Apoi, trebuie să am:

\begin{align} & \log(10) <(2 - e^\epsilon)^2 \ \iff & \epsilon < \log(2 - \sqrt{\log(10)}) = -0,7286 \end{align} ceea ce nu este niciodată posibil. Deci când $k = 2$, iar dacă sunt dispus să adaug doar $0.1$ la $\delta'$, atunci nu pot îmbunătăți niciodată compoziția de bază cu compoziția avansată?

Editarea 2: În general, putem spune că compoziția avansată îmbunătățește compoziția de bază doar dacă sunt îndeplinite următoarele:

$$ \epsilon < \log\left[2 - \sqrt{\frac{2 \log ( 1/\tilde{\delta})}{k}} \right] $$

care necesită $k > 4$ când, de exemplu, $\tilde{\delta} = 0,1$ iar acest număr crește când $\tilde{\delta}$ scade.

În general, simt că compoziția avansată este cu adevărat inutilă când $k$ nu este mare. Este adevărat?

În primul rând, există și alte rezultate de compoziție, de exemplu, cred Aceasta îmbunătățește compoziția avansată. Voi răspunde totuși la o întrebare mai generală (la care cred că ajungi).

Mecanisme date $M_1,\puncte, M_n$, cum se obține cei mai buni parametri pentru compoziția lor?

În mod ideal am putea spune „folosește compoziția de bază pentru mici $k$", și "utilizați compoziția avansată pentru mari $k$". Din păcate, se poate arăta în mod oficial că acest lucru nu este simplu. Complexitatea calculării compoziției optime a confidențialității diferențiale studii, pentru mecanisme de „input”. $M_1,\puncte, M_n$ a parametrilor $(\epsilon_1,\delta_1),\dots, (\epsilon_n, \delta_n)$, problema găsirii parametrilor „minimi”. $(\epsilon^*, \delta^*)$ a mecanismului de compunere.

Rezultatele anterioare erau cunoscute, de exemplu

Dacă $M_1,\puncte, M_n$ sunt toti $(\epsilon,\delta)$-privat pentru o pereche fixă ​​de $(\epsilon, \delta)$, și o țintă $\delta^*$ este dată, atunci valoarea optimă a $\epsilon^*$ este minimul $\epsilon^*\geq 0$ astfel încât $$\frac{1}{(1+e^\epsilon)^n}\sum_{\ell = \lceil (\epsilon^*+n\epsilon)/2\epsilon\rceil}^n\binom{n }{\ell}(e^{\ell \epsilon}-e^{\epsilon^*}e^{(n-\ell)\epsilon}) \leq 1 - \frac{1-\delta^*} {(1-\delta)^n}.$$

Lucrarea pe care am legat-o extinde acest rezultat la cazul $M_1,\puncte, M_n$ fiind privat de parametri $(\epsilon_1,\delta_1),\dots,(\epsilon_n,\delta_n)$ nu toate la fel. Ei găsesc o expresie similară (dar mai complicată) care caracterizează valoarea optimă a $\epsilon^*$ (când i se oferă o „țintă” $\delta^*$), și găsiți că calcularea acestei soluții optime este $\#P$-complet, de ex. este puțin probabil să poată fi realizat eficient. Acest lucru este valabil chiar și în cazul compoziției pentru mecanisme pure, adică $\delta_i = 0$ pentru toți $i$.

Poate cel mai interesant pentru tine este că există algoritmi de aproximare pentru această problemă (tot în lucrarea respectivă). Nu știu dacă cineva le-a implementat, dar dacă le-a făcut atunci mi se pare o opțiune bună pentru selecția concretă a parametrilor.

De asemenea, merită menționat faptul că există noțiuni de confidențialitate strâns legate (și anume intimitate diferențială concentrată) unde povestea compoziției este mai simplă, în timp ce încă (într-un anumit sens) se realizează $O(\sqrt{k})$ scalare cu $k$-compoziţia pliului, mai degrabă decât $O(k)$ scalarea „compoziție de bază” vă oferă.