Projection-Free Methods for Solving Nonconvex-Concave Saddle Point Problems
Authors: Morteza Boroun
Erfan Yazdandoost Hamedani
Afrooz Jalilzadeh
Venue: NeurIPS 2023 poster (2023)
Keywords: Saddle Point Problem
Projection-free method

Abstract: In this paper, we investigate a class of constrained saddle point (SP) problems where the objective function is nonconvex-concave and smooth. This class of problems has wide applicability in machine learning, including robust multi-class classification and dictionary learning. Several projection-based primal-dual methods have been developed to tackle this problem; however, the availability of methods with projection-free oracles remains limited. To address this gap, we propose efficient single-loop projection-free methods reliant on first-order information. In particular, using regularization and nested approximation techniques, we propose a primal-dual conditional gradient method that solely employs linear minimization oracles to handle constraints. Assuming that the constraint set in the maximization is strongly convex, our method achieves an $\epsilon$-stationary solution within $\mathcal{O}(\epsilon^{-6})$ iterations. When the projection onto the constraint set of maximization is easy to compute, we propose a one-sided projection-free method that achieves an $\epsilon$-stationary solution within $\mathcal{O}(\epsilon^{-4})$ iterations. Moreover, we present improved iteration complexities of our methods under a strong concavity assumption. To the best of our knowledge, our proposed algorithms are among the first projection-free methods with convergence guarantees for solving nonconvex-concave SP problems.

Projection-Free Methods for Solving Nonconvex-Concave Saddle Point Problems
Morteza Boroun", Erfan Yazdandoost Hamedani", Afrooz Jalilzadeh"
*Department of Systems & Industrial Engineering
The University of Arizona
Tucson, AZ. 85721
mortezadarizona.ed erfany@arizona edu, afrooz@arizona.edu
Abstract
In this paper, we investigate a class constrained saddle point (SP) problems where the objective function is nonconvex-coneav and smooth. This class of problems has wide applicability in machine learning, including robust multi-class classifica- tion and dictionary learning. Several projection-base primal-dual methods have been developed to tackle this problem; however, the availability of methods with projection-free oracles remains limited. To address this gap, propose efficient single-loop projection-fiee frree methods reliant on first-order information. In particular, using regularization and nested approximation techniques, dual conditional gradient method that solely employs linear minimization oracles to handle constraints. Assuming that the constraint set in the maximization is strongly convex, our method achieves an e-stationary solution within (E iterations. When the projection onto the constraint set of maximization easy to compute, we propose one-sided projection-free method that achieves an c-stationary solution within Occ-4) iterations. Moreover, we present improved iteration complexities of our methods under strong concavity assumption. To the best of our knowl- edge, our proposed algorithms are among the first projection-free methods with convergence guarantees for solving nonconvex-concave SP problems.
propose a primal-
Introduction
Let (X, (1-1x) and (D, ll-lly) be finiee-iimensionll, real normed spaces with the corresponding dual spaces denoted by 1I'", 11.1xx-)) and ()",, (1-Ily=)) respectively. In this paper, study saddle point (SP) problem of the following form:
min max C(r, v), xeX yeY
(1)
where : X) + IR is possibly nonconvex in x for any y E Y and concave in for any E X with certain differentiability properties (see Assumption 2.6): moreover, C X' and Y y are convex and compact sets. Such problem has broad range of applications including robust optimization reinforcement learning [Л], and adversarial learning [17), to name just a few.
4
There has been vast research conducted on developing algorithms for solving SP problems 37 Despite the extensive studies conducted on the development of algorithms to solve problem common drawback of these methods is their reliance costly operations involving the projection onto constraint sets. In the optimization literature, the shortcomings associated with projection- based techniques prompted the emergence and advancement of projection- -fre approaches. Namely, Frank Wolfe-based algorithms [4] are first-order methods designed for minimizing smooth constrained optimization problems where instead of projection onto constraint set only linear minimization
42 18
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

