Tôi gặp khó khăn trong việc hiểu định lý thành phần nâng cao trong DP.
Hãy để tôi có hai cơ chế DP gần đúng ($k = 2)$ trong đó mỗi thỏa mãn $(\epsilon = 0,5, \delta = 0,1)$-ĐP. Theo thành phần cơ bản, tôi biết rằng việc sử dụng hai truy vấn tuần tự sẽ đảm bảo $(2 \cdot 0,5, 2 \cdot 0,1) = (1, 0,2)$-ĐP.
Tuy nhiên, thành phần nâng cao nói rằng, thay vì thành phần có $\delta' = k\cdot \delta$, nếu chúng ta sẵn sàng nhận $\delta ' = k\cdot \delta + \tilde{\delta}$ cho một số $\tilde{\delta}>0$, sau đó của chúng tôi $\epsilon'$ cải thiện từ $2\epsilon$ đến $\epsilon' = k\cdot \epsilon(\exp(\epsilon) - 1) + \epsilon\sqrt{2 \cdot k \cdot \log (1/\tilde{\delta})}$.
Bây giờ, giả sử tôi hài lòng với $\delta' = 0,3$ thay vì $\delta' = 0,2$. Điều này có nghĩa là $\tilde{\delta}= 0,1$. Cho nên,
$$\epsilon' = 2\cdot 0,5(\exp(0,5) - 1) + 0,5\sqrt{2 \cdot 2 \cdot \log (1/0,1)} = 2,16 \gg 1.$$
Tôi không hiểu làm thế nào điều này được cải thiện dựa trên thành phần cơ bản, vì rõ ràng ở đây không phải vậy! Tôi có đang làm gì sai không?
Chỉnh sửa:
Những con số tôi đã cố định không đóng vai trò gì. Nói chung, chúng tôi biết rằng chúng tôi có thể sáng tác $k$ cơ chế (giả sử mỗi cơ chế là $(\epsilon, \delta)$-DP) và nhận $(k\epsilon, k\delta)$-DP chỉ bằng thành phần cơ bản. Nhưng, bằng cách tăng $k\delta$ một chút, chúng tôi nhận được một $\epsilon'$ tương đương với:
$$k \epsilon \underbrace{(e^\epsilon - 1)}_{\geq 0} + \underbrace{\epsilon \sqrt{2 k \log(1 / \tilde{\delta})}}_{ \geq 0} $$
không phải lúc nào cũng nhỏ hơn $k\epsilon$.
Cụ thể, hãy để khoản trợ cấp thêm của tôi là $\tilde{\delta} = 0,1$. Tôi muốn xem khi nào bố cục nâng cao cải thiện bố cục cơ bản. Vì vậy, tóm lại, tôi muốn xem khi nào những điều sau đây được giữ:
\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}
Bây giờ giả sử tôi muốn sử dụng $2$ cơ chế. Sau đó, tôi cần phải có:
\begin{align}
& \log(10) <(2 - e^\epsilon)^2 \
\iff & \epsilon < \log(2 - \sqrt{\log(10)}) = -0,7286
\end{align}
điều không bao giờ có thể. Vì vậy, khi $k = 2$, và nếu tôi sẵn sàng chỉ thêm $0.1$ đến $\delta'$, thì bao giờ mới cải thiện được bố cục cơ bản bằng bố cục nâng cao?
Chỉnh sửa 2:
Nói chung, chúng ta có thể nói rằng thành phần nâng cao chỉ cải thiện dựa trên thành phần cơ bản nếu thỏa mãn những điều sau:
$$ \epsilon < \log\left[2 - \sqrt{\frac{2 \log ( 1/\tilde{\delta})}{k}} \right] $$
đòi hỏi $k > 4$ khi nào, ví dụ: $\tilde{\delta} = 0,1$ và con số này tăng lên khi $\tilde{\delta}$ giảm.
Nhìn chung, tôi cảm thấy bố cục nâng cao thực sự vô dụng khi $k$ là không lớn. Điều này có đúng không?
