acceptodds
Withdrawn from ICLR 2027

Anchored randomized subspace Newton method with local superlinear convergence

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Randomized subspace projection techniques offer a scalable approach to Newton-type methods by restricting updates to low-dimensional randomized subspaces. However, unlike classical Newton-type methods, they generally fail to achieve superlinear convergence near a solution. In fact, when the subspace is constructed purely at random, such fast local rates are provably unattainable, even under local strong convexity. We show that this limitation can be overcome by a minimal modification of the subspace construction. Specifically, we augment the randomized subspace with a single anchor direction computed via a randomized Kaczmarz-type procedure. This simple addition improves the alignment of the subspace with local curvature. Under local-strongly-convex assumptions, we establish superlinear convergence for randomized subspace variants of quadratic and cubic regularized Newton methods. Our results demonstrate that fast local convergence is recoverable without abandoning the subspace framework. Numerical experiments further show that the proposed method often achieves improved performance despite the additional cost of computing the anchor.

Primary area:
optimization
Keywords:
randomized subspace methods, Newton methods, randomized Kaczmarz methods, regularized Newton methods, second-order optimization, superlinear convergence, large-scale optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_LVL4OpenReview ↗
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 TkT_k 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 TkT_k for local superlinear convergence, while the experiments shown in the main paper are only with fixed TT. Have you also conducted experiments with logarithmically increasing TkT_k and how do they compare to constant TT and other schedules of TkT_k 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?

1 comment

