Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes an optimization method for empirical risk minimization, combining two techniques from the literature: (1) adaptive sample sizes, where the optimization algorithm is initially ran on a small batch of data, which is then gradually increased by doubling it every couple iterations; and (2) quasi-Newton methods for updating the iterates, such as the BFGS algorithm. The authors leverage recent results on non-asymptotic local convergence analysis of BFGS and show that with an appropriate choice of sample size, the quasi-Newton method will stay in its local convergence regime throughout the optimization, leading to strong convergence guarantees.
main_review: Thank you to the authors for the response and the following discussion. The authors have clarified that superlinearity of BFGS is not needed to establish their results, and they promised to clarify this in the paper, which is good. They also promised to include in the future version of the paper a discussion and empirical results comparing to the prior work of [DMKVW18], which is appreciated. On the other hand, in my view a significant part of the technical novelty of the approach rested on the apparent reliance on the superlinear nature of the BFGS updates, but after a discussion with the authors I concluded that the BFGS Hessian updates have basically no effect on the complexity analysis. This weakens the paper in my view. Thus, all in all, I maintain my score.

First, there is one important related work that is missing from the literature review, namely [DMKVW18]. In fact, that paper is to my knowledge the first to propose using adaptive sample sizes with a quasi-Newton method (in their case, L-BFGS). However, it does not provide a convergence analysis that is specific to any particular quasi-Newton method, which is the main contribution of the present submission. Instead, they show that if for each sample size an optimizer exhibits a convergence rate of at least, say, (1/2)^t, then one should double the sample size at each stage after a constant number of iterations (same as in the present submission). Thus, in principle, one could combine that result with the recent work on local convergence rates of BFGS [21-23] to establish a guarantee analogous to the one obtained by the authors. Of course, this is by no means straightforward, but it should at least be addressed in the submission. I would also be interested to see an empirical comparison of AdaQN with the BET method proposed by [DMKVW18] (ran with L-BFGS), since that can be considered as the closest baseline from the literature.

Second, I take issue with the claim that the proposed approach “exploits the superlinear convergence” of quasi-Newton methods. As the authors discuss, the superlinear convergence of BFGS takes the form of roughly (1/t)^t, where t is the number of iterations performed in one stage of Algorithm 1. However, since the algorithm performs only 3 iterations per stage, then it has no opportunity to exploit superlinear convergence, and all you actually obtain is linear convergence that is independent of the condition number. In fact, the proposed analysis demonstrates that the superlinear convergence doesn’t really matter here, because we reach statistical accuracy before it kicks in. So, I think the authors should not say that the algorithm is “exploiting the superlinear convergence”, but it is ok to say that the algorithm is “exploiting local convergence”, because that is still very much accurate. 

The above discussion about the lack of true superlinear convergence highlights another issue with the algorithm, namely, with the way that the Hessian estimate is being updated. Basically, what the authors propose is that every stage is initialized with the Hessian estimate computed from the smallest sample size (stage 1), then three iterations of BFGS slightly improve that estimate, and then it goes back to the original one. This seems strange. Why not continue with the improved estimate and keep updating it with the BFGS updates? The authors partially address this in Remark 1, pointing out that the initial Hessian estimate is good enough to ensure the local convergence phase of BFGS. But then what is the point of the three updates to the estimate? In fact, I’m quite convinced that the convergence guarantee from Theorem 1 can be shown for the method that just uses the initial Hessian estimate without every updating it. But then, this is no longer BFGS or even quasi-Newton. This is why, in my view, the paper is to a certain extent misrepresenting the nature of why the proposed method achieves the convergence it achieves.

Overall, the strategy of combining adaptive sample sizes with quasi-Newton methods is very interesting, and it is very nice to have a complete convergence analysis of an algorithm that follows that strategy. However, I do have some serious concerns regarding the novelty and presentation of this paper. I am open to reconsider the score if those concerns are addressed in the response.

[DMKVW18] M. Derezinski, D. Mahajan, S. S. Keerthi, S. V. N. Vishwanathan, and M. Weimer. "Batch-expansion training: an efficient optimization framework." In International Conference on Artificial Intelligence and Statistics, pp. 736-744, 2018.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces an adaptive sample size quasi-Newton (AdaQN) method that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The authors also provide convergence analysis to verify the AdaQN method, showing less gradient computation, as well as computational cost compared with previous SOTA methods. The numerical experiments on various datasets also confirm their theoretical findings.

