Source-linked AI summary
Solving variational inequalities with Stochastic Mirror-Prox algorithm
Anatoli Juditsky, Arkadii S. Nemirovskii, Claire Tauvel
TL;DR
The paper addresses stochastic variational inequalities with monotone operators when first-order information is noisy and operators may combine smooth and nonsmooth components. It develops Stochastic Mirror-Prox, establishes dimension-uniform optimal convergence rates under a suitable stepsize strategy, and applies it to composite minimization, semidefinite feasibility, and eigenvalue minimization.
Problem
Stochastic variational inequalities require iterative methods when exact first-order information is unavailable and only noisy observations can be obtained.
Method
The paper develops a Stochastic Mirror-Prox algorithm for monotone stochastic variational inequalities and tunes it to the problem geometry with a stepsize strategy.
Results
The method attains a dimension-uniform optimal convergence rate and is applied to stochastic composite minimization, semidefinite feasibility, and eigenvalue minimization.
Takeaways & Limitations
Saddle-point reformulations make stochastic composite optimization amenable to first-order algorithms through unbiased stochastic oracles for the associated variational-inequality operator.
Takeaways & Limitations
The framework assumes monotone operators and imposes an additional regularity requirement on the operator.
Abstract
from arXiv · showhide
In this paper we consider iterative methods for stochastic variational inequalities (s.v.i.) with monotone operators. Our basic assumption is that the operator possesses both smooth and nonsmooth components. Further, only noisy observations of the problem data are available. We develop a novel Stochastic Mirror-Prox (SMP) algorithm for solving s.v.i. and show that with the convenient stepsize strategy it attains the optimal rates of convergence with respect to the problem parameters. We apply the SMP algorithm to Stochastic composite minimization and describe particular applications to Stochastic Semidefinite Feasability problem and Eigenvalue minimization.
1 Introduction
The paper develops first-order methods for stochastic variational inequalities with monotone operators when exact first-order information is replaced by unbiased stochastic estimates. It extends Mirror-Prox to achieve dimension-uniform optimal convergence rates and applies the framework to several convex problems.
- Variational inequalities with monotone operators provide a unified framework for convex minimization, convex-concave saddle points, and convex Nash equilibria.
- Stochastic variational inequalities arise when algorithms access operators through a stochastic oracle returning noisy estimates at queried points.The oracle receives a search point and returns a random vector estimate.
- Large-scale stochastic monotone variational inequalities have lower bounds limiting the accuracy attainable by iterative algorithms.The paper normalizes this setting using the unit Euclidean ball in R^n with large n.
- Existing methods include Robust Stochastic Approximation and deterministic extra-gradient methods, with rates depending on smoothness, boundedness, and noise parameters.
- The paper extends Mirror-Prox to stochastic monotone variational inequalities and targets the dimension-uniform optimal rate of convergence.It also studies geometry-dependent tuning and probability bounds for large deviations.
- The Stochastic Mirror-Prox framework is developed for convex Nash equilibria, saddle-point problems, convex minimization, and stochastic composite minimization.Applications include stochastic semidefinite feasibility and eigenvalue minimization.
2 Preliminaries and Problem of interest
The preliminaries formulate convex Nash, saddle-point, minimax, and composite optimization problems as monotone variational inequalities. Saddle-point reformulations preserve relevant solution measures while making smooth and stochastic first-order structure accessible.
- Nash v.i.’s and functional error: A convex Nash equilibrium is a profile where each player minimizes their loss given the other players’ choices.
- Nash v.i.’s and functional error: Convex Nash problems induce monotone operators whose variational-inequality solutions are exactly the Nash equilibria.The associated operator can be chosen bounded when the player loss functions are Lipschitz continuous.
- Nash v.i.’s and functional error: The Nash functional error measures the sum of players’ incentives to change their choices while others keep theirs fixed.
- Saddle Point v.i.: In the convex zero-sum case, Nash equilibria are saddle points of a function convex in one variable and concave in the other.The functional error is expressed through the worst-case primal-dual gap.
- Saddle Point v.i.: Saddle points correspond to the product of the primal and dual optimal sets, and the functional error sums the two non-optimalities.
- Composite Optimization problem and its saddle point reformulation: Saddle-point reformulation makes smooth component functions suitable for first-order algorithms and preserves unbiased stochastic-oracle access to the variational-inequality operator.This applies to minimax and composite minimization structures.
3 Stochastic Mirror-Prox algorithm
The paper defines SMP for monotone variational inequalities using stochastic approximations of the operator and a geometry-matched prox setup. Its results provide error and deviation bounds, including comparisons showing when SMP can outperform robust stochastic approximation.
- Algorithm setup: SMP extends Mirror-Prox to bounded monotone operators when exact operator evaluations are replaced by possibly random approximations.The method assumes access to approximate values through a stochastic oracle.
- Algorithm setup: The setup combines a norm, a distance-generating function, and a prox-mapping whose optimization problems should be easy to solve.The prox-function is the Bregman-type quantity V(z,u)=ω(u)−ω(z)−⟨ω′(z),u−z⟩.
- Geometric setups: Euclidean, simplex, and spectahedron geometries provide concrete SMP setups with corresponding prox-functions and mappings.The spectahedron setup uses matrix entropy and relates prox computation to singular value decomposition.
- Algorithm steps: The algorithm uses stochastic oracle calls, initializes at the minimizer of the distance-generating function, iterates with selected stepsizes, and outputs an averaged solution.The paper also states assumptions controlling oracle errors and perturbations.
- Performance guarantees: Under its assumptions, Theorem 1 and Corollary 1 give error and large-deviation bounds for SMP, with Nash variational inequalities allowing functional error measures.The bounds depend on the operator parameters, the geometry term Ω, and the perturbation or nonsmoothness scale M.
- Comparison and scope: Compared with robust stochastic approximation, SMP is never worse in the stated comparison and can be much better when the relevant smooth component is large but well observed.The paper identifies insensitivity to such smooth components as SMP’s most interesting feature, while noting the typical advantage may be limited when parameter scales are similar.
4 Application to Stochastic Composite minimization
The paper applies SMP to stochastic composite minimization and related semidefinite feasibility and eigenvalue problems, using stochastic-oracle assumptions and problem-specific mirror setups. The resulting estimates include near-costless handling of multiple matrix constraints, optimal Euclidean convergence rates, and sublinear data access in a matrix setting.
- Stochastic composite minimization: SMP is applied to composite minimization after reformulating the problem as a variational inequality with a stochastic oracle.The setup augments the composite problem with assumptions defining the stochastic oracle and SMP framework.
- Stochastic composite minimization: The composite-minimization efficiency estimates follow from the general SMP bounds after replacing σ and Ω with problem-specific quantities M and Ω.The construction equips the product space and feasible set with tailored norms and distance-generating functions.
- Stochastic Semidefinite Feasibility: For matrix inequalities, the spectahedron setup and matrix norms satisfy the required assumptions for applying SMP to semidefinite feasibility.The matrix formulation uses block-diagonal spectahedra and operator-specific parameters.
- Stochastic Semidefinite Feasibility: The expected accuracy for a system of m matrix inequalities is only logarithmically worse in p than for a single matrix inequality.The paper characterizes this as making the transition from one constraint to a system nearly costless in solution quality.
- Eigenvalue optimization via SMP: With fixed ν and δ, SMP significantly outperforms its deterministic counterpart when m ≥ n/p and n/p is large.The construction uses an artificial stochastic oracle for the deterministic problem.
- Eigenvalue optimization via SMP: With fixed δ and ν, SMP builds the required approximate solution while inspecting only a tiny fraction of the matrix data.Each step visits randomly chosen entries, yielding sublinear-time behavior under the stated dimensional regime.
5 Appendix
The appendix develops technical results supporting SMP’s convergence analysis, including prox-map properties, stochastic error bounds, and the passage from general variational-inequality error to Nash variational-inequality error.
- Prox-map properties: The prox mapping is single-valued and Lipschitz continuous, providing the stability property used by the mirror-prox updates.The appendix derives corresponding Bregman-distance inequalities for the updates.
- Stochastic error control: The stochastic analysis controls accumulated error through the quantity Γ(t), combining initial distance, oracle moments, approximation errors, and martingale terms.The resulting estimates are obtained by summing one-step inequalities and applying concentration arguments.
- Nash variational inequalities: For Nash variational inequalities, the general error Errvi can be replaced by the functional error ErrN.This replacement follows from the convexity and concavity structure of the Nash formulation.