Faster Projection-Free Algorithms for Minimax Problems over Polytopes

Projection-free methods are attractive for constrained minimax problems when linear minimization oracles (LMOs) are substantially cheaper than projection. However, existing fully projection-free methods can suffer from much worse iteration complexities than their projection-based counterparts. We develop a fully projection-free method for polytope-constrained minimax problems, which exploits polyhedral geometry through away-step Frank–Wolfe updates, requiring only one LMO call over each feasible set per iteration. For nonconvex–concave problems, our method finds an $ϵ$-stationary point in $\mathcal{O}({ϵ}^{-3})$ iterations, improving the previous projection-free bound of $\mathcal{O}({ϵ}^{-6})$. Under a one-sided Kurdyka–ojasiewicz condition with exponent $\theta \in (0,1)$, imposed on either the primal or dual problem, we obtain an $\mathcal{O}\left({ϵ}^{-\max \{2,4\theta \}}\right)$ complexity. To the best of our knowledge, these are the first fully projection-free complexity guarantees for the corresponding nonconvex–nonconcave problems. We further obtain an $\mathcal{O}({ϵ}^{-3})$ complexity for convex–nonconcave problems. For convex–concave problems, we improve the best-known projection-free complexity from $\mathcal{O}({ϵ}^{-5})$ to $\mathcal{O}({ϵ}^{-2})$. Our numerical results further demonstrate the practical effectiveness of the proposed method.