acceptodds
Under review as a conference paper at ICLR 2027

Faster Projection-Free Algorithms for Minimax Problems over Polytopes

Abstract

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 iterations, improving the previous projection-free bound of . Under a one-sided Kurdyka–ojasiewicz condition with exponent , imposed on either the primal or dual problem, we obtain an 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 complexity for convex–nonconcave problems. For convex–concave problems, we improve the best-known projection-free complexity from to . Our numerical results further demonstrate the practical effectiveness of the proposed method.

Primary area:
optimization
Keywords:
Minimax optimization, Projection-free optimization, Frank-Wolfe variants

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_cPZWOpenReview ↗
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 ϵ\epsilon-Frank–Wolfe stationary point in O(ϵ−3)O(\epsilon^{-3}) iterations, improving the previous O(ϵ−6)O(\epsilon^{-6}) bound; for convex–concave problems, it achieves O(ϵ−2)O(\epsilon^{-2}), improving O(ϵ−5)O(\epsilon^{-5}). Under a one-sided KŁ condition, it obtains O(ϵ−max⁡{2,4θ})O(\epsilon^{-\max\{2,4\theta\}}) complexity — the first fully projection-free guarantees in this regime — along with O(ϵ−3)O(\epsilon^{-3}) 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 O(ϵ−6)O(\epsilon^{-6}) to O(ϵ−3)O(\epsilon^{-3}) and the C–C complexity from O(ϵ−5)O(\epsilon^{-5}) to O(ϵ−2)O(\epsilon^{-2}), 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)$, Y=conv(B)\mathcal{Y} = \mathrm{conv}(B) 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 PWidth(A)\mathrm{PWidth}(A), PWidth(B)\mathrm{PWidth}(B), which can be very small in high dimensions (e.g., 1/d1/\sqrt{d} for the cube), so the practical constants in the rate may be large even when the order in ϵ\epsilon is improved.
Questions for authors
  1. 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 O(ϵ−6)O(\epsilon^{-6}) to O(ϵ−3)O(\epsilon^{-3}), 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?
  2. 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?
