# Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization

arXiv: https://arxiv.org/abs/2308.09604 · HTML: https://mlsanity.com/paper/2308.09604/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 52 references that are in the map.
- First posted on arXiv 18 Aug 2023.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Improved Training of Wasserstein GANs](https://mlsanity.com/paper/1704.00028/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [Generalized Federated Learning via Sharpness Aware Minimization](https://mlsanity.com/paper/2206.02618/) (2022)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Adversarial Attack Generation Empowered by Min-Max Optimization](https://mlsanity.com/paper/1906.03563/) (2019)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Optimal Algorithms for Convex Nested Stochastic Composite Optimization](https://mlsanity.com/paper/2011.10076/) (2020)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds](https://mlsanity.com/paper/2010.06097/) (2020)
- [AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization](https://mlsanity.com/paper/2106.16101/) (2021)
- [Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence](https://mlsanity.com/paper/2006.09361/) (2020)
- [Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization](https://mlsanity.com/paper/1912.13515/) (2019)
- [Stochastic Recursive Momentum Method for Non-Convex Compositional Optimization](https://mlsanity.com/paper/2006.01688/) (2020)

## Built on by (most cited first, 2 of 2)

- [Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to K-Level Stochastic Optimizations](https://mlsanity.com/paper/2407.05286/) (2024)
- [Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees](https://mlsanity.com/paper/2408.12505/) (2024)

## Abstract (arXiv)

This paper delves into the realm of stochastic optimization for compositional minimax optimization - a pivotal challenge across various machine learning domains, including deep AUC and reinforcement learning policy evaluation. Despite its significance, the problem of compositional minimax optimization is still under-explored. Adding to the complexity, current methods of compositional minimax optimization are plagued by sub-optimal complexities or heavy reliance on sizable batch sizes. To respond to these constraints, this paper introduces a novel method, called Nested STOchastic Recursive Momentum (NSTORM), which can achieve the optimal sample complexity of O(kappa3 /ε3 ) to obtain the ε-accuracy solution. We also demonstrate that NSTORM can achieve the same sample complexity under the Polyak-L ojasiewicz (PL)-condition - an insightful extension of its capabilities. Yet, NSTORM encounters an issue with its requirement for low learning rates, potentially constraining its real-world applicability in machine learning. To overcome this hurdle, we present ADAptive NSTORM (ADA-NSTORM) with adaptive learning rates. We demonstrate that ADA-NSTORM can achieve the same sample complexity but the experimental results show its more effectiveness. All the proposed complexities indicate that our proposed methods can match lower bounds to existing minimax optimizations, without requiring a large batch size in each iteration. Extensive experiments support the efficiency of our proposed methods.