Apr, 2019

无双线性结构问题的随机原始 - 对偶算法比 O (1/√T) 更快地收敛

PDF
TL;DR本文提出了一种新的随机原始 - 对偶算法来解决一类包含凸 - 凹结构的问题，并且相比现有算法在迭代次数上有更快的收敛速度，其中使用了梯度更新和确定性对偶变量更新的混合方法。
stochastic primal-dual algorithmsmin-max problemsconvex-concave problemsfaster convergence ratesdeterministic dual updates
发现论文，激发创造
  • 用主 - 对偶次梯度法最小化一致凸函数

    讨论非欧几里得确定性和随机算法，解决强凸和一致凸的优化问题，提供算法性能的准确性界限，设计针对强或一致凸性参数的自适应方法：在总迭代次数 $N$ 固定的情况下，它们的准确度与最优算法的准确度相同，直到 $N$ 的对数因子。

    Jan, 2014

  • 大规模优化的随机主支配 - 最小化算法

    本文提出了一种可扩展的随机主化最小化方案，能够应对大规模或可能无限的数据集，解决凸优化问题，并开发了几种基于此框架的有效算法，包括一个新的随机近端梯度方法，用于大规模 l1 逻辑回归的非凸稀疏估计的在线 DC 编程算法和解决大规模结构矩阵分解问题的有效性。

    Jun, 2013

  • 随机原始 - 对偶近端块坐标更新

    本文提出了一种用于解决多块凸优化问题的随机 Primal-Dual 近端块坐标更新框架，并使用其达到 $O (1/t)$ 的收敛速度，且包含现有算法的特例，以及推广至解决随机编程的问题。

    May, 2016

  • 近端随机梯度 Langevin 算法的原始对偶解释

    本文研究基于对数凹概率分布的采样任务，首先建立了该最小化问题的强对偶结果，然后使用该结果研究了投影 Langevin 算法的复杂度，结果表明 Proximal Stochastic Gradient Langevin 算法的复杂度优于 Projected Langevin 算法，尤其是目标分布为强凸时。

    Jun, 2020

  • 随机原始 - 对偶混合梯度的收敛性

    本文分析了新提出的 SPDHG 算法并给出了新的理论结果，证明了算法的收敛性和线性收敛性，同时提供数值实验证明了该算法在实际应用中的表现竞争力很强，特别是在支持向量机等问题上的实现效果不错。

    Nov, 2019

  • 随机原始 - 对偶法用于经验风险最小化，每次迭代复杂度为 O（1）

    本文提出了新的随机原始对偶算法，用于解决具有线性预测器的正则化经验风险最小化问题。通过泰勒展开、凸组合和割平技巧得到具有较优复杂度和收敛性质的算法，进一步提出了方差减少版算法和数值实验表明该算法在高维问题上优于现有算法，收敛速度更快。

    Nov, 2018

  • 基于随机对偶平均的快速期望对数损失最小化

    本文介绍了一种用于最小化预期对数损失的随机一阶算法，解决了凸优化问题中由于损失函数的缺乏 Lipschitz 连续性和平滑性而导致标准迭代复杂度保证不直接适用的问题，提出的算法取得了比现有方法更好的复杂度和性能。

    Nov, 2023

  • 具任意采样随机原始对偶混合梯度算法及其在成像领域的应用

    提出一种随机扩展的原始 - 对偶混合梯度算法用于解决在对偶变量中可分离的鞍点问题，该算法适用于一般的凸凹鞍点问题和部分平滑 / 强凸或完全平滑 / 强凸问题，并且在任意抽样的对偶变量中，有多个变体的随机方法在各种图像任务中显着优于确定性变体。

    Jun, 2017

  • 非 Lipschitz 连续情况下的确定性与随机次梯度方法的收敛速度

    通过对 Shor 子梯度分析的推广，我们将子梯度方法的经典收敛速度理论扩展到可适用于非 Lipschitz 函数。我们证明了在任何具有局部 Lipschitz 性的凸函数中，确定性投影子梯度算法的全局 O（1/√T）收敛速度。我们还表明，对于具有最多二次增长的凸函数，随机投影子梯度方法的收敛速度为 O（1/√T），在强凸性或较弱的二次下限条件下，该速度可进一步提高至 O (1/T)。

    Dec, 2017

  • 自适应原始对偶随机梯度方法用于期望约束凸随机规划

    本文提出了一种基于拉格朗日函数的新的自适应贪婪分布算法去解决期望约束凸随机优化问题，收敛速度快于现有的非自适应算法和基于原始变量的 SGM，并且扩展到解决凸凹随机极小极大问题。

    Dec, 2020