Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings-猫眼课题宝

DOI：

发表时间：

2021-07

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Raef Bassily;Crist'obal Guzm'an;Michael Menart

研究了凸和非凸环境下的微分私有随机优化问题。对于凸情况，我们关注非光滑广义线性损失族（gll）。对于$\ell_2$设置，我们的算法在近线性时间内实现了最优超额种群风险，而对于一般凸损失，最著名的差分私有算法在超线性时间内运行。我们的算法对于$\ell_1$设置具有几乎最优的过剩人口风险$\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$，并且绕过了\cite{Asi:2021}的维相关下界，用于一般非光滑凸损失。在差分私有非凸环境下，我们提出了几种新的逼近总体风险平稳点的算法。对于具有光滑损失和多面体约束的$\ell_1$-情况，我们给出了线性时间下的第一个近维无关率$\tilde O\big(\frac{\log^{2/3}{d}}{(n\varepsilon)^{1/3}}}\big)$。对于具有平滑损失的受限$\ell_2$-情况，我们得到了速率$\tilde O\big(\frac{1}{n^{1/3}}+\frac{d^{1/5}}{(n\varepsilon)^{2/5}}\big)$的线性时间算法。最后，对于$\ell_2$-情况，我们给出了率$\tilde O\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$的第一个{\em非光滑弱凸}随机优化方法，该方法匹配了$d= O(\sqrt{n})$时的最佳非私有算法。我们还将上面所有关于非凸$\ell_2$设置的结果扩展到$\ell_p$设置，其中$1

We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal excess population risk $\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$, and circumvents the dimension dependent lower bound of \cite{Asi:2021} for general non-smooth convex losses. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the $\ell_1$-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, $\tilde O\big(\frac{\log^{2/3}{d}}{{(n\varepsilon)^{1/3}}}\big)$ in linear time. For the constrained $\ell_2$-case with smooth losses, we obtain a linear-time algorithm with rate $\tilde O\big(\frac{1}{n^{1/3}}+\frac{d^{1/5}}{(n\varepsilon)^{2/5}}\big)$. Finally, for the $\ell_2$-case we provide the first method for {\em non-smooth weakly convex} stochastic optimization with rate $\tilde O\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$ which matches the best existing non-private algorithm when $d= O(\sqrt{n})$. We also extend all our results above for the non-convex $\ell_2$ setting to the $\ell_p$ setting, where $1

Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings

文献摘要

相似文献