# AISTATS Reviews

## Reviewer 1 (3/3)
Thinks theory is new and experiments are encouraging.
**Main Concerns**
1. Is our algorithm globally convergent?
A. Global explicit rate convergence is unknown: even in QN except recent paper and global convergence is unknown in IQN world. @Spandan do you remember the issue Aryan talked about in getting a global rate? If we could point this out

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

## Reviewer 2 (2/4)
mixed experimental results. issues with reproducibility
**Main Concerns**
1. You did not include time experiments?
A: We can say issues with CPU time, but provide $O(d^2)$ vs $O(d^3)$ per-iter values for large d, and num iters.

2. Why did you not include SAN?
A: Linear rate algorithm like SAG, SAGA, SVRG. We did not compare.

3. Why did you use $p=2.1$ regularization?
A: No good answer. Suggested answer: Is it to make the term in the hessian coming from the regularization to be dependent of the iterate?

4. How is your analysis different from SQN?
A: (Do not mention theta) Mix of these. Challenges

5. You cannot use random iterates?
A: Yes, we allow stochastic sampling in one epoch. Incremental is more general than stochastic sampling.
(Look at this again); unsolved problem

6. Bad writing in some places:
A: accept and can be fixed

7. No explicit epsilon:
A: They also give a suggestion, maybe this is the cost of using implicit updates. On the comparison front, this is still apples and oranges. NIM, we only compare cause this is the best we can hope for. SQN is not comparable, different regime.

8. How did you tune alphas, mu and L? Since you do not have access to them etc.
A: Common in optimization world. The algorithm is robust and not sensitive to alpha (cite needed), a small value like Sharpened.

9. Global convergence?
A: Same as above

------------------------
## Reviewer 3 (3/2)
does not understand the paper; thinks these are new results. issues with reproducibility
**Main Concerns**
1. You did not include time experiments?
A: We can say issues with CPU time, but provide $O(d^2)$ vs $O(d^3)$ per-iter values for large d, and num iters.

2. SIQN vs SQN (O(nd^2)) for one epoch?
A: Explain incremental setting. Tell them in real life you expect faster convergence.

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

## Reviewer 4 (3/3)
issues with reproducibility, appreciates that the work is technical and the results are new

**Major Issues**

1. mixed results (e.g., significant performance in some but not all experiments, missing a baseline)
2. Why is the complete trajectory for IQN not shown on a9a, w8a, and protein?
3. System of equations: How much savings in memory? Reading a matrix is O(d^2) cannot hope to do better.

