本文提出了适用于具有各种设置的函数约束 VI 问题的新型一阶方法,包括具有随机算子和 / 或随机约束的平滑或非平滑问题。通过使用算子和约束的外推来更新变量和 Lagrange 乘子,我们的算法能够实现最优操作员或样本复杂度。对于平滑的确定性问题,我们还提出了一种新的单循环自适应 Lagrangian 外推方法,可以自适应地搜索和显式地绑定 Lagrange 乘子。此外,我们的算法可以轻松地扩展到具有耦合函数约束的鞍点问题。
Apr, 2023
本文提出了两种针对带约束凸问题的一阶方法,分别使用增广拉格朗日方法和单一近端梯度步进行变量更新,并证明了它们的全局和局部收敛性。数值实验验证了理论结果与实际表现的一致性。
Nov, 2017
本文提出了一种名为 ALAVI 的增广 Lagrangian 原始 - 对偶方法,用于解决带有凸锥约束的非单调(混合)变分不等式模型,并证明了该方法的收敛性和全局收敛速率以及具有单调映射时的加速收敛速率,同时进行了大量的数值实验以证明方法的实用性。
Jun, 2023
该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性,包括梯度映射和 Frank-Wolfe 间隙准则,并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性,数值实验证明了该方法的有效性。
Jun, 2024
机器学习中的快速进步基于与梯度优化的高效连接,在决策和多智能体问题上的转变为算法设计的新领域提出了新的数学挑战,我们提供了一个更广泛的梯度优化算法框架的简要介绍。
Sep, 2023
本文提出了一种原始 - 对偶算法框架,以获得近似解决方案来解决典型的约束凸优化问题,并严格描述了常见结构假设如何影响数值效率。通过选择双重平滑策略和中心点,我们的框架将分解算法、增广 Lagrange 以及交替方向乘子方法作为其特殊情况,并为所有迭代的原始目标残差和原始可行性间隙提供最优收敛速率。
Jun, 2014
提出一种用于优化框架、鞍点问题和变分不等式的一般算法框架,通过构建主要问题组成部分即优化目标函数或者变分不等式运算符的不精确模型,不但可以产生许多已知的算法方法,同时可以构造新的算法方法,如具有复合结构的变分不等式的通用条件梯度法和相对光滑度算子的变分不等式算法。
Jan, 2020
本文研究带复杂约束条件下在线凸优化问题,提出了一种基于镜像投影算法的新算法,可以在任何范数空间中实现低后悔和低约束违反度。
Jun, 2020
该论文提出了一种基于 Mirror-Prox 算法的普适性算法,适用于具有噪声和非噪声数据以及平滑和非平滑函数的情况。算法通过适应性步长的选择来处理相关的约束问题,可以用于解决凸最小化和凸 - 凹鞍点问题等应用。
Feb, 2019
通过对双向上升算法进行特性化,我们在非凸条件下解决了理论与实践之间的差距,揭示了双向学习的先前经验成功,并在公平学习任务中验证了我们的结果。
Mar, 2024