We thank the reviewer for the detailed review and constructive comments. We address each question and concern below.

  1. (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."

  2. (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."

  3. (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 rr and TkT_k."

  4. (Q2) "Have you also conducted experiments with logarithmically increasing TkT_k, 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=2000n=2000, comparing fixed and logarithmically increasing inner iteration budgets TkT_k. 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).

  5. (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 rr and TkT_k. Increasing r can reduce the required TkT_k, 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 rr and TkT_k. However, the practical choice also depends on the Hessian spectrum and implementation details.

    Details are provided in Appendix G, in the paragraph "Choice of rr and TkT_k."

We hope our responses have addressed your comments. If there are any further questions or suggestions, we would be happy to address them.

Reviewer_bjcpOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Anchored Randomized Subspace Regularized Newton (ARS-RN), which adds an approximate Newton direction to a random subspace to accelerate local convergence. This anchor is computed using warm-started randomized Kaczmarz iterations and Hessian–vector products. Under the stated assumptions, the method retains an O(ε−2)O(\varepsilon^{-2}) global outer-iteration bound and achieves almost-sure local superlinear convergence with logarithmically growing inner iteration budgets. Experiments on logistic and softmax regression demonstrate potential convergence and runtime improvements, although their fixed inner budgets do not directly validate the asymptotic superlinear guarantee.

Critical strengths
  1. Simple, effective anchoring: Adding one approximate Newton direction overcomes the local convergence limitation of purely random subspaces without requiring low-rank objective structure.

  2. Strong theoretical analysis: Establishes almost-sure local superlinear convergence under explicit assumptions while retaining an O(ε−2)O(\varepsilon^{-2}) global outer-iteration bound.

  3. Practical computational design: Warm-started randomized Kaczmarz iterations and Hessian–vector products support efficient implementation, with synthetic and real-data experiments demonstrating potential runtime benefits.

Critical weaknesses
  1. Conditional local guarantee: Superlinear convergence assumes that iterates converge to a stationary point with a positive-definite Hessian and requires increasing inner iteration budgets, limiting the guarantee for general nonconvex problems.

  2. Incomplete empirical validation: Experiments use fixed inner iteration budgets, so they do not directly validate the paper’s central asymptotic superlinear convergence result.

  3. Computational overhead and limited benchmarks: Anchor construction requires additional Hessian–vector products that can offset iteration savings, while experiments are restricted to logistic and softmax regression.

Questions for authors

Can ARS-RN be adapted to large-scale tasks such as LLM pre-training and post-training? What modifications would be needed to handle stochastic mini-batch gradients and indefinite or nearly singular Hessians, while keeping the computational and memory costs of anchor construction practical?

1 comment
  1. "Can ARS-RN be adapted to large-scale tasks such as LLM pre-training and post-training?" / "Computational overhead and limited benchmarks"

    We thank the reviewer for this important comment regarding the applicability of our method to large-scale problems.

    We have extended the theoretical analysis of ARS-RN to incorporate full-batch gradients and mini-batch Hessian averaging, establishing global iteration complexity and local superlinear convergence guarantees (Section 3.3 and Appendix E.3).

    To reduce computational and memory costs, we also introduced sparse Gaussian random matrices and separately established their convergence guarantees (Appendix E.5).

    Furthermore, we conducted additional experiments on three problems with approximately one million optimization variables, using ARS-RN with mini-batch Hessians and sparse Column Gaussian sketches.

    The results show that ARS-RN achieves lower objective values than its unanchored counterparts (Figure 3).

    These results demonstrate the applicability of ARS-RN to large-scale problems.

  2. "Conditional local guarantee"

    Our paper distinguishes between global iteration complexity guarantees for nonconvex problems and local superlinear convergence guarantees near solutions with positive-definite Hessians.

    Positive definiteness of the Hessian is a standard assumption widely used in local superlinear convergence analyses of Newton-type methods. For general nonconvex problems, superlinear convergence cannot be guaranteed at arbitrary stationary points.

  3. "Incomplete empirical validation"

    To examine the convergence behavior corresponding to the conditions of our local superlinear convergence theory, we conducted additional experiments with logarithmically increasing inner iteration budgets TkT_k on a synthetic strongly convex logistic regression problem with dimension n=2000n=2000.

    The results show superlinear convergence in terms of outer iterations, consistent with our local superlinear convergence theory. However, we also observed that logarithmically increasing TkT_k does not necessarily reduce computation time.

    Details are provided in Appendix H.1 (Figure 4).

We hope our responses have addressed your comments. If there are any further questions or suggestions, we would be happy to address them.

Reviewer_StG3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper suggests a way to improve Newton-type optimization methods.

These methods are slow in high dimensions and one way to accelerate them is to apply them in a randomized low dimensional space. However, they fail to achieve fast local superlinear convergence—even near locally strongly convex minimizers—yielding at best linear local rates unless restrictive rank-deficiency assumptions are imposed.

The solution proposed by the authors is to add an anchored direction, computed using a Kaczmarz-type procedure that essentially points the optimizer in the right direction.

Critical strengths

The paper is really a theoretical contribution that proves superlinear convergence under specific conditions. Numerical experiments on both synthetic and real dataset demonstrate the benefits of the method.

Critical weaknesses

My main concern is that there might be a disconnect between the theory and the practice.

I'm not sure the experiments support the theory. Yes, the empirical results are good, but does that mean the underlying assumption made by the theory hold in practice?

As an aside, I'm not sure that a conference is the right venue for this type of publication. The mathematical proofs run for pages and require much more rigorous analysis than the one allowed by the given timeline. A journal seems a much better fit.

Questions for authors

Can the authors quantify how well the underlying assumptions made for the theoretical part hold in practice?

1 comment

(Q1) "Can the authors quantify how well the underlying assumptions made for the theoretical part hold in practice?"

We thank the reviewer for this important comment regarding the consistency between the theoretical assumptions and numerical experiments. We have added experiments with increasing inner-iteration budgets and an explicit verification of the theoretical assumptions.

  1. Additional experiments with logarithmically increasing TkT_k.

    To examine the convergence behavior corresponding to the conditions of our local superlinear convergence theory, we conducted additional experiments with logarithmically increasing inner iteration budgets TkT_k on a synthetic strongly convex logistic regression problem with dimension n=2000n=2000. The results show superlinear convergence in terms of outer iterations, consistent with our local superlinear convergence theory. However, we also observed that logarithmically increasing TkT_k does not necessarily reduce computation time. Details are provided in Appendix H.1 (Figure 4).

  2. Verification of assumptions on the objective functions.

    We analytically examined whether the ten real-world problems used in our numerical experiments satisfy the assumptions underlying our global and local convergence analyses. We found that seven problems satisfy the conditions under which our global and local convergence theory applies. For the remaining three problems, the theoretical assumptions are not guaranteed to hold. These three experiments evaluate the performance of our method in settings where the assumptions of the local convergence theory are not guaranteed. The applicability of each assumption and its justification are summarized in Appendix H.7 (Table 5).

We hope our responses have addressed your comments. If there are any further questions or suggestions, we would be happy to address them.

Comments on the paper

1 comment

We sincerely thank all reviewers for their careful reading and constructive feedback. In response to the initial reviews, we have substantially revised the paper, particularly by expanding the experimental evaluation, extending ARS-RN to stochastic Hessian settings, and strengthening the analysis of its computational efficiency.

The main changes are summarized below.

  1. Additional experiments on convergence behavior.

    We added experiments comparing fixed and logarithmically increasing inner Kaczmarz iteration budgets. The results further support the convergence mechanism underlying our theoretical analysis, while illustrating the trade-off between faster convergence and additional computational cost.

  2. Stochastic extension with convergence guarantees.

    To improve applicability to large-scale problems, we extended ARS-RN using mini-batch Hessian estimates and Hessian averaging. Under the stated assumptions, we establish both global O(ε−2)O(\varepsilon^{-2}) iteration complexity and local superlinear convergence for the stochastic extension.

  3. Large-scale numerical experiments.

    We added experiments on Avazu, 20 Newsgroups, and CIFAR-10, each involving approximately one million optimization variables. Using mini-batch Hessian averaging and sparse Column Gaussian sketches, ARS-3RN achieves better finite-time performance than its unanchored counterpart on 20 Newsgroups and CIFAR-10, while the results on Avazu are more dependent on the subspace dimension. We also extended the theoretical analysis to sparse Gaussian sketches designed for larger-scale problems.

  4. Computational efficiency analysis.

    We strengthened the comparison of total computational costs, explicitly accounting for the additional inner Kaczmarz iterations and the reuse of derivative information. This analysis clarifies how the additional cost of anchor construction can be outweighed by faster convergence, leading to improved overall efficiency.

We hope that our revisions and individual responses adequately address the concerns raised by the reviewers. We would be happy to address any further questions or suggestions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.