New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness

Some adaptive analogue of the Mirror Prox method for variational inequalities is proposed. In this work we consider the adaptation not only to the value of the Lipschitz constant, but also to the magnitude of the oracle error. This approach, in particular, allows us to prove a complexity near \(O\le...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-09
Main Authors: Stonyakin, Fedor, Vorontsova, Evgeniya, Alkousa, Mohammad
Format: Article
Language:English
Subjects:
Adaptation
Cybernetics
Estimates
Inequalities
Operators
Smoothness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Some adaptive analogue of the Mirror Prox method for variational inequalities is proposed. In this work we consider the adaptation not only to the value of the Lipschitz constant, but also to the magnitude of the oracle error. This approach, in particular, allows us to prove a complexity near \(O\left(\frac{1}{\varepsilon}\log_2\frac{1}{\varepsilon}\right)\) for variational inequalities for a special class of monotone bounded operators. This estimate is optimal for variational inequalities with monotone Lipschitz-continuous operators. However, there exists some error, which may be insignificant. The results of experiments on the comparison of the proposed approach with some known analogues are presented. Also, we discuss the results of the experiments for matrix games in the case of using non-Euclidean proximal setup.
ISSN:2331-8422
DOI:10.48550/arxiv.1907.13455