A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:164194, 2019.
Abstract
We consider variational inequalities coming from monotone operators, a setting that includes convex minimization and convexconcave saddlepoint 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 MirrorProx algorithm. Concretely, our algorithm \emph{simultaneously} achieves the optimal rates for the smooth/nonsmooth, and noisy/noiseless settings. This is done without any prior knowledge of these properties, and in the general setup of arbitrary norms and compatible Bregman divergences. For convex minimization and convexconcave saddlepoint problems, this leads to new adaptive algorithms. Our method relies on a novel yet simple adaptive choice of the stepsize, which can be seen as the appropriate extension of AdaGrad to handle constrained problems.
Related Material


