Skip to Main content Skip to Navigation
Conference papers

Sifting through the noise: Universal first-order methods for stochastic variational inequalities

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03357714
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Wednesday, September 29, 2021 - 2:54:55 AM
Last modification on : Wednesday, July 6, 2022 - 4:23:06 AM
Long-term archiving on: : Thursday, December 30, 2021 - 6:11:18 PM

File

RelativeNoise.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03357714, version 1

Citation

Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities. NeurIPS 2021 - 35th International Conference on Neural Information Processing Systems, Dec 2021, Virtual, Unknown Region. pp.1-39. ⟨hal-03357714⟩

Share

Metrics

Record views

156

Files downloads

78