Research map / Optimization / Nonconvex and smooth optimization
Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization
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 NSTORM, a nested STORM-style variance-reduced method for compositional minimax optimization achieving O(κ^3/ε^3) sample complexity without large batches, plus an Adam-adaptive variant ADA-NSTORM, evaluated on deep AUC maximization.
Problem
Stochastic optimization of nonconvex compositional minimax problems min_x max_y f(E[g(x;ξ)], y), where unbiased gradient estimates are unavailable and prior methods reach only O(κ^4/ε^4) complexity or need large batches.
Approach
Applies STORM-style recursive momentum variance reduction to both inner function values and Jacobians and to the outer gradients, with projection on the inner Jacobian estimator, achieving optimal sample complexity with two samples per iteration; ADA-NSTORM adds Adam-style adaptive preconditioning matrices.
Key results
- On CIFAR10 at 10% imbalance, ADA-NSTORM reaches 0.931 test AUC vs 0.926 for NSTORM, 0.926 for PDSCA and 0.818 for SCGDA.
- On STL10 at 10% imbalance, ADA-NSTORM achieves 0.833 AUC, the best among compared methods (PDSCA 0.824, NSTORM 0.827).
- NSTORM achieves sample complexity O(κ^3/ε^3) versus O(κ^4/ε^4) for SCGDA/PDSCA, with a constant batch size.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace SCGDA with ADA-NSTORM | Deep AUC optimization · CAT_vs_DOG, 10% imbalance | AUC: 0.857 -> 0.933 | Helped |
| Replace PDSCA with ADA-NSTORM | Deep AUC optimization · CIFAR10, 10% imbalance | AUC: 0.926 -> 0.931 | Helped |
| Replace PDSCA with ADA-NSTORM | Deep AUC optimization · CIFAR100, 10% imbalance | AUC: 0.708 -> 0.715 | Helped |
| Replace PDSCA with ADA-NSTORM | Deep AUC optimization · STL10, 10% imbalance | AUC: 0.824 -> 0.833 | Helped |
| Use NSTORM instead of SCGDA | Deep AUC optimization · CAT_vs_DOG, 10% imbalance | AUC: 0.857 -> 0.932 | Helped |
| Use NSTORM instead of SCGDA | Deep AUC optimization · CIFAR10, 10% imbalance | AUC: 0.818 -> 0.926 | Helped |
| Use NSTORM instead of SCGDA | Deep AUC optimization · CIFAR100, 10% imbalance | AUC: 0.673 -> 0.709 | Helped |
| Use NSTORM instead of SCGDA | Deep AUC optimization · STL10, 10% imbalance | AUC: 0.779 -> 0.827 | Helped |
| Vary parameter m (ablation) | NSTORM · CIFAR100, 10% imbalance | AUC | No clear effect |
| Set gamma to approximately 0.5 (ablation) | NSTORM · CIFAR100, 10% imbalance | AUC: 0.827 | Helped |
| Increase the upper bound for a_t and b_t from 50 to 1000 (ablation) | ADA-NSTORM · CIFAR100, 10% imbalance | AUC | No clear effect |
| Vary tau from 0.1 to 0.9 (ablation) | ADA-NSTORM · Deep AUC problem | AUC: 0.127 | No clear effect |
Surprising findings
- On the 1% imbalance CAT_vs_DOG and CIFAR100 settings, the baselines PDSCA and SCGDA outperform the proposed methods on some entries (e.g., PDSCA 0.792 vs 0.786 on CAT_vs_DOG), which the authors attribute to proximity to training distribution.
- Varying the Adam tau hyperparameter from 0.1 to 0.9 changes ADA-NSTORM AUC by only 0.127 in the reported ablation, suggesting sensitivity is noticeable but not drastic.
Limitations
- NSTORM requires small step sizes (gamma<1 and small learning rates), limiting practical use; ADA-NSTORM addresses this heuristically.
- Experiments are limited to deep AUC on image classification with ResNet20; risk-averse portfolio and RL policy evaluation are deferred to supplementary.
- Theoretical guarantees rely on bounded gradient and variance assumptions and, for ADA-NSTORM, on an additional bounded adaptive-matrix assumption.
Experimental setup
Datasets: CAT_vs_DOG CIFAR10 CIFAR100 STL10
Benchmarks: CAT_vs_DOG CIFAR10 CIFAR100 STL10
Metrics: test AUC
Baselines: SCGDA PDSCA
Builds on: STORM SCGDA PDSCA Adam
Closest papers by meaning
- Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions (NeurIPS 2024 · similarity 0.88)
- Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms (ICML 2024 · similarity 0.88)
- Gradient-Free Methods for Nonconvex Nonsmooth Stochastic Compositional Optimization (NeurIPS 2024 · similarity 0.87)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.86)
- Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization (NeurIPS 2025 · similarity 0.86)
- A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · 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.