1. Summary and contributions: Briefly summarize the paper and its contributions. (max. 1000 characters)
The paper proposes an incremental Quasi-Newton algorithm for optimizing finite sums of smooth, strongly convex functions with smooth gradient functions. The method achieves a non-asymptotic superlinear convergence guarantee with an O(d^2) per-iteration complexity (in terms of elementary operations). The method mainly employs "sharpened" updates that combine classical and greedy BFGS updates to mitigate the trade-off of Hessian approximation vs updating along the Newton direction and a constant scaling strategy to maintain the O(d^2) iteration complexity. The authors discuss implementation aspects as well, including how to deal with the O(nd^2) storage complexity.
2. Soundness of theory and theorems, if applicable:
correct
3. Justification of your provided judgment in Q4, if not applicable, put in “N/A”. If your choice is “minor errors” or “major errors”, please specify the details of your concerns. (max. 2000 characters)
There seems to be a minor typo in the first result of Lemma A.2.
4. Significance of empirical results, if applicable:
mixed results (e.g., significant performance in some but not all experiments, missing a baseline)
5. Justification of your provided judgment in Q6, if not applicable, put in “N/A”. If your choice is “mixed results” or “generally not significant”, please specify the details of your concerns. (max. 2000 characters)
On the experimental side, I believe it would be nice to show how the methods respond to changes in the condition number of the Hessian in the quadratic minimization problem and how they respond to d in both cases, as this is an important motivation for second-order methods in the first place. Showing the number of iterations needed to achieve a particular suboptimality or the suboptimality achieved in a fixed number of second-order oracles called on the y-axis against dimension or condition number on the x-axis would be helpful. Also, why is the complete trajectory for IQN not shown on a9a, w8a, and protein?
6. Novelty of the theoretical results and/or empirical methodology:
New results that are significantly different from existing ones
7. Justification of your provided judgment in Q8. If your choice is “known results” or “incremental/combinatorial” please specify the previous publication(s) that support your choice. (max. 2000 characters)
While the proof strategies seem to be similar to Mokhtari (2018), this is to be expected when combining ideas. The work is still very technical.
8. Non-conventional contributions: does the submission contain non-conventional research contributions? Examples: novel ideas with not widely accepted assumptions, new problems and/or tasks, “bridging fields” contributions. (max. 2000 characters)
N/A
9. Clarity: Is the paper clearly written? Consider whether the paper has clearly (1) stated its contributions, notation and results, (2) explained the meaning of the theoretical assumptions, and/or (3) motivated the proposed methodology well with e.g., examples. (max. 2000 characters)
I appreciate the author's attempts at clarity and comprehensiveness, such as the implementation focused Appendices C, D, and F. That said, I find this paper quite difficult to read. It would be nice to actually contain all introduced notation in the notation section, such as sigma from eq (5) or the M used in the definition of beta_t (which I don't think is even defined before, but I assume is the strong self concordance parameter). I believe the quantities K and r should, at least in the statement of results, be indexed with the points that they are defined by. For example, in Corollary B.1, r seems like a constant itself, and it is unclear what alpha is bounding over unless you go back to the definition. Because these points change from proof to proof, it might be easier to read with indices.

More generally, it is difficult to parse what aspect of the algorithms are hyperparameters. Again, I cannot tell if M (which defines beta_t) is a hyperparameter or referring to a property of the objective function, and whether it would be known by the user.

Finally, I see that the "lazy propagation" and "sharpened updates" are the core parts of the algorithm, but they are simply stated in jargon in Sections 1-3 without any explanation, and I have reread 4 many times to try to understand them. I believe Section 4.1 is used to show the "wrong" algorithm as a lead up to the final algorithm, but I find it to be more distracting than helpful. I think the space can be dedicated to helping the reader clearly understand the meaning and effect of lazy propagation/sharpened updates rather than just stating them repeatedly. A similar thing happens with the repeated phrase "scale the individual Hessian approximations just before they are updated in their respective iterations, but treat all memoized quantities as if the approximations are already scaled", which is ultimately opaque to me. I am not an expert on second-order methods, but the appeal can be broadened.
10. Relation to prior work: Is it clearly discussed how this work differs from or relates to prior work in the literature? Any related work missing (if yes provide details in Q13)?
All related works are clearly discussed
11. Additional Comments: add your additional comments, feedback and suggestions for improvement, as well as any further questions for the authors. what would you do differently if you were given the chance to improve the paper? (Optional) (max. 2000 characters)
Is it common to put a closeness condition on the iterates epsilon and conditioning (?) sigma to achieve convergence? Without these conditions, does the algorithm converge linearly/sublinearly to a point until it is close enough? I believe this weakens the result, and I am curious which rates in Table 1 require this condition and which do not.

In 6.2, the statement "It is easy to observe that f(x) is smooth..." should be included as a formal statement and proof in the Appendix. I would not assume anything is easy for the reader. :)

There is apparently no code and the checklist does not answer this point, so I consider this non-reproducible.

I believe for the complexities it should be specified whether they refer to complexity of elementary operations vs those that refer to the number of second-order oracle calls. Is there a version of Theorem 1 in terms of global complexity of elementary operations (instead of number iterations)?

Implementation-wise a lot of effort is put toward being able to compute the the inverse of the Hessian approximation exactly in terms of the inverse of the previous Hessian approximation. How does this compare experimentally (time/memory) of just solving the linear system directly every iteration using conjugate gradient iterations? An exact algorithm might be preferable for analysis, but in practice are inexact approaches sufficient?