Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle

Fedor Stonyakin, Alexander Gasnikov, Pavel Dvurechensky, Mohammad Alkousa, A. TitovarXiv 2018 · DOI · arXiv

Abstract

We introduce an inexact oracle model for variational inequalities (VI) with monotone operators and propose a numerical method to solve them. Our approach, the Generalized Mirror Prox (GMP), is "universal," meaning it achieves optimal convergence rates for Hölder-continuous operators without prior knowledge of the Hölder parameters $\nu$ and $L_\nu$. We extend this method to strongly monotone operators using a restart scheme and demonstrate its application to convex-concave saddle point problems.

Introduction

Variational Inequalities (VIs) serve as a powerful mathematical abstraction encompassing convex optimization, saddle-point problems, and equilibrium problems common in Game Theory and Machine Learning (e.g., Generative Adversarial Networks). Solving these problems efficiently typically requires precise knowledge of the operator's smoothness, often characterized by a Lipschitz constant. However, in many practical scenarios, the operator may only satisfy a more general Hölder continuity condition, where the parameters are unknown. Furthermore, the information provided by the "oracle" (the gradient or operator value) is frequently inexact due to noise or numerical approximations.

This paper presents the Generalized Mirror Prox (GMP) algorithm, a robust framework designed to handle both unknown smoothness and inexact oracles while maintaining optimal theoretical complexity.

The Problem of Unknown Smoothness

In traditional optimization, the Lipschitz constant $L$ dictates the step size. If $L$ is unknown or overestimated, the algorithm may converge slowly; if underestimated, it may diverge. For many problems, the operator $A$ satisfies a Hölder condition: $$\|A(x) - A(y)\|_* \leq L_\nu \|x - y\|^\nu$$ where $\nu \in [0, 1]$. When $\nu=1$, the operator is Lipschitz continuous; when $\nu=0$, it is bounded. In practice, calculating $\nu$ and $L_\nu$ is often impossible.

Additionally, we assume access only to an inexact oracle. The oracle provides an approximation $(\delta, A_\delta(x))$ such that the error is bounded by a combination of a controlled term (which can be reduced at a cost) and an uncontrolled term (inherent noise).

The Generalized Mirror Prox (GMP) Algorithm

The GMP algorithm addresses these challenges through several key innovations:

1. Adaptive Step-Sizing

Unlike standard Mirror Prox, which uses a fixed step size, GMP employs an adaptive strategy. It uses an inner loop to test a step size and verify if a specific descent condition is met. If the condition fails, the step size is reduced, and the iteration is repeated. This allows the algorithm to locally adapt to the geometry of the operator without global constants.

2. Unified Hölder Treatment

The authors employ a mathematical technique to treat Hölder-continuous operators as Lipschitz-continuous operators with an additional "inexactness" term. This unification allows a single algorithmic structure to solve the entire spectrum of Hölder-continuous problems, from non-smooth to smooth.

3. Restart Scheme for Strong Monotonicity

For problems that are strongly monotone—the VI equivalent of strong convexity—the authors introduce a restart version of GMP (Algorithm 2). By restarting the GMP algorithm at specific intervals, the convergence rate is accelerated from polynomial to near-linear, significantly improving efficiency for this subclass of problems.

Key Theoretical and Empirical Results

The paper proves that GMP achieves a complexity of: $$O\left( \inf_{\nu\in[0,1]}\left(\frac{L_\nu}{\varepsilon} \right)^{\frac{2}{1+\nu}}R^2 \right)$$ where $R$ is the diameter of the feasible set and $\varepsilon$ is the target accuracy. This rate is mathematically optimal for first-order methods in this class.

Numerical Validation

The researchers tested the algorithm on the Fermat-Torricelli-Steiner problem with non-smooth functional constraints. The results showed that the adaptive GMP significantly outperformed traditional subgradient methods. While theoretical "worst-case" bounds for non-smooth problems suggest a complexity of $O(1/\epsilon^2)$, the adaptive GMP reached solutions in approximately $O(1/\epsilon^{0.25})$ iterations in practice, demonstrating that adaptivity can far exceed theoretical pessimism.

In tests on synthetic strongly monotone VIs, the restart scheme (Algorithm 2) maintained high accuracy and efficiency, outperforming the existing Modified Projection Method.

Conclusion and Future Work

The Generalized Mirror Prox provides a "universal" solution for monotone VIs, eliminating the need for manual tuning of smoothness parameters while remaining robust to oracle inexactness. While the current work focuses on deterministic noise, future extensions could address stochastic variational inequalities. Additionally, applying these adaptive principles to higher-order methods or decentralized systems remains a promising avenue for research.

Summary updated

Abstract

We introduce an inexact oracle model for variational inequalities (VI) with monotone operator, propose a numerical method which solves such VI's and analyze its convergence rate. As a particular case, we consider VI's with Hölder-continuous operator and show that our algorithm is universal. This means that without knowing the Hölder parameter $ν$ and Hölder constant $L_ν$ it has the best possible complexity for this class of VI's, namely our algorithm has complexity $O\left( \inf_{ν\in[0,1]}\left(\frac{L_ν}{\varepsilon} \right)^{\frac{2}{1+ν}}R^2 \right)$, where $R$ is the size of the feasible set and $\varepsilon$ is the desired accuracy of the solution. We also consider the case of VI's with strongly monotone operator and generalize our method for VI's with inexact oracle and our universal method for this class of problems. Finally, we show, how our method can be applied to convex-concave saddle point problems with Hölder-continuous partial subgradients.
BibTeX
@misc{stonyakin2018generalized,
  author = {Fedor Stonyakin and Alexander Gasnikov and Pavel Dvurechensky and Mohammad Alkousa and A. Titov},
  title = {{Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle}},
  year = {2018},
  eprint = {1806.05140},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.05140},
}
Figure