Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization
DOI:
https://doi.org/10.1609/aaai.v38i12.29300Keywords:
ML: Optimization, SO: Non-convex OptimizationAbstract
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 and obtain the nearly accuracy solution, matching the existing minimax methods. We also demonstrate that NSTORM can achieve the same sample complexity under the Polyak-Lojasiewicz (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.Downloads
Published
2024-03-24
How to Cite
Liu, J., Pan, X., Duan, J., Li, H.-D., Li, Y., & Qu, Z. (2024). Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12), 13927-13935. https://doi.org/10.1609/aaai.v38i12.29300
Issue
Section
AAAI Technical Track on Machine Learning III