In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) in Euclidean and general $\ell_p^d$ spaces. Specifically, we focus on three settings that are still far from well understood: (1) DP-SCO over a constrained and bounded (convex) set in Euclidean space; (2) unconstrained DP-SCO in $\ell_p^d$ space; (3) DP-SCO with heavy-tailed data over a constrained and bounded set in $\ell_p^d$ space. For problem (1), for both convex and strongly convex loss functions, we propose methods whose outputs could achieve (expected) excess population risks that are only dependent on the Gaussian width of the constraint set rather than the dimension of the space. Moreover, we also show the bound for strongly convex functions is optimal up to a logarithmic factor. For problems (2) and (3), we propose several novel algorithms and provide the first theoretical results for both cases when $1<p<2$ and $2\leq p\leq \infty$.
翻译:在本文中,我们重新思考了欧几里得空间和$\ell_p^d$空间中的差分隐私随机凸优化(DP-SCO)问题。具体而言,我们专注于三种仍未被很好理解的情况:(1)在欧几里得空间的约束和有界(凸)集上的DP-SCO;(2)$\ell_p^d$空间中的无约束DP-SCO;(3)$\ell_p^d$空间中带有重尾数据的DP-SCO,在有约束和有界$\ell_p^d$空间中的应用。对于问题(1),针对凸和强凸损失函数,我们提出了一种方法来实现期望人口风险过量的结果,该结果仅取决于约束集的高斯宽度而不是空间维数。此外,我们还表明对于强凸函数,该界限是最优的,除了对数因子。对于问题(2)和(3),我们提出了几种新算法,并针对$1<p<2$和$2 \leq p \leq \infty$的两种情况首次给出了理论结果。