Escaping Saddle Point Efficiently in Minimax and Bilevel Optimizations

1. My primary concern is the presentation of this paper. For instance:

1-1. In line 230, the author should provide references to support the assertion: "According to previous work $\cdots \cdots$".

1-2. In line 250, the meaning of $v_t$ is unclear. It should be clarified that $v_t$ represents the estimation of the hypergradient and not the partial derivative of $f$ with respect to $x$.

1-3. The purpose of step 13 in Algorithm 1 is unclear and requires clarification.

1-4. In Theorems 1 and 2, the choices for step sizes $\eta$, $\eta_H$, batch sizes $S_1$, $S_2$, period $\rho$, inner loop $K$, perturbation radius $r$, threshold $t_{thres}$, and average movement $\bar{D}$ should be clearly outlined.

1-5. In line 360, definitions for $JV$ and $HV$ should be provided before using them.

2. My primary concern is that the main theorems of this paper (Theorems 1 and 2), which are based on random settings, lack explicit assumptions regarding randomness. Although the authors introduce an assumption about the randomness of the gradient (Equation (13)), I believe such assumptions may be insufficient. It might be necessary to include assumptions about the randomness of function values as well. Furthermore, these assumptions should be included in the main text rather than relegated to the appendix.

3. A comprehensive analysis should compare the complexity results and the adopted assumptions with those of existing methods (Theorems 1 and 2 of this paper).

1. The overall presentation of the article is not clear enough. (1) In Sections 1 and 2, the author mentions numerous algorithms but does not provide a clear classification of them. For instance, the author could consider classifying the algorithms into deterministic and stochastic categories, and further subdividing them into those capable of finding first-order stationary points and those that can identify second-order stationary points. (2) In Sections 4 and 5, the author relies solely on textual descriptions and inline formulas, resulting in a dense presentation that can be challenging to understand. It is advisable for the author to condense the text and appropriately position formulas between lines of the text. If there are concerns about exceeding the article's page limit, I recommend focusing on either the minimax problem or the bilevel problem in the main text, with the other problem placed in an appendix. (3) Compared to existing algorithms, it is unclear where the author's novelty lies. (4) The author does provide commentary on some existing work, but these observations are scattered throughout the article. It is recommended that the author include more structured 'Remarks' to enhance readability.

(1): Usually, for stochastic optimization, we need assumptions regarding noise. However, in the main text and in Theorems 1 and 2, the authors did not state those assumptions. The authors state that their Theorems 1 and 2 actually need additional assumptions in appendix (13) and (57): $||\nabla F(x, y,\xi)-F(x,y)||\leq \delta$ and called it as "bounded variance". However, this is not "bounded variance" and is stronger than the bounded variance assumption that is usually used in stochastic optimization. Could the authors explain why they use this stronger assumption?

(2): The authors never define HV and JV in Theorem 2. Could the authors add the definitions? I assume they are the required numbers of Hessian and Jacobian. Then, in Theorem 2, the authors showed that their algorithm actually needs $O(\epsilon^{-4})$ Hessian and Jacobian. Thus, the actual complexity of their algorithm for bilevel optimization should be $O(\epsilon^{-4})$. If so, the claimed improvement in complexity over previous work and the claimation that their work matches $O(\epsilon^{-3})$ the best result of finding the first-order stationary point would not hold.

(3): The authors said in the abstract: "Specifically, we propose a new algorithm named PRGDA without the computation of second order derivative of the primal function." However, PRGDA for bilevel optimization actually uses the second order derivatives.

1. Table 1 missed some results, Chen et al. also provides stochastic version of their algorithms.

2. The technique seems quite standard and direct, using existing state-of-the-art variance reduced methods for NC-SC problems and the perturbed methods to escape the saddle point of $\phi(\cdot)$. It is quite unclear what is the technical difficulty used in this paper.

3. This paper studies stochastic problems, however, I do not see any assumptions on the variance of the noise in the main theorems or the assumption section.