Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
复制标题
DOI：
10.1609/aaai.v36i6.20609
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Alina Ene;Huy L. Nguyen
中科院分区：
文献类型：
--
作者：
Alina Ene;Huy L. Nguyen
我们开发了新的自适应算法与单调算子的变分不等式，它捕获了许多感兴趣的问题，特别是凸优化和凹凸鞍点问题。我们的算法自动适应未知的问题参数，如平滑和规范的运营商，和方差的随机评估预言。我们表明，我们的算法是通用的，同时达到最佳的收敛速度在非光滑，光滑，随机设置。我们的算法的收敛保证改善现有的自适应方法，并匹配最佳的非自适应算法。此外，以前的工作要求优化域是有界的。在这项工作中，我们删除这个限制，并给出算法的无界域是自适应的和普遍的。我们的一般证明技术可以用于算法的许多变体，每次迭代使用一个或两个运算符评估。基于ExtraGradient/RightProx算法的经典方法每次迭代需要两次运算符评估，这在许多设置中是运行时间的主要因素。
We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms automatically adapt to unknown problem parameters such as the smoothness and the norm of the operator, and the variance of the stochastic evaluation oracle. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates in the non-smooth, smooth, and stochastic settings. The convergence guarantees of our algorithms improve over existing adaptive methods and match the optimal non-adaptive algorithms. Additionally, prior works require that the optimization domain is bounded. In this work, we remove this restriction and give algorithms for unbounded domains that are adaptive and universal. Our general proof techniques can be used for many variants of the algorithm using one or two operator evaluations per iteration. The classical methods based on the ExtraGradient/MirrorProx algorithm require two operator evaluations per iteration, which is the dominant factor in the running time in many settings.