Jun, 2018

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

PDF
TL;DR我们介绍了一种不精确的 VI 正演算子模型，提出了一种数值方法来解决此类 VI 问题，并分析其收敛速度。我们还考虑了强单调算子的情况，并将我们的方法推广到具有不精确正演算子和 H"older 连续偏次梯度的凸凹鞍点问题。
variational inequalitiesmonotone operatornumerical methodconvergence rateconvex-concave saddle point problems
发现论文，激发创造
  • 一种适应于光滑度和噪声的变分不等式通用算法

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

    Feb, 2019

  • 使用随机镜像下降算法求解变分不等式

    本文提出了一种新的随机镜子代理（SMP）算法，通过便捷的步长策略优化收敛率，应用于解决了随机组合最小化和特定应用于随机半定可行性问题和最小化特征值的随机变分不等式问题

    Sep, 2008

  • 变分不等式的黄金比例算法

    本文介绍了一种针对单调变分不等式问题的全显式算法，该算法使用计算变量步长的方法来近似本地 Lipschitz 常数，每次迭代只需要评估单调算子 $F$ 和一个 proximal 映射 $g$，并且如果 $F，g$ 满足误差条件，则该方法表现出的收敛速度是 $O (1/k)$ 和 $R$ 线性速度，可以应用于不同类型的固定点问题。

    Mar, 2018

  • 关于不精确模型下优化和变分不等式的非精确相对光滑度和强凸性

    提出一种用于优化框架、鞍点问题和变分不等式的一般算法框架，通过构建主要问题组成部分即优化目标函数或者变分不等式运算符的不精确模型，不但可以产生许多已知的算法方法，同时可以构造新的算法方法，如具有复合结构的变分不等式的通用条件梯度法和相对光滑度算子的变分不等式算法。

    Jan, 2020

  • 近最优无参数单调包含和变分不等式有限强解的哈尔普恩迭代

    基于 Halpern 迭代的潜能函数收敛证明，我们利用非扩张映射、单调 Lipschitz 算子和近端映射之间的联系，得到了解决单调包含问题的近乎最优无参方法，同时转化为解决变分不等式问题、拟凸 - 凹极小极大优化问题的近乎最优保证，并在分析中提供了一系列的算法降低证明复杂度。

    Feb, 2020

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

    本文研究一类广义单调变分不等式问题及其非欧几里得外推梯度算法，并通过数值实验表明该算法在求解大规模问题上具有明显优势。

    Nov, 2013

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

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

    Mar, 2017

  • 一类变分不等式加速方案

    本文提出了一种新的方法 —— 加速镜像近端（AMP）方法，用于计算一类确定性和随机单调变分不等式的弱解，该方法将多步加速方案融入到镜像近端方法中。对于确定性和随机 VI，AMP 方法计算出最佳收敛速度的弱解。特别地，如果 VI 中的单调算子由平滑函数的梯度组成，则 AMP 方法的收敛速度估计中的 Lipschitz 常数可以加速。对于有界可行集的 VI，AMP 方法的收敛速度估计取决于可行集的直径。对于无界 VI，我们采用 Monteiro 和 Svaiter 引入的修改间隙函数，证明了 AMP 方法的收敛速度取决于初始点到强解集合的距离。

    Mar, 2014

  • 有限和单调包含的方差减少哈尔彭迭代

    应用机器学习方法解决针对敌对鲁棒性或多主体环境产生的博弈均衡问题，提出了基于有限和结构的方法。使用方差缩减技术改进了经典的 Halpern 迭代，通过在求和中的组分算子上引入可比较的 cocoercive 或 Lipschitz 连续单调性，取得了性能改进。所提出的方法具有可验证的退出准则，并且在最后迭代次数和（可计算的）操作符范数残差方面提供了保证。其 oracle 复杂性为 $𝜃(𝑛+√𝑛𝐿𝜖^{-1})$，相较于现有方法提升了多达√𝑛倍，将方差缩减引入到通用有限和单调包含问题和具体问题中，如算子范数残差是最优性度量的凸 - 凹优化，创造了一项新的成果。进一步论证表明，在单调 Lipschitz 设置中，除去多项式对数因子，这种复杂性是无法被改进的，即提供的结果几乎是最优的。

    Oct, 2023

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

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

    Apr, 2023