TY - JOUR
AU - Gopi, Sivakanth
AU - Lee, Yin Tat
AU - Liu, Daogao
PY - 2024/02/11
Y2 - 2024/03/05
TI - Private Convex Optimization via Exponential Mechanism
JF - Journal of Privacy and Confidentiality
JA - JPC
VL - 14
IS - 1
SE - TPDP 2022
DO - 10.29012/jpc.869
UR - https://journalprivacyconfidentiality.org/index.php/jpc/article/view/869
SP -
AB - <p>In this paper, we study private optimization problems for non-smooth convex functions $F(x)=\mathbb{E}_i f_i(x)$ on $\mathbb{R}^d$.<br>We show that modifying the exponential mechanism by adding an $\ell_2^2$ regularizer to $F(x)$ and sampling from $\pi(x)\propto \exp(-k(F(x)+\mu\|x\|_2^2/2))$ recovers both the known optimal empirical risk and population loss under $(\eps,\delta)$-DP. Furthermore, we show how to implement this mechanism using $\widetilde{O}(n \min(d, n))$ queries to $f_i(x)$ for the DP-SCO where $n$ is the number of samples/users and $d$ is the ambient dimension.<br>We also give a (nearly) matching lower bound $\widetilde{\Omega}(n \min(d, n))$ on the number of evaluation queries.</p><p>Our results utilize the following tools that are of independent interest:<br>\begin{itemize}<br>\item We prove Gaussian Differential Privacy (GDP) of the exponential mechanism if the loss function is strongly convex and the perturbation is Lipschitz. Our privacy bound is \emph{optimal} as it includes the privacy of Gaussian mechanism as a special case and is proved using the isoperimetric inequality for strongly log-concave measures.<br>\item We show how to sample from $\exp(-F(x)-\mu \|x\|^2_2/2)$ for $G$-Lipschitz $F$ with $\eta$ error in total variation (TV) distance using $\widetilde{O}((G^2/\mu) \log^2(d/\eta))$ unbiased queries to $F(x)$. This is the first sampler whose query complexity has \emph{polylogarithmic dependence} on both dimension $d$ and accuracy $\eta$.<br>\end{itemize}</p>
ER -