Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion
复制标题
DOI：
10.48550/arxiv.2302.03775
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Ashok Cutkosky;Harsh Mehta;Francesco Orabona
中科院分区：
文献类型：
--
作者：
Ashok Cutkosky;Harsh Mehta;Francesco Orabona
我们提出了一种新的分析技术的基础上优化非光滑，非凸随机目标的新算法。这将当前最著名的寻找$（\delta，\delta）$-平稳点的复杂度从$O（\delta ^{-4}\delta^{-1}）$随机梯度查询提高到$O（\delta ^{-3}\delta^{-1}）$，我们也证明了这是最优的。我们的主要技术是减少从非光滑非凸优化在线学习，之后，我们的结果遵循标准的遗憾界在线学习。对于确定性和二阶平滑目标，应用更先进的乐观在线学习技术可以实现新的复杂度O（\Delta ^{-0.5}）$。我们的技术也恢复所有的最佳或最知名的结果找到平稳或二阶光滑的目标在随机和确定性设置的平稳点。
We present new algorithms for optimizing non-smooth, non-convex stochastic objectives based on a novel analysis technique. This improves the current best-known complexity for finding a $(\delta,\epsilon)$-stationary point from $O(\epsilon^{-4}\delta^{-1})$ stochastic gradient queries to $O(\epsilon^{-3}\delta^{-1})$, which we also show to be optimal. Our primary technique is a reduction from non-smooth non-convex optimization to online learning, after which our results follow from standard regret bounds in online learning. For deterministic and second-order smooth objectives, applying more advanced optimistic online learning techniques enables a new complexity of $O(\epsilon^{-1.5}\delta^{-0.5})$. Our techniques also recover all optimal or best-known results for finding $\epsilon$ stationary points of smooth or second-order smooth objectives in both stochastic and deterministic settings.