Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents two modified greedy quasi-Newton updates, originally given by Rodomanov and Nesterov [18]. They first consider using these updates to approximate a positive definite Hessian. In particular, for the greedy SR1 update, they introduce a different progress measure, which is maximized over the coordinate bases to yield the vector used in the update. This new measure allows them to obtain a superlinear convergence rate for the Hessian approxiamtion error, where the rate is independent of the condition number $\kappa$. For the greedy BFGS update, they use the same progress measure as in Rodomanov and Nesterov [18], but preconditions the corresponding greedily selected vector with the current Hessian approximation. This yields a linear convergence rate for the Hessian approximation, although their greedy selection for BFGS is rather impractical. In addition to the modified greedy selection strategies, their analyses and rates also apply to a random selection from a spherically symmetric distribution.

Similar to Rodomanov and Nesterov [18], they then apply these results to analyzing the convergence rate of minimizing strongly-convex quadratics, as well as strongly self-concordant objectives. They obtain similar explicit local rates as the previous work, but without the condition number (although the initial, non-local phase still converges linearly with a dependence on $\kappa$).

Experiments on evaluating the newly introduced Hessian approximations show that their methods are quite effective. On a strongly-convex quadratic minimization problem the conclusions are similar. For minimizing a strongly-convex logistic regression problem, the randomized BFGS (with the preconditioned vector) does not perform better than the version from Rodomanov and Nesterov [18], which does not contain the preconditioning. This is true for the two logistic regression problems with different scales of condition numbers. 

main_review: **Strengths**
This work is strong in the sense that they are able to significantly improve existing rates with very simple modifications to an existing algorithm, especially when the improved (local) rates do not depend on the condition number. These results are very interesting and further establish the potential of greedy/random quasi-Newton methods. The paper is easy to read as it mainly follows the same structure as Rodomanov and Nesterov [18], with key differences emphasized appropriately.

**Weaknesses**
One of the drawbacks in the proposed greedy updates is that we now have two different greedy selection rules for SR1 and BFGS, respectively. This is not a main issue in terms of implementation ease, as the two Hessian approximation updates themselves are already different. However, this distinction leads to separate analyses for SR1 and BFGS, which is not as satisfying as the analyses provided by Rodomanov and Nesterov [18], where the three main quasi-Newton updates (SR1, BFGS, DFP) are all covered. Another drawback of this distinction is that, the proposed greedy BFGS is rather impractical, as the authors mentioned that the cost to obtain the vector is $O(n^3)$.  Furthermore, this work does not seem to cover the DFP update, which leaves me wondering whether the new progress measure introduced for SR1 or the preconditioning of the greedy vector in the BFGS case are mainly ad hoc, and whether there is a way to obtain condition number free rates for the general Broyden family.

=== Update ===
I no longer view this as a weakness. Unified analyses would be nice if they also provide tight rates, but it seems to be highly non-trivial for the Broyden family. 

In terms of the related work, the authors should discuss the work of [Jin and Mokhtari, 2020], in which non-asymptotic superlinear convergence rate of the original Broyden family are also proved. In their results, the rates are independent of the problem dimension $n$. In addition, they do not use the greedy/random basis selection, nor do they require access to the diagonal of the true Hessian. 

For the first set of experiments (Figure 1), it would be helpful to see a comparison between problems with varying condition numbers, and compare whether the local convergence of the proposed updates are indeed condition-number independent in practice. 

**Reference mentioned**
[Jin and Mokhtari, 2020] *Non-asymptotic superlinear convergence of standard quasi-Newton methods*


**Minor concerns**
- B.3 Proof of Theorem 3.2
	- This proof invokes Lemma 3.1 (Lemma 3.2 from Rodomanov and Nesterov [18]), while assuming it holds with an expectation. I believe it indeed holds with an application of the operator convexity property of the matrix inverse, but it would help clarify if the authors can include the proof of this lemma under expectation.
