Расширенная композиция в DP хуже, чем базовая композиция

У меня проблемы с пониманием расширенной теоремы композиции в DP.

Пусть у меня есть два приближенно-DP-механизма ($к = 2)$ где каждый удовлетворяет $(\эпсилон = 0,5, \дельта = 0,1)$-ДП. По базовой композиции я знаю, что последовательное использование двух запросов гарантирует $(2 \cdot 0,5, 2 \cdot 0,1) = (1, 0,2)$-ДП.

Усовершенствованная композиция, однако, говорит о том, что вместо композиции, имеющей $\дельта' = k\cdot \дельта$, если мы готовы принять $\delta ' = k\cdot \delta + \tilde{\delta}$ для некоторых $\тильда{\дельта}>0$, то наш $\эпсилон'$ улучшается от $2\эпсилон$ к $\epsilon' = k\cdot \epsilon(\exp(\epsilon) - 1) + \epsilon\sqrt{2 \cdot k \cdot \log (1/\tilde{\delta})}$.

Теперь предположим, что я доволен $\дельта' = 0,3$ вместо $\дельта' = 0,2$. Это означает $\тильда{\дельта}= 0,1$. Так, $$\epsilon' = 2\cdot 0,5(\exp(0,5) - 1) + 0,5\sqrt{2 \cdot 2 \cdot \log (1/0,1)} = 2,16 \gg 1.$$

Я не понимаю, как это улучшает базовую композицию, поскольку здесь это явно не так! Я делаю что-то неправильно?

Редактировать:

Числа, которые я зафиксировал, не играют никакой роли. В общем, мы знаем, что можем сочинять $к$ механизмы (предположим, что каждый $(\эпсилон,\дельта)$-ДП) и получить $(к\эпсилон, к\дельта)$-ДП как раз по основному составу. Но, увеличивая $к\дельта$ немного, мы получаем $\эпсилон'$ что равно:

$$k \epsilon \underbrace{(e^\epsilon - 1)}_{\geq 0} + \underbrace{\epsilon \sqrt{2 k \log(1 / \tilde{\delta})}}_{ \geq 0} $$ что не всегда меньше $к\эпсилон$.

В частности, пусть моя надбавка будет $\тильда{\дельта} = 0,1$. Я хочу увидеть, когда продвинутая композиция улучшит базовую композицию. Итак, в заключение я хочу увидеть, когда выполняется следующее:

\начать{выравнивать} & 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{выравнивание} Теперь предположим, что я хочу использовать $2$ механизмы. Тогда мне нужно иметь:

\начать{выравнивать} & \log(10) <(2 - e^\epsilon)^2 \ \iff & \epsilon < \log(2 - \sqrt{\log(10)}) = -0,7286 \end{выравнивание} что никогда не возможно. Так когда $к = 2$, и если я хочу только добавить $0.1$ к $\дельта'$, то я никогда не смогу улучшить базовую композицию с помощью расширенной композиции?

Редактировать 2: В целом мы можем сказать, что расширенная композиция улучшает базовую композицию только в том случае, если выполняется следующее:

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

что требует $к > 4$ когда, например, $\тильда{\дельта} = 0,1$ и это число увеличивается, когда $\тильда{\дельта}$ уменьшается.

В целом, я чувствую, что расширенная композиция действительно бесполезна, когда $к$ не большой. Это правда?

Во-первых, есть другие результаты состава, например, я считаю Вот этот улучшает продвинутую композицию. Я отвечу на более общий вопрос (который, я думаю, вы получаете).

Данные механизмы $M_1,\точки, M_n$, как получить наилучшие параметры для их композиции?

В идеале мы могли бы сказать: «используйте базовую композицию для небольших $к$", и "использовать расширенную композицию для больших $к$". К сожалению, можно формально показать, что это не так просто. Сложность вычисления оптимальной композиции дифференциальной конфиденциальности исследования, для «входных» механизмов $M_1,\точки, M_n$ параметров $(\epsilon_1,\delta_1),\dots, (\epsilon_n, \delta_n)$, задача нахождения «минимальных» параметров $(\эпсилон^*, \дельта^*)$ механизма композиции.

Предыдущие результаты были известны, например

Если $M_1,\точки, M_n$ все $(\эпсилон,\дельта)$-частный для фиксированной пары $(\эпсилон,\дельта)$, и цель $\дельта^*$ задано, то оптимальное значение $\эпсилон^*$ минимальный $\эпсилон^*\geq 0$ такой, что $$\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-\дельта)^n}.$$

Документ, на который я ссылаюсь, распространяет этот результат на случай $M_1,\точки, M_n$ приватность параметров $(\epsilon_1,\delta_1),\dots,(\epsilon_n,\delta_n)$ не все так. Находят аналогичное (но более сложное) выражение, характеризующее оптимальное значение $\эпсилон^*$ (при задании "цели" $\дельта^*$), и найти, что вычисление этого оптимального решения является $\#П$-полный, напр. вряд ли удастся сделать это эффективно. Это верно даже в случае композиции для чистых механизмов, т.е. $\дельта_i = 0$ для всех $я$.

Возможно, наиболее интересным для вас является то, что для этой задачи существуют приближенные алгоритмы (также в этой статье). Не знаю, реализовал ли их кто-нибудь, но если да, то вроде неплохой вариант для конкретного подбора параметров.

Стоит также упомянуть, что существуют тесно связанные понятия конфиденциальности (а именно концентрированная дифференциальная конфиденциальность), где история композиции более прямолинейна, но все же (в определенном смысле) достигается $ О (\ sqrt {к}) $ масштабирование с $к$-кратная композиция, а не $ О (к) $ масштабирование «базовая композиция» дает вам.