- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper develops a fully projection-free algorithm for smooth minimax problems over polytopes. The method combines a doubly smoothed formulation with a quadratic dual perturbation and performs away-step Frank–Wolfe updates over the product polytope, requiring only one LMO call per feasible set per iteration. For nonconvex–concave problems, it finds an -Frank–Wolfe stationary point in iterations, improving the previous bound; for convex–concave problems, it achieves , improving . Under a one-sided KŁ condition, it obtains complexity — the first fully projection-free guarantees in this regime — along with for convex–nonconcave problems. Key technical ingredients include proximal error bounds for the primal–dual coupling term and an active-set counting argument for clipped away steps. Experiments on graphical matching and robust budget allocation support the theory.
Critical strengths
- The results are surprising and represent substantial improvements over prior work: the NC–C complexity improves from to and the C–C complexity from to , while using the stronger two-sided FW-stationarity certificate (Proposition 2.4 shows it implies the criteria used in prior work). The NC–KŁ and KŁ–NC guarantees are, to my knowledge, new for fully projection-free methods and match the best-known projection-based rates.
- The motivation is clear and well-articulated. The paper identifies a concrete gap — existing fully projection-free minimax methods are much slower than projection-based counterparts — and poses a natural question of whether polyhedral geometry can close this gap, drawing a well-grounded analogy to the role of away steps in convex minimization (Lacoste-Julien & Jaggi, 2015).
Critical weaknesses
- The setting is restricted to polytope constraints ($\mathcal{X} = \mathrm{conv}(A)$, with finite atom sets), which is somewhat narrow compared to prior work such as Giang-Tran et al. (2026), which covers general compact convex sets. Moreover, the constants depend on the pyramidal widths , , which can be very small in high dimensions (e.g., for the cube), so the practical constants in the rate may be large even when the order in is improved.
Questions for authors
- Is there an intuitive explanation for why the geometry of the polytope speeds up minimax optimization? In convex minimization, away steps are understood to eliminate zig-zagging near optimal faces and yield linear rates via the pyramidal-width error bound. In the minimax setting, the improvement here seems to come from several interacting ingredients (double smoothing, dual perturbation, away steps, the active-set counting). Could the authors clarify which mechanism is primarily responsible for the jump from to , e.g., via an ablation (vanilla FW steps within the same doubly smoothed framework) or a discussion of where the analysis would break without away steps?
- Can the proposed framework be used beyond the polytope setting, e.g., for general convex constrained optimization over polytopes or over general compact convex sets? In particular, since the analysis relies on the pyramidal-width error bound (Lemma C.2), which is specific to finite atom sets, is there a path to extending the improved rates to general compact convex sets (perhaps with strongly convex sets as an intermediate case), or is the polyhedral structure essential?
Authors response:
Polytope Constraints and Pyramidal-Width Dependence.
We thank the reviewer for highlighting these important limitations. We agree that the restriction to polytopes limits the generality of our results, and that small pyramidal widths may lead to large constants in high dimensions. Our improved rates concern the dependence on ϵ for fixed polytopes and do not imply dimension-independent complexity guarantees. Nevertheless, we believe that polytope constrained minimax optimization remains an important setting, particularly for structured combinatorial problems where linear minimization can be substantially cheaper than Euclidean projection. There are many examples of polytopes where such computational advantages arise, including the matching polytope we consider in our experiments. Combettes and Pokutta (2021) consider the complexity differences between computing the projection and LMO of further examples such as flow polytopes.
We appreciate the reviewer's observation and will clarify the dependence on pyramidal widths in the revised manuscript. We will also highlight extending the results beyond polytopes and reducing the geometric dependence as interesting directions for future work.
Q1: Intuition for geometric acceleration.
We thank the reviewer for this insightful question. Intuitively, away steps play a similar role as in convex minimization: they reduce or remove weights on unfavorable active atoms, mitigating zig-zagging near optimal faces. Together with the pyramidal-width inequality, this provides linear gap-to-distance error bounds for the regularized primal and dual subproblems (Lemma D.3), as opposed to the square-root bounds generally available with vanilla FW.
The key difference in minimax optimization is how these geometric bounds translate into convergence rates. The primal and dual updates are coupled, and the linear error bounds allow us to absorb the primal–dual coupling term into the Lyapunov descent estimate (Appendix F, Eq. (8)). Without away steps, this argument no longer closes.
As detailed in our Common Response, the improvement from O(ϵ−6) to O(ϵ−3) results from the complementary roles of smoothing, dual perturbation, and away steps. We also provide a theoretical comparison of the reduced variants to further clarify their respective contributions.
Q2: Extension Beyond Polytope Constraints.
We thank the reviewer for this interesting question. As discussed in our Common Response, we distinguish between the applicability of our regularization techniques and the geometric requirements for the improved convergence rates.
First, our framework covers both smooth convex and nonconvex minimization over polytopes as special cases of C–C and NC–C minimax optimization, respectively. Indeed, taking f(x,y)=h(x) independent of y gives GY=0. Consequently, our results yield O(ϵ−2) and O(ϵ−3) FW-stationarity complexities for convex and nonconvex minimization, respectively.
For general compact convex sets, neither smoothing nor dual perturbation inherently requires polyhedral geometry. In particular, the perturbation-only LMO–LMO framework of Giang-Tran et al. (2026) achieves O(ϵ−6) and O(ϵ−5) complexities for NC–C and C–C problems, respectively, under their convergence criteria. When the dual feasible set is strongly convex, these rates improve to O(ϵ−5) and O(ϵ−4), respectively, illustrating that geometric structures beyond polytopes can also improve projection-free convergence rates.
Thus, polyhedral geometry is not necessary for establishing fully projection-free convergence over general compact convex sets. However, our sharper O(ϵ−3) and O(ϵ−2) rates rely on the pyramidal-width error bound (Lemma C.2), which is specific to polytopes. Whether comparable rates can be achieved over more general compact convex sets, potentially through alternative geometric error bounds, remains an interesting direction for future work.