A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise
This provides an adaptive solution for constrained optimization problems, but it is incremental as it extends existing methods like AdaGrad to handle constraints.
The paper tackles the problem of solving variational inequalities from monotone operators, which includes convex minimization and saddle-point problems, by proposing a universal algorithm based on Mirror-Prox that adapts to smoothness and noise without prior knowledge, achieving optimal rates in all settings.
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.