我们介绍了一种新的零阶算法，用于非凸和非光滑目标的私有随机优化。给定一个大小为 M 的数据集，我们的算法确保（α，αρ²/2）-Rényi 差分隐私，并找到一个（δ，ε）- 稳定点，只要 M=Ω^(~)[(d/(δε³)) + (d^(3/2)/(ρδε²)) ]。这与其非私有的零阶模拟的最优复杂度相匹配。值得注意的是，尽管目标不是光滑的，只要 ρ ≥ √(d)ε，我们就有了 “免费” 的隐私。

Jun, 2024

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

Jun, 2024

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

Dec, 2019

非凸优化中寻找近似驻点的计算和查询复杂性是本文的关键研究内容，其中包括在无约束域中寻找近似驻点的问题的 PLS 完备性、二维情况下的零阶算法以及近似驻点的查询复杂性的特征化，同时还研究了约束优化问题中寻找近似 KKT 点的查询复杂性，并指出约束优化中近似 KKT 点与无约束优化中近似驻点的对应关系。

Oct, 2023

本文介绍了一种针对非光滑、非凸函数的最新方法，通过概率论的方法实现了解决 ReLU 神经网络参数调整中的复杂问题的方法，其中提出的梯度算法能够使结果的准确度近似于一阶算法，并在距离解决方案的距离 delta 的范围内，得出广义梯度与解决方案的凸组合。

Feb, 2020

非凸优化中采用维度无关的随机一阶方法 (DISFOM) 来解决样本复杂度问题，使用小批量估计梯度以达到 ε- 稳定点的样本复杂度为 O ((log d) / ε^4)，进一步利用方差缩减可将该界限提高至 O ((log d)^(2/3) / ε^(10/3))，并提供了两种非平滑距离函数的选择，数值实验验证了所提框架的维度无关性。

Jun, 2024

本文介绍了一些带有或没有耦合的非凸优化模型，使用了相关的优化算法，如条件梯度和 ADMM， 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验，证明了这些算法的高效性，特别是在张量鲁棒 PCA 的场景下。

May, 2016

该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界，并探讨了基于 Oracle 算法的复杂度测量方法，显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。

Oct, 2017

本文提出了一种快速的随机拟牛顿方法，针对平滑性不均匀的情况，通过梯度剪切和方差减小，实现了最优的 O (ε^(-3)) 样本复杂度，并通过简单的超参数调节实现了收敛加速，数值实验证明了该算法优于现有方法。

Mar, 2024

本文研究了非凸优化中的无导数算法，利用有限差分器进行梯度逼近，最终提出了一种使用嘈杂的零阶方法来避免鞍点的算法，并在收敛速度上达到了与精确梯度接近的性能。

Oct, 2019