基于二阶方法的更快差分隐私凸优化
本文研究带有重尾数据的随机凸优化问题,并在差分隐私(DP)约束条件下进行研究。该文提出了一种新的算法用于估计重尾数据的均值,并针对凸损失函数提供了改进的上界。同时,证明了私密随机凸优化的几乎匹配下界,这表明了纯 DP 和集中 DP 之间的新分离。
Jun, 2021
研究不同 ially private (DP) 算法在随机非凸优化中的应用,通过提供对私有梯度法的分析,提出了 DP RMSProp 和 DP Adam 等最佳算法来达成更快的收敛速度,在两个流行的深度学习任务中,证明了 DP 自适应梯度法比标准的 DP SGD 更具有优势。
Jun, 2020
我们研究了具有用户级隐私的差分隐私随机凸优化(DP-SCO),其中每个用户可能拥有多个数据项。我们开发了新算法用于用户级 DP-SCO,在多项式时间内获得凸和强凸函数的最优速率,并且在维度上只要求用户数量呈对数增长。此外,我们的算法是第一个在多项式时间内获得非平滑函数最优速率的算法。这些算法基于多遍 DP-SGD,结合了一种集中数据的新颖私有均值估计过程,在估计梯度的平均值之前应用了一个异常值移除步骤。
Nov, 2023
本文系统研究了在不同的 normed space 下,拥有标准平滑性假设的 Differentially private stochastic convex optimization 问题,提出了新的算法并证明了其优于之前已知的算法
Mar, 2021
本文尝试缩小理论优化与实际优化之间的差距,提出了一种可扩展的二阶预处理方法来优化深度模型,利用异构硬件架构进行训练,相比于常规一阶方法在机器翻译、语言建模、点击率预测和图像分类等任务中表现出优异的性能。
Feb, 2020
本文提出了一种基于采样和聚合框架的方法和基于梯度平滑和剪枝的方案,可有效应对重尾型数据下的不规则性挑战,实现了强凸和一般凸损失函数的差分隐私,且在高概率下应达到预期的超额群体风险水平。
Oct, 2020
本文研究隐私保护随机优化问题在凸性和非凸性情况下的解决方案,并给出了针对不同损失函数的最优算法,其中包括 non-smooth generalized linear losses(GLLs)和多种约束条件以及多种平滑系数的情况。
Jul, 2021
本文研究了一类基于牛顿方法的优化算法在非凸机器学习问题中的应用,展示了其可以更好地利用曲率信息来逃离平坦区域和鞍点,并在泛化性能方面表现相当于或优于手动调整学习率的随机梯度下降算法。
Aug, 2017
在多面体环境中,我们研究了差分隐私(DP)随机凸 - 凹鞍点问题。我们提出了基于随机镜像下降的(ε,δ)-DP 算法,实现了接近维度无关的收敛速率用于预期对偶间隙,这种保证类型以前仅适用于双线性目标。对于凸 - 凹和一阶平滑的随机目标,我们的算法取得了一个速率为√(log (d)/n) + (log (d)^(3/2)/[nε])^(1/3),其中 d 是问题的维度,n 是数据集大小。在额外的二阶平滑性假设下,我们将预期间隙的速率改进为√(log (d)/n) + (log (d)^(3/2)/[nε])^(2/5)。在此额外的假设下,我们还通过使用减少偏差的梯度估计器展示了对偶间隙受限于常数成功概率的边界为 log (d)/√n+log (d)/[nε]^(1/2)。这个结果证明了该方法的接近最优性。最后,我们展示了将我们的方法与在线学习的加速技术相结合,得到了第一个在多面体环境中不基于 Frank-Wolfe 方法的 DP 随机凸优化算法。对于凸和一阶平滑的随机目标,我们的算法获得了过量风险为√(log (d)/n) + log (d)^(7/10)/[nε]^(2/5),在另外假设二阶平滑性的情况下,我们将速率提高到√(log (d)/n) + log (d)/√nε。所有这些结果都依赖于经典 Maurey 稀疏化引理的各种推广,可能具有独立的兴趣。
Mar, 2024