Jun, 2024
简化的简单降维的大尾部私密随机凸优化近乎最优解
Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality
from Simple Reductions
TL;DR我们研究了具有重尾梯度的差分隐私随机凸优化（DP-SCO）问题，在这里我们假设样本函数的Lipschitz常数具有k次矩界而不是统一界。我们提出了一种新的基于约束的方法，使我们能够在重尾设置中获得首个最优速率（达到对数因子），在（ε，δ）-近似差分隐私下，实现误差G2⋅1/√n+Gk⋅(√d/nε)^(1-1/k)，几乎匹配于[Lowy and Razaviyayn 2023]的下界。在额外假设下，我们进一步给出了一套重尾设置的私有算法，包括在已知Lipschitz常数假设下的最优算法，平滑函数的近线性时间算法以及平滑广义线性模型的最优线性时间算法。