Projection-Free Algorithms for Minimax Problems

Khanh-Hung Giang-Tran, Soroosh Shafiee, Nam Ho-Nguyen
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:34899-34960, 2026.

Abstract

This paper addresses constrained smooth saddle-point problems in settings where projection onto the feasible sets is computationally expensive. We bridge the gap between projection-based and projection-free optimization by introducing a unified dual dynamic smoothing framework that enables the design of efficient single-loop algorithms. Within this framework, we establish convergence results for nonconvex-concave and nonconvex-strongly concave settings. Furthermore, we show that this framework is naturally applicable to convex-concave problems, providing a unified analysis across varying payoff structures. We propose and analyze three algorithmic variants based on the application of a linear minimization oracle over the minimization variable, the maximization variable, or both. Notably, our analysis yields anytime convergence guarantees without requiring a pre-specified iteration horizon. These results significantly narrow the performance gap between projection-free and projection-based methods for minimax optimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-giang-tran26a, title = {Projection-Free Algorithms for Minimax Problems}, author = {Giang-Tran, Khanh-Hung and Shafiee, Soroosh and Ho-Nguyen, Nam}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {34899--34960}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/giang-tran26a/giang-tran26a.pdf}, url = {https://proceedings.mlr.press/v306/giang-tran26a.html}, abstract = {This paper addresses constrained smooth saddle-point problems in settings where projection onto the feasible sets is computationally expensive. We bridge the gap between projection-based and projection-free optimization by introducing a unified dual dynamic smoothing framework that enables the design of efficient single-loop algorithms. Within this framework, we establish convergence results for nonconvex-concave and nonconvex-strongly concave settings. Furthermore, we show that this framework is naturally applicable to convex-concave problems, providing a unified analysis across varying payoff structures. We propose and analyze three algorithmic variants based on the application of a linear minimization oracle over the minimization variable, the maximization variable, or both. Notably, our analysis yields anytime convergence guarantees without requiring a pre-specified iteration horizon. These results significantly narrow the performance gap between projection-free and projection-based methods for minimax optimization.} }
Endnote
%0 Conference Paper %T Projection-Free Algorithms for Minimax Problems %A Khanh-Hung Giang-Tran %A Soroosh Shafiee %A Nam Ho-Nguyen %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-giang-tran26a %I PMLR %P 34899--34960 %U https://proceedings.mlr.press/v306/giang-tran26a.html %V 306 %X This paper addresses constrained smooth saddle-point problems in settings where projection onto the feasible sets is computationally expensive. We bridge the gap between projection-based and projection-free optimization by introducing a unified dual dynamic smoothing framework that enables the design of efficient single-loop algorithms. Within this framework, we establish convergence results for nonconvex-concave and nonconvex-strongly concave settings. Furthermore, we show that this framework is naturally applicable to convex-concave problems, providing a unified analysis across varying payoff structures. We propose and analyze three algorithmic variants based on the application of a linear minimization oracle over the minimization variable, the maximization variable, or both. Notably, our analysis yields anytime convergence guarantees without requiring a pre-specified iteration horizon. These results significantly narrow the performance gap between projection-free and projection-based methods for minimax optimization.
APA
Giang-Tran, K., Shafiee, S. & Ho-Nguyen, N.. (2026). Projection-Free Algorithms for Minimax Problems. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:34899-34960 Available from https://proceedings.mlr.press/v306/giang-tran26a.html.

Related Material