Skip to Main content Skip to Navigation
Conference papers

An adaptive mirror-prox algorithm for variational inequalities with singular operators

Abstract : Lipschitz continuity is a central requirement for achieving the optimal O(1/T) rate of convergence in monotone, deterministic variational inequalities (a setting that includes convex minimization, convex-concave optimization, nonatomic games, and many other problems). However, in many cases of practical interest, the operator defining the variational inequality may exhibit singularities at the boundary of the feasible region, precluding in this way the use of fast gradient methods that attain this optimal rate (such as Nemirovski's mirror-prox algorithm and its variants). To address this issue, we propose a novel regularity condition which we call Bregman continuity, and which relates the variation of the operator to that of a suitably chosen Bregman function. Leveraging this condition, we derive an adaptive mirror-prox algorithm which attains the optimal O(1/T) rate of convergence in problems with possibly singular operators, without any prior knowledge of the degree of smoothness (the Bregman analogue of the Lipschitz constant). We also show that, under Bregman continuity, the mirror-prox algorithm achieves a $O(1/ \sqrt{T})$ convergence rate in stochastic variational inequalities.
Document type :
Conference papers
Complete list of metadatas

Cited literature [49 references]  Display  Hide  Download

https://hal.inria.fr/hal-02403562
Contributor : Panayotis Mertikopoulos <>
Submitted on : Tuesday, December 10, 2019 - 9:19:15 PM
Last modification on : Tuesday, October 6, 2020 - 4:20:10 PM
Long-term archiving on: : Wednesday, March 11, 2020 - 6:02:48 PM

File

AdaptiveMirrorProx-NIPS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02403562, version 1

Citation

Kimon Antonakopoulos, Elena Veronica Belmega, Panayotis Mertikopoulos. An adaptive mirror-prox algorithm for variational inequalities with singular operators. NeurIPS 2019, 2019, Vancouver, Canada. ⟨hal-02403562⟩

Share

Metrics

Record views

443

Files downloads

317