1 comment

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 ϵ\epsilon 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)O(\epsilon^{-6}) to O(ϵ−3)O(\epsilon^{-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)f(x,y)=h(x) independent of yy gives GY=0\mathcal G_{\mathcal Y}=0. Consequently, our results yield O(ϵ−2)\mathcal{O}(\epsilon^{-2}) and O(ϵ−3)\mathcal{O}(\epsilon^{-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)\mathcal{O}(\epsilon^{-6}) and O(ϵ−5)\mathcal{O}(\epsilon^{-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)\mathcal{O}(\epsilon^{-5}) and O(ϵ−4)\mathcal{O}(\epsilon^{-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)\mathcal{O}(\epsilon^{-3}) and O(ϵ−2)\mathcal{O}(\epsilon^{-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.

Reviewer_EabbOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies constrained min max problem, where the constraint sets are considered as polytopes. The work uses smoothed objective function with respect to both primal and dual subproblems. Then away step and Frank-Wolfe updates (that requires LMO oracle calls) are performed with respect to both min and max variables. The LMO oracle call makes the process projection-free.

Critical strengths

The paper is well written. Convergence rate improvements under different settings are studied.

Critical weaknesses
  1. The stated KL property in Assumption 2.2(ii) needs more discussion. That expression somehow relates to the gap formulation and the assumption is stronger than the local KL assumption. Can the paper present nonconcave examples that satisfies Assumption 2.2(ii)?

  2. Also please compare with the paper "Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization" by Niao He and Zaid Harchaoui (Proposition 3.2) for the Convex-Convex rates. Please illustrate what's new in the current manuscript as similar rate exists for C-C case.

Questions for authors

Please address my weakness section.

2 comments
AuthorsOpenReview ↗

Authors response

  • KŁ Examples.

    We agree that Assumption 2.2(ii) imposes a uniform global KŁ condition, which is stronger than the standard local KŁ property. This assumption is used to establish the uniform proximal error bound in Proposition 4.2(ii), which is crucial for our convergence analysis.

    Recent projection-based methods have studied nonconvex–nonconcave minimax problems under local KŁ conditions (Lu and Wang, 2025). However, their analysis relies on additional localization arguments that do not directly extend to our single-loop projection-free framework. Relaxing our assumption to a local KŁ condition is an interesting future direction.

    Nonconcave examples. The assumption accommodates genuinely nonconcave dual objectives, as illustrated by the following examples.

    Example 1 (Global PL; Yang et al., 2020). Consider the nonconvex–nonconcave function

    f(x,y)=x2+3sin⁡2xsin⁡2y−4y2−10sin⁡2y,f(x,y)=x^2+3\sin^2x\sin^2y-4y^2-10\sin^2y,

    which was shown by Yang et al. (2020, Example 1) to satisfy a global two-sided PL condition. On X=Y=[−2,2]\mathcal X=\mathcal Y=[-2,2], its inner maximizer is y∗(x)=0y^*(x)=0, and direct calculation gives

    max⁡y′∈Yf(x,y′)−f(x,y)≤14y2,\max_{y'\in\mathcal Y}f(x,y')-f(x,y)\le 14y^2,

    dist⁡(0,−∇yf(x,y)+NY(y))=∣∇yf(x,y)∣≥∣y∣.\operatorname{dist}(0,-\nabla_y f(x,y)+N_{\mathcal Y}(y))=|\nabla_y f(x,y)|\ge |y|.

    Thus, Assumption 2.2(ii) holds uniformly with θ=1/2\theta=1/2 and τy=1/14\tau_y=1/\sqrt{14}. Moreover, ∂yyf(0,π/2)=12>0\partial_{yy}f(0,\pi/2)=12>0, confirming that the dual objective is nonconcave.

    Example 2 (Higher KŁ exponents). We further construct a family of smooth nonconcave objectives on X=Y=[−1,1]\mathcal X=\mathcal Y=[-1,1]:

    fk(x,y)=−x2−12kq(y−x/10)2k,q(s)=s−s36,k∈{1,2}.f_k(x,y)=-x^2-\frac{1}{2k}q(y-x/10)^{2k},\qquad q(s)=s-\frac{s^3}{6},\quad k\in\{1,2\}.

    Writing s=y−x/10s=y-x/10, we have ∣s∣≤11/10|s|\le 11/10, q′(s)≥79/200q'(s)\ge79/200, and y∗(x)=x/10y^*(x)=x/10. Consequently,

    [max⁡y′∈Yfk(x,y′)−fk(x,y)]θk≤20079(2k)θkdist⁡(0,−∇yfk(x,y)+NY(y)),\left[\max_{y'\in\mathcal Y}f_k(x,y')-f_k(x,y)\right]^{\theta_k}\le\frac{200}{79(2k)^{\theta_k}}\operatorname{dist}(0,-\nabla_y f_k(x,y)+N_{\mathcal Y}(y)),

    where θk=(2k−1)/(2k)\theta_k=(2k-1)/(2k). Hence, Assumption 2.2(ii) holds uniformly with θ1=1/2\theta_1=1/2 and θ2=3/4\theta_2=3/4. Both objectives are nonconcave in yy, since ∂yyf1(0,1)=7/12>0\partial_{yy}f_1(0,1)=7/12>0 and ∂yyf2(0,1)=25/432>0\partial_{yy}f_2(0,1)=25/432>0. These examples cover both KŁ exponent regimes considered in Theorem 3.1.

  • He–Harchaoui.

    Thank you for pointing out this relevant work; we were not aware of it previously. Indeed, He and Harchaoui (2015, Proposition 3.2) establish an O(ϵ−2)\mathcal{O}(\epsilon^{-2}) LMO complexity for structured monotone variational inequalities. Their framework includes our convex–concave setting and allows general compact convex feasible sets.

    Our C–C result achieves the same O(ϵ−2)\mathcal{O}(\epsilon^{-2}) oracle complexity under the assumption of polytope constraints, but differs in two respects:

    • The algorithm structure is different in that the fully projection-free variant of He and Harchaoui's algorithm is a double-loop algorithm, which uses inner Frank–Wolfe iterations to approximately solve the prox subproblems. In contrast, our algorithm is single-loop, requiring only one LMO call over each feasible set per iteration.

    • The convergence guarantees concern different optimality criteria. He and Harchaoui establish an O(ϵ−2)\mathcal{O}(\epsilon^{-2}) LMO complexity for the variational-inequality dual gap at an averaged iterate (Theorem 3.1 and Proposition 3.2). Although not explicitly stated by the authors, their analysis also implies the same complexity for the saddle-point gap. Our convergence guarantee differs in that we establish two-sided Frank–Wolfe stationarity at a non-averaged iterate. In the C–C setting, this is a stronger criterion, since an ϵ\epsilon-FWSP is also a 2ϵ2\epsilon-SP (see Proposition 2.4 of our manuscript), whereas a small saddle-point gap does not, in general, imply comparably small FW gaps.

    We have now revised the manuscript to include a discussion on He and Harchaoui's work in the introduction as well as an explanation of how their analysis yields guarantees in terms of the saddle-point gap in Appendix B. A comparison of their complexity results is also included in Table 1. Our convex–concave graphical games experiments now also include their algorithm as a comparison. To provide a fair comparison, the graphical games plots report the FW gap versus the total number of LMO calls, rather than the number of outer iterations.

    We would like to emphasize that the main focus of our paper remains fully projection-free algorithms for nonconvex minimax optimization, where we establish new complexity guarantees for NC–C and other nonconvex settings.

References:

  1. Lu, Zhaosong, and Xiangyuan Wang. "A First-Order Method for Nonconvex-Nonconcave Minimax Problems under a Local Kurdyka–Łojasiewicz Condition." SIAM Journal on Optimization 36.4 (2026): 1997-2030.

  2. Yang, Junchi, Negar Kiyavash, and Niao He. "Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems." arXiv preprint arXiv:2002.09621 (2020).

Thank you to the authors for addressing my questions. I will maintain my score and overall positive evaluation of the paper.

Reviewer_Pso2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents a new projection-free numerical method for minimax problems, that instead of projected descent-ascent requires only a linear minimization (solving a linear program) in each iteration. The motivation is that LM is often cheaper than projection. It is harder to obtain good convergence rates for projection-free methods than for methods using projections.

The authors design a method based on Frank-Wolfe with away steps. Augmeting it with primal and dual proximal regularization and further dual quadratic regularization around a fixed anchor point. They prove that this method improves the constant kk in the (sublinear) convergence rates (ϵ−k)(\epsilon^{-k}) over the existing projection free methods. The achieved rate differs according to whether the objective f(x,y)f(x,y) is convex-concave, nonconvex-concave, or one/both is KL. But caution must be taken when comparing rates of prior and new methods because they relate to somewhat different definitions of accuracy ϵ\epsilon.

The convergence analysis is non-trivial and it is not a straightforward extension of the nearest previous result (Zheng et al, 2023), though the proof technique is similar.

The experiments show that the method converges faster than baseline projection-free methods, on two (rather simple but realistic) minimax problems, one convex-concave and one nonconvex-concave.

Critical strengths

The paper strictly improves over theoretical asymptotic convergence rates of existing methods for several types of minimax problems.

The convergence analysis is nontrivial

The experiments convincingly show that the method is faster than prior methods, though only on two quite simple problems. However, the difference in speeds is not very high.

Critical weaknesses

The presented experiments weaken the paper's motivation, since both can be naturally solved by other numerical methods. Eg, in th esecond experiment the projection on the feasible sets would be cheap, so projected descent-ascent would probably a method of choice.

Questions for authors

To what extent are the improved convergence rates due to the away steps, and to what extent to the smoothing? Could comparable rates be established for the same framework using ordinary Frank–Wolfe, or is there a fundamental obstacle? Do you see a counter-example minimax problem for which the method without away steps would have strictly smaller rate than the one achieved?

How much novel is the active set counting argument?

On the two problems in the experiments, would other than projection-free methods beat the proposed method in speed?

2 comments

Authors response:

  • Roles of Smoothing and Away Steps.

    We thank the reviewer for this interesting question.

    (i) As explained in our common response, smoothing, perturbation, and away steps play complementary roles. In particular, away steps provide the linear gap-to-distance error bounds needed to absorb the primal–dual coupling term in Appendix F, Eq. (8). Replacing them with ordinary FW generally yields only square-root gap-to-distance bounds, preventing the same Lyapunov descent argument from closing. Thus, away steps are crucial to our current analysis, although this does not rule out comparable rates through a different analysis.

    (ii) Nevertheless, fully projection-free convergence remains possible without away steps. At the objective level, removing the moving-center smoothing terms leaves the dual perturbation −δ2∥y−yˉ∥2-\frac{\delta}{2}\|y-\bar y\|^2. With ordinary FW updates and appropriate parameter choices, this leads to the perturbation-only LMO–LMO framework of Giang-Tran et al. (2026), which achieves O(ϵ−6)\mathcal{O}(\epsilon^{-6}) for NC–C and O(ϵ−5)\mathcal{O}(\epsilon^{-5}) for C–C problems under their convergence criteria. In contrast, our combination of smoothing, perturbation, and away steps achieves O(ϵ−3)\mathcal{O}(\epsilon^{-3}) and O(ϵ−2)\mathcal{O}(\epsilon^{-2}), respectively, under the stronger two-sided FW stationarity criterion.

    (iii) Regarding counterexamples, smooth strongly convex minimization over polytopes is a special case of C–C minimax optimization. Classical results by Canon and Cullum (1968) and Wolfe (1970), as discussed in Lacoste-Julien and Jaggi (2015), show that ordinary FW can exhibit sublinear convergence even for strongly convex objectives hh, whereas away-step FW enjoys geometric convergence. Since h(xt)−h⋆≤gFW(xt)h(x^t)-h^\star\leq g_{\mathrm{FW}}(x^t), these lower-bound examples also preclude geometric convergence of the FW gap along the corresponding ordinary-FW trajectories.

    These examples already illustrate a genuine separation within a special case of minimax optimization. They further suggest that analogous slow convergence phenomena may persist in more general minimax problems. However, establishing such a separation for our full smoothing-based framework without away steps would require a separate lower-bound analysis, which remains an interesting direction for future investigation.

  • Novelty of the Active-Set Counting Argument.

    The active-set counting principle is classical in away-step Frank–Wolfe methods (Lacoste-Julien and Jaggi, 2015), and our joint primal–dual construction follows Gidel et al. (2017).

    The main difficulty in our smoothing–perturbation framework is that, unlike standard AFW analyses, we need to guarantee sufficiently many iterations that control not only the FW gap but also the proximal residuals associated with zz and vv. This requires distinguishing three types of iterations. Non-clipped steps yield the full Lyapunov descent estimate, whereas clipped steps keep zz and vv fixed. Among the latter, clipped FW steps yield a uniform Lyapunov decrease, while clipped away steps may have arbitrarily small progress but remove at least one active atom. Combining these properties with the classical counting argument (Lemma 4.3), we establish Ω(T)\Omega(T) non-clipped iterations, which is crucial for our convergence guarantees.

  • Comparison with Projection-Based Methods (Q3+Weakness).

    We thank the reviewer for raising this important practical question. We agree that projections onto the feasible sets in the original robust budget allocation problem are inexpensive, making projection-based methods like AGDA natural alternatives that generally perform better on this benchmark.

    To better illustrate the motivation for projection-free methods, we have added an NC–C extension of robust budget allocation with matching constraints. In this setting, the primal feasible set is a matching polytope, for which linear minimization can be efficiently performed using the Blossom algorithm, whereas Euclidean projection is considerably more involved. Our additional experiments show improved FW-stationarity performance compared with LMO–LMO in terms of iterations. Appendix K.3 of our revised manuscript describes these new experiments in detail.

    Together with the graphical matching experiment, this provides both C–C and NC–C benchmarks with combinatorial constraints that better reflect the intended setting of our method.

Reviewer_Pso2OpenReview ↗

Reply to Rebuttal

In their reply to my review, the authors addressed all my objections and answered some of the raised questions. They acknowledge that they do not not have answers to some difficult questions - eg, a counterexample showing a slower rate for the same method but without away steps.

My view of the paper remains the same and I keep my score. Please take into account that the topic is not exactly my research field.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Common Response

We thank the reviewers for their insightful questions. Below we give an overview of the role of the three complementary techniques we use to obtain the faster complexity guarantees we achieve in this paper, namely double smoothing, dual perturbations, and away-step Frank--Wolfe updates. Their roles can be divided into two categories: function-level regularization, which does not require the assumption of polytope constraints, and geometry-dependent updates, which exploit the facial structure of polytopes.

Function-level regularization. We first discuss smoothing and dual perturbation, both of which can be applied over general compact convex sets.

  • Smoothing. Even when ff is smooth and convex–concave, the primal value function ϕ(x)=max⁡y∈Yf(x,y)\phi(x)=\max_{y\in\mathcal Y}f(x,y) can be nonsmooth. Primal smoothing introduces a smooth Moreau envelope, allowing the algorithm to approximate proximal point updates without solving the proximal subproblems exactly. Our double smoothing framework further constructs strongly convex–strongly concave regularized problems, even when the original objective is nonconvex–nonconcave.

    Smoothing is also the key ingredient that enables our extension beyond NC–C problems. Under a one-sided KŁ condition, the resulting Lyapunov framework allows us to control the primal–dual coupling through a proximal error bound (Proposition 4.2(ii)), without requiring dual concavity or perturbation. This leads to our NC–KŁ guarantees and, by symmetry, the KŁ–NC results.

  • Dual perturbation. For NC–C problems, adding −δ2∥y−yˉ∥2-\frac{\delta}{2}\|y-\bar y\|^2 makes the inner maximization strongly concave and the perturbed primal value function smooth. More importantly, this additional curvature yields a stronger quadratic proximal error bound (Proposition 4.2(i)), with a constant of order O(1/δ)\mathcal{O}(1/\delta). This allows the primal–dual coupling term to be absorbed by choosing βx=O(δ)\beta_x=\mathcal{O}(\delta), leading to the improved O(ϵ−3)\mathcal{O}(\epsilon^{-3}) complexity when combined with smoothing and away steps. Unlike smoothing, a small dual perturbation does not generally eliminate nonconcavity in NC–KŁ problems. We therefore set δ=0\delta=0 in those settings and instead exploit the KŁ-based proximal error bound.

    These mechanisms are complementary. A similar synergy appears in projection-based NC–C methods: smoothing or perturbation alone achieves O(ϵ−4)\mathcal{O}(\epsilon^{-4}) game-stationarity complexity, whereas their combination improves it to O(ϵ−3)\mathcal{O}(\epsilon^{-3}) (Li et al., 2026).

Geometry-dependent optimization. Away steps exploit the facial structure of polytopes by allowing the algorithm to remove weight from previously selected atoms. Since smoothing makes the regularized primal and dual subproblems strongly convex and strongly concave, respectively, the pyramidal-width inequality (Lemma C.2) yields the following linear gap-to-distance error bounds (Lemma D.3):

\|x^t-x(y^t,z^t,v^t)\| &\le \frac{g_{\mathrm{PFW},x}^t} {(r_x-L)\operatorname{PWidth}(A)}, \text{and } \|y^t-y(x^t,z^t,v^t)\| \le \frac{g_{\mathrm{PFW},y}^t} {(r_y-L+\delta)\operatorname{PWidth}(B)}. \end{aligned}$$ Since $g_{\mathrm{PFW},x}^t+g_{\mathrm{PFW},y}^t\le 2g^t$, both errors are linearly controlled by the algorithmic gap. In contrast, vanilla FW generally provides only a square-root gap-to-distance bound, $\|x^t-x(y^t,z^t,v^t)\|=\mathcal{O}(\sqrt{g_{\mathrm{FW},x}^t})$, rather than the linear bound available with away steps. This improvement is crucial in our Lyapunov analysis (Appendix F, Eq. (8)): away steps allow the primal–dual coupling error to be bounded by $\mathcal{O}(\gamma_t g^t)$, which can be absorbed into the leading descent term $\gamma_t g^t$. With vanilla FW, the corresponding bound would be $\mathcal{O}(\gamma_t\sqrt{g_{\mathrm{FW}}^t})$, which cannot generally be absorbed as the gap vanishes. This is where the stronger polyhedral error bound enables our Lyapunov descent analysis. Finally, the active-set counting argument (Lemma 4.3) controls clipped away steps, ensuring sufficiently many non-clipped iterations to establish the convergence rates. In summary, smoothing provides the flexibility to handle NC–C and more general NC–KŁ problems; dual perturbation strengthens the error bound and accelerates convergence in the NC–C setting; and away steps exploit polyhedral geometry to make these regularization mechanisms effective within our fully projection-free analysis. Together, they yield the improved convergence rates.
AuthorsOpenReview ↗

Common Response (Continued)

Theoretical comparison. To quantify the contributions of smoothing and perturbation, we consider two reduced variants that retain away-step updates: double smoothing without perturbation (δ=0\delta=0 in Algorithm 1) and dual perturbation without moving-center smoothing (a separate perturbation-only AFW variant). Their complexities are summarized below:

NC–CC–C
Smoothing + away stepsO(ϵ−4)\mathcal{O}(\epsilon^{-4})O(ϵ−3)\mathcal{O}(\epsilon^{-3})
Perturbation + away stepsO(ϵ−4)\mathcal{O}(\epsilon^{-4})O(ϵ−3)\mathcal{O}(\epsilon^{-3})
All three techniquesO(ϵ−3)\mathcal{O}(\epsilon^{-3})O(ϵ−2)\mathcal{O}(\epsilon^{-2})

These guarantees use the same two-sided FW stationarity criterion. Thus, even with the polyhedral geometry exploited by away steps, combining smoothing and perturbation yields an additional improvement in both settings.

Scope beyond polytopes. The function-level regularization techniques remain applicable over general compact convex sets, as neither smoothing nor dual perturbation requires polyhedral geometry. In particular, removing the moving-center smoothing terms leaves the dual perturbation −δ2∥y−yˉ∥2-\frac{\delta}{2}\|y-\bar y\|^2. With standard FW updates and suitable parameter choices, this recovers the perturbation-based LMO–LMO framework of Giang-Tran et al. (2026), which achieves O(ϵ−6)\mathcal{O}(\epsilon^{-6}) and O(ϵ−5)\mathcal{O}(\epsilon^{-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)\mathcal{O}(\epsilon^{-5}) and O(ϵ−4)\mathcal{O}(\epsilon^{-4}), respectively.

With double-smoothing alone and ordinary Frank-Wolfe updates, appropriate parameter choices can lead to an algorithm with complexity guarantees over general compact convex sets. A conservative Lyapunov analysis yields O(ϵ−8)\mathcal{O}(\epsilon^{-8}) and O(ϵ−7)\mathcal{O}(\epsilon^{-7}) complexity bounds for NC–C and C–C problems, respectively, under the same two-sided FW stationarity criterion. We do not claim these bounds are tight, and obtaining sharper guarantees through alternative analyses remains an interesting question.

These results illustrate that function-level regularization is applicable beyond polytopes and that other geometric structures can also improve projection-free convergence rates. However, our sharper O(ϵ−3)\mathcal{O}(\epsilon^{-3}) and O(ϵ−2)\mathcal{O}(\epsilon^{-2}) guarantees rely on the pyramidal-width error bound (Lemma C.2). Without this geometric bound, the current Lyapunov analysis does not directly yield comparable rates. Whether alternative analyses can achieve similar improvements over general compact convex sets remains an open question.

References

  1. Li, Jiajin, et al. "Smoothing meets perturbation: Unified and tight analysis for nonconvex-concave minimax optimization." arXiv preprint arXiv:2602.14185 (2026).

  2. Giang-Tran, Khanh-Hung, Soroosh Shafiee, and Nam Ho-Nguyen. "Projection-Free Algorithms for Minimax Problems." arXiv preprint arXiv:2603.29870 (2026).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.