- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies the Newton methods under Lipschitz continuity of the preconditioned Hessian. Such condition generalizes the Anisotropic smoothness for gradient methods and can be reduced by the -smoothness of . This paper propose methods with local superlinear convergence rates and global convergence rates for convex and nonconvex settings. The paper is well-motivated.
Critical strengths
-
The setup studied in this paper is interesting. The generalized smoothness on the preconditioned Hessian is weaker than the classical Hessian smoothness studied in the existing literature. It also covers several important settings. Thus, it is meaningful to develop Newton's methods under this setting.
-
The convergence analysis is sound. The paper provides convergence guarantees for both strongly-convex, convex, and nonconvex settings.
Critical weaknesses
-
It remains unclear how to efficiently solve the subproblem for the nonconvex setiing. The current analysis only provide well-definedness of the solution of the subsolver. However, it remains unknown how to solve it. Can the authors present the detailed subroutine of how to solve the problem and the convergence analysis?
-
Although the quasi-self-concordant (or (L_0,L_1)-smoothness) can lead to the current assumpion, I am wondering if there exists some practical settings that satisfy the current assumption 2.2 but does not satisfy (4)? In addition, I am curious about the cost of computing the H(x) in practice.
Questions for authors
See the weakness part.
2 comments
Thank the authors for their response. I will update my score accordingly
Dear Reviewer,
Thank you for your review. We are happy to learn that you found our work interesting and sound. Below we address your concerns.
The subproblems for the preconditioned Newton methods (Algorithms 2 and 3) can be solved efficiently by applying minor modifications to the standard Lanczos-Krylov techniques for cubic-regularized Newton methods. The high-level idea was already described in Lines 314-323, but we acknowledge that the manuscript would benefit from a more detailed description. For that reason, we have added the new appendix E, which discusses this in detail and highlights the minor modifications needed to handle the preconditioned subproblems.
Condition (4) is a sufficient condition for Assumption 2.2, but not a necessary condition. We have included explicit example for this in the revised manuscript (Example 2.9).
The computational cost of solving the Newton system is discussed in detail in Lines 125-136. In essence, the preconditioned Newton system is equivalent to the original Newton system with a modified right hand side. For the references used in this work (isotropic and separable) this right hand side can be computed efficiently such that the dominant computational cost remains solving a system with the same Hessian ∇2f. Overall, this results in a very minor overhead. A similar idea holds for the regularized Newton systems, cf. (5) and (6). Explicitly computing H(x) is more expensive, but this not required in our algorithms.
We hope this adequately addresses your concerns and would greatly appreciate a reconsideration of our work.