Venue: NeurIPS 2022 Conference

Reviews:

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 submission, the authors proposed a new Newton's method called the Affine-Invariant Cubic Newton algorithm (AIC). This novel algorithm is the Newton's method with explicit new step size leading to the global convergence and local convergence. This AIC method can achieve a global convergence rate of $\mathcal{O}(1/k^2)$ which matches the state-of-art global convergence rate. On the other hand, this algorithm can also reach a local quadratic convergence rate which is the best-known local rate of second-order methods. One advantage of this algorithm is that the computation of step size is simple and doesn't need to solve the sub-problem. Another advantage is that the convergence results hold under the assumption that the objective function is affine-invariant, which is a good geometric property. The authors also conduct numerical experiments and the empirical results show that the performance of AIC is competitive with other state-of-art algorithms.
strengths_and_weaknesses: This paper has the following strengths in terms of the originality, significance, quality and clarity:

Originality and significance: this paper provides the first variant of Newton's method that could achieve state-of-art convergence rates in both terms of the global and local convergence for the objective function satisfying the affine-invariant property. And the computation of the step size is not complicated. This is the main and independent contribution of this paper.

Quality and clarity: the authors provides detailed and clear explanations in both the theoretical analysis section and the numerical experiments section. The theoretical proof in the appendix is correct. The empirical results show that the proposed novel algorithm is competitive against other state-of-art methods. The paper is also 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 following weaknesses:

The main issue is that the parameters in definition 2, 3 and 4 are expressed a bit unclear. Is this $L_f$ the same for all assumptions 2,3,4? Or are they different? Then, the authors should use different notations to express them. Also in the Theorem 2 and 3, the authors should mention the exact parameter $L_f$ for the assumptions of weakly-strongly self-concordance and semi-strongly self-concordance.

Another issue is that the authors presented the definitions 2, 3, 4 explicitly and showed the relationship of them. Are these assumptions necessary for the theoretical analysis of the AIC algorithm? Can we obtain the similar results with only the assumption of self-concordance? If these global and local convergence rates also hold for the only assumption of standard self-concordance, then there is no need to create these new assumptions and this submission will be much more clear and simple.

Also, for all these variants of Newton's method, the authors should mention that the computational expense per iteration is $\mathcal{O}(d^3)$ where $d$ is the dimension of the problem. This is because we need to compute the inverse of the Hessian matrix to obtain the step size at each iteration. And this expense is very high, which is the main limitation of the Newton's method. In term of the computational cost per iteration, the proposed new AIC algorithm is the same as all the previous variants of Newton's method.

The last minor issue is that in Algorithm 1, what's $L_H$? Is this a typo and it should be $L_f$?
questions: In the checklist the authors said that they discussed the limitations of this proposed algorithms. Could you please summarize the limitations in one final conclusions section after the numerical experiments section?
limitations: The authors didn't include limitations in the paper. They should add one conclusion section summarizing the paper and discussing any potential limitations and future work directions after the numerical experiments 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: It is well known that Newton's method can fail to converge even for smooth, convex functions. This paper proposes a damped Newton's method with a stepsize schedule such that the method achieves $\mathcal{O}(1/k^2)$ global rate, which matches the convergence rate of Nesterov's cubic regularization method. The main idea is to minimize a cubic upper bound similar to the one used in cubic regularization, but replace the cubic term with a local Hessian norm. 
Compared to previous methods, the proposed algorithm has an explicit formula for the step-size and enjoys fast local and global convergence. 
strengths_and_weaknesses: This article is well-written and offers an overview of potential problems for Newton's method and how these problems were previously addressed. The authors motivate their algorithm, which they call AIC newton, quite naturally and the idea behind the proofs are also nicely communicated. In the end, under certain assumptions, the proposed algorithm is easy to implement and has strong local and global guarantees. However, there are a few issues that prevent me from giving this article a higher score.

 1. The assumptions under which convergence is proved are quite strong. In particular, Theorem 2, which guarantees global convergence, requires that the function is weakly-strongly self-conconrdant and also *convex*. Compare this with cubic newton of Nesterov, which guarantees convergence towards a second-order stationary point for *non-convex* functions at the same rate, only under the assumption of gradient and Hessian lipschitz. The authors does indeed consider a relaxation of the self-concordance assumption, but in the case the convergence rate the prove is slower, and does not match best known results. 

2. The author states that one key advantage of the proposed algorithm is that it has an explicit stepsize and does not require line search, like previous methods. It seems to me that this claim is inaccurate, since computing the step-size requires knowledge of the parameter $L\_f$, which is a constant related to self-concordance. In cubic regularization, for instance, if the Hessian lipschitz constant is also known, then the line search can also be avoided. Therefore, in this regard the proposed method again offers no advantage over cubic newton. 

3. In the numerical experiments, it seems to me that cubic Newton often outperforms the AIC newton, unlike what the authors claim in the intro. However the difference is usually minor and i do not consider this an huge issue. 

In the end, I do think the global convergence of Newton's method is important and interesting for the NeurIPS community. The proposed method, AIC newton can potentially be a useful algorithm, but my main issue is that it has restrictive assumptions and no clear advantage over cubic newton. 



 
questions: - As the authors claim,  one advantage of AIC Newton is that it is affine-invariant. This is indeed a natural consequence of replacing the $\ell_2$ norm by the local Hessian norm in the cubic term. But i'm not sure what is the real advantage here in terms of practical performance? What is the actual benefit of the method satisfying self-concordance?
- In the numerical experiments, the authors say that the parameters $L_f, L_2$ and $\alpha$ are all fine-tuned. How is this done exactly? In general, how would I pick $L_f$ for AIC Newton?
- In terms of per-iteration cost, does AIC Newton offer any advantage compared to cubic Newton of Nesterov? There has been many recent work that reduce the cost of the cubic subproblem [1] [2]. In light of these, how does of real running time of AIC newton compare with cubic Newton?


[1] Carmon, Y., & Duchi, J. (2019). Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM Journal on Optimization, 29(3), 2146-2178.

[2] Cartis, C., Gould, N. I., & Toint, P. L. (2011). Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Mathematical Programming, 127(2), 245-295.
limitations: Yes.
review_title: null

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 paper provide a Newton Method with simple step size and provide an affine-invariance analysis of it with local and global convergence rates.
strengths_and_weaknesses: Pros:
- The paper is very well-written and easy to follow. 
- The contributions are elegant and significant.
- There are compelling numerical experiment.

CCL: this is the best paper in my batch of review.

questions: None.
limitations: None.
review_title: null

Meta-review: metareview: There is general agreement that this paper should be accepted.
confidence: Certain
Decision: Accept