main_review: 
I consider this work gives an effective QN method through interesting intuition using adaptive sample size. Adopting adaptive sample size arises in previous works [1], but not for Quasi-Newton methods, and it indeed provides convincing results. Therefore, I still approve of the originality of this work. Moreover, the work is well-written and has high quality and clarity.

The exploitation of the superlinear convergence of quasi-Newton methods globally is an important problem in my view. As far as I know, previous results build on a small local neighborhood of the optimal solution as the authors mentioned. Therefore, the significance of this work is undoubted.


limitations_and_societal_impact: The only concern is the mismatching of m0 in experiments and theory. At first glance from Theorem 1, I consider such an m0 is only suitable for the well-conditioned case that $N \geq \kappa^2\log d$. However, the numerical experiments show that the initial sample size m0 could be much smaller than the threshold.  Although the authors believe this limitation could be resolved by a tighter non-asymptotic analysis of the BFGS method, I could not believe the explanation from the large gap in theory and experiments. Thus I keep a conservative assessment.

Overall, I am willing to defend my assessment and am unfamiliar with some pieces of related work. Proof details were not carefully checked.

[1] Mokhtari, A., & Ribeiro, A. (2017, December). First-order adaptive sample size methods to reduce complexity of empirical risk minimization. In Proceedings of the 31st International Conference on Neural Information Processing Systems (pp. 2057-2065).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper 
- introduces a new quasi-Newton (QN) algorithm called AdaQN to solve the ERM problem. This method is adaptive since it increases the sample size after few (3) runs of BFGS on a small ERM subproblem. 
- gives its corresponding convergence analysis using a Matrix Bernstein bound
- explains that AdaQN perfoms well because of the superlinear convergence on each subproblem which is possible when $m_0$ is large enough (greater than $\mathcal{O} (\kappa^2 log (d))$ if we leave out $s$)
- provides clear comparison in term of theoretical computational cost is made against AdaNewton in Table 1 
- performs numerical experiments showing the efficiency of the methods on small and medium size problems for l2 regularized logistic regression
main_review: The paper is really clear. 
I really liked the idea of exploiting this local superlinear convergence of the QN methods successively, by having $S_1 \subset S_2 \subset ...$. The paper explains carefully its concepts, its algorithm implementation compares its cost against AdaNewton and then provides an easy to follow convergence analysis.

My first main concern (that I will develop below) is that the condition on $m_0$ that is $m_0 = \Omega (\kappa^2 s\log d)$ is to my opinion completely undermined by the authors. 
My second main concern is the experimental part wish I find unclear and unfair. I develop this below.


Here are some comments, critics and questions:

Style/typo comments:
- 1) lines 37 and 74/75: not consistent writing of Quasi-Newton / quasi-Newton
- 2) line 48, not nice looking line because of \emph
- 3) line 77: missing word before reference [20]
- 4) line 106: ERM already defined earlier
- 5) line 111: $w^*$ is an optimal solution of the expected risk minimization. The authors will agree that $R$ is a function not an optim problem
- 6) line 264: typo, remove "the"
- 6 bis) line 552-553: strangely few lines are not numbered + typo " inequality(notice)" also there at line 570

Minor comments:
- 7) line 77: What did you mean when saying "To exploit quasi-newton methods for the described adaptive sample scheme, however ..." ? To be corrected I think
- 8) line 7 of Algo. 1: a break-line for $y$ would make it way easier to read
- 9) $\mu$ is not really standard for a regularization parameter, I would prefer $\lambda$ then say $\mu \approx \lambda$
- 9 bis) line 373: cite maybe the most recent version of Bottou and Bousquet 2011

