Research map / Optimization / Nonconvex and smooth optimization
Variance-Reduced Forward-Reflected-Backward Splitting Methods for Nonmonotone Generalized Equations
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 two unbiased variance-reduced estimators (loopless-SVRG and SAGA) for the forward-reflected quantity Gx^k - γGx^{k-1} and plugs them into forward-reflected-type splitting methods for nonmonotone finite-sum generalized equations, achieving O(n + n^{2/3} ε^{-2}) oracle complexity under weak-Minty assumption.
Problem
Solving nonmonotone finite-sum generalized equations (inclusions 0 ∈ Gx + Tx with G an average of n operators) under weak-Minty solution conditions, where standard gap-function certification is not applicable.
Approach
Instead of variance-reducing G directly, the method variance-reduces the intermediate forward-reflected quantity S^k = Gx^k − γGx^{k−1} (γ in (1/2,1)) via a class of unbiased estimators, instantiated with loopless-SVRG and SAGA, and embeds it in forward-reflected-backward splitting updates.
Key results
- Both loopless-SVRG and SAGA variants achieve O(n + n^{2/3} ε^{-2}) oracle complexity for the operator residual norm, matching best-known SVRG complexity in nonconvex optimization.
- In the unconstrained synthetic minimax experiments, LVFR-svrg performed best and clearly outperformed OG, VFRBS, and VEG over epochs.
- In the constrained minimax and logistic regression experiments, the proposed SVRG/SAGA variants outperform the competitors VFRBS, OG, and VEG in most settings (VEG is comparable to VFR-saga in the constrained case).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LVFR-SVRG instead of the compared methods | Unconstrained synthetic nonconvex-nonconcave minimax · (p, n) = (100, 5000) and (200, 10000) | relative residual norm | Helped |
| Use VFR-SVRG instead of the compared methods | Constrained synthetic nonconvex-nonconcave minimax · (p, n) = (100, 5000) and (200, 10000) | relative FBS residual norm | Helped |
| Use VFR-SAGA instead of the compared methods | Constrained synthetic nonconvex-nonconcave minimax · (p, n) = (100, 5000) and (200, 10000) | relative FBS residual norm | Mixed |
| Use VFR-SVRG, LVFR-SVRG, or VFR-SAGA instead of the competitors | Logistic regression with ambiguous features · a9a and w8a | relative FBS residual norm | Helped |
| Use VFRBS instead of OG or VEG | Logistic regression with ambiguous features · a9a and w8a | relative FBS residual norm | Helped |
Surprising findings
- The deterministic optimistic gradient method (OG) is outperformed by VFRBS and VEG in some tests but beats VFRBS and VEG in the unconstrained synthetic case.
- Unbiased estimators are used because biased estimators such as SARAH or Hybrid-SGD are hard to analyze without an objective function.
Limitations
- The SAGA estimator requires storing a table of n component evaluations, which is memory-intensive for large n and p.
- The constant in the complexity bound (Γ = 731 / 2816) is large and not optimized.
- Assumes weak-Minty with κ satisfying L κ ≤ δ = O(sqrt(ρ)), restricting the nonmonotonicity allowed.
Experimental setup
Datasets: a9a w8a synthetic nonconvex-nonconcave minimax data
Benchmarks: synthetic nonconvex-nonconcave minimax logistic regression with ambiguous features on a9a and w8a
Metrics: relative residual norm ||Gx^k||/||Gx^0|| relative FBS residual norm vs epochs
Baselines: OG (optimistic gradient) VFRBS VEG (variance-reduced extragradient)
Builds on: forward-reflected-backward splitting SVRG SAGA EG+ (weak-Minty extragradient)
Closest papers by meaning
- Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function (NeurIPS 2020 · similarity 0.87)
- Stochastic Variance Reduction for Nonconvex Optimization (ICML 2016 · similarity 0.87)
- Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs (ICML 2018 · similarity 0.87)
- Stochastic Nested Variance Reduction for Nonconvex Optimization (NeurIPS 2018 · similarity 0.86)
- Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient (ICML 2024 · similarity 0.85)
- Stochastic Optimization with Random Search (NeurIPS 2026 · 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.