Dec, 2019

非凸随机优化下的下限界

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

    研究随机梯度下降法（SGD）在强凸目标函数上的收敛性，证明了ICML 2018和2019提出的降低步长的速率序列在每次迭代后的收敛速度与我们的下限相差不到32倍，为最优状态；该下限相较于现有工作大约高出了因子775×d，其中d是维度。

    Oct, 2018

  • 非光滑随机梯度下降的严格分析

    使用随机梯度下降来最小化Lipschitz函数和强凸函数但不一定可微的问题，证明了在T步随机梯度下降后，最终迭代的误差高概率为O(log(T)/T)；同时构造了一个函数，证明了在确定性梯度下降中，最终迭代的误差为Ω(log(T)/T)；然后证明了在采用后缀平均法的情形下，它的高概率误差界是优化函数相关类别中的最优界（O(1/T)）；最后证明了对于Lipschitz和凸函数 class，使用随机梯度下降解决此问题后，最终迭代的误差高概率为O(log(T)/sqrt(T))

    Dec, 2018

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

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

    Feb, 2019

  • 非凸优化中随机梯度下降的二阶保证

    本文研究了梯度下降算法在非凸优化问题中的性能保证，发现梯度噪声对逃脱鞍点和到达二阶稳定点的效率起到了关键作用，提出了一个基于均方方法的替代方案来保证梯度噪声的相对方差较小就足以确保逃脱鞍点，而不需要注入其他噪声或采用全局分散噪声假设。

    Aug, 2019

  • 使用随机梯度下降法找到稳定点的复杂度

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

    Oct, 2019

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

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

    Apr, 2021

  • 非凸随机优化中重尾的高概率界限

    本研究讨论了使用第一阶梯度算法进行的非凸随机优化问题，其中梯度估计可能具有重尾特征，结果表明梯度剪裁，动量和归一化梯度下降的组合可以在高概率下收敛于关键点，特别适用于光滑损失的已知最佳速率，适用于任意光滑度规范，并针对克服该领域二阶光滑损失引发的问题进行讨论。

    Jun, 2021

  • 自适应梯度方法在细化平滑度和噪声假设下的收敛分析

    分析了AdaGrad在随机非凸优化中收敛速率，证明了存在优于SGD的收敛速度，并给出了收敛速率的上界和下界。

    Jun, 2024

  • 具有强收敛保证的确定性约束随机非凸优化的方差减少的一阶方法

    本文解决了确定性约束随机优化问题中如何确保约束几乎被确定性满足的核心问题。我们提出了一种单循环方差减少的随机一阶方法，通过计算确定性部分的确切梯度，确保在复杂度保证下能找到近似的随机静态点。研究表明，该方法在样本复杂度和一阶操作复杂度上达到了显著提升，具有重要的实际应用潜力。

    Sep, 2024

  • 具有强收敛保证的确定性约束随机非凸优化的一阶方差减少方法

    本研究解决了确定性约束的随机优化问题，现有方法往往只寻求满足一定准确度的随机平衡点，但在实际应用中，确保约束的确定性满足更为重要。我们提出了一种单循环方差减少的随机一阶方法，实验证明，该方法在满足约束的可能性上具有显著改进，且实现了样本复杂度和操作复杂度的优化。

    Sep, 2024