Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose a modifications of well-known Quasi-Newton methods for solving strongly-convex-strongly-concave saddle-points problems with Lipschitz gradietns and Hessians. The key algorithmic novelty is in changing the matrix that is inverted. Unlike to Quasi-Newton methods for minimization problems, where the methods approximate the inverse of the Hessian, the proposed methods estimate the squared Hessian. This modification is important for the analysis of the methods.

Following the analysis in the case of minimization [37, 38, 39, 24], the authors derive two-period local convergence results (one period with linear convergence and one period with superlinear convergence) for general random Broyden family with better rates for BFGS and SR1. These rates are similar to the ones known for minimization up to the replacement of $\kappa$ (condition number) by $\kappa^2$. The worsening in terms of $\kappa$ is expected, since the methods use the inverse of the approximated square of the Hessian.
strengths_and_weaknesses: ## Strengths
1. **Novelty and significance.** The results are novel: there are only 2 papers that also propose Quasi-Newton methods for min-max problems (for nonlinear equations), but they consider a different setup and use different ideas. The topic is relevant to ML community. The obtained results are significant.
2. **Clarity.** The results are presented in the clear way, the proofs are also detailed enough and easy to follow. 

## Weaknesses
1. **Bad dependence on the condition number.** The derived results suffer from the squared dependence on the condition number $\kappa$. Although I find the proposed approach of approximating the squared Hessian matrix interesting, it would be interesting to see some discussion about the possibility of avoiding such dependence.
2. **Comparison with [46] and [23] is incomplete.** Although the authors discuss the results and assumptions from the concurent works [23, 46], the explicit comparison of rates is missing. I believe such a comparison of rates should be presented in the text. Moreover, in the experiments, it would be interesting to compare with the method from [23] as well: although in [46] it is shown that the method from [23] is inferior to the one from [46], it is shown on particular problems different from the one considered in this paper. Therefore, for completeness, it is important to compare the proposed methods with the one from [23] as well.
questions: 1. How do the initial conditions from Theorem 3.17 relate to the ones known for the same methods in minimization? How do they relate to the ones from the concurent works [23] and [46]?
2. Line 582: object --> objective
3. Line 587: continuous --> continuity; object --> objective; "that" should be removed
4. Line 626: should be $\frac{\beta}{M} \leq \frac{1}{4L}$. In fact, this is sufficient since in (56) factor $\mu$ in front of $\frac{\beta}{2M}\rho_k^2$ is missing.
5. Inequality (63): how the last inequality is obtained? 


limitations: All assumptions are properly formulated. There are no potential negative social impact, since the work is purely theoretical.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors focus on applying quasi-Newton methods to solve the strongly-convex-strongly-concave saddle point problems. They achieved the explicit local superlinear convergence rates of quasi-Newton methods of Broyden updates. They utilized the technique of estimating the square of the indefinite Hessian matrix instead of the Hessian matrix itself. They also reach the non-asymptotic convergence rate of BFGS method and SR1 method. The authors conduct several numerical experiments on different datasets and these empirical results are consistent with the theoretical results.
strengths_and_weaknesses: This paper has the following strengths in terms of the originality, quality and clarity:

Originality: this paper provides the first explicit local superlinear convergence rates of quasi-Newton algorithms applied to the saddle point problems. This is the main and independent contribution of this paper.

Quality: the authors provides detailed proof in the theoretical section and the consistent empirical results in the numerical experiments section. These empirical results show that the theoretical results are correct in practice.

Clarity: the paper is organized with clear and clean structure and the language is well-organized so that the readers can easily understand the content of this submission.

However, despite the above advantages, the paper has the one weakness in term of the significance:

This submission presented incremental results of the non-asymptotic superlinear convergence analysis of quasi-Newton methods applied to different problems with different backgrounds. All these proof ideas and techniques are based on the previous work and reference as the authors mentioned in the paper. The authors extend the current superlinear convergence results of quasi-Newton methods applied to the general convex optimization problems to the strongly-convex-strongly-concave saddle point problems. Although the theoretical proof is correct and the authors presented the consistent empirical results, this does not change the essence that this work is an incremental analysis based on the previous similar work. Hence in summary, although this submission is with high quality which improves our understanding of explicit superlinear convergence rates of quasi-Newton methods, it is not totally original and 100% independent. This is a submission with good quality but neither very impressive nor very significant enough.

Some other minor weakness includes:

1. The authors should use t as the time index instead of the k. Because k is very similar to the condition number notation $\kappa$. This can lead to misunderstanding.

2. The authors should use d as the notation of the dimension instead of the n. In the numerical experiment section the authors used d. n is mostly used as the number of functions in the main objective function.

3. The authors should use some other upper-class constant such as $K$ or $C$ to denote the Hessian Lipchitz parameter instead of $L_2$. This notation is much more clear and consistent.
questions: The authors didn't mention the specific results for the DFP method. Is it because that the theoretical results of DPF is not as good as BFGS so there is no need to present the part for DFP?
limitations: The authors have presented the limitations of this paper in the final conclusion section.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a randomized Broyden family updates for strongly-convex-strongly concave saddle point problems and show that the algorithm achieves a local superlinear convergence rate. The key idea is to update the square of the Hessian instead of the Hessian itself. Numerical experiments show that the proposed algorithm outperforms classical first-order methods. 
strengths_and_weaknesses: - The authors circumvent the issue of dealing with an indefinite Hessian, which is a nontrival obstacle for saddle point problems, by applying BFGS type updates to the square of the Hessian instead. I am not aware of previous work that have established similar guarantees for quasi-newton methods on saddle point problems, so the analysis presented in this paper can be of interest to the NeurIPS audience. 

- My main concern about this paper is the presentation.  In this current form the notations are very dense and often introduced without much motivation. Section 3.1 is particularly difficult to parse as the authors introduces a number of lemmas in previous papers without clearly laying out a purpose for these lemmas. I think the presentation would be greatly improved if the main results are introduced first, and then the necessary lemmas for proving the main results are presented with some motivation. 

questions: Although the authors do discuss relevant work in the introduction, a related work section is missing from this paper, which makes it unclear which parts of this paper are novel and which parts are mostly based on previous results. Can the authors clarify the key technical difficulties in this paper apart from the need to deal with an indefinite Hessian?
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper adapts greedy quasi-Newton method to saddle point problems. The proposed algorithms are based on estimating the square of indefinite Hessian matrix and turn out to have local superlinear convergence.
strengths_and_weaknesses: The paper is well structured. It is stated clearly for the proposed algorithm that the key is the estimation of squared Hessian. I would like to see a more intensive discussion on how to store the approximate Hessian efficiently. Nevertheless, if all ingredients fit into the memory and are computable, the proposed algorithm is quite efficient, in theory and practice. From all experiments shown in this paper, the proposed algorithms work pretty well eventually. However, in section 5.2, it is better to address more clearly that the objective function satisfies all assumptions. 
questions: Since in the paper authors mentioned two stages convergence behavior, I hope this characteristic can be discussed in the section: experiments. 
limitations: First, this paper requires sufficient smoothness of a strongly-convex and strongly concave function $f$ and proposed algorithm requires the evaluation of squared Hessian, which results in computational complexity. Second, the rate of local super linear convergence is highly related to dimension $n$ which can be very large in practice. If $n$ is large, then the rate will be close to the one for local linear convergence.
review_title: null

Meta-review: metareview: Thank you for your submission to NeurIPS. The reviewers unanimously found the work to address an important, relevant problem, and the paper to be clear and generally well-written. All four reviewers unanimously recommend accepting the paper.

The work has obvious impact for the ML community: the idea of rewriting the Newton update $z_+ = z - H^{-1}g$ in terms of the positive definite squared Hessian $z_+ = z - H^{-2} (H g)$ and then using a quasi-Newton scheme to approximate $H^{-2}$ is immediately intuitive and applicable to a wide range of practical problems. The paper provides a rigorous guarantee that such a quasi-Newton scheme converges superlinearly within a neighborhood of the saddle point. 

Please incorporate reviewer feedback in preparing the camera ready version. In particular, please take care to include the Comparison to Concurrent Work [23, 46] in your response to reviewer MK9.
confidence: Certain
Decision: Accept