Projection-Free Algorithms for Minimax Problems

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.

Source: arXiv:2603.29870v1 - http://arxiv.org/abs/2603.29870v1 PDF: https://arxiv.org/pdf/2603.29870v1 Original Link: http://arxiv.org/abs/2603.29870v1