Sep, 2020

矩阵游戏的协调方法

PDF
TL;DR本文提出基于 primal-dual coordinate 方法，并应用于解决包含线性规划、分类和回归问题的双线性鞍点问题。通过设计高效的数据结构和低方差梯度估计器，我们获得了近乎恒定的每次迭代复杂度，并且在采样复杂度上实现了改进。同时，我们应用该方法到最小圆覆盖，最大内接圆和线性回归的计算几何问题中，并获得了改善的计算复杂度。
primal-dual coordinate methodsbilinear saddle-point problemslinear programmingregressionlow-variance gradient estimators
发现论文，激发创造
  • 矩阵博弈的方差减少

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

    Jul, 2019

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

    算法设计为在欧几里得或单纯形域内最小化 max (f_i (x))，若每个 f_i 为 1-Lipschitz 和 1 - 光滑函数，我们的方法可以在评价复杂度中找到 ε- 近似解，并具有优化性能。

    Nov, 2023

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

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

    Dec, 2020

  • 大规模多类别分类的高效原始 - 对偶算法

    本文介绍了如何使用随机镜像下降法和非均匀采样方案，来快速训练高维度特征空间、多分类通用的线性分类器，特别是在多类 Hinge 损失下，本文提出了一个迭代次数为 $O (d+n+k)$ 的子线性算法。

    Feb, 2019

  • 非强凸凸凹鞍点问题的原始 - 对偶梯度法的线性收敛

    本研究针对具有凸 - 凹鞍点问题的优化进行了研究，证明了即使 $f$ 不强凸，使用一般的原始 - 对偶梯度方法也可以实现线性收敛，并给出了具有有限和结构的凸 - 凹鞍点问题的原始 - 对偶随机方差减少梯度方法的分析。

    Feb, 2018

  • 块坐标原始对偶方法在线性约束下的非光滑最小化

    研究了解决线性约束下凸、可分、非光滑函数的最小化问题，提出了一种基于 Chambolle-Pock 原始 - 对偶算法的块坐标扩展的数值方法，并证明了方法的收敛性，而不需要诸如凸性或强凸性、矩阵的满秩条件、强对偶性甚至线性系统的连续性之类的假设。不需加上关于线性系统的假设可以保证在系统缺失或存在噪声的情况下的收敛性保证。

    Jan, 2018

  • 自适应随机原始对偶坐标下降算法处理可分离鞍点问题

    本文提出了一种基于随机块坐标下降和自适应步长的原始 - 对偶更新框架，用于解决具有可分结构的凸 - 凹鞍点问题，并在正则化的经验风险最小化问题上进行了实证分析，结果表明该方法具有较快的收敛速度和良好的表现。

    Jun, 2015

  • 高效求解密集线性系统的方法

    提出了一种随机优化算法，通过块坐标下降方法和矩阵草图技术，在线性系统中实现了良好的收敛性能和快速迭代时间。

    Dec, 2023

  • 原始 - 对偶坐标下降的随机外推

    本文介绍了一种随机外推的原始 - 对偶坐标下降方法，它适应数据矩阵的稀疏性和目标函数的有利结构，更新了仅包含稀疏数据的一小部分原始和对偶变量，并使用较大的步长和密集数据，保留了为每种情况设计的特定方法的优点。此外，我们的方法不需要任何修改即可适应稀疏性，在有利的情况下获得快速收敛保证，特别是我们证明了在度规亚正则情况下的线性收敛，这适用于强凸强凹问题和分段线性二次函数。我们显示了序列的几乎确定收敛和原始 - 对偶间隙和目标值的最优亚线性收敛率，在一般凸凹情况下。数值证据证明了我们的方法在稀疏和密集环境中的最新实证表现，与现有方法相匹配和改进。

    Jul, 2020

  • 基于盒约束牛顿法和内点方法的矩阵缩放和平衡

    本篇论文提出了一种新的二阶优化框架，用于处理矩阵缩放和平衡问题，提出了可以忽略对数因子的算法，可以在几乎线性时间内解决这些问题，同时提供了一种使用内部点方法的单独算法，以及广泛适用的第二阶鲁棒函数最小化方法。

    Apr, 2017