Dec, 2015

随机对偶上升用于解线性系统

PDF
TL;DR提出了一种新的随机迭代算法 —— 随机对偶上升 (SDA)，用于在线性系统的解空间中找到给定向量的投影。该算法通过随机矩阵的列子空间上的精心选择点来更新对偶变量，并证明了与对偶过程相关的原始迭代会期望指数级别收敛至投影。SDA 收敛于一致性之外的无其他假设的线性系统，特殊情况下，该方法可用于分布式平均共识问题，产生各种新算法。
发现论文，激发创造
  • 随机梯度下降 - 上升：统一理论和新高效方法

    本文提出了 SGDA 的统一收敛性分析框架，覆盖了各种随机梯度下降上升方法，并分别提出了多种新变体方法，通过大量数值实验证明了这些方法的重要性质。

    Feb, 2022

  • SDNA：随机二次牛顿提升算法用于经验风险最小化

    通过 Stochastic Dual Newton Ascent 算法，我们提出一种新的途径最小化正则化经验损失，该方法更新了随机子集的对偶变量，可以利用模型中所有曲率信息，实践中有着明显的提高，特别对于二次损失函数。

    Feb, 2015

  • 用于正则化损失最小化的随机对偶坐标上升方法

    本研究介绍了随机对偶坐标上升法 (SDCA) 的新分析，证明了这类方法具有与随机梯度下降法 (SGD) 相当或更好的理论保证，从而证明了 SDCA 在实际应用中的有效性。

    Sep, 2012

  • 分散随机梯度下降上升算法的稳定性和泛化性

    我们研究了分布式随机梯度上升下降（D-SGDA）算法的原始 - 对偶广义界限，通过算法稳定性方法，在凸凹和非凸非凹环境下对分布式最小最大算法的广义界限进行了改进。我们的理论研究表明，分布式结构不会破坏 D-SGDA 的稳定性和广义化能力，在某些情况下可以实现和普通 SGDA 相同的广义化能力。此外，我们还评估了凸凹设定下 D-SGDA 算法的优化误差，并将其与广义间隙相平衡，以获得最佳的总体风险。最后，我们进行了多项数值实验来验证我们的理论发现。

    Oct, 2023

  • 无对偶的 SDCA

    本文介绍了一种 Stochastic Dual Coordinate Ascent 算法的变体，用于解决非凸损失函数的正则化损失最小化问题，并且证明了只要期望损失是凸的，就可以确保该算法具有线性收敛速度。

    Feb, 2015

  • 解线性系统的高效加速坐标下降方法和更快的算法

    该论文介绍了如何加速随机坐标下降方法，提高收敛速度，同时又不用支付每次迭代的代价。它提出了一个新的通用方法，并证明它的收敛性，并在多个领域中获得更快的渐近运行时间。

    May, 2013

  • 线性系统的随机迭代方法

    该研究发展了一种基于随机迭代的方法来解决线性系统问题，并通过变化两个参数来恢复广泛的已知算法，并且在单个定理中证明了误差的指数收敛，并给出了预期迭代的精确公式。

    Jun, 2015

  • 自适应概率随机对偶坐标上升

    介绍了 AdaSDCA：一种自适应的随机对偶坐标上升（SDCA）变体，用于解决正则化经验风险最小化问题。AdaSDCA 通过在迭代过程中自适应地改变对偶变量上的概率分布，实现了比 SDCA 更好的复杂度界限。同时，我们提出了 AdaSDCA+：一种实用的变体，在实验中表现优于现有的非自适应方法。

    Feb, 2015

  • DSA：去中心化双随机平均梯度下降算法

    该论文提出了分布式双随机平均梯度算法 (DSA) 来解决大规模机器学习问题，具有线性收敛特性，相对于其他分散式随机优化方法，可以减少收敛时间和处理的功能向量数量。

    Jun, 2015

  • 无对偶、正则化和单独凸性的 SDCA

    提出了改进型的随机对偶坐标上升方法，无需显式正则化，无需依赖对偶性，甚至对于非凸损失函数，只要期望损失函数是强凸的，就可以证明收敛率是线性的。

    Feb, 2016