I have problems with understanding the advanced composition theorem in DP.
Let I have two approximate-DP mechanisms ($k = 2)$ where each satisfies $(\epsilon = 0.5, \delta = 0.1)$-DP. By basic composition, I know that using two queries sequentially will guarantee $(2 \cdot 0.5, 2 \cdot 0.1) = (1, 0.2)$-DP.
Advanced composition, however, says that, instead of the composition having $\delta' = k\cdot \delta$, if we are willing to take $\delta ' = k\cdot \delta + \tilde{\delta}$ for some $\tilde{\delta}>0$, then our $\epsilon'$ improves from $2\epsilon$ to $\epsilon' = k\cdot \epsilon(\exp(\epsilon) - 1) + \epsilon\sqrt{2 \cdot k \cdot \log (1/\tilde{\delta})}$.
Now, assume I am happy with $\delta' = 0.3$ instead of $\delta' = 0.2$. This means $\tilde{\delta}= 0.1$. So,
$$\epsilon' = 2\cdot 0.5(\exp(0.5) - 1) + 0.5\sqrt{2 \cdot 2 \cdot \log (1/0.1)} = 2.16 \gg 1.$$
I don't understand how this is improving upon the basic composition, as obviously here this is not the case! Am I doing something wrongly?
Edit:
The numbers I have fixed play no role. In general, we know that we can compose $k$ mechanisms (assume each is $(\epsilon, \delta)$-DP) and get $(k\epsilon, k\delta)$-DP just by basic composition. But, by increasing $k\delta$ a bit, we get an $\epsilon'$ which is equal to:
$$k \epsilon \underbrace{(e^\epsilon - 1)}_{\geq 0} + \underbrace{\epsilon \sqrt{2 k \log(1 / \tilde{\delta})}}_{\geq 0} $$
which is not always less than $k\epsilon$.
Specifically, let my extra allowance be $\tilde{\delta} = 0.1$. I want to see when the advanced composition improves upon the basic composition. So, in summary I want to see when the following holds:
\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}
Now assume I want to use $2$ mechanisms. Then, I need to have:
\begin{align}
& \log(10) <(2 - e^\epsilon)^2 \\
\iff & \epsilon < \log(2 - \sqrt{\log(10)}) = -0.7286
\end{align}
which is never possible. So, when $k = 2$, and if I am willing to only add $0.1$ to $\delta'$, then I can never improve basic composition with advanced composition?
Edit 2:
We can, in general, say that advanced composition only improves upon the basic composition if the following is satisfied:
$$ \epsilon < \log\left[2 - \sqrt{\frac{2 \log ( 1/\tilde{\delta})}{k}} \right] $$
which requires $k > 4$ when, e.g., $\tilde{\delta} = 0.1$ and this number increases when $\tilde{\delta}$ decreases.
Overall, I feel like advanced composition is really useless when $k$ is not large. Is this true?