Nov, 2019

光滑凸优化自适应催化剂

PDF
TL;DR本文提出了一个通用框架，允许加速几乎任意非加速确定性和随机算法用于光滑凸优化问题，其中通过使用加速的近端外梯度方法作为非加速内方法的包络来实现。该算法有两个关键不同之处：容易验证的内部算法停止标准和学习率的可调节性，使得此工作的主要贡献是适用于自适应内部算法 Steepset Descent、Adaptive Coordinate Descent 和 Alternating Minimization 的新框架。此外，在非自适应情况下，我们的方法允许获得没有对数因子的 Catalyst，这与标准 Catalyst 不同。
convex optimizationalgorithm accelerationregularizationinner algorithmadaptive optimization
发现论文，激发创造
  • 从理论到实践的一阶凸优化的催化剂加速

    介绍了一种名为 Catalyst 的通用方案，通过解决一系列适当选择的辅助问题来加速各种优化算法（包括梯度下降、块坐标下降和增量算法），从而加快收敛速度。

    Dec, 2017

  • 基于梯度的非凸优化的催化剂加速

    该论文介绍了一种通用的方案，使用最初设计用于最小化凸函数的梯度下降算法来解决非凸优化问题，该方案允许我们将这些方法用于弱凸性目标，这涵盖了机器学习和信号处理中通常出现的大类非凸函数。该方案无需假定目标函数具有凸性，而是通过自适应于未知的弱凸性常数来实现其保证。最后，本文还展示了将该方案应用于增量算法的几个实验结果。

    Mar, 2017

  • 随机组合优化的通用加速框架

    本文介绍了在目标函数为凸或强凸函数时获取加速一阶随机优化算法的各种机制，同时扩展了最初用于确定性目标的 Catalyst 方法到随机问题领域，并提供了一个新的关于处理不精确近端算子时的鲁棒性的泛化分析

    Jun, 2019

  • 一种用于一阶优化的通用催化剂

    本研究引入了一种通用方案，利用对加速邻域点算法的新分析，加快一阶优化方法。通过近似解决一系列精心选择的辅助问题来最小化凸目标，从而实现更快的收敛速度，为包括梯度下降、块坐标下降、SAG、SAGA、SDCA、SVRG、Finito/MISO 及其邻域点变体在内的大类算法提供加速和明确的非强凸目标支持，加速在实践中证明对病态问题尤其有用。

    Jun, 2015

  • 加速方法

    本文介绍了用于凸优化中的加速技术的两个关键方法族（动量和嵌套优化方案），动量方法结构收敛证明使用几个主模板（例如用于优化梯度方法的那个）和近端加速，探讨了重新启动方案和一些常见的加速的技术。

    Jan, 2021

  • 一种强凸函数的鲁棒加速优化算法

    本文提出了一种加速的一阶优化算法 —— 鲁棒动量法，可用于优化平滑强凸函数。该算法有一种参数可以调节对梯度噪声的稳健性与最差情况下的收敛速度之间的平衡。算法具有简单的解析形式，并通过在干净和梯度噪声情况下的一系列数值模拟进行了验证。

    Oct, 2017

  • 用于大规模结构化非凸优化的高效随机坐标下降算法

    本篇研究分析几种解决非凸优化问题的新方法，其中目标函数为由非凸光滑项和已知凸简单项组成的总和，提出了随机坐标下降算法，并研究了它们的收敛性质及一些最优性衡量指标。同时，还针对一般情况下的非凸复合优化问题，证明了算法所生成的序列渐近收敛到固定点，同时在某些最优性测度下期望具有亚线性收敛率，如果目标函数满足误差界限条件，则导出了目标函数期望值的局部线性收敛率，并进行了广泛的数值实验来评估算法性能和与现有方法的比较。

    May, 2013

  • 非光滑非凸优化的快速随机方法

    本文研究随机算法优化非凸、非光滑的有限和问题。针对此问题，本文提出快速的随机算法，可获得常数迷你批量的收敛性。本文还使用这些算法的变种，证明了比批量近端梯度下降更快的收敛性，并在非凸、非光滑函数的一个子类中证明全局线性收敛率。

    May, 2016

  • 适应性梯度方法用于约束凸优化和变分不等式问题

    本文提出了 AdaACSA、AdaAGD + 等新的自适应一阶优化算法，以加速受限制的凸优化问题中的收敛速度，同时针对平滑和不平滑函数，实现几乎最优的收敛速率；同时，通过自动调整每个坐标学习率，这些算法不需要固定事先知道目标函数的参数化，是针对限制优化的真正加速 Adagrad 方法之一。此外，本文提出了适用于无限制优化和单调算子的自适应方法，并附有具体的算法实现。

    Jul, 2020

  • 适应性额外梯度方法用于极小化 - 极大化优化及博弈

    提出了一种新的 MinMax 优化算法家族，它利用早期迭代所观察到的梯度数据的几何信息，以在后期执行更具信息性的额外梯度步骤，从而自适应地检测问题是否光滑。

    Oct, 2020