研究非光滑、非凸的 Lipschitz 目标函数在具有噪声函数评估的条件下生成 $(\delta,\epsilon)$- 稳定点的复杂性，提出的算法具有 $O (d\delta^{-1}\epsilon^{-3})$ 的复杂度和最优收敛速率。

Jul, 2023

我们研究了非光滑非凸目标在分散随机优化中找到 ($\delta,\epsilon$)- 稳定点的有限时间分析。我们提出了一种称为 ME-DOL 的新算法，并在不同环境中建立了样本复杂性。我们证明了该算法在光滑非凸目标中恢复了最优收敛速度的在线至非凸技术，并扩展了分析到非光滑设置，建立在随机平滑和 Goldstein - 次微分集的属性上。我们在一阶设置中建立了 $O (\delta^{-1}\epsilon^{-3})$ 的样本复杂度，这是我们所知道的第一次对于分散非光滑非凸随机优化的有限时间保证（无弱凸性），与其最优集中对应。我们进一步证明了在不使用方差减少的零阶预言机设置时相同的速率。

Jun, 2024

本文综述了不同凸且光滑目标函数的梯度下降算法与输出扰动方法，不仅能达到近乎最优的效用，而且也提高了以前的隐私优化算法的运行时间。同时，对于非凸光滑目标函数，还提出了 RRPSGD 算法，并附上了隐私保障的收敛性证明。实验表明，我们的算法在效益和运行时间方面始终优于现有方法。

Mar, 2017

本文研究隐私保护随机优化问题在凸性和非凸性情况下的解决方案，并给出了针对不同损失函数的最优算法，其中包括 non-smooth generalized linear losses（GLLs）和多种约束条件以及多种平滑系数的情况。

Jul, 2021

非凸函数的最小化，利用近似正负曲率方向步长，相对不精确度度量梯度和 Hessian 矩阵，松弛一阶和二阶精度的耦合，通过马丁格尔分析和浓度不等式得到收敛性分析，并将算法应用于经验风险最小化问题。

Oct, 2023

本文提出两种新的不同 ially private 的方法，实现了凸优化的最优解，使用较少的梯度计算，同时需要对数据有轻度平滑性的假设。

May, 2020

我们研究基于差分隐私的私有经验风险最小化问题，其中损失函数满足（γ，κ）-Kurdyka-Lojasiewicz 条件。当损失函数是利普希茨且光滑的时候，我们提出了一种基于方差减少梯度下降的新算法，并在超过经验风险的速率达到了几乎最优。当 KL 参数未知时，我们对噪声梯度下降算法进行了修改和分析，并证明了该算法在适应性上的性能几乎最优。同时，我们还展示了在不假设 KL 条件的情况下，同样的梯度下降算法可以以快速的收敛速度逼近利普希茨、光滑（甚至非凸）目标的驻点。

Nov, 2023

本文提出了一种适应目标函数难度的私有随机凸优化算法，对于具有 ' 增长 ' 趋势的函数，可以实现更快的隐私速率，而不需要知道增长常数 κ，算法基于反敏感机制和隐私优化中的本地化技术，并具有匹配的下界。

Aug, 2021

采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

Dec, 2019

我们提供了一个简单灵活的框架，用于设计差分隐私算法以找到非凸损失函数的近似稳定点。我们的框架基于使用私有近似风险最小化器来 “预热” 另一个用于寻找稳定点的私有算法。我们将这一框架应用于多个类别的非凸损失函数中，获得了改进的且有时是最优的速率。

Feb, 2024