Dec, 2019

非凸随机优化下的下限界

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

    研究了随机梯度下降（SGD）算法在最小化光滑、可能非凸函数梯度范数方面的迭代复杂度，结果表明，Ghadimi 和 Lan 的上限不能得到改进，除非做出额外的假设，即使对于凸二次函数，也是如此；此外还表明，对于非凸函数，SGD 最小化梯度的可行性需要根据所选择的最优性标准而定。

    Oct, 2019

  • 寻找静态点的下界 I

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

    Oct, 2017

  • 随机凸优化中梯度变小的复杂性

    本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

    Feb, 2019

  • 非凸强凹 Min-Max 优化的复杂度下界

    我们通过使用第一阶 oracle 及条件数，提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性 oracle 也适用于随机 oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

    Apr, 2021

  • 减小方差以实现更快的非凸优化

    本篇论文研究了非凸优化中高效到达稳定点的基本问题，并利用方差缩减技巧和适用于非凸优化的全新方差缩减分析提出一种首个非凸优化的一阶小批量随机算法，并在非凸损失函数和神经网络训练中表现出了有效性。

    Mar, 2016

  • 基于修正偏置动量的加速随机极小 - 极大优化

    针对非凸优化中最小最大优化问题，本研究提出了利用高效的 Hessian - 向量乘积的新型修正动量算法，建立了收敛条件并证明了所提算法的迭代复杂度为 O (ε^{-3})。通过在实际数据集上进行鲁棒的逻辑回归的应用验证了该方法的有效性。

    Jun, 2024

  • 非凸优化中找到稳定点的计算复杂度

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

    Oct, 2023

  • 非凸随机梯度下降逃离鞍点的尖锐分析

    本文将通过对随机梯度下降进行深入分析，证明当目标函数满足梯度 Lipschitz、Hessian-Lipschitz 和发散噪声假设时，SGD 能够在 O（ε^ -3.5）次随机梯度计算中逃离鞍点并找到（ε，O（ε^ 0.5））- 近似二阶稳定点，从而推翻了 SGD 至少需要 O（ε^ - 4）的经典信念。此类 SGD 速率与大多数采用其他技术的加速非凸随机优化算法的速率相匹配，如 Nesterov 的动量加速，负曲率搜索，以及二次和三次正则化技巧。本文的新型分析为非凸 SGD 提供了新的见解，并可潜在地推广到广泛的随机优化算法类。

    Feb, 2019

  • 非凸优化的加速方法

    通过使用只需要计算梯度的加速梯度方法，该论文提出了一种快速求解具有 Lipschitz 连续的一阶和二阶导数的非凸优化问题的算法，该方法相较于梯度下降算法在复杂度和精度上都表现更优。

    Nov, 2016

  • 基于随机模型的弱凸函数最小化

    本文提出一族算法通过简单的随机模型样本和优化方法，成功的减少了目标函数。我们展示出，合理的近似质量和模型的正则性下，此类算法将自然的稳定度衡量推向 0，该衰减速度为 O (k^(-1/4))，基于此原理，我们为随机的近端子梯度法，近端次梯度法以及规则化的高斯牛顿法等提供了第一个复杂性保证。

    Mar, 2018