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.
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.
Quality. 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.
Clarity. 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.
Significance. 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.
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?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.