Research map / Optimization / Nonconvex and smooth optimization
Solving hidden monotone variational inequalities with surrogate losses
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a surrogate-loss framework (alpha-descent on squared-error surrogates) for solving hidden monotone variational inequalities with any deep-learning optimizer, with linear convergence guarantees, a Gauss-Newton unification of preconditioning methods, and a surrogate-based TD(0) variant.
Problem
Solving variational inequalities (min-max optimization, projected Bellman error minimization) with hidden monotone structure in deep models, where naive gradient-based methods from supervised learning diverge or cycle.
Approach
Reduce each VI step to approximately minimizing a sequence of squared-error surrogate losses in parameter space, with a new alpha-descent condition that lets any black-box optimizer (e.g., ADAM) be used as the inner loop without assuming summable or globally bounded errors; PHGD is shown to be one Gauss-Newton step on the surrogate.
Key results
- Theorem gives linear convergence of z_t to z* for alpha < mu/(2L) and eta = 2mu/(5L^2), with rate 1 - mu^2/(5L^2).
- Surrogate-based methods with a fixed batch and inner loop of about 50 steps outperform TD(0) in data efficiency and wall-clock time on Ant and HalfCheetah, and reach lower value prediction error.
- Proposition shows alpha < 1 can still diverge in a strongly monotone bilinear VI, so small alpha is necessary.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use surrogate methods instead of TD(0) | Nonlinear policy evaluation · Ant and HalfCheetah | value prediction error | Helped |
| Increase the inner-loop steps for Surr-GD (ablation) | Surr-GD · Hidden Matching Pennies | convergence to equilibrium | Helped |
| Increase the inner-loop steps for Surr-GD (ablation) | Surr-GD · Hidden Matching Pennies | convergence to equilibrium | Mixed |
| Increase the inner-loop steps for Surr-GD (ablation) | Surr-GD · Hidden rock-paper-scissors | stability and performance | Helped |
| Use too many inner steps (ablation) | LM · Hidden rock-paper-scissors | convergence performance | Hurt |
| Use too many inner steps (ablation) | Surr-GD · Hidden rock-paper-scissors | convergence performance | Hurt |
| Increase the inner-loop size (ablation) | Surrogate methods · Nonlinear policy evaluation | data efficiency | Helped |
| Increase the inner-loop size (ablation) | Surrogate methods · Nonlinear policy evaluation | wall-clock convergence | Hurt |
| Use an inner-loop count of 50 (ablation) | Surrogate methods · Nonlinear policy evaluation | data efficiency and wall-clock time | Mixed |
| Resample a new batch for the squared-error term at each gradient step (ablation) | Surrogate with double sampling · Nonlinear policy evaluation | gradient bias | Helped |
| Resample a new batch for the squared-error term at each gradient step (ablation) | Surrogate with double sampling · Nonlinear policy evaluation | gradient variance | Hurt |
| Use a larger surrogate stepsize (ablation) | PHGD · Hidden Matching Pennies | convergence | Hurt |
Surprising findings
- Alpha < 1 descent on the surrogate is not sufficient for convergence in VIs, unlike in non-convex scalar minimization.
- More inner-loop compute on the surrogate does not necessarily give faster outer-loop convergence in the min-max experiments.
Limitations
- Convergence guarantees require Z convex and strong monotonicity/Lipschitz assumptions; stochastic case requires Z = R^n.
- Assumption of lower-bounded singular values of Dg^T is strong and is shown to force Z unbounded.
Experimental setup
Datasets: Ant (MuJoCo) HalfCheetah (MuJoCo) slow-mixing 100-state Markov chain
Benchmarks: hidden matching pennies hidden rock-paper-scissors Ant value prediction HalfCheetah value prediction
Metrics: distance to equilibrium value prediction error wallclock time
Baselines: PHGD gradient descent-ascent (GDA) TD(0) least-squares policy evaluation
Builds on: preconditioned hidden gradient descent (PHGD) surrogate losses for policy optimization Gauss-Newton method TD(0)
Closest papers by meaning
- A Fast Optimistic Method for Monotone Variational Inequalities (ICML 2023 · similarity 0.88)
- On the convergence of single-call stochastic extra-gradient methods (NeurIPS 2019 · similarity 0.87)
- Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions (NeurIPS 2023 · similarity 0.87)
- Characterizing the Edge of Stability in Variational Training Without Priors (NeurIPS 2026 · similarity 0.87)
- Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (NeurIPS 2020 · similarity 0.86)
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.