Research map / Optimization / Nonconvex and smooth optimization
Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
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.
Studies second-order methods for variational inequalities with inexact Jacobians, proving a matching lower bound, an optimal method VIJI, Quasi-Newton Jacobian approximations, and a tensor extension.
Problem
Second-order methods for variational inequalities (VIs) need exact Jacobians and expensive auxiliary subproblems; the explicit effect of Jacobian inexactness on global convergence rates was unclear.
Approach
Uses an inexact Taylor model built from a delta-inexact Jacobian inside a dual-extrapolation (Perseus-style) method with an extra adaptive step-size term, giving rate O(L1 D^3/T^{3/2} + delta D^2/T); proves a matching lower bound and plugs in Quasi-Newton (L-Broyden, damped L-Broyden) Jacobian approximations to cheapen the subproblem.
Key results
- VIJI achieves O(L1 D^3/T^{3/2} + delta D^2/T) gap rate for monotone VIs and matches exact optimal second-order rates when delta <= L1 D/sqrt(T)
- Lower bound Omega(delta D^2/T + L1 D^3/T^{3/2}) for first-order methods with delta-inexact Jacobians is established
- On the cubic-regularized bilinear min-max experiment, VIQA with damped Broyden is significantly faster than EG, Perseus1 and classical Broyden VIQA
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Jacobian information in Perseus (Perseus2 instead of Perseus1) | Perseus · Cubic regularized bilinear min-max, d = 50, ρ = 1e − 3 | Gap | Helped |
| use VIQA with Damped Broyden instead of EG, Perseus1, or VIQA Broyden | VIQA · Cubic regularized bilinear min-max, d = 50, ρ = 1e − 3 | Gap | Helped |
| use Damped L-Broyden instead of classical L-Broyden for the Jacobian approximation | VIJI · Cubic regularized bilinear min-max, d = 50, ρ = 1e − 3 | Gap | Helped |
Limitations
- Experiments limited to one synthetic cubic-regularized bilinear min-max problem
- Lower bound applies only to methods satisfying the dual-extrapolation structure (Assumption 4.1), not extragradient-type methods
- Subproblem solution assumed approximately solvable; nonmonotone subproblems are hard to solve
Experimental setup
Benchmarks: cubic regularized bilinear min-max problem (d=50)
Metrics: gap function value vs iterations gap vs JVP/F(x) computations
Baselines: Extragradient Perseus1 (first-order) Perseus2 (exact second-order) VIQA Broyden
Builds on: Perseus Extragradient Inexact-Newton-MinMax
Closest papers by meaning
- Advancing the Lower Bounds: an Accelerated, Stochastic, Second-order Method with Optimal Adaptation to Inexactness (ICLR 2024 · similarity 0.90)
- Generalized Smooth Variational Inequalities: Methods with Adaptive Stepsizes (ICML 2024 · similarity 0.88)
- A Primal-Dual Approach to Solving Variational Inequalities with General Constraints (ICLR 2024 · similarity 0.88)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.87)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.86)
- Generalized Smooth Stochastic Variational Inequalities: Almost Sure Convergence and Convergence Rates (NeurIPS 2026 · similarity 0.86)
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.