- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies an augmentation of randomized subspace Newton methods and the question whether it is possible to recover local superlunar convergence without additional restrictive assumptions, such as rank-deficient structure.
The authors answer this question affirmative by extending the randomized subspace with a single anchor direction, which is approximated via a randomized Kaczmarz-type procedure, which they term "Anchored Randomized Subspace Regularized Newton" (ARS-RN).
The main theoretical contribution consists of the local convergence analysis, which shows superlunar convergence under logarithmically increasing number of inner Kaczmarz iterations and local-strongly-convex assumptions.
Empirical results on a synthetic strongly convex logistic regression problems as well as real-world convex ERM problems on multi-label regression, binary logistic regression and softmax regression complement the theoretical results, showing that under suitable choices of s, r, and T ARS-RN can also lead to practical improvements.
Critical strengths
The theoretical result of recovering local superlinear convergence without rank-deficient assumptions is novel to the best of my knowledge and shows that randomized-subspace Newton-type methods do not inherently are limited to a local linear convergence rate.
Critical weaknesses
My main concern is regarding the additional cost of the random Kaczmarz iterations and the resulting overhead that it induces. While the authors dedicate a section on the HVP-based computational cost per-outer-iteration and also dedicated another section in the Appendix on "A unified base-point cost model" comparing RSRNM to ARS-RN, I am not sure whether the inner random Kaczmarz iterations are hiding overall computational costs. Can the authors perhaps elaborate on this?
Questions for authors
-
Thank you for providing such a detailed comparison of RSRNM to ARS-RN in terms of their overall computational complexity. Can you also make a similar comparison for the cubic regularized model?
-
The theoretical results require a logarithmically increasing for local superlinear convergence, while the experiments shown in the main paper are only with fixed . Have you also conducted experiments with logarithmically increasing and how do they compare to constant and other schedules of in terms of time and iteration complexity?
-
ARS-RN introduces two new hyperparameters to randomized subspace Newton methods, r and T. As seen in the experiments, these can lead to quite different convergence behavior depending on the specific problem. Can you perhaps provide some intuition on how to choose these hyperparameters, and on which properties of the problem they depend on?
We thank the reviewer for the detailed review and constructive comments. We address each question and concern below.
(Q1) "Can you also make a similar comparison for the cubic regularized model?"
Following the reviewer's suggestion, we have added a comparison of the total computational costs of ARS-3RN and RS-3RN.
Details are provided in Appendix G, in the paragraph "Extension to cubic regularization."
(W2) "My main concern is regarding the additional cost of the random Kaczmarz iterations and the resulting overhead that it induces."
To address this concern, we have conducted a total computational cost comparison that explicitly accounts for the additional cost of the inner randomized Kaczmarz iterations. We derived conditions under which the reduction in outer iterations due to faster local convergence, together with the reuse of derivative information at the same base point, outweighs the additional cost and leads to an overall computational speedup.
Details are provided in Appendix G, in the paragraphs "Total-work comparison with derivative reuse," "Rate-aware total-work comparison," and "Extension to cubic regularization."
(W3) "I am not sure whether the inner random Kaczmarz iterations are hiding overall computational costs. Can the authors perhaps elaborate on this?"
We explicitly account for the additional HVP costs and reduced-matrix operations associated with the inner randomized Kaczmarz iterations. Furthermore, our total computational cost comparison includes the costs of updating and reusing derivative information and solving reduced subproblems. Thus, the additional cost of the inner iterations is not omitted from our analysis. These costs are also included in the computation times reported in our numerical experiments.
Details of the total computational cost comparison are provided in Appendix G, particularly in the paragraphs "HVP-based computational cost," "Total-work comparison with derivative reuse," "Extension to cubic regularization," and "Choice of r and Tk."
(Q2) "Have you also conducted experiments with logarithmically increasing Tk, and how do they compare to constant T and other schedules of Tk in terms of time and iteration complexity?"
To examine the convergence behavior corresponding to the conditions of our local superlinear convergence theory, we conducted additional experiments on a strongly convex synthetic logistic regression problem with dimension n=2000, comparing fixed and logarithmically increasing inner iteration budgets Tk. The results show accelerated local convergence in terms of outer iterations, consistent with our local superlinear convergence theory. However, this does not necessarily translate into shorter computation time.
Details are provided in Appendix H.1 (Figure 4).
(Q3) "These can lead to quite different convergence behavior depending on the specific problem. Can the authors perhaps provide some intuition on how to choose these hyperparameters, and on which properties of the problem they depend on?"
We have clarified the relationship between anchor accuracy and computational cost to provide guidance on choosing the hyperparameters r and Tk. Increasing r can reduce the required Tk, but increases the cost per inner iteration. In the theoretical worst-case cost bound, when HVPs dominate the computational cost, the leading cost is independent of how the computational budget is allocated between r and Tk. However, the practical choice also depends on the Hessian spectrum and implementation details.
Details are provided in Appendix G, in the paragraph "Choice of r and Tk."
We hope our responses have addressed your comments. If there are any further questions or suggestions, we would be happy to address them.