本文提出了一种适应目标函数难度的私有随机凸优化算法,对于具有 ' 增长 ' 趋势的函数,可以实现更快的隐私速率,而不需要知道增长常数 κ,算法基于反敏感机制和隐私优化中的本地化技术,并具有匹配的下界。
Aug, 2021
本文提出两种新的不同 ially private 的方法,实现了凸优化的最优解,使用较少的梯度计算,同时需要对数据有轻度平滑性的假设。
May, 2020
本文介绍了一个基于指数机制和加正则化项的方法,用于解决凸函数私人优化问题,并证明了其满足 Differential Privacy 和 Gaussian Differential Privacy,同时提出了实现这种机制的方法及其采样器
Mar, 2022
本文研究隐私保护随机优化问题在凸性和非凸性情况下的解决方案,并给出了针对不同损失函数的最优算法,其中包括 non-smooth generalized linear losses(GLLs)和多种约束条件以及多种平滑系数的情况。
Jul, 2021
我们介绍了一种新的零阶算法,用于非凸和非光滑目标的私有随机优化。给定一个大小为 M 的数据集,我们的算法确保(α,αρ²/2)-Rényi 差分隐私,并找到一个(δ,ε)- 稳定点,只要 M=Ω^(~)[(d/(δε³)) + (d^(3/2)/(ρδε²)) ]。这与其非私有的零阶模拟的最优复杂度相匹配。值得注意的是,尽管目标不是光滑的,只要 ρ ≥ √(d)ε,我们就有了 “免费” 的隐私。
Jun, 2024
我们在插值条件下证明了随机 Nesterov 加速的新的收敛速度。不同于以往的分析,我们的方法可以加速任何在期望中取得足够进展的随机梯度方法。证明使用估计序列框架进行,适用于凸函数和强凸函数,并且可以轻松推广到满足强生长条件的加速 SGD。在这种特殊情况下,我们的分析将强生长常数的依赖性从 ρ 减小到√ρ,相对于以前的工作来说,这一改进相当于最坏情况下条件数的平方根,并解决了对于随机加速的保证可能不如 SGD 的批评。
Apr, 2024
通过解决凸性问题,可以得到针对光滑(可能强烈凸)函数的固定步长的一阶方法的最坏情况下的性能。将一种黑盒一阶方法的最坏情况性能的确定视为在一组光滑(强)凸函数和初始条件上的优化问题。此工作证明了性能的最坏情况估计问题可以看作是一个相当的有限维度独立半定优化问题,其精确解可以恢复到数值精度。
Feb, 2015
使用随机梯度下降来最小化 Lipschitz 函数和强凸函数但不一定可微的问题,证明了在 T 步随机梯度下降后,最终迭代的误差高概率为 O (log (T)/T);同时构造了一个函数,证明了在确定性梯度下降中,最终迭代的误差为 Ω(log (T)/T);然后证明了在采用后缀平均法的情形下,它的高概率误差界是优化函数相关类别中的最优界(O (1/T));最后证明了对于 Lipschitz 和凸函数 class,使用随机梯度下降解决此问题后,最终迭代的误差高概率为 O (log (T)/sqrt (T))
Dec, 2018
本篇论文研究了关于随机逼近问题的现有算法,提出了两种新型随机梯度算法,并在回归和逻辑分类两种经典的监督学习问题上进行了测试,得到了较好的优化效果。
Jun, 2013
非凸函数的最小化,利用近似正负曲率方向步长,相对不精确度度量梯度和 Hessian 矩阵,松弛一阶和二阶精度的耦合,通过马丁格尔分析和浓度不等式得到收敛性分析,并将算法应用于经验风险最小化问题。
Oct, 2023