Introduction
Many complex machine learning and engineering problems—including the training of Generative Adversarial Networks (GANs), resource allocation, and game-theoretic equilibria—are best modeled as Variational Inequalities (VIs). To solve these efficiently, researchers typically rely on "fast" gradient methods like Nemirovski’s Mirror-Prox, which achieve an optimal $O(1/T)$ convergence rate for deterministic problems.
However, these methods traditionally require the operator to be Lipschitz continuous relative to a global norm. In many practical scenarios, this assumption is violated due to singularities at the boundary of the feasible region or rapid growth in the loss profile. This paper introduces a novel "Bregman continuity" condition to solve VIs where standard smoothness assumptions fail, alongside an Adaptive Mirror-Prox (AMP) algorithm that achieves optimal convergence rates without requiring prior knowledge of the operator's smoothness constant.
The Challenge of Singular Operators
Standard optimization algorithms often become unstable or fail to converge when they are "oblivious" to the geometry of a problem's landscape. The global Lipschitz continuity assumption frequently breaks down in practice for two main reasons:
- Singularities: The gradient might blow up to infinity as the algorithm approaches the boundary of the feasible set. A classic example is resource allocation problems using Kleinrock models.
- Rapid Growth: The loss profile might grow too quickly for a global norm to capture, such as in GANs utilizing Kullback-Leibler divergence.
When these conditions occur, standard algorithms using global Euclidean norms struggle to navigate the steep gradients near boundaries.
Methodology: Taming Singularities with Geometry
To bridge this gap, the authors introduce two primary innovations that adapt the algorithm to the problem's underlying geometry.
1. Bregman Continuity
Instead of measuring smoothness against a fixed global norm, the authors define a regularity condition relative to a Bregman function and a family of local norms. This allows the "measure of distance" to warp and adapt to the specific singularities of the problem. If an operator is "Bregman continuous," its variation is bounded by the variation of a suitably chosen Bregman divergence.
This geometry-aware regularization is a crucial insight: the failure of standard methods isn't a flaw in the algorithms themselves, but in the distance metric used to analyze them. By choosing a Bregman function that matches the singularity of the operator (e.g., using a log-barrier for a $1/x$ singularity), the problem is transformed to look "smooth" in the warped space.
2. Adaptive Mirror-Prox (AMP)
Standard Mirror-Prox requires a step-size $\gamma < 1/\beta$, where $\beta$ is the Lipschitz (or Bregman) constant. In practice, $\beta$ is often unknown or impossible to calculate for singular operators.
The AMP algorithm estimates this constant on the fly by comparing the operator's values at successive states. It utilizes a "shrinkage" policy to ensure the step size remains valid even when the operator's behavior changes drastically near a boundary. AMP effectively "learns" the local smoothness of the problem, taking large, aggressive steps in well-behaved regions and automatically slowing down as it approaches dangerous singular boundaries.
Experimental Validation
As a theoretical optimization paper, the authors evaluate their algorithm using rigorous synthetic benchmarks rather than standard image or text datasets. They simulate a Resource Sharing Problem involving $R = 1000$ servers and $N = 100$ commodities. The service times are modeled using M/M/1 queues, which naturally exhibit singularities (service time goes to infinity as load approaches capacity). This provides a robust testbed for handling singular operators.
Key Results
- Optimal Convergence: The authors prove that AMP achieves the optimal $O(1/T)$ rate for monotone, deterministic VIs and $O(1/\sqrt{T})$ for stochastic VIs under the Bregman continuity assumption.
- Stability over Baselines: In numerical experiments, the standard "extra-gradient" (Euclidean) method proved unstable and failed to converge because the gradients near the boundary were too large.
- Superior Speed: AMP converged significantly faster than standard Mirror-Prox with a fixed step size. Because AMP can use a "greedier" initial step size and only shrink it when necessary, it avoids the overly conservative fixed step sizes required to account for worst-case singularities.
Limitations and Future Work
While AMP represents a significant step forward for singular VIs, the authors note a few areas for future exploration:
- Choice of Bregman Function: While the algorithm is adaptive to the constant $\beta$, the user must still choose an appropriate Bregman function $h$ that matches the problem's geometry. Developing a fully "model-agnostic" version remains an open challenge.
- Non-Monotone Problems: The current analysis assumes the operator is monotone (the VI equivalent of a convex function). Extending these guarantees to local convergence in non-monotone settings (like non-convex GAN training) is a vital next step.
- Line Search Integration: Combining the adaptive step-size with traditional backtracking or line-search methods could potentially yield even faster convergence in practice.
Summary updated