Major comments:
- 10) A long comparison is made against AdaNewton, yet very few comparison is made agaisnt other (stochastic) QN methods like L-BFGS, which is known to perform very well in a lost of case, or the more recent K-BFGS ("Practical quasi-newton methods for training deep neural networks", Goldfarb, Ren, Bahamou, 2020) or Stochastic Block BFGS (Stochastic Block BFGS: Squeezing More Curvature out of Data, Gower, Goldfarb, Richtarik, 2016) 
- 11) My main concern (that I will develop below) is that the condition on $m_0$ that is $m_0 = \Omega (\kappa^2 s\log d)$ is to my opinion completely undermined by the authors.  I would have liked a clear explanation about what happens when we are facing a very ill-conditioned problem such that $\kappa = N$ or even worse  $\kappa >> N$. What does AdaQN become in such a case ? Does it become QN with a constant sample size $m\equiv N$ ? In this case isn't it way more costly than 1st order methods ? What about numerical experiments in this case ?
- 12) In Prop. 1 and elsewhere in the paper, you clearly explain that having $S_1 \subset S_2 \subset ...$ is necessary for AdaQN to work. I have been through the proof and I was expecting that you would have to deal with a problem : at each outer loop iteration the points are \textbf{not} sampled independently. How is that it does not appear in your proof ?
- 13) Remark 4: Don't you omit the matrix inversions and the matrix vector product required by AdaQN when comparing it to Katyusha ? In other words, is this comparison of gradient complexity really fair between a first and a second order method ? 
- 14) How can you get a condition number which equals 1 in your experiments ? Normalizing can improve the condition number, but I have never seen such a bound related to just simple normalization.
- 15) It is not clear what is monitored by "time" in your experiments. So I have been into the code and I noticed that the initialization which requires inverting the first hessian is not taken into account... In addition, SAGA is not initialized with a full gradient step, plus SAGA algorithm was launched with a decreasing step size which is unnecessary. This is one of the main advantage of VR methods. This is wat I really doubt about the fairness of the experiments.
- 16) In all your experiments $N$ is at most of medium size, you should have tried on RCV1.binary for instance $N = 600K$ to see if first order methods are still performing poorly compared to AdaQN.
- 17) Regularization parameters in table 2. look way to large... It is not representing the range of lambda used in practice. I would recommend $10^{-4}$ or $10^{-6}$. Moreover we could maybe see this way an experiment with large $\kappa$


Questions:
- 18) Why is AdaQN adaptive since you basically double the sample size at each iteration, so it's not dependent on anything else than the current number of samples m ?
- 19) Why didn't you include L-BFGS in your experiments ? 
- 20) With is your initial point set to 1 in your experiments ?

---------------------------------------------------------------------------------------------------------------

**Update after rebuttal and exchanges with the authors and the other reviewers**

Main concerns I had about experimental settings, I think have been addressed. I think the authors must detail the experimental settings in the appendix such that the community can understand their numerical experiments and really be convinced that the settings are fair. 

Despite the discussion on the practical "leveraging of superlinearity", I finally decide to **increase my score** but only up **to 6**. 


---------------------------------------------------------------------------------------------------------------

**Final words**

In his updated review, reiewer RQBF wrote :

>   [...] after a discussion with the authors I concluded that the BFGS Hessian updates have basically no effect on the complexity analysis.

I agree with him on this point (and I think the authors too). Yet on my side, this discussion does not diminish the ideas nor the quality of the paper. Moreover, as I said above, my concerns about numerical experiments will be addressed in the final version of the paper (with fairer comparisons). My final thoughts about the paper are that despite this concern about superlinarity, it can be very profitable for the QN community and optimizers interested in adaptive mini-batch/sample size. 
Hence, I increase my score to 7 and argue in favor of accepting this paper with one condition : a clear and important remark about this discussion on superlinearity must be added and highlighted.
limitations_and_societal_impact: The authors did not really talk about the case where $m_0$ is in fact large. 
No real experiments for very ill-conditioned problem.
review_title: null

Meta-review: This paper focuses on characterizing rates of convergence for Quasi-Newton method applied to empirical risk minimization. Traditional stochastic Quasi-Newton methods have not enjoyed guarantees that are faster than their first order counterparts. This paper uses an adaptive sampling scheme to achieve global superlinear convergence. All reviewers thought the idea of combining adaptive sampling with Quasi-Newton methods is interesting and appreciated the thorough global convergence analysis. The reviewers did however raise a few concerns including: (1) one reviewer had concerns about the claim that the proposed approach “exploits the superlinear convergence” of quasi-Newton methods, (2) lack of discussion of some related literature, (3) mismatch in m0 between theory and practice, and (4) a variety of other technical discussions. The authors provided a thorough response and the reviewers had a lively discussion with the authors and together. As a result some of the above issues were resolved and some reviewers raised their score. Issue number (1) however remained and that reviewer increased their score contingent on this issue being revised in the final version. I agree for the most part with the reviewers that the paper is interesting and clearly written with nice results. But also concur with them about the technical issues and that claims of exploiting superlinearity are a bit misleading. Therefore I recommend acceptance with the requirement that a clear discussion on superlinearity must be highlighted in the paper.
Decision: Accept (Poster)