- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proves information-theoretic complexity lower bounds for finding approximate stationary points of nonconvex-strongly-concave (NC-SC) minimax problems. The lower bound matches the convergence rate of SAPD+ from [Zhang et al., 2024] and SPDE from [Zhang et al. 2026] under the bounded variance assumption, which improves the previous results in [Li et al., 2021]. Under the average smoothing setting, the lower bound is new, and it matches the best convergence rate combining SAPD+ from [Zhang et al. 2024] and VR-SPDE from [Zhang et al. 2026].
Critical strengths
The main strength is that the paper addresses an important open theoretical question and derives lower bounds for nonconvex-strongly-concave minimax problems under both the bounded variance assumption and the averaged smooth assumption. All of them match the upper bound in the literature and the lower bound under the second case is new. This is a meaningful contribution to the complexity theory of nonconvex-strongly-concave minimax optimization. Also, the paper is well organized, and I can follow the proofs easily.
Critical weaknesses
My main concern is that the algorithm SAPD+ in [Zhang et al., (2024)] proves the convergence rate under the case where the initial primal dual gap is bounded. However, the paper's construction of the hard case is in the following form: In this case, we have for every . This directly leads to , even though the primal gap is finite. Since the paper claims that the lower bounds match the upper bound, this will substantially weaken its claims. Basically, the matching upper and lower bound are not for the same common class.
The other major point is that the stochastic oracle that is deployed, is more powerful and more general than the gradients of sample losses.
Minor Comments:
- [Zhang et al. (2022b)] and [Zhang et al. (2024)] both refer to the same paper that introduces SPAD+. Please check all the references and delete repeated ones.
- It seems that the is strctly dominated by . Maybe it is better to mention only SPAD+ in Table 1 without the rate of SPAD+(VR).
Questions for authors
Questions For Authors
- Could you prove the tightness of the convergence bound either by constructing a hard instance that satisfies SAPD+’s assumption with or by changing the proof of SAPD+ using only instead?