over the set needs to be solved. Such an operation can significantly reduce the computational cost of the algorithm as in the case of nuclear-norm ball constraints.
Nonconvex SP problems have already been extensively investigated in the literature and various meth- ods have been proposed for different setrings. Namely, the vanilla projected gradient descent ascent has been shown to achieve iteration complexity O for finding an e-stationary of nonconvex- strongly concave problem [27] matching the lower bound in this setting. However, this method fails to address nonconvex-concar problems, therefore, many researchers studied various smoothing [5]] and acceleration [40] techniques to ensure a convergence rate guarantee. Most of these methods are built upon the idea of solving regularized subproblems inexactly resulting in multi-loop method that can pose implementation challenges. To avoid such a complication, single-loop primal-dume dual methods have gained popularity. Recently, a unified projected primal-dual gradient using the reg- ularization technique has been studied [49]. The proposed method can achieve the complexities settings. While
of () and (e)-1) for nonconvex-strongll concave and nonconvex-conee the studies on primal-dual projected gradient-basee based methods are rich and fruitful, less known about projected-free frre methods for SP problems. With only handful of studies focusing on (strongly) convex-(strongly) concave problems [16 46 91. no projection-free method for solving nonconvex SP problems is currently available, to the best of our knowledge. Moreover, recently there has been a growing interest in developing algorithms for solving bilevel optimization problems [43 20 [3]
which subsumes SP problems as special case. However, it is important to note that most of the existing methods for solving bilevel optimization problems consider an additional assumption on the lower-level objective function satisfying strong convexity Polyak Lojasiewicz (PL) condition 20 31. These assumptions in the context of SP problems translate into strong concavity or PL. condition for L(xx -) which cannot handle merely concave setting considered in this paper. Therefore, in this paper, we focus on developing projection-free methods for solving (T. In particular, our main research question is
Can we develop one-sided or fully projection-free primal-dual method with a convergence rate guarantee for solving (onconvex-sstrongyy concave SP problem in !
Our response to this question is affirmative, and next we outline the key contributions of our work.
1.1 Contribution
In this paper, we consider a broad class of constrained SP problems where the objective function is nonconvex-concave and smooth. Motivated by the pressing need for developing projection algorithms from an application perspective as well as the lack of efficient methods with theoretical guarantees, propose primal-dual projection-free methods for solving nonconvex-concav SP problems, Using regularization and nested approximation techniques we first develop a single-loop primal-dual method that solely uses linear minimization oracle (LMO) to find a direction for both primal and dual steps. Next, assuming that the projection oracle (PO) is available for the maximization component of the objective function, develop one-sided projection -foeee method with regularized projection gradient ascent. Our main theoretical contributions are summarized below.
1) Assuming the constraint set in the maximization component is strongly convex, show that our proposed primal-dual conditional gradient method that employs LMOs for both variables achieves an e-stationary solution within ((e-6) iterations. To the best of our knowledge, this is the first complexity result for primal-dual methods with only LMOs for nonconvex -onncvvee SP problems. Moreover, when the objective function is nonconvex-strongs -tronnly concave, our proposed method achieves e-primal and c-dual gaps within O(e and O(E 2) iterations, respectively.
2) Considering the case where projection onto the constraint set of the maximization component is easy to compute, we demonstrate that our one-sided projection-fres method achieves an e-stationary solution within ((--1) iterations matching the hest-known results for single-loop projection- -bsed primal-dual methods. For senconvex-strongll concave setting, the iteration complexity improves to O(e 22).
1.2
Related work
SP problems have been subject to extensive studies, primarily in the context of the convex-concave setting [37 41 8 [8]. However, the practical applications of SP problems in nonconvex settings,

---

particularly in the context of robust optimization and adversarial learning have sparked demand for a thorough investigation and further exploration. Next, we briefly discuss the state-of-ther oftte-of-hhearrt art methods in the literature for nonconvex-(strongly concave problems. We divide our review into two sections of projected gradient- baased and projection-free
algorithms.
Projected gradient based algorithms: Various algorithms have been proposed for nonconvex- 40
concave setting under different assumptions B0
52 3] Authors 44 proposed a double
loop algorithm to solve nonsmooth weakly convex-concave with complexity of (c--)). In the pursuit of more efficient solutions, Triple-loop inexact proximal point methods with the faster convergence rate of Ö(E are developed in
48 23]. Additionally, single-loop algorithms for addressing nonconvex-coneat problems were introduced by [29] and [32] where they achieved the iteration complexities of Ö (e) and (e) respectively. More recently, authors in [3 proposed optimistic gradient descent ascent and extra-gradioe methods and obtained a convergence rate of Ol 9. Employing Nesterov's smoothing technique (38), the iteration complexity of ( +) was obtained by [51] for general nonconvex-conett
problem. In addition, [50] achieved the same convergence rate with linear coupled equality or inequality constraints. Recently, 49 proposed an alternating gradient projection (A (AGP) algorithm where it utilizes gradient projection for updating and y and achieves the suboptimal complexity of O(c All the aforementioned methods rely on projection onto the constraint sets.
Projection-fre free based algorithms: There has been a surge of interest in the application of projection- free methods within the machine learning and optimization problems [24] 15
25 26).. Despite the widespread application of projection free methods such as the Frank Wolfe (FW) algorithm. there have been limited studies that examine their use in the context of SP problems [I [9 47 16,
46 | (22] In
[19 a projection-free free algorithm for convex-concave setting is proposed and achieved the complexity of O(E LMO calls. This algorithm was subsequently refined by (47) with the development of a parallelizable algorithm. Gidel et al. [16] presented the first convergence result for an FW-type algorithm for nonbilinear SP problems. Assuming that the SP solution lies within the interior of constraint sets, the proposed method achieves a linear rate for strongly convex-stronge concave SP problems. Moreover, the method achieves the same complexity for convex-concave setting, assuming that the constraint sets are strongly convex and gradients of the objective function are uniformly lower-bounded. Roy et al. (46) advanced a projection-free algorithm for the same setting and introduced a variant of the FW algorithm that is particularly suited for the nonstationary stochastic SP problems. Additionally, the authors in 9 proposed a four-loop projection -fee algorithm which can be viewed as variant of Mirror- Proox in which proximal subproblems are solved inexactly using conditional gradient sliding (25 for convex-strongly concave problems. Considering nonconvex- concave setting, Nouiched et al. (39] proposed a multi-loop one-sided projection-free primal-dual method that achieves the complexity of Ö(c-3.5) to find an e-game stationary solution. Notably, in their method, at each iteration & the minimization subproblem needs be computed over the set fx E X' x + I&& E X, ||^||| < 1}. Kolmogorov et al. [22 developed a two-loop one-sided projection-free primal-duae method for solving bilinear is solely used for computing the minimization variable. The proposed method achieves an iteration complexity of Oc-1)) The summary of related work and their comparison are presented in Table 1
SP problems where L.O
1.3 Motivating Examples
Example 1. Robust Multiclass Classification: Consider a multiclass classification task for a given training dataset D'r = {(a bo)) where a; E Rd denotes the feature vector of the i-th sample and b, E k)) is the corresponding label. The goal to find a linear predictor with parameter 0- = 10| 0__ ..... 0N] E 1xxd that is able to predict the labels for an unlabeled dataset Drest = (a, j In particular, given a new data point à E D'est the corresponding label can be predicted via 6 = arg max} 0J á. It has been shown that 112 the linear predictor 0 can be found by minimizing multinomial logistic loss function, i.e., (0) loo (1 exp(E; (0J a, 0% )))). over a nuclear norm constraint, i.e., X = (0 ||0||_ S r) for some r > O. On the other hand, in many applications where safety and reliability are crucial distributionally robust optimization offers a promising approach for a more robust and reliable prediction that can be used in classification tasks to capture uncertainty in data distribution 335 34). This can be achieved by considering worst-case performance of non-parametrie uncertainty set on the underlying data distribution. This leads to min-max formulation where the maximization is taking over uncertainty set Y. For
3

---

Table I: Comparative analysis of optimization schemes for convex-strongly concave (C-SC), convex- concave (C-C), nonconvex-strongly concave (NC-SC) and nonconvex-conert (NC-C) problems, featuring different oracles: Linear Minimization Oracle (LMO) and Projection/Proximal Oracle (PO). (.) denotes ((-) up logarithmic factor. In the column of "additional assumption", the abbreviation SC stands for strongly convex. "The complexities are presented for c-primal and c-dual,
respectively.
Setting
Ref
Non-bilineur
Oracle
# of loops
Addt'l Assump.
Rute
C-SC
Chen et al. 9
LMO-LMO
None
O(e-2)
Gidel et
LMO-LMO
X and Y are sets
Olloge
C-C
Kolmogorov et al.
22
X
LMO-PO
2
X is SC set
O((²))
Xu et
PO-PO
None
O(c
NC-SC
CG-RPGA (Theoram
4.2
/
LMO-PO
Nome
0(r²))
R-PDCG (Theoren
4.4
LMO-LMO
Y is SC set
O(e "),O(e "y
Xu et 49
/
PO-PO
Nome
O(r
NC-C
CG-RPCA (Theorem
5.1
V
LMO-PO
None
Ole
R-PDCG (Theoren
5.3
LMO-LMO
is SC set
O(e
instance, Y fy A, Vy, 1,) < p) is considered in different papers such [4] where A. n an n--dimensional simplex set, and P)) denotes the divergence measure between two sets of probability measures Q and P. Therefore, distributionally robust multiclass classification can be formulated as the following SP problem
min max DEX y= MWPREE EY
Σ (0).
This problem can be readily cast as (I) by defining [(0, y) = Ei= (0). ( The constraint of the maximization is the intersection of simplex set and divergence measure constraints. Indeed, one can relax the simplex constraint using the splitting technique and Fenchel duality. The resulting equivalent saddle point problem has maximization constraint of Y {y Vv, 1,) p). which only described by the divergence measure constraint, In some popular examples such as the Pearson Chi-square divergence, i.e., V (y, 1n/n) = ||n 1, 11. Y satisfies the assumption of strongly convex constraint set.
Example 2. Dictionary Learning: Dictionary learning aims to acquire a succinct representation of the input data extracted from large dataset. Given input dataset A = [a1...., an] m our primary goal is to find a dictionary D = [di,.... dpl E Rm= that can accurately approximate the data through linear combinations. Dictionary learning problem can be formulated in nonconvex optimization form
45
min min
AA - DCI
s.t. ||||, S: 14,112 < 1,1v E (I....,P)
DER CEREXA
where C IR denotes the coefficient matrix. In various learning scenarios, such as lifelong learning, the learner engages in a sequential series of tasks, aiming to accumulate knowledge from previous tasks in order enhance performance in subsequent tasks. Suppose that we have learned dictionary E Rxxp and its corresponding coefficient matrix C e IRpx" for the dataset A. Given a new dataset A' E _m we aim to refine a new dictionary D' E pmxx such that it still provides an accurate representation of old dataset A with the learned coefficient matrix C. Consequently, this problem can be written as the following non-convex problem with a convex nonlinear constraint:
min min ||A D'C''I.
|A D'ĆII < 6; |C'||. r; || < 1, E (1,....9). (4)
where 8 0 denotes the user-predefing accuracy for the representation of the old dataset and
Č E R is the extension of C by adding 4 columns of zeros. This problem can be formulated
equivalently as an SP problem (1) using Lagrangian duality. In particular, it can be cast as ①I
by setting L(D'' C'),y) - 12: + A D'C 5), x = ((D', (D), [[C']. r, |ddi1l2 < V, E (I,...,,)}, and = R4, Note that nonconvex-concave and smooth.
Moreover, due to the existence a Slater point for problem 4 a dual bound, i.e., |lvll S B for some
B 0, can be constructed efficiently suggested in (36] [8] to ensure boundedness of set Y.

---

Other than min-max max formulation, the nuclear-non norm constraint in the above examples makes the problem computationally demanding for projection- based algorithms. Therefore, imperative to address this challenge by developing and utilizing projection-fre free methods, which can effectively overcome the computational limitations associated with these problems.
Preliminaries
In this section, outline the notations and required assumptions that need for the analysis of our proposed methods as well as some important definitions.
Notations. Given two sets X and Y, X x Y denotes the Cartesian product of X and Y. The lower-case x and y, as well as their accented variants, are reserved for vectors in the space of X and )1 respectively; moreover, the letter will be used to indicate the concatenation of those vectors, i.e.,
= [xr y T The upper-case X and Y are reserved for constraint sets; moreover, Z will be used to indicate their Cartesian product. Given a differentiable function [(r, y). V.L(x, (z. y) and V,C(xx y) denote the partial derivatives of L. with respect to x and y. respectively. Given a set X, I x-)) denotes the indicator function. Given a fimit--dimensiona normed vector space, I1-11p for some p 2 1 denotes
the normm.
2.1 Oracle Description
In this paper. we will utilize the following oracles to acquire first-order information and solution of structured subproblems for the proposed algorithms in different settings.
. Given (z, y), first-order oracle (FO) returns VzL(x, v) and V VyL(r.y).
Given a vector ī E L4 and a convex and compact set U C U1 linear minimization oracle (LMO) returns solution of minzeu (T,
Given vector ã E l and convex and compact set U C U1 projection oracle (PO) returns the solution of minzeu || øllux
Based on the above oracles, define some gap functions to measure the quality of the solution. More specifically, when the proposed algorithm uses LMO we use the following definition.
Definition 2.1 (Gap function for LMO). The stationary gap function 9x + for the min-
imization part of problem (1) is defined as (x, 7) å supyex (V, 0). I x>) Similarly, for the maximization part of problem ① the stationary gap function Gy Z + R is defined as
Gy (z. 7) A supyey (V C(, 7). y). Moreover, we define Gz 7) 2 Gx (I, Φ) + (ā. 3).
In the case where the proposed method uses PO for the maximization part of the objective function of (I) we use the same gap function Gx for the minimization component while employing the following gap function for the maximization component.
Definition 2.2 (Gap function for PO). The stationary dual gap function Gy 7 R corresponding to the maximization part of problem is defined as Gy (zz 77 2 1 I Moreover, we define Gz Ø) Gx(2, 7) + Gy (ē, Ø) where Gx is defined in Definition 2.1
1ay--Pre Pr o C(, g))l
Definition 2.3. For a given gap function Gz Z - R. a point (z, 7) E Z is an e-stationary of problem L if GZ(ā, <
Remark 2.4. As indicated in the above definitions, since we use different oracles for the maximization component of the objective function we need to employ different gap functions for the dual iterates. With slight abuse of notation, we used Gy when using both LMO and PO for the constraint set Y. The reason is that an e-solution terms of both definitions implics an e-game stationary solution. More specifically, if Gz 7) < for some (z. 7) Z, then
V L(t, D E 01x (z) + u, s.t. |||||| x < O(e,
V V, 5) d1y + s.t. Lt.lel/y < O(e).
Therefore, we consider the above definition as unified notion of e-stationary solution similar to [4 We refer the reader to [21 28 for the details of the relation between a game stationary solution and other notations of stationary solution.
5

---

Definition 2.5. Let (4, ll-ll)) be dinte--nmmnsi normed vector space. A convex set K C Uis
a-strongly convex with respect Il-IIz for any u, V E K, U, and y E [o, 1],
yu (1 7)v + 71- ||u
v E K,, s.t. ||wllz
We next state our main assumptions considered in the paper.
2.2 Assumptions
Assumption 2.6. (I) For any y E Y, [(., v) is continuously differentiable with a Lipschitz continuous
gradient, i.e, there exists Lax 2 0 and Lyz 0 such that for any 2, 7 and y, y E Y the followings hold
] - Vz 1lx S Laz | - æ||x + Lyz lly ølyy
(II) For any E X. ()x,)) is concave and continuously differentiable with Lipschitz continuous gradient, i.e, there exists Tuy 2 0 and Lyy > 0 such that for any x, T E and y. ú E Y the followings hold
IV WyL(r, - vyL(ū, My S Tag 1a - x||x + L - ølyy
(II) X X' and Y S y are convex and compact sets with diameters Dx and Dy, respectively. i... Dx - supa,aex || =1,xx and Dy - supy.sey 8ly.
In the case where LMO available for both minimization and maximization components of we will consider the following additional assumption.
Assumption 2.7. Y y is a-strongly convex for some 0.
Remark 2.8. Strongly convex sets arise in many applications and there have been several studies characterizing various instances [[5]. In particular, many of these examples, the corresponding LMO admits a closed-form solution or can solved efficiently. Here we present two interesting examples:
(1) Let (r) A {x E X' f()) S r) where L-smooth function. Then, the set (r(r) strongly convex with modulus a 2/ w2/2. In particular, this example includes l. nonor ball when f(x) ||==I for E (1,
and f X - R. is μ-strongly convex and
(2) For given matrix A T let the singular values be denoted by (A))2 where 9 = min(n, m). Schatten lp ball for p (1, i... Bstp) (r) A [A R= (E or (A))) S <r).
is a strongly convex set with modulus a = (p- - 1)q² s/r (For details and more examples see [15]
Proposed Methods
In this section, we propose our algorithms based on a primal-dual conditional -gradieett approach for addressing problem (T). As previously mentioned in section [ we assume that the minimization component of problem (T) includes constraint set X, which allows for an efficient LMO, whereas the associated PO may involve computationally expensive procedures. However, with regard the maximization component of the objective function, we consider two main scenarios based on the (i) when an LMO available; and (ii) when a PO available.
Oracle assumption:
Note that problem (I) can be viewed a minimization problem min f(x) where f() & maxyey C(x,V) A naive implementation of a conditional gradient method, such as the Frank Wolfe method, has two main challenges: Firstly, evaluation of the objective function and/or its first-order information requires exact evaluation of y" yxx) E argmax L(z, y) at each iteration given æ E X which may not be possible. Secondly, since the objective function L(x, -) is concave fact, it can be shown that Ca y" (x)) E 0f(z), for any (z) argmax L(x, y). To overcome the later challenge, typical approach to add regularization term to the objective function to provide smooth approximation for the function f. More specifically, one can add regularization term
for any x X, implies that f(x) is a nonsmooth and nonconvex function.
# Iyy volls for some Yo Y to the objective function leading to the following regularized SP problem
min max
C,(x, v) & C(x, v) 2
11 11v voll3
zex vEY

---

Note the objective function in the above problem is strongly concave and smooth in y, hence, for any given a X the corresponding maximizer y (z) argmax C (z. y) is uniquely defined. Moreover, to bypass the requirement for evaluating an exact solution at each iteration, one can provide an increasingly accurate approximated solution for (ar), however, this leads two-loop method that still requires an excessive computational cost at each iteration to solve subproblem inexactly [53]. Moreover, the performance of such inexact methods is generally sensitive to the choice of the subproblem's 's parameters. Therefore, resolve these issues, we propose single-lopp and easy-to-implement inexact projection-free primal-dual algorithms.
Algorithm 1 Regularized Primal-dual Conditional Gradient (R-PDCG) method
Input: Mo E X, yo E Y. 1 > 0, {Tt}# C R+
for k 0,... K 1 do
Sk argmin e (V [= yk),
1i++ f- T&S8 (1 Th 2
Ph 4 argmaxyey V [f Web - plys - 90).
0k++1 <- 0.PP + (1 σ yik
end for
In particular, when LMO is available for both primal and dual steps, develop an alternating conditional gradient method where at each iteration a Frank Wolfe step is taken with respect to the primal variable via the direction V (zT( 8k) followed by a Frank Wolfe step for the regularized maximization problem with respect to the dual variable. The outline of our proposed method is presented in Algorithm [ Moreover, considering the scenario where the projection onto set Y is efficiently computable, we propose a one-sided projection-free primal-dual method. In particular, at each iteration, similar to the previous algorithm we perform Frank Wolfe step with respect the primal variable. Then to update the dual variable, instead of taking an FW-type update, we take a step of projected gradient ascent with respect the regularized objective function as follows
Py (yE + a (V (F
1
The outline of these steps is presented in Algorithm 2
Algorithm 2 Conditional Gradient with Regularized Projected Gradient Ascent (CG-RPGA)
Input: Zo E X, yo E Y. > 0, T.. ohh S R
for 0....: K
argmin = (V, (V.L(zt
#k+1 < T&& + Tk T
yk+1 + Py yk + oh VVy Bk) plyk 30))
end for
Convergence Analysis of R-PDCG
In this section, we study the convergence properties of Algorithms and First, in the next lemma, we provide a one-step analysis of Algorithm by providing an upper bound on the reduction of the objective function in terms of the consecutive iterates.
Lemma 4.1. Suppose Assumptions an6 2.7 holld and let (ZE, yn) Juza be the sequence generated
by Algorithm / with step-sizes Tk T O and (ax) and parameter p. O. Define os 2
min (1, 4(Togo t yu (K), yk) 1 and HE & La( v (xx)) L (2 yk) for any k
Then for any 2
aVp 8v2(L + 1))
HK+1 5 max 5.
H
H4 + E(T),
(5)
where E(T) & Lyot Dx 2 DDx
7

---

Note that the above one-step inequality demonstrates that given the iterate sequence [ the generated iterates {y reduce the suboptimality of regularized objective function Cn within an error bound E()). In other words, the generated iterates {yk) provides progressively accurate estimation of the optimal trajectory (Tx) with an error depending on the primal step-size т. Therefore, the key idea lies in the meticulous selection of to prevent error growth while ensuring sufficient progress in the primal variable. To this end, in the following theorem we establish bounds on the primal and dual gaps based the previous lemma that are connected via parameters 7 and μ.. Subsequently, in the next corollary by carefully selecting those parameters we demonstrate convergence rate guarantee for Algorithm I
Theorem 4.2. Suppose Assumptions 2.6 and 2.7 hold and let {(rns yx)}a20 be the sequence gener- and {or and parameter μ > O. Define σx - | y (1 yk) yx)lly- h then for any K 2 1, there exists t {[K/2], ..... K
ated by Algorithm / with step-sizes Tk -
1,, 4(y ta)
such that (xe, M1.
E X satisfy the following bounds
(x(2,, 91) - 2(f(xo) f(xx))
(Jezz + T
/D)T
D& + 2/2Lym Dx
Dē +
TK
TK
K
V/
1/3
3 3log(K + +1)
16(Lyy +
(8 + (N)((T)
VE(T) +
max (Vllo
K
aVi
avK
36c
256(TTm
+ 11)2
Gy Go4, v1) 5 (K + 4)2
max
Hu-
+cxE(())
a²u
2/3
8V2(Ly + (TE(T) +
C₁ + HDy.
where Cp. 22 Lygu/1 and E(T) is defined in Lemma 4.1
Now, we ready state the convergence rate and complexity results of Algorithm
Corollary 4.3. Under the premises of Theorem 4.2 choose j O(e) and O then for any K 2 1, there exists E {[K/21,.... K 1} such that (zt,8e) E X x Y satisfy Gz (2r, ue) s O(1/K1/6) Moreover, (Ie, We) satisfy (z 4e) S and consequently is an e-game stationary within O(e iterations.
Considering that the proposed method achieves convergence through dual regularization, becomes essential to address the question of convergence guarantee for Algorithm ① when the objective function nonconvex in x and strongly concave y. In such a scenario, where the objective function exhibits strong concavity, regularization can be circumvented by setting adjustment aligns Algorithm [ with the approach presented in [16]. albeit it should be noted that the study in [66 solely focused on convex-concave settings and their analysis does not extend to the nonconvex scenario.
= 0. This
2.7 hold and function L(x, .) is ji-strongly concave for any x X. Let ((T,, y& ()) J120 be the sequence generated by Algorithm with parameter μ O and step-sizes Tk = (11//3/4)) and {az]x20- Define ag & min(1, TLyy (ark, yk 31)]l }, then for
Theorem 4.4. Suppose Assumptions 2.6 and 2.7
any K > I, there exists 1 E ([K/2], ...,).,..K K 1} such that (at; M.) E X x Y satisfy:
(i) 9x(x,, vt) & ((1/K1/A) and Gy Ub) < (1////11//
(ii) (Te, Mt) satisfy c-primal gap 9x (It, M/.) S e within (le iterations and satisfy c-dual gap Gy(2z, Mt) I c within ((c-2 iterations.
Remark 4.5. It is important emphasize that Algorithm is single-loop method that leverages the gradient of the objective function and relies solely on the use of the L.O for handling constraints. To the best of our knowledge, our results in Corollary 4.3 and Theorem 4.4.44444eeeeeeee the first complexity results for finding an e-stationary solution in uunconvex-concatt and nonconvex-strongly concave SP problems, respectively, without the need for projection onto the constraint sets.
5 Convergence Analysis of CG-RPGA
In this section, we assume that the projection onto set Y can be computed efficiently and the vector space y is equipped with the Euclidean norm, i.c. I1-Ily- I1-I1g- We present the analysis for
8

---

convergence of CG-RPGA (Algorithm 2 for solving problem I In particular, we first consider the nonconvex-concave setting and the following theorem and corollary, we demonstrate that the convergence rate can be improved to O(L/K1/44, Afterward, we consider a nonconvex-strongly concave setting and we establish the convergence rate results for CG-RPGA in Theorem 5.3
Theorem 5.1.
Suppose Assumptions 2.6 holds and let ((Tkyyk)) k22 be the sequence generated by Algorithm with step-sizes Tę T > 0 and σk = =o= I Lyy+2n' and parameter p>> 0. Then for any K 2 there exists E {[K/2],.... ... K 1} such that (It, Uc) E X x Y satisfy the following bounds
2(f(zo) -f(xx))
2
(x(xx.81)
D2
+
Dx [800
2 (20))12
TK
TK
(1
p)
2
L2
+
+ Lax +
TDx
1u(1 p)
11
1180 (ro) 11 2/²
2L yy -T -Dx + Ly
Gy gy v0) S
r +Dx Dx= + pDy.
ou(l p)
ou
5.1 choose μ = ((e) and T = O(e²), then for any K 2 there exists E [[K/2),-... K 1) such that (ft, E X Y satisfy 9z yt) S (Ze, ve) and consequently is an e-game stationary
Corollary 5.2. Under the premises of Theorem
OL1/K1/4,, Moreover, (1) satisfy (z within O(e iterations.
Similar section 4 it is important to address the question of convergence guarantee for Algorithm 2 when the objective function is strongly concave in y. In this scenario, regularization can be avoided by setting l = O. the following theorem, we establish the convergence rate of Algorithm for SP problem ① in this setting.
Theorem 5.3. Suppose Assumptions holds and function C(x, -) is ju-strongly concave for any x E X. Let {(rK, yv) ] }320 be the sequence generated by Algorithm 2 with parameter μ = and step-sizes The (1/K2/2) and os = = S Lyy+R' Then for any K Z 1, there exists t E {[K/2],.... K K-1KK 13 such that (It, (or,y1) E x Y satisfy (2( S O(1/K(22). Moreover, (I,, Vt) satisfy Gz(Ze, ve) S within (c iterations.
6 Numerical Experiment
In this section, we implement our methods to solve Robust Multiclass Classification problem described Example I and Dictionary Learning problem in Example For the algorithms, the step-sizes are selected suggested by their theoretical result and scaled to have the best performance. In particular, for R-PDCG we let 7
10 and μ K
10 K for CG-RPGA let х and
10-3 1 : for AGP let the primal step-size 1 dual step-size 0.2, and the dual regularization 1
VE parameter as ; for SPFW both primal and dual step-sizes are selected to be diminishing as 22 Supplementary plots are provided in the appendix.
*+2
Robust Multiclass Classification: To assess the performance of our proposed algorithms (R- PDCG and CG-RPGA), we tested them against the Alternating Gradient Projection (AGP) algorithm introduced by 49) and the Saddle Point Frank Wolfe (SPFW) algorithm introduced by [16]. We conduct experiments on rcv1 dataset
15564, d 47236, k 53) and news20 dataset (n = 15935, d = 62061, k = 20) from LIBSVM repository As shown in Figure I our algorithms outperform the competing approaches, highlighting the advantage of utilizing a projection free approach. In this example, the high per-iteration computational cost of the projection operator significantly impacts AGP, with more than three iterations taking over 300 seconds reflecting the benefit of projection-free algorithms for certain class of problems. For problems with easy-to-projec to-proeect constraints, projection-banl -aasd algorithms such as AGP may have a better performance, however, this example supports the motivation behind the development of projection-free methods for saddle point problems with torojjctt constraints, particularly when an LMO is available.

---

10
RLOOGG OG-RPGA
-A SPEW
16.5
(2(Fe.30)
10
R. PDGG
-DD-RPAA
10"
38 WSP
10 16
SPFW
100 timets) 200
300
100 time(s)
200
300
(a) revl
(b) news20
Figure I: Comparing the performance of our proposed methods R-PDCG (blue) and CG-RPGA (red)
with AGP (magenta) and SPFW (green) in the Robust Multiclass Classification problem.
Dictionary Learning: Considering the dictionary learning problem in (4) compared the perfor-
mance of our proposed methods, R-PDCG (Algorithm T and CG-RPGA (Algorithm with AGP
49] and SPFW [16] although SPFW does not have theoretical guarantee for nonconvex-coneave SP. The datasets are generated randomly from a standard Gaussian distribution with details described in Section of the Appendix. Notably, CG-RPGA has faster convergence rate compared to R-PDCG matching our theoretical results (see Table I Moreover, AGP which is a fully projection-band based algorithm has the slowest convergence behavior in terms of time compared other methods. Solving a linear optimization problem over the nuclear norm ball requires computing only single pair of singular vectors corresponding the largest singular value, whereas computing a projection onto the nuclear norm ball demands a full SVD. The computational cost of latter operation is Okd min (k: d)), while the computational cost of the former one is (vln(k + d) /oi/ vε). where < kd and 0i are the number of nonzero entries and the top singular value of - - [zz v). respectively, and is the accuracy 10, Therefore, in this example, LMO is considerably more cost-effective to compute than the projection method. Figure 2 depicts our methods' superior performance compared to other algorithms.
10
x10
10
Grtse (N)
Infeassbility
10"1
PDCS
OG-RPGA
10
CG-RPGA
AGP
AGP
-SPPW
SPFW
10 time (s) 20
time (s)
Figure 2: Comparing the performance of our proposed methods R-PDCG (blue) and CG-RPGA (red) with other methods AGP (magenta) and SPFW (green). The plots from left right are trajectories of gap function and infeasibility for problem (4.
7 Conclusion
In this paper, we proposed primal-dual projection-free methods for solving a broad class of constrained nonconvex-concave problems. Using a regularization technique we devised single-loop method relying on LMO for handling constraints. In particular, we show that R-PDCG achieves an 6- stationary solution within O(e -6) iterations assuming that the constraint set strongly convex. Also, our method achieves e-primal and e-dual gaps within O(e and O iterations, respectively, for nonconvex-strongs concave problems. To the best of our knowledge, this is the first fully projection- free primal-dual method with a convergence guarantee for nonconvex SP problems. Additionally, when the projection on the maximization constraint easy to compute we propose one-sided projection-free free primal-dual method called CG-RPGA with iteration complexity of O(e matching the best-known results for projection-bee -baeed primal-dual methods, and improves to O(e iterations for nonconvex-strong!! concave setting. We acknowledge that the proposed method is currently limited to the deterministic setting and we plan to study such SP problems under uncertainty and distributed settings in future work.
10

---

References
[I] Jacob Abernethy and Jun-Kun Wang. On frank-wolfe and equilibrium computation. Advances in Neural Information Processing Systems, 30, 2017.
[2] Nazanin Abolfazli, Ruichen Jiang, Aryan Mokhtari, and Erfan Yazdandoost Hamedani. An inexact conditional gradient method for constrained bilevel optimization. arXiv preprint (tt::222060022299 2023.
[3] Sina Baharlouci, Maher Nouiched, Ahmad Beirami, and Meisam Razaviyayn. inference. arXiv preprint 1XXiv:190..10000 2019.
Renyi fair
[4] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton University Press, 2009.
[5] Pierre Bernhard and Alain Rapaport. On theorem of danskin with application to theorem of von neumann-sion. Nonlinear Analysis: Theory, Methods & Applications, 246 1995.
[6] Morteza Boroun, Zeinab Alizadeh, and Afrooz Jalilzadeh. Accelerated primal-dual scheme for a class of stochastic nonconvex-concave saddle point problems. In 2023 American Control Conference (ACC), pages 204-209, 2023.
[7] Radu Ioan Bot and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex- concave minimax problems. arXiv preprint arXiv:2007. 2020.
[8] Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of first-order primal-dual algorithm. Mathematical Programming, 159(1-2) 2016.
[9] Cheng Chen, Luo Luo, Weinan Zhang, and Yong Yu. Efficient projection-free algorithms for saddle point problems. Advances in Neural Information Processing Systems, 33: 10799-10808. 2020.
[10] Cyrille W Combettes and Sebastian Pokutta. Complexity of linear minimization and projection on some sets. Operations Research Letters, 49(4):565-571, 2021.
[11] Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In Interna- lional Conference on Machine Learning, pages 1 1125-1134 PMLR, 2018.
[12] Miroslav Dudik, Zaid Harchaoui, and Jérôme Malick. Lifted coordinate descent for learning with trace-norm regularization. In Artificial intelligence and statistics, pages 327-336 PMLR, 2012.
[13] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pages
PMLR, 2018
[14] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval research logistics quarterly, 3(1-2):95-110, 1956.
[15] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets. In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[16] Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Artificial Intelligence and Statistics, pages 162-371. PMLR, 2017.
[17] Ian Goodfellow, Jean Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1):13--144, 2020.
Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil
[18] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM Journal on Optimization, 1399, 2021.
11

---

[19] Niao He and Zaid Harchaoui. Semi proximal mirror- purro--prox for nonsmooth composite minimiza- tion. Advances in Neural Information Processing Systems, 28, 2015.
[20] Kaiyi Ji, Junjie Yang, and Yingbin Liang, Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pages 4882 4892. PMLR, 2021.
[21] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex- nonconcave minimax optiiizatio? In International conference on machine learning, pages 4880-4889. PMLR, 2020.
[22] Vladimir Kolmogorov and Thomas Pock. One-sided frank-wolfe algorithms for saddle problems. In International Conference on Machine Learning, pages 5665-5675. PMLR, 2021.
[23] Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-concav min-max problems. SIAM Journal on Optimizationn 31(4):2558- 2585, 2021.
[24] Guanghui Lan. The complexity of sarge-scale convex programming under a linear optimization oracle. arXiv preprint 1309. 2013.
[25] Guanghui Lan, Sebastian Pokutta, Yi Zhou, and Daniel Zink. Conditional accelerated lazy stochastic gradient descent. In International Conference on Machine Learning, pages 1965- 1974. PMLR, 2017.
[26] Qi Lei, Jiacheng Zhuo Constantine Caramanis, Inderjit S Dhillon, and Alexandros G Dimakis. Primal-dual block generalized frank-wolfe, Advances Neural Information Processing Systems, 32, 2019.
[27] Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex-stronglly -oooc-roooooyyyccvveeeeeeeee min-max optimization. Advances in Neural Information Process- ing Systems, 14:17-2-1804, 2021.
[28] Jiajin Li, Linglingzhi Zhu, and Anthony Man-Cho So. Nonsmooth composite nonconvex- concave minimax optimization. arXiv preprint arXiv:2209. 10825, 2022.
[29] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-conen concavee minimax problems. In International Conference on Machine Learning, pages 6083-6093. PMLR, 2020.
[30] Tianyi Lin, Chi Jin, and Michael I Jordan. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pages 2738-2779. PMLR, 2020.
[31] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35:17248-17262. 2022.
[32] Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 68:3676-3691 2020.
[33] Pouria Mahdavinia, Yuyang Deng, Haochuan Li, and Mehrdad Mahdavi. Tight analysis of extra-gradiess and optimistic gradient methods for nonconvex minimax problems. arXiv preprint 10X0v=2210.09338. 2022.
[34] Hongseok Namkoong and John C Duchi. Stochastic gradient methods for distributionally robust optimization with f-divergences. In Advances in Neural Information Processing Systems, pages 2208-2216, 2016.
[35] Hongseok Namkoong and John C Duchi. Variance-based regularization with convex objectives. Advances in neural information processing systems, 30, 2017.
[36] Angelia Nedic, Asuman Ozdaglar, et al. Convex optimization in signal processing and commu- nications, chapter cooperative distributed multi-agent optimization. eds., eldar, y. and palomar, d, 2008.
12

---

[37] Arkadi Nemirovski. Prox-meti Frox-method with rate of convergence (1//t) for variational inequali- ties with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004.
[38] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming, 103(1):127-152, 2005.
[39] Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
[40] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first- order nash equilirria nonconvex-concave smooth min-max problems. SIAM Journal on Optimization, 31(4)22508 2538, 2021.
[41] Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Eduardo Pasiliao Jr. An accelerated linearized alternating direction method of multipliers. SIAM Journal on Imaging Sciences, 8(1):644-681, 2015.
[42] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Mathematical Programming, 185(1-2):1-35, 2021.
[43] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pages 737-746. PMLR, 2016.
[44] Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex concave min- max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.020 2018.
[45] Alain Rakotomamoniy. Direct optimization of the dictionary learning problem. IEEE Transac- tions on Signal Processing, 61(2)):595--556 2013.
[46] Abhishek Roy, Yifang Chen, Krishnakumar Balasubramanian, and Prasant Mohapatra. Online and bandit algorithms for nonstationary stochastic saddle-poin optimization. arXiv preprint 1rXiv:1912.001698, 2019.
[47] Arun Suggala and Pranceth Netrapalli. Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games. Advances in Neural Information Processing Systems, 33 33:22316 1--2226, 2020.
[48] Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
[49] Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-lopp alternatig gradi- ent projection algorithm for nonconvex- concave and Sonvex-nonconcave minimax problems. Mathematical Programming, pages 1-72, 2023.
[50] Huiling Zhang, Junlin Wang, Zi Xu, and Yu-Hong Dai. Primal dual alternating proximal gradient algorithms for nonsmooth nonconvex minimax problems with coupled linear constraints. arXiv preprint arXiv:2212.046677 2022.
[51] Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. single-loop smoothed gradient descent-ascent algorithm for nonconvex-concat min-max problems. Advances in neural information processing systems, 33:7377-7389, 2020.
[52] Xuan Zhang, Necdet Serhat Aybat, and Mert Gurbuzbalaban. Sapd+: An accelerated stochastic method for nonconvex-coneave minimax problems. arXiv preprint arXiv:2205. 2022.
[53] Renbo Zhao. Accelerated stochastic algorithms for convex-concave saddle-point problems. Mathematics of Operations Research, 1733):143-1447 2022.
13


Reviews:
[{"review_id": "GwEGiWNkyf", "reviewer": "Reviewer_RF27", "summary": "This paper proposes two Frank-Wolfe (FW) based algorithms for solving a class of nonconvex-(strongly) concave saddle point problems. The proposed algorithms are among the first projection-free methods with convergence guarantees for such problems as authors claimed. The paper uses regularization and nested approximation techniques to deal with the nonsmooth component, and apply it to the primal-dual scheme.  Shortly, it approximates the nonsmooth function $f(x)$ by $\\mu$ in convex-concave setting.  If the objective function is strongly concave in $y$, the regularization can be avoided by setting $\\mu=0$. In terms of novelty, the techniques used in this paper are common, and the analysis seems quite classic to me. However, this simple combination still brings interesting results. I think this is a very good and well written paper, and it has made a great contribution. Therefore, I suggest accepting this paper, but I may change my perspective based on other comments.\n", "questions": "The four theorems proposed in this paper said that \"there exists $t\\in\\{\\cdots\\}$ such that ... satisfy the following bounds\". Does this mean that only a limited amount of iterations satisfies the boundary? Is this measure reasonable and what is its practical significance?", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality. This paper is a good combination of the regularization technique and Frank-Wolfe method. This allows to obtain a single-loop projection-free method with cheaper computational cost for the nonconvex-concave problem. \n\nQuality. As far as I see, the proofs are correct. Experiments show the advantage of the projection-free methods. It would be better to add another simulation example for situations where projecting on constraints $X$ and $Y$ are difficult.\n\nClarity. The paper is easy to understand and the results are clearly stated and well-organized. I would like to suggest the authors to double check language, symbols, and definitions. For example, \"problem 1\" should be changed to \"problem (1)\", and $\\mathcal{G}_X(\\bar z)$ should be changed to $\\mathcal{G}_X(\\bar x,\\bar y)$ in Definition 2.1.\n\nSignificance.  This paper considers a class of nonconvex-concave saddle-point problems, which widely exists in robust optimization, reinforcement learning and adversarial learning. Given existing results, the main contribution of this paper are about solving such problems via projection-free schemes, which reduce the computational complexity in dealing with the problem with structured complicated constraint set, such as nuclear norm ball.  The proposed methods can be useful in practice because of its cheaper computational cost and ability to solve the problem with complicated constraint sets. ", "weaknesses": "The convergence requirement of the fully projection-free method R-PDCG  is that the set $Y$ is strongly convex, which is very limited in practical applications. If this assumption can be removed while achieving faster convergence performance (comparable to projection based methods), it would be a better result. In addition, the value of step size $\\tau_k$ and the parameter $\\mu_k$ is related to the total iteration $K$. If the total number of iterations is large, this will result in a small step size of the algorithms and slow convergence. It would be better to improve the step size $\\tau_k$ to a constant that is independent of the total number of iterations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1\nAdd an example where projecting on constraints are difficult**\n\n**A1**\nThank you for your suggestions. We will add more experiments to the revised manuscript. Specifically, we have implemented our proposed algorithms to address the Robust Multiclass Classification example and have compared the results with those of competitive schemes. (see the attached PDF file)\n\n---\n\n**Q2 The convergence of R-PDCG required the set $Y$ to be strongly convex, which is very limited in practical applications. Can this assumption be removed?**\n\n**A2** \nThe strong convexity for set $Y$ plays a critical role in our convergence analysis which is closely related to the analysis of FW-type methods.\n\nTo gain a deeper understanding of this assumption, it is helpful to examine the convergence results of FW-type methods for solving strongly convex minimization problems. Classical studies on FW-type methods have shown that, unlike projection-based methods, strong convexity of the objective function does not necessarily lead to an accelerated rate (faster than $\\mathcal O(1/K)$) [R1]. Achieving a faster rate often requires imposing additional assumptions (see [31]), such as the existence of a solution in the interior of the domain or a uniform lower-bound on the norm of the gradient of the objective function at the solution.\nIt is important to note that the extension of most of these assumptions to the min-max problems may not be a reasonable assumption since the solution set corresponding to the maximization problem $\\mathcal Y^\\star(x)=\\hbox{argmax}_{y\\in Y}\\mathcal L(x,y)$ as well as the gradient at the maximizer $\\nabla_y\\mathcal L(x,y^\\star(x))$ changes with respect to $x$. Consequently, our novel analysis using the relatively mild set of assumptions led to convergence results that appeared for the first time in the literature for the considered setting. \n\nOur motivating examples along with Remark 2.8 underscores the significant relevance of our assumption in various machine learning applications. In Section 5 of reference [31], a comprehensive explanation of diverse examples and their applications is provided which further emphasizes the practical implications of our work.  We would also like to mention that the applications of strongly convex set even goes beyond machine learning and it has also a subject of interest in optimal control theory [R2].\n\nIn our paper, we show two specific applications satisfying the strongly convex set assumption. The Continual Dictionary Learning example in our paper effectively exhibits the application of strong convexity of the set $Y$ as it includes an $\\ell_2$-norm ball constraint. For the Robust Multiclass Classification example, the constraint of the maximization is the intersection of simplex set and divergence measure constraints. Indeed, one can relax the simplex constraint using the splitting technique and Fenchel duality. The resulting equivalent saddle point problem has a maximization constraint of $Y=${$y:V(y,\\frac{1}{n}\\mathbf 1_n)\\leq \\rho$}.\nwhich is only described by the divergence measure constraint. In some popular examples such as the Pearson Chi-square divergence, i.e., $V(y,\\mathbf{1}_n/n)=||ny-\\mathbf{1}_n||^2$, $Y$ satisfies the assumption of strongly convex constraint set. We will add a more detailed discussion in this regard to the revised manuscript. \n\n[R1] Lan G, Zhou Y. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization. 2016;26(2):1379-409.\n\n[R2] Veliov VM, Vuong PT. Gradient methods on strongly convex feasible sets and optimal control of affine systems. Applied Mathematics \\& Optimization. 2020 Jun;81:1021-54.\n\n---\n\n**Q3 The value of $\\tau_k$ and $\\mu_k$ is related to the total iteration $K$.** \n\n**A3**\nPlease note that the step-size $\\tau_k$ and parameter $\\mu_k$ can be equivalently selected in terms of the user-specified accuracy $\\epsilon>0$. Specifically, in Corollary 4.3, we have $\\mu=\\mathcal O(\\epsilon)$ and $\\tau=\\mathcal O(\\epsilon^5)$. In Corollary 5.2, we find $\\mu=\\mathcal O(\\epsilon)$ and $\\tau=\\mathcal O(\\epsilon^3)$. Therefore, these parameters can be set according to the user-prescribed parameter $\\epsilon$. We will modify these parameter selections in the Corollaries accordingly for further clarification. \n\n---\n\n**Q4 The theorems said that \"there exists such that $t\\in ...$ satisfy the following bounds\". Is this measure reasonable and what is its practical significance?**\n\n**A4**\nThank you for raising this question. In our convergence analysis, we demonstrated that after performing $K$ iterations, our proposed methods guarantee that at least one of the iterations in $\\{(x_k,y_k)\\}_{k=1}^{K}$, say $(x_t,y_t)$, satisfies $\\epsilon$-gap criterion, i.e., $\\mathcal G_Z(x_t,y_t)\\leq \\epsilon$.  \nWe highlight that this criterion is indeed easy to track during the course of the algorithm. In particular, one can track the values $\\mathcal G_Z(x_k,y_k)=\\langle \\nabla_x \\mathcal L(x_k,y_k),x_k-s_k\\rangle + \\langle \\nabla_y \\mathcal L(x_k,y_k),p_k-y_k\\rangle$ without any additional cost at each iteration until it reaches or falls below the desired accuracy $\\epsilon>0$."}, {"review_id": "IiZzWaUbjV", "reviewer": "Reviewer_WRhg", "summary": "This paper proposed two projection-free algorithms for solving smooth nonconvex- (strongly) concave saddle point problems. The authors showed that the convergence rates of the proposed algorithms matches the state-of-the-art convergence rate of projection-based methods. Experimental results on dictionary learning verify that the proposed algorithms show great advantage in terms of training time compared to existing projection-based methods.", "questions": "1. In the related work section, I would recommend the authors to discuss the works on projection-free methods for solving bilevel optimization. Since saddle point problem can be viewed as a special case of bilevel problem, methods proposed for solving bilevel problems should be applicable for SP problems. \n\n2. The result in line 247 needs a reference. I believe it is related to Danskin's Lemma.\n\n3. In the experiment part, I noticed that the one-sided projection-free method CG-RPGA has better performance in terms of training time compared with the fully projection-based method R-PDCG. The authors argue that this matches the convergence rates. I'm not sure about this argument, because the convergence rates are in terms of number of iterations and time per-iteration is obviously different for each methods. I think the training time plots are trying to verify that even AGP has the same convergence rate as CG-RPGA, AGP is slower mainly due to the projection oracle. If the authors would like to verify the different convergence rates of CG-RPGA and R-PDCG, a plot of gap function and iteration number is more appropriate.", "limitations": "Limitations are well discussed in the last section of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The motivation and contribution of this paper are clear. Projections in algorithms could be problematic in practice and potentially slow down the training. This work fills this gap in nonconvex-(strongly) concave saddle point problems.", "weaknesses": "I do not see any major weakness, but I do have some questions. Please see the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 It is recommended that the authors discuss the works on projection-free methods for solving bilevel optimization.** \n\n\n**A1** Thanks for the great suggestion. There is indeed a connection between bilevel optimization and saddle point (SP) problems and we will add the related work on bilevel optimization in the revised manuscript. However, it is important to note that most of the existing methods for solving bilevel optimization problems consider an additional assumption on the lower-level objective function satisfying strong convexity or Polyak {\\L}ojasiewicz (PL) condition. These assumptions in the context of SP problems translate into strong concavity or PL condition for $\\mathcal L(x,\\cdot)$ which cannot handle merely concave setting considered in this paper to the best of our knowledge. \n\n---\n\n**Q2 The result in line 247 needs a reference. I believe it is related to Danskin's Lemma.**\n\n**A2** Thanks for pointing this out. We will add the reference in the revised manuscript. \n\n---\n\n**Q3 In the experiment part, I noticed that the one-sided projection-free method CG-RPGA has better performance in terms of training time compared with the fully projection-based method R-PDCG. The authors argue that this matches the convergence rates. I'm not sure about this argument, because the convergence rates are in terms of number of iterations and time per-iteration is obviously different for each methods. I think the training time plots are trying to verify that even AGP has the same convergence rate as CG-RPGA, AGP is slower mainly due to the projection oracle. If the authors would like to verify the different convergence rates of CG-RPGA and R-PDCG, a plot of gap function and iteration number is more appropriate.**\n\n**A3** \nWe believe that there is confusion regarding the algorithms plots and their convergence rate which we would like to clarify. Note that R-PDCG has a complexity of $\\mathcal O(1/\\epsilon^6)$ while CG-RPGA has a complexity of $\\mathcal O(1/\\epsilon^4)$. From Figure 1 in the paper, it can be observed that CG-RPGA has a faster convergence compared to R-PDCG which matches the complexity results obtained in the paper. Moreover, we believe that the plots in terms of time demonstrate a better picture of comparing these methods. Note that one of the main goals of our paper is to show the advantage of using LMO for certain classes of problems. This is indeed the case when the computational cost of LMO is cheaper than PO which can be observed when comparing the computational cost of these algorithms. Per the reviewer's suggestion, the plots of the algorithms in terms of iteration counters will be added to the paper (see the attached pdf file). "}, {"review_id": "YvpN3k15KK", "reviewer": "Reviewer_dDgV", "summary": "This paper proposes projection-free optimization algorithms for constrained nonconvex-(strongly) concave saddle point problem.\n\nSolution concept: $\\epsilon$-stationarity\n\nTo this end, they propose R-PDCG and CG-RPGA algorithms. \n1. Without projection, iteration complexity for R-PDCG is $O(\\epsilon^{-6})$ for nonconvex-concave and  $O(\\epsilon^{-4})$ nonconvex- strongly concave objective.\n\n2. With projection for the maximization step, iteration complexity for CG-RPGA is $O(\\epsilon^{-4})$ for nonconvex-concave and  $O(\\epsilon^{-2})$ nonconvex- strongly concave objective.\n\nThey illustrate the results through experiments. \n", "questions": "\n1. Could you comment on the optimality of the bounds, i.e., how tight are the bounds?\n\n2. Could you highlight the novelties required for the proof beyond Lemma 4.1, and Lemma B.1?\n\n3. In the experiments, the algorithm does converge to a stationary point, but does stationarity guarantee a good solution for these applications? \n\n4. It seems like if the function is smooth nonconvex-nonconcave, the algorithm should guarantee stationarity. If yes, you should highlight that in the paper. If not, could you explain why? In other words, how important is the convexity?", "limitations": "See \"Weakness\" section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "1. The problem is well-motivated and the applications are clear. \n2. This is the first projection-free method for constrained nonconvex-concave saddle point problem.", "weaknesses": "I am judging the paper by it's theoretical contribution because the applications are supportive of the theory but that's not the main message. \n\n\nThe main weakness of the work is the novelty of the theoretical tools used in the proofs. **Lemma 4.1 + Lemma B.1 are the keys to the proofs. \nThe proof techniques, specifically (12)-(14) (rest of the proof follows by assumptions) are standard steps in any FW-based method for smooth functions (see [14] for example).**\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 Could you comment on the optimality of the bounds, i.e., how tight are the bounds?**\n\n**A1**\nThank you for raising this question. We would like to remark that the lower bound complexity for finding an $\\epsilon$-stationary of the problem (1) in nonconvex-concave setting is not known yet. However, we comment that the complexity of our proposed algorithm CG-RPGA matches with the state-of-the-art single-loop algorithms (see [13]). Moreover, considering the nonconvex-strongly concave setting, our proposed methods match the lower bound complexity of $\\mathcal O(\\epsilon^{-2})$ (see [R1]).  \n\n[R1] Li H, Tian Y, Zhang J, Jadbabaie A. Complexity lower bounds for nonconvex-strongly-concave min-max optimization. Advances in Neural Information Processing Systems. 2021 Dec 6;34:1792-804.\n\n---\n\n**Q2 Could you highlight the novelties required for the proof beyond Lemma 4.1, and Lemma B.1? The proof techniques, specifically (12)-(14) (rest of the proof follows by assumptions) are standard steps in any FW-based method for smooth functions (see [14] for example).**\n\n\n\n**A2** That's a great question. \nThe novelty of our methods lies in addressing the maximization component of the problem as a parametric optimization problem: $\\max_{y\\in Y} \\mathcal L(x,y)$. Our convergence analysis goes beyond established methods, showcasing new and valuable insights. Notably, our analysis introduces new intermediary steps, exemplified by Lemma 4.1. Within this lemma, we illustrate how the suboptimality of the regularized objective function $\\mathcal L_\\mu(x_k,\\cdot)$ can be diminished within the bound of the error term $\\mathcal E(\\tau)$. These new steps lead to new results that appear for the first time in the literature (see Theorem 4.2 and 5.1). Although some of the analysis steps resemble the standard analysis of FW-type methods, we present unique inequalities. An illustration of this is equation (17), which emerges as a consequence of proving the technical Lemma B.1. This enriches the scope of our findings and distinguishes our work in this domain.\n\n---\n\n**Q3 In the experiments, the algorithm does converge to a stationary point, but does stationarity guarantee a good solution for these applications?**\n \n\n**A3**\nThank you for sharing your feedback. In our paper, all of our proposed methods achieve an $\\epsilon$-game stationary gap. The relation between $\\epsilon$-game stationary and other $\\epsilon$-stationary points of saddle point problems have been studied extensively in [R2]. For instance, in the Dictionary Learning example considered in our paper an $\\epsilon$-game stationary solution leads to an $\\epsilon$-infeasibility and reduction of the objective loss function. This observation aligns perfectly with our primary goal of Dictionary Learning.\n\n[R2] Li J, Zhu L, So AM. Nonsmooth Composite Nonconvex-Concave Minimax Optimization. arXiv preprint arXiv:2209.10825. 2022 Sep 22.\n\n---\n\n**Q4 It seems like if the function is smooth nonconvex-nonconcave, the algorithm should guarantee stationarity. If yes, you should highlight that in the paper. If not, could you explain why? In other words, how important is the convexity?** \n \n\n**A4**\nWe are a bit puzzled by the reviewer's question. It would be great if the reviewer can provide more details about the question. The definition of the stationary solution is presented in Definition 2.3 of the paper and we provide a gap function in Definitions 2.1 and 2.2 to measure an $\\epsilon$-stationary solution of the saddle problem. Due to the lack of convexity assumption, our only hope is to guarantee a stationary solution which is stated in the results of the paper (see Corollary 4.3 and 5.2). "}, {"review_id": "OH8gAP36Ui", "reviewer": "Reviewer_LwGk", "summary": "This paper investigates algorithms for constrained saddle point (SP) problems where the objective function is nonconvex-concave and smooth. Existing methods are usually projection-based and this paper focuses on developing single-loop projection-free algorithms which only use linear minimization oracles. \n\nIn particular, this paper provides convergence guarantees for nonconvex-concave SP problems and nonconvex-strongly concave SP problems. This paper also investigates one-sided projection-free methods which can achieve an improved convergence matching the SOTA results for projection-based methods.", "questions": "See the \"Weaknesses\" part.", "limitations": "The authors addressed the limitations adequately.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written and easy to follow. The contributions of this paper are also straightforward: developing projection-free algorithms for saddle point problems and providing convergence guarantees for the proposed methods. By considering the LMO-PO oracle, the rate obtained matches the SOTA convergence of projection-based algorithms.", "weaknesses": "1) When analyzing the convergence guarantees for the R-PDCG method, the author also assumes that Y is S-Convex set. Is this condition inevitable? Also, the rate for R-PDCG is slightly worse than projection-based methods, is this rate improvable, or it is already optimal for projection-free algorithms?\n2) It seems a bit strange that the experiment results are shown in the Introduction part. The paper would be more convincing if the authors can present more extensive experiments and additional numerical results.\n3) It seems that parameter $\\mu$ and $\\tau$ are related to parameter $K$; how to set $K$ in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 When analyzing the convergence guarantees for the R-PDCG method, the author also assumes that Y is S-Convex set. Is this condition inevitable? Also, the rate for R-PDCG is slightly worse than projection-based methods, is this rate improvable, or it is already optimal for projection-free algorithms?**\n \n\n**A1**\nThank you for raising this question. \nWe would like to remark that the lower bound complexity for finding an $\\epsilon$-stationary of the problem (1) in nonconvex-concave setting is not known yet. However, the complexity of our proposed algorithm CG-RPGA matches with the state-of-the-art single-loop algorithms (see [13]). \nOn the other hand, classical studies on FW-type methods have shown that, unlike projection-based methods, strong convexity of the objective function does not necessarily lead to an accelerated rate (faster than $\\mathcal O(1/K)$) [R1]. Therefore, we conjecture that our complexity result for R-PDCG is indeed optimal. Achieving a faster rate often requires imposing additional assumptions (see [31]), such as the existence of a solution in the interior of the domain or a uniform lower-bound on the norm of the gradient of the objective function at the solution.\nIt is important to note that the extension of most of these assumptions to the min-max problems may not be reasonable since the maximization problem is parameterized by the minimizer variable $x$. Consequently, our novel analysis using the relatively mild set of assumptions led to convergence results that appeared for the first time in the literature for the considered setting. \n\n[R1] Lan G, Zhou Y. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization. 2016;26(2):1379-409.\n\n---\n\n**Q2 It seems a bit strange that the experiment results are shown in the Introduction part. The paper would be more convincing if the authors can present more extensive experiments and additional numerical results.**\n\n\n\n**A2**\nThank you for your suggestions. We will add more experiments to the revised manuscript. Specifically, we have implemented our proposed algorithms to address the Robust Multiclass Classification example and have compared the results with those of competitive schemes. As evident in the attached PDF file, our methods outperform the others, highlighting the advantage of utilizing a projection-free approach. Furthermore, as suggested by the reviewer, we will incorporate a ``Numerical Experiments\" section in the revised manuscript and relocate the plots to this section.\n\n---\n\n**Q3 It seems that parameter \n $\\mu$ and $\\tau $ are related to parameter $K$; how to set $K$\n in practice?**\n \n\n**A3**\nThank you for bringing up this point. Please note that the step-size $\\tau_k$ and parameter $\\mu_k$ can be equivalently selected in terms of the user-specified accuracy $\\epsilon>0$. Specifically, in Corollary 4.3, we have $\\mu=\\mathcal O(\\epsilon)$ and $\\tau=\\mathcal O(\\epsilon^5)$. In Corollary 5.2, we find $\\mu=\\mathcal O(\\epsilon)$ and $\\tau=\\mathcal O(\\epsilon^3)$. Therefore, these parameters can be set according to the user-prescribed parameter $\\epsilon$. We will modify these parameter selections in the Corollaries accordingly for clarification."}, {"review_id": "oh4ooInVyD", "reviewer": "Reviewer_cP1u", "summary": "This paper studies the constrained nonconvex-concave minimax problem. This problem has been studied in several papers in the literature, but this paper proposes a projection free (single loop) algorithm to solve this problem.", "questions": "See above", "limitations": "See above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed algorithms are interesting and extend Frank-Wolf type methods to the nonconvex setting. ", "weaknesses": "1. The authors have made some effort into explaining why the FMO oracle might be much more computationally efficient as compared to a projection onto a set. The motivating example seems to be that of the nuclear norm constraint. Can the authors describe in a little more detail as to why this is the case for this constraint. It would make the paper more complete and provide motivation to study projection free methods.\n\n2. Once again, the motivating example of the nuclear constraint does not seem to be addressed in the assumption of $\\alpha$-strongly-convex sets. Are these constraints not strongly convex? If this is the case, then there seems to be a mismatch between the motivating examples and the assumptions. \n\n3. What is the relation between the strong convexity of the set and the strong convexity of the objective function? For example, if the inner problem is strongly concave (like in the setting of Theorem 4.4), do we still need to assume the strong convexity of the constraint set?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1 The authors have made some effort into explaining why the FMO oracle might be much more computationally efficient as compared to a projection onto a set. The motivating example seems to be that of the nuclear norm constraint. Can the authors describe in a little more detail as to why this is the case for this constraint. It would make the paper more complete and provide motivation to study projection free methods.**\n\n**A1**\nThat is an excellent question. Please note that solving a linear optimization problem over the nuclear norm ball requires computing only a single pair of singular vectors corresponding to the largest singular value, whereas computing a projection onto the nuclear norm ball demands a complete SVD decomposition. The computational cost of latter operation is $\\mathcal O(kd\\min(k,d))$, while the computational cost of the former one is $\\mathcal O(\\nu \\mbox{ln}(k+d)\\sqrt{\\sigma_1}/\\sqrt{\\epsilon})$, where $\\nu\\leq kd$ and $\\sigma_1$ are the number of nonzero entries and the top singular value of $-\\nabla_x\\mathcal L(x,y)$, respectively, and $\\epsilon$ is the accuracy (see [R1] for more details). Therefore, in this example, LMO is considerably more cost-effective to compute than the projection method. We will add this discussion to the revised manuscript.\n\n[R1] Combettes CW, Pokutta S. Complexity of linear minimization and projection on some sets. Operations Research Letters. 2021 Jul 1;49(4):565-71.\n\n---\n\n**Q2 Once again, the motivating example of the nuclear constraint does not seem to be addressed in the assumption of $\\alpha$-strongly-convex sets. Are these constraints not strongly convex? If this is the case, then there seems to be a mismatch between the motivating examples and the assumptions.**\n\n\n\n**A2**\n Please note that we only require the strong-convexity set assumption for the maximization problem, i.e., set $Y$. In both motivating examples, the nuclear norm constraint is used for the minimization part of the objective function, where we do not require strong convexity of the constraint set assumption. More specifically, the Continual Dictionary Learning example in our paper effectively exhibits the application of strong convexity of the set $Y$ as it includes an $\\ell_2$-norm ball constraint. \n Additionally, for the Robust Multiclass Classification example, the constraint of the maximization is the intersection of simplex set and divergence measure constraints. Indeed, one can relax the simplex constraint using the splitting technique and Fenchel duality. The resulting equivalent saddle point problem has a maximization constraint of $Y=${$y:V(y,\\frac{1}{n}\\mathbf 1_n)\\leq \\rho$}\nwhich is only described by the divergence measure constraint. In some popular examples such as the Pearson Chi-square divergence, i.e., $V(y,\\mathbf{1}_n/n)=||ny-\\mathbf{1}_n||^2$, $Y$ satisfies the assumption of strongly convex constraint set. We will add a more detailed discussion in this regard to the revised manuscript. \n\n---\n\n**Q3 What is the relation between the strong convexity of the set and the strong convexity of the objective function? For example, if the inner problem is strongly concave (like in the setting of Theorem 4.4), do we still need to assume the strong convexity of the constraint set?**\n \n\n**A3**\nThe definitions of 'strongly convex set' and 'strongly convex objective function' are distinct from each other. For Algorithm R-PDCG, even in strongly-concave setting, we still need the strong convex set for the maximization problem. This assumption plays a critical role in our convergence analysis which is closely related to the analysis of FW-type methods.\n\nTo gain a deeper understanding of this assumption, it is helpful to examine the convergence results of FW-type methods for solving strongly convex minimization problems. Classical studies on FW-type methods have shown that, unlike projection-based methods, strong convexity of the objective function does not necessarily lead to an accelerated rate (faster than $\\mathcal O(1/K)$) [R2]. Achieving a faster rate often requires imposing additional assumptions, such as the existence of a solution in the interior of the domain or a uniform lower bound on the norm of the gradient of the objective function at the solution.\nIt is important to note that the extension of most of these assumptions to the min-max problems may not lead to a reasonable assumption since the solution set corresponding to the maximization problem $\\mathcal Y^\\star(x)=\\hbox{argmax}_{y\\in Y}\\mathcal L(x,y)$ as well as the gradient at the maximizer $\\nabla_y\\mathcal L(x,y^\\star(x))$ changes with respect to $x$. Consequently, our novel analysis using the relatively mild set of assumptions led to convergence results that appeared for the first time in the literature for the considered setting.\n\n[R2] Lan G, Zhou Y. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization. 2016;26(2):1379-409."}]

Author rebuttal:
In response to the questions from reviewers, we have implemented our proposed algorithms to address the Robust Multiclass Classification example and have compared the results with those of competitive schemes. Moreover, in response to the reviewer WRhg, for the Dictionary Learning problem, the plot of the algorithms in terms of iteration counters is added. 

Meta-review: The paper investigates projection-free methods for a class of nonconvex-concave saddle point problems. Two methods are proposed: The first one (R-PDCG) employs FW-type steps (LMO-based) for both minimization and maximization constraints. This method requires the constraint set for the maximization problem to be strongly convex and finds an eps-stationary solution to the saddle point problem in O(eps^{-6}) iterations. The second method (CG-RPGA) employs FW-steps for minimization but projection-based steps for the maximization problem and achieves an eps-stationary solution in O(eps^{-4}) iterations. The rates improve for nonconvex-stronglyconcave problems. 

The reviewing team has collectively voted that the paper surpasses the acceptance threshold. The problem at hand is well-motivated, and the results presented are considered novel. The NeurIPS community has exhibited interest in both FW-type methods and saddle point problems in recent years. Therefore, the exploration of projection-free methods for nonconvex-concave saddle point problems aligns naturally. On the weaker side, the primary limitation lies in the requirement of a strongly convex set for the fully projection-free variant (referred to as R-PDCG). Several reviewers have highlighted this as a restrictive assumption in practical scenarios. Although the authors reference (Garber & Hazan, 2015) for a list of examples where this assumption holds, I agree with the reviewers that the number of applications meeting the criteria of a strongly convex constraint set, easy-to-solve linear minimization, and challenging projection is somewhat limited. Whether similar guarantees can be achieved without a strong convexity assumption on the constraints remains an interesting open problem.
Decision: Accept (poster)