Private Convex Optimization in General Norms
Private Convex Optimization in General Norms
复制标题
DOI：
10.48550/arxiv.2207.08347
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Sivakanth Gopi;Y. Lee;Daogao Liu;Ruoqi Shen;Kevin Tian
中科院分区：
文献类型：
--
作者：
Sivakanth Gopi;Y. Lee;Daogao Liu;Ruoqi Shen;Kevin Tian
我们提出了一个新的框架，差分私人优化的凸函数是Lipschitz在一个任意的范数$\cdot\|$。我们的算法是基于一个正则化的指数机制，从密度$\propto \exp（-k（F+\mu r））$采样，其中$F$是经验损失和$r$是一个正则化的强凸相对于$\cdot\|$，推广最近的工作[Gopi，李，刘'22]非欧几里德设置。我们表明，该机制满足高斯差分隐私，并解决了DP-ERM（经验风险最小化）和DP-SCO（随机凸优化）通过使用凸几何的本地化工具。我们的框架是第一个适用于一般赋范空间中的私有凸优化，并直接恢复通过镜像下降实现的非私有SCO率作为隐私参数$\bad\to \infty$。作为应用，对于所有$p \in（1，2）$的$\ell_p$范数的Lipschitz优化，我们获得了第一个最优的隐私-效用权衡;对于$p = 1$，我们将最近的作品[Asi，Feldman，Koren，Talwar '21，Basily，Guzman，南迪'21]获得的权衡改进了至少一个对数因子。我们的$\ell_p$ norm和Schatten-$p$ norm优化框架补充了多项式时间采样器，其查询复杂度我们明确绑定。
We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm $\|\cdot\|$. Our algorithms are based on a regularized exponential mechanism which samples from the density $\propto \exp(-k(F+\mu r))$ where $F$ is the empirical loss and $r$ is a regularizer which is strongly convex with respect to $\|\cdot\|$, generalizing a recent work of [Gopi, Lee, Liu '22] to non-Euclidean settings. We show that this mechanism satisfies Gaussian differential privacy and solves both DP-ERM (empirical risk minimization) and DP-SCO (stochastic convex optimization) by using localization tools from convex geometry. Our framework is the first to apply to private convex optimization in general normed spaces and directly recovers non-private SCO rates achieved by mirror descent as the privacy parameter $\epsilon \to \infty$. As applications, for Lipschitz optimization in $\ell_p$ norms for all $p \in (1, 2)$, we obtain the first optimal privacy-utility tradeoffs; for $p = 1$, we improve tradeoffs obtained by the recent works [Asi, Feldman, Koren, Talwar '21, Bassily, Guzman, Nandi '21] by at least a logarithmic factor. Our $\ell_p$ norm and Schatten-$p$ norm optimization frameworks are complemented with polynomial-time samplers whose query complexity we explicitly bound.