- L102: The authors claimed that the progress measure $\sigma_\mathbf{A}(G)=\text{tr}(A^{-1}(G-A))$ might be improper for analyzing the SR1 update. Could you please elaborate why this might be true? Is it because SR1 is a rather good approximation of the exact Hessian, and thus preconditioning the progress measure with $A^{-1}$ could de-emphasize the proximity between $G$ and $A$? And hence the modification to $\tau_\mathbf{A}(G)=\text{tr}(G-A)$ ?
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces new non-asymptotic analysis for quasi-Newton methods, extending recent results on DFP to BFGS and SR1. This is relevant since these two methods produce better Hessian approximations so can converge faster. The authors show that the same rates of convergence can be achieved using either greedy or random updates, which is relevant because greedy updates do not always come for free.
main_review: The paper introduces interesting new analysis which advances the understanding of quasi-Newton methods. Its outline is relatively straightforward. The theoretical results are written in a way that the reader can see its important parts, rather than being overcome with complex constants (which sadly happens quite often in the related literature). The theoretical results are convincing.

On the other hands, a few concerns appear.
First, the clarity of the paper could be improved upon. There are three steps: matrix approximation, then minimisation of a very simple quadratic objective (with fixed Hessian), and finally optimisation of a more. relevant ML objective. Making this gradation more explicit would help the non-expert reader figure out what exactly is being optimised at any given moment, which can prove a bit tricky for now.

Second, a lot of energy and space is devoted to developing theory on very simple problems on which the algorithms will not be applied (if there's a closed form solution, why bother optimising?). It appears at the very end of the paper that on relevant tasks, the new method does not perform better than previous work, which makes the whole endeavour somewhat less relevant.

All told, while this paper is not groundbreaking from a practical standpoint it presents convincing new theoretical analysis and advances our understanding of relevant methods.


Details:
- in the notations using x as the argument and index for the norm definition is confusing.
- In theorem 2.3, the inequality does not seem to imply super but rather sub-linear convergence, unless the G_0 is replaced by G_{k-1}?
limitations_and_societal_impact: I see no additional societal impact to the existing literature on the topic
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work considers the topic of the convergence of quasi-Newton and it builds on top of a series of recent results by Rodomanov and Nesterov. The main two contributions of this paper are: 1) improve the bounds for greedy quasi-Newton methods using a new potential function; 2) to propose a new modification of greedy strategy to obtain better results. The authors consider two settings: unconstrained quadratics and general strongly self-concordant functions (the same settings were considered in prior work). All results are local but this is probably inevitable as quasi-Newton methods approximate Newton's method, which itself is a local method.

I find the results to be very solid and promising. The topic of quasi-Newton methods might get a second breath due to the recent results and I would be glad to see this paper accepted. It does have a small number of typos but I think most of them can be fixed if the authors proofread their work (I hope the authors will do at least a partial pass during the discussion stage). 
main_review: ## Strength
1. This work has a very interesting theory and I particularly appreciate that the authors managed to use a somewhat simpler potential than the one employed by Rodomanov and Nesterov. 
2. I also enjoyed the style of writing and the presentation of the obtained results.
3. I find the topic of quasi-Newton to be quite promising right now, and I hope that this work will inspire further research in this direction.
4. Quasi-Newton methods are widely used in practice but there are still many limitations (such as stochastic extensions of quasi-Newton methods), which helpfully can be addressed once we have a better understanding of their basic variants.


## Weaknesses
1. The paper has a number of typos and the use of articles is not great. I would also appreciate if the authors made some of the sentences shorter as it's hard to read them (for instance, the last sentence in the first paragraph).
2. The experiments are performed on logistic regression, which is often not a good example because it's well-conditioned. Please do similar experiments on the log-sum-exp objective, whose conditioning can be controlled using the smoothing parameter (by smoothing I mean approximation of the maximum function).

## Questions
In the proof of Corollary 4.4 (the part about SR1), the authors combine their guarantees with the guarantees of Rodomanov and Nesterov. However, when greedy strategies are used, I think this is not correct because Rodomanov and Nesterov use a different strategy for selecting u_k. Therefore, I think Corollary 4.4 is not precise in relation to SR1.

## Suggestions
1. As the results from Appendix C are not too long and they allow for a more efficient implementation that needs only O(n^2), I think they should be moved to the main part or at least explained briefly. I think this is particularly important because BFGS is sometimes more numerically stable than SR1.
2. Theorems 4.2 and 4.3 give slightly different results that suggest a better bound for BFGS than for SR1, for instance, in terms of the initial distance to the solution. I suggest adding this to Table 1.
3. Please update the numerical discussion to include log-sum-exp experiments.

## Typos
"quasi-Newton methods, that": no comma here
"Newton methods to certain approximation": "Newton methods with a certain approximation"
"worse long history behavior": "worse long-history behavior"
"Second, we extent": "Second, we extend"
"our analysis to practical scheme": "our analysis to a practical scheme"
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This  paper proposes a tighter local analysis of two popular variants of quasi-Newton methods: BFGS and SR1 with greedy or random choice of directions. It is heavily based on a recent work of Rodomanov & Nesterov, but the analysis is simpler and, most importantly, the guarantees are strictly better (the final bounds do not contain the conditional number $\kappa$).

I think it is really a good paper.

main_review:   Similarly to Rodomanov & Nesterov, the authors first study quadratic case (where the Hessian doesn't change from iteration to iteration) and then consider a general case with strongly self-concordant functions (where the Hessian changes in a controlled way). For SR1 update they use a slightly different (and simpler) measure function, which was key in establishing tighter bounds.



I checked mathematics only partially, mostly related to SR1 update. Although I still need some clarification on that, the major derivations seem correct.


__Proof of Theorem 4.3__:

1. line 451: why $M\lambda_k < 2$? We need it in order to apply Lemma B.2
2. Eq. (44): why do we write the last term in all inequalities as $\eta_k + 2Mr_k$  and not $\eta_k + 2M\lambda_k$ that we obtained in (41)? We need to use the latter anyway in the end of (44).
3. line 465: I find it a bit too quick. Also, we didn't use just (43), some derivations from (44) were also used.

__Proof of Corollary 4.4__:
1. Eq. after line 470: from that inequality we can only obtain the lower bound for $k_1$. Similarly for $k_2$ below.



__Minor comments__:
1. line 40: I think this work is not about closing the gap in the experiments, it is a theoretical work.
2. Algorithm 1, line 2: it is better to write "for $k = 0,\dots, n-1$"
3. I would add the updates for InvSR1 and InvBFGS to the main text.
4. line 171: there is no training process, it is just pure optimization.
5. Section 4: $\kappa$ has to be redefined here, before it was defined only for quadratics.
6. line 244: Is there any particular reason why we use the Frobenius norm for $X$ and not the spectral one (the smaller one)?
7. line 377: it is true, but for me it wasn't obvious.




The English of the paper might be improved, I list some errors below (maybe I didn't understand something).

1. Too many sentences start from "And", often there is no need for it.
2. line 44: "both the methods"
3. line 86: I am not sure what the authors want to say by "benign monotonicity"
4. line 103: "we would reuse"
5. line 111: "from the"
6. line 208: we do not verify theorems in optimization by numerical experiments.
7. line 232-233: "all obtain", "Theorem shows in Figure".
8. line 385 and in other places: not sure what "expectation view" means.
9. line 388: "are spherical symmetry"


limitations_and_societal_impact: 0
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors have applied the methods of greedy/random choice of directions that enable better Hessian approximation (proposed by Rodomanov and Nesterov in [18]) to the quasi-Newton optimization scheme. In this way, the authors have achieved a condition-number free super-linear convergence rate. 
main_review: The paper is clearly written and the mathematics is clear. The only concern is that the improvment over Rodomanov and Nesterov in [18] might be incremental, so it would be a good idea if the authors can accompany the paper with a section indicating explicitly the improvements over Rodomanov and Nesterov in [18]. 
limitations_and_societal_impact: N/A
review_title: null

Meta-review: All reviewers recommended acceptance, and this represents as a non-trivial improvement over the existing results. Please make the changes discussed in the reviews/responses, such as the addition of the log-sum-exp experiment.
Decision: Accept (Poster)