Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees

Yuyang Deng, Fuli Qiao, Mehrdad Mahdavi
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:3835-3843, 2025.

Abstract

Stochastic compositional minimax problems are prevalent in machine learning, yet there exist only limited established findings on the convergence of this class of problems. In this paper, we propose a formal definition of the stochastic compositional minimax problem, which involves optimizing a minimax loss with a compositional structure either in primal, dual, or both primal and dual variables. We introduce a simple yet effective algorithm, stochastically Corrected stOchastic gradient Descent Ascent (CODA), which is a primal-dual type algorithm with compositional correction steps, and establish its convergence rate in the aforementioned three settings. We also propose a variance reduced variant, CODA+, which achieves the best-known rate on nonconvex-strongly-concave and nonconvex-concave compositional minimax problems. This work initiates the theoretical study of the stochastic compositional minimax problem in various settings and may inform modern machine learning scenarios such as domain adaptation or robust model-agnostic meta-learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-deng25a, title = {Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees}, author = {Deng, Yuyang and Qiao, Fuli and Mahdavi, Mehrdad}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {3835--3843}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/deng25a/deng25a.pdf}, url = {https://proceedings.mlr.press/v258/deng25a.html}, abstract = {Stochastic compositional minimax problems are prevalent in machine learning, yet there exist only limited established findings on the convergence of this class of problems. In this paper, we propose a formal definition of the stochastic compositional minimax problem, which involves optimizing a minimax loss with a compositional structure either in primal, dual, or both primal and dual variables. We introduce a simple yet effective algorithm, stochastically Corrected stOchastic gradient Descent Ascent (CODA), which is a primal-dual type algorithm with compositional correction steps, and establish its convergence rate in the aforementioned three settings. We also propose a variance reduced variant, CODA+, which achieves the best-known rate on nonconvex-strongly-concave and nonconvex-concave compositional minimax problems. This work initiates the theoretical study of the stochastic compositional minimax problem in various settings and may inform modern machine learning scenarios such as domain adaptation or robust model-agnostic meta-learning.} }
Endnote
%0 Conference Paper %T Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees %A Yuyang Deng %A Fuli Qiao %A Mehrdad Mahdavi %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-deng25a %I PMLR %P 3835--3843 %U https://proceedings.mlr.press/v258/deng25a.html %V 258 %X Stochastic compositional minimax problems are prevalent in machine learning, yet there exist only limited established findings on the convergence of this class of problems. In this paper, we propose a formal definition of the stochastic compositional minimax problem, which involves optimizing a minimax loss with a compositional structure either in primal, dual, or both primal and dual variables. We introduce a simple yet effective algorithm, stochastically Corrected stOchastic gradient Descent Ascent (CODA), which is a primal-dual type algorithm with compositional correction steps, and establish its convergence rate in the aforementioned three settings. We also propose a variance reduced variant, CODA+, which achieves the best-known rate on nonconvex-strongly-concave and nonconvex-concave compositional minimax problems. This work initiates the theoretical study of the stochastic compositional minimax problem in various settings and may inform modern machine learning scenarios such as domain adaptation or robust model-agnostic meta-learning.
APA
Deng, Y., Qiao, F. & Mahdavi, M.. (2025). Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:3835-3843 Available from https://proceedings.mlr.press/v258/deng25a.html.

Related Material