Nov, 2013

关于广义单调算子变分不等式的非欧几里得外推方法的收敛性质

PDF
TL;DR本文研究一类广义单调变分不等式问题及其非欧几里得外推梯度算法，并通过数值实验表明该算法在求解大规模问题上具有明显优势。
generalized monotone variational inequalitynon-euclidean extragradient methoditeration complexitylipschitz continuitynumerical studies
发现论文，激发创造
  • 求解黎曼流形变分不等式问题的外推类方法

    利用 Riemann 曲面的特性，本文探讨了 Riemann 凸优化、极小极大优化等问题，并引入了 Riemann 外推梯度方法和 Riemann 过去外推梯度方法，证明了它们在最后迭代时的收敛性。

    Sep, 2023

  • 约束单调变分不等式的 Extragradient 算法和乐观梯度下降上升算法的紧凑最后迭代收敛性

    本研究解决了开放性问题，证明了用切向残差作为潜势函数的 extragradient 算法（或乐观梯度上升下降算法）在任意凸可行域上具有极致的收敛速率，其简单的表达为 $O (1/√T)$ 。

    Apr, 2022

  • 具有方差缩减的随机变分不等式外推法

    我们提出了一种超梯度方法，它具有远离零的步长，适用于仅需要伪单调性的随机变分不等式。我们提供了收敛性和复杂性分析，其可允许无界可行集，无界算子，或不均匀的预测方差，并且不需要任何规则化。

    Mar, 2017

  • 单次随机额外梯度方法的收敛性

    本文介绍了一种名为 Extra-Gradient 算法的方法，通过仅使用一个 oracle 调用每个迭代来代替额外的梯度步骤，是深度学习应用中极具潜力的方法，证明了它们在解决光滑、确定性问题的同时仍然保持了 O (1/t) 的收敛速度，并且还展示了单调确定性情况下单次、随机额外梯度方法的最后迭代仍具有局部收敛速度到解决非单调变分不等式问题的二阶充分条件。

    Aug, 2019

  • 锥约束非单调变分不等式问题的增广 Lagrangian 方法

    本文提出了一种名为 ALAVI 的增广 Lagrangian 原始 - 对偶方法，用于解决带有凸锥约束的非单调（混合）变分不等式模型，并证明了该方法的收敛性和全局收敛速率以及具有单调映射时的加速收敛速率，同时进行了大量的数值实验以证明方法的实用性。

    Jun, 2023

  • 广义镜像下降算法解单调变分不等式：普适性与不精确预言机

    我们介绍了一种不精确的 VI 正演算子模型，提出了一种数值方法来解决此类 VI 问题，并分析其收敛速度。我们还考虑了强单调算子的情况，并将我们的方法推广到具有不精确正演算子和 H"older 连续偏次梯度的凸凹鞍点问题。

    Jun, 2018

  • 带函数约束的随机变分不等式问题的一阶方法

    本文提出了适用于具有各种设置的函数约束 VI 问题的新型一阶方法，包括具有随机算子和 / 或随机约束的平滑或非平滑问题。通过使用算子和约束的外推来更新变量和 Lagrange 乘子，我们的算法能够实现最优操作员或样本复杂度。对于平滑的确定性问题，我们还提出了一种新的单循环自适应 Lagrangian 外推方法，可以自适应地搜索和显式地绑定 Lagrange 乘子。此外，我们的算法可以轻松地扩展到具有耦合函数约束的鞍点问题。

    Apr, 2023

  • 具有最佳复杂度和通信保证的分布式额外梯度算法

    我们考虑在多 GPU 设置中使用局部随机对偶向量解决单调变分不等式问题，提出了一种量化的广义额外梯度算法，通过提供自适应步长规则和分布式训练加速收敛来验证理论结果，并在多 GPU 上训练生成对抗网络。

    Aug, 2023

  • 随机变分不等式问题的最优鲁棒平滑外推算法

    本文考虑了随机泛型不等式问题及其解决方案，利用局部随机平滑方案求解，并证明了该解决方案在平均意义下和几乎肯定意义下都能收敛到问题的解，同时也实现了 $1/k$ 的收敛速度。

    Mar, 2014

  • 一种适应于光滑度和噪声的变分不等式通用算法

    该论文提出了一种基于 Mirror-Prox 算法的普适性算法，适用于具有噪声和非噪声数据以及平滑和非平滑函数的情况。算法通过适应性步长的选择来处理相关的约束问题，可以用于解决凸最小化和凸 - 凹鞍点问题等应用。

    Feb, 2019