A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Abstract

We consider variational inequalities coming from monotone operators, a setting that includes convex minimization and convex-concave saddle-point problems. We assume an access to potentially noisy unbiased values of the monotone operators and assess convergence through a compatible gap function which corresponds to the standard optimality criteria in the aforementioned subcases. We present a universal algorithm for these inequalities based on the Mirror-Prox algorithm. Concretely, our algorithm simultaneously achieves the optimal rates for the smooth/non-smooth, and noisy/noiseless settings. This is done without any prior knowledge of these properties, and in the general set-up of arbitrary norms and compatible Bregman divergences. For convex minimization and convex-concave saddle-point problems, this leads to new adaptive algorithms. Our method relies on a novel yet simple adaptive choice of the step-size, which can be seen as the appropriate extension of AdaGrad to handle constrained problems.

References in corpus (3)

• Adaptive Bound Optimization for Online Convex Optimization
• Optimization, Learning, and Games with Predictable Sequences
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces

Cited by in corpus (14)

• On the convergence of single-call stochastic extra-gradient methods
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• Adaptive Gradient Descent for Convex and Non-Convex Stochastic Optimization
• Cautious Reinforcement Learning via Distributional Risk in the Dual Domain
• Adaptive extra-gradient methods for min-max optimization and games
• Generalization Bounds for Stochastic Saddle Point Problems
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games
• Extragradient with player sampling for faster Nash equilibrium finding
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters
• Heuristic adaptive fast gradient method in stochastic optimization tasks
• Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements
• Geometry-Aware Universal Mirror-Prox
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization