论文标题
通过私人梯度下降逃避无约束私人GLM的维度诅咒
Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
论文作者
论文摘要
我们重新审视了差异性私人经验风险最小化（ERM）的充分研究的问题。我们表明，对于不受限制的凸通通式线性模型（GLM），可以获得$ \ tilde o \ left的多余经验风险（\ sqrt {\ sqrt {\ texttt {strank}}}}/εn\ right）$，其中$ {\ texttt {rank pank}} $ is smak and smak and smard of smak and $ n是$ n $ n of sm $ $ε$是隐私参数。该结合是通过私人梯度下降（DP-GD）获得的。此外，通过第一个无限制的私人ERM的第一个下限，我们表明上限很紧。与受约束的ERM设置形成鲜明对比的是，不依赖环境模型空间的维度（$ p $）。 （请注意，$ {\ texttt {rank}} \ leq \ min \ {n，p \} $。）此外，我们还获得了一个类似的多余种群风险绑定，取决于$ {\ texttt {rank rank}}} $而不是$ p $。 For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of $\tilde O\left(\sqrt{\texttt{rank}}/εn\right)$ to a first-order-stationary-point of the underlying objective. 最后，我们表明，对于凸Glms，covex glms是在实践中通常使用的DP-GD的变体（涉及剪裁单个梯度）也表现出相同的尺寸独立收敛到定义明确的目标的最小值。为此，我们提供了一个结构引理，该引理表征了剪辑对DP-GD优化曲线的影响。
We revisit the well-studied problem of differentially private empirical risk minimization (ERM). We show that for unconstrained convex generalized linear models (GLMs), one can obtain an excess empirical risk of $\tilde O\left(\sqrt{\texttt{rank}}/εn\right)$, where ${\texttt{rank}}$ is the rank of the feature matrix in the GLM problem, $n$ is the number of data samples, and $ε$ is the privacy parameter. This bound is attained via differentially private gradient descent (DP-GD). Furthermore, via the first lower bound for unconstrained private ERM, we show that our upper bound is tight. In sharp contrast to the constrained ERM setting, there is no dependence on the dimensionality of the ambient model space ($p$). (Notice that ${\texttt{rank}}\leq \min\{n, p\}$.) Besides, we obtain an analogous excess population risk bound which depends on ${\texttt{rank}}$ instead of $p$. For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of $\tilde O\left(\sqrt{\texttt{rank}}/εn\right)$ to a first-order-stationary-point of the underlying objective. Finally, we show that for convex GLMs, a variant of DP-GD commonly used in practice (which involves clipping the individual gradients) also exhibits the same dimension-independent convergence to the minimum of a well-defined objective. To that end, we provide a structural lemma that characterizes the effect of clipping on the optimization profile of DP-GD.
