Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited
This work addresses privacy-preserving optimization in machine learning, offering improved bounds and new algorithms for non-Euclidean spaces, though it appears incremental in building on existing DP-SCO frameworks.
The paper tackles differentially private stochastic convex optimization in Euclidean and ℓ_p^d spaces, achieving excess population risks dependent on Gaussian width rather than dimension for constrained cases and providing first theoretical results for unconstrained and heavy-tailed data settings.
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$.