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