Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions

本文研究了带有重尾梯度的差分隐私随机凸优化（DP-SCO）问题，其中假设样本函数的Lipschitz常数具有$k$阶矩限制而不是统一限制。我们提出了一种新的基于约化的方法，使我们能够在重尾设置中获得第一个最优率（最多对数因子），在$(\epsilon，\delta)$-近似差分隐私下实现误差$G_2 \cdot \frac 1 {\sqrt n} + G_k \cdot (\frac{\sqrt d}{n\epsilon})^{1 - \frac 1 k}$，最多有一个温和的$\textup{polylog}(\frac{1}{\delta})$因子，其中$G_2^2$和$G_k^k$是样本Lipschitz常数的$2^{\text{nd}}$和$k^{\text{th}}$矩限制，几乎匹配了[Lowy和Razaviyayn 2023]的下限。此外，我们在重尾设置中提供了一组私有算法，这些算法在附加假设下改进了我们的基本结果，包括在已知Lipschitz常数假设下的最优算法，针对平滑函数的近线性时间算法，以及针对平滑广义线性模型的最优线性时间算法。

论文研究的问题是在具有重尾梯度的差分隐私随机凸优化中，如何获得最优速率。

论文提出了一种新的基于约化的方法，通过对样本Lipschitz常数的k阶矩限制来获得最优速率。

论文给出了一系列在重尾设置下的私有算法，在一些额外假设下，这些算法比基本结果更优。实验结果表明，这些算法在一些数据集上表现良好。

最近的相关研究包括Lowy和Razaviyayn（2023年）的下限和其他一些私有随机凸优化算法的研究。