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