Non-Euclidean Differentially Private Stochastic Convex Optimization
Non-Euclidean Differentially Private Stochastic Convex Optimization
复制标题
DOI：
--
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Raef Bassily;Crist'obal Guzm'an;Anupama Nandi
中科院分区：
文献类型：
--
作者：
Raef Bassily;Crist'obal Guzm'an;Anupama Nandi
差分私有随机凸优化（Differentially private stochastic convex optimization，SCO）是一个基本问题，目标是在给定n个独立同分布的数据集上，使种群风险相对于凸损失函数近似最小化。来自分布的样本，同时满足相对于数据集的差异隐私。在私有凸优化的文献中的大多数现有工作集中在欧几里德（即，$\ell_2$）设置，其中假设损失是Lipschitz（并且可能是平滑的）w.r.t.有界直径约束集上的范数。基于噪声随机梯度下降（SGD）的算法是已知的，以达到最佳的超额风险在这种情况下。在这项工作中，我们进行了系统的研究DP-SCO的$\ell_p$-设置下的损失的标准平滑假设。对于$1<p\leq 2$，在一个标准的平滑假设下，我们给出了一个新的，线性时间DP-SCO算法与最优超额风险。以前已知的最优超额风险为1 <p<2$的结构在超线性时间内运行。对于p=1，我们给出了一个具有近似最优超额风险的算法.我们的结果为$\ell_1$-设置也扩展到一般的多面体规范和可行集。此外，我们表明，从我们的算法$1\leq p \leq 2$的超额风险界限达到高概率。对于$2<p \leq \infty$，我们表明，现有的线性时间结构的欧几里德设置在低维制度达到了接近最优的超额风险。因此，我们表明，这样的结构达到一个接近最优的超额风险为$p=\infty$。我们的工作借鉴了赋范空间的几何概念，如正则性，一致凸性和一致光滑性的概念。
Differentially private (DP) stochastic convex optimization (SCO) is a fundamental problem, where the goal is to approximately minimize the population risk with respect to a convex loss function, given a dataset of $n$ i.i.d. samples from a distribution, while satisfying differential privacy with respect to the dataset. Most of the existing works in the literature of private convex optimization focus on the Euclidean (i.e., $\ell_2$) setting, where the loss is assumed to be Lipschitz (and possibly smooth) w.r.t. the $\ell_2$ norm over a constraint set with bounded $\ell_2$ diameter. Algorithms based on noisy stochastic gradient descent (SGD) are known to attain the optimal excess risk in this setting. In this work, we conduct a systematic study of DP-SCO for $\ell_p$-setups under a standard smoothness assumption on the loss. For $1<p\leq 2$, under a standard smoothness assumption, we give a new, linear-time DP-SCO algorithm with optimal excess risk. Previously known constructions with optimal excess risk for $1<p<2$ run in super-linear time in $n$. For $p=1$, we give an algorithm with nearly optimal excess risk. Our result for the $\ell_1$-setup also extends to general polyhedral norms and feasible sets. Moreover, we show that the excess risk bounds resulting from our algorithms for $1\leq p \leq 2$ are attained with high probability. For $2<p \leq \infty$, we show that existing linear-time constructions for the Euclidean setup attain a nearly optimal excess risk in the low-dimensional regime. As a consequence, we show that such constructions attain a nearly optimal excess risk for $p=\infty$. Our work draws upon concepts from the geometry of normed spaces, such as the notions of regularity, uniform convexity, and uniform smoothness.