Oct, 2023

凸优化中算法可重复性和梯度复杂性的最佳保证

PDF
TL;DR通过改变训练过程中的微小变化以度量算法的可重现性，我们挑战了之前的观点，并证明在各种有错误的预测设置下，对于平滑凸优化和平滑凸凹极小极大问题，可以实现最佳的可重现性和接近最优的收敛保证。
algorithmic reproducibilitymachine learning algorithmsconvergence ratesmooth convex minimizationgradient complexity
发现论文，激发创造
  • 优化中的可重复性：理论框架与限制

    本文研究了优化过程中的可重复性问题，定义了一个量化的可重复性度量方法并对于凸函数进行了分析，发现在计算和可重复性之间存在根本性的权衡关系。

    Feb, 2022

  • 随机凸优化的预言机复杂度信息论下界

    本文研究使用计算机预测的随机凸优化的复杂性，提出了改善已知结果的方法，并获得了各种函数类的紧致极小复杂度估计。

    Sep, 2010

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

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

    Feb, 2019

  • 一种具有近似评估和复杂度保证的非凸最小化随机算法

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

    Oct, 2023

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

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

    Mar, 2018

  • 极小极大优化的近似最优算法

    本文提出了一种基于加速的近端点方法和最小值近端步求解器的算法，其梯度复杂度为 O（kappa_x kappa_y^0.5），匹配了已有的最优下界，可用于解决强凸强凹、凸凹、非凸强凹和非凸凹函数的问题。

    Feb, 2020

  • 平滑与强凸强凹极小 - 极大优化的首个最优算法

    通过重新定义问题为最小化问题，应用特定变体的近端点算法和使用最佳算法计算不准确的近端算子，我们将最小极小化优化问题的梯度计算复杂度降至 O (sqrt (kappax*kappay)*log (1/epsilon))

    May, 2022

  • 通过函数增长条件度量，用一阶方法解决凸优化问题的新计算保证

    本文提出了新的计算方法和相关计算保证，利用一阶方法来解决凸优化问题，并且引入了增长常数 G 用作计算复杂度分析。特别地，当函数 f (・) 为非光滑函数时，提供了 Subgradient Descent Method 和平滑方法的新的计算保证。当 f (・) 是光滑函数时，对重新启动加速梯度方法的方案进行了阐述。

    Nov, 2015

  • 非强凸平稳随机逼近，收敛速率 O (1/n)

    本篇论文研究了关于随机逼近问题的现有算法，提出了两种新型随机梯度算法，并在回归和逻辑分类两种经典的监督学习问题上进行了测试，得到了较好的优化效果。

    Jun, 2013

  • 随机优化中的渐近最优性

    本文针对随机凸优化问题，提出了局部复杂度度量，并给出了与优化固有几何概念相对应的统计难度的收敛结果。基于 Nesterov 的对偶平均方法和 Riemannian 方法，开发出完全在线的适应性最优收敛算法，实现了函数特定的下界和收敛结果，并对约束鉴别和线性约束与非线性约束等方面做了探讨。

    Dec, 2016