Nov, 2023

全新的角色扮演加速方法：矩阵游戏和平滑函数的最大化最小化

PDF
TL;DR算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。
发现论文，激发创造
  • 矩阵博弈的方差减少

    本研究提出了一种随机原始 - 对偶算法用于求解优化问题，并通过引入新的梯度估计算法，将计算复杂度降低到矩阵稀疏的情况下达到了最优。

    Jul, 2019

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

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

    Oct, 2020

  • 使用球优化 Oracle 进行加速

    使用 oracle 和 Newton 方法来设计加速算法以达到更优秀的拟合结果。

    Mar, 2020

  • 矩阵游戏的协调方法

    本文提出基于 primal-dual coordinate 方法，并应用于解决包含线性规划、分类和回归问题的双线性鞍点问题。通过设计高效的数据结构和低方差梯度估计器，我们获得了近乎恒定的每次迭代复杂度，并且在采样复杂度上实现了改进。同时，我们应用该方法到最小圆覆盖，最大内接圆和线性回归的计算几何问题中，并获得了改善的计算复杂度。

    Sep, 2020

  • 一般矩阵博弈的次线性经典和量子算法

    本研究提出了一种插值算法，该算法能够在两个特殊情况之间插值，并解决矩阵游戏问题。我们同时提供经典算法和量子算法，用于近似 Cara​théodore 问题和 lq-margin 支持向量机。

    Dec, 2020

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

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

    Feb, 2020

  • 有限和平凡导数光滑优化的复杂性研究

    本文研究了一种优化问题，在多项式朗托泽维奇条件下，通过梯度方法在分布式环境中找到次优解，提出了一个去中心化一阶方法，并给出了相应的下界。

    Feb, 2024

  • 加速梯度算法与自适应子空间搜索用于快速实例优化

    设计和分析基于梯度的算法，适用于机器学习中的优化问题，包括线性回归等，并改进了现有的复杂度下界。

    Dec, 2023

  • 具有小维松弛预测器的原始 - 对偶加速梯度方法

    本文提出一种新的加速梯度下降的变种，该方法不需要任何有关目标函数的信息，使用精确线性搜索进行实际加速收敛，可以根据已知的凸和非凸目标函数的下界进行收敛，具有原始对偶属性，并可在非欧几里得设置中应用。同时，我们还提出了一种适用于非平滑问题的通用方法。

    Sep, 2018

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

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

    May, 2022