Timezone: »

 
Poster
Sifting through the noise: Universal first-order methods for stochastic variational inequalities
Kimon Antonakopoulos · Thomas Pethick · Ali Kavis · Panayotis Mertikopoulos · Volkan Cevher

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
in Poster Session 3 »
We examine a flexible algorithmic framework for solving monotone variational inequalities in the presence of randomness and uncertainty. The proposed template encompasses a wide range of popular first-order methods, including dual averaging, dual extrapolation and optimistic gradient algorithms – both adaptive and non-adaptive. Our first result is that the algorithm achieves the optimal rates of convergence for cocoercive problems when the profile of the randomness is known to the optimizer: $\mathcal{O}(1/\sqrt{T})$ for absolute noise profiles, and $\mathcal{O}(1/T)$ for relative ones. Subsequently, we drop all prior knowledge requirements (the absolute/relative variance of the randomness affecting the problem, the operator's cocoercivity constant, etc.), and we analyze an adaptive instance of the method that gracefully interpolates between the above rates – i.e. it achieves $\mathcal{O}(1/\sqrt{T})$ and $\mathcal{O}(1/T)$ in the absolute and relative cases, respectively. To our knowledge, this is the first universality result of its kind in the literature and, somewhat surprisingly, it shows that an extra-gradient proxy step is not required to achieve optimal rates.
Keywords:

Author Information

Kimon Antonakopoulos (INRIA)
Thomas Pethick (Swiss Federal Institute of Technology Lausanne)
Ali Kavis (EPFL)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research) and Criteo AI Lab)
Volkan Cevher (EPFL)

More from the Same Authors