acceptodds
Under review as a conference paper at ICLR 2027

Acc-RSRN: Accelerated Randomized Subspace Regularized Newton

Abstract

We propose Accelerated Randomized Subspace Regularized Newton (Acc-RSRN) for smooth, possibly nonconvex optimization, with improved local linear convergence rates. Our improvement over the prior work has two components: a sharp analysis of the randomized subspace iterations replaces the dependence on the full Hessian condition number with a smaller tail-averaged quantity which leverages the preconditioning effect of randomized subspaces, and Nesterov acceleration further reduces the dependence on this quantity from linear to square root. For an -dimensional problem and subspace dimension proportional to , the local iteration complexity improves from in prior work to , where is the average of the Hessian's tail eigenvalues at the minimizer divided by its smallest eigenvalue. Our results support two different Hessian access models: Hessian-vector products via Gaussian sketching, and entry-wise access via ridge leverage score sampling. Experiments on kernel logistic regression and a CNN objective illustrate the benefits of acceleration in RSRN.

Primary area:
optimization
Keywords:
Randomized subspace Newton methods, Nesterov acceleration, Nonconvex optimization, Randomized numerical linear algebra

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_LhxFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies randomized subspace Newton for smooth, possibly nonconvex problems, building on RSRN (Fuji et al., 2025). It adds a ridge floor, Nesterov momentum, and a two-mode design: a global phase with a decrease safeguard, and a local phase that runs the accelerated recursion once a "local entry" test passes. The main claim is that the local iteration count improves from O~(nκ/r)\tilde O(n\kappa/r) to O~(nκˉr/r)\tilde O(n\sqrt{\bar\kappa_r}/r), where κ=λ1/λn\kappa=\lambda_1/\lambda_n and κˉr\bar\kappa_r is the average of the tail eigenvalues divided by the smallest eigenvalue. Matching moment bounds are proved for Gaussian sketches (Hessian-vector products) and ridge-leverage-score sampling (entry-wise access). Experiments compare with RSRN, AGD, and Adam on kernel logistic regression and a small CNN.

Critical strengths
  1. Good main idea. κ=λ1/λn\kappa=\lambda_1/\lambda_n is too pessimistic when only a few eigenvalues are large. The tail average κˉr\bar\kappa_r is the right quantity, and the gain is shown for outliers-plus-bulk and power-law spectra.
  2. Clean analysis. The momentum parameters follow from the two moment bounds, the quadratic step is short to check, and the nonlinear part is handled by an explicit error argument.
  3. The paper also shows when acceleration fails (Remark E.4: zero-ridge coordinate sampling gives no gain). This justifies the ridge floor and the shifted Hessian.
  4. Careful design and careful experiments: monotone global phase, one-way switch, matched RSRN control, paired seeds, bootstrap intervals. The experimental claims are stated modestly.
Critical weaknesses
  1. The switch test needs a provable lower bound mm on the smallest Hessian eigenvalue, and the paper never says how to get one. For the KLR objective used here the Hessian is 1nK⊤DK+λregK\frac1n K^\top DK+\lambda_{\mathrm{reg}}K with D⪰0D\succeq0, so the best simple bound is λregλmin⁡(K)\lambda_{\mathrm{reg}}\lambda_{\min}(K). However, kernels usually have near-zero eigenvalues. The test then implies ∥∇f∥≤m2/(16LH)\lVert\nabla f\rVert\le m^2/(16L_H) and a ball of radius m/(4LH)m/(4L_H), which is triggered only when the iterate is already very close to the solution. The "return false" line and the δcert\delta_{\mathrm{cert}} budget do not apply when mm is intractable (Definition C.3). The cost of choosing or certifying the spectral parameters is considered nowhere.

  2. The experiments are far below the motivation in scale and never look at the spectrum. In KLR and CNN experiments, n=5,000n=5{,}000 and 1,710 parameters with sketches of size 50-400 are sizes where full Newton is affordable, so "Newton is too expensive" does not hold for the experiments.

  3. The KLR instance may not lie in the regime the theory favors. RBF kernels are known for very fast (exponential or faster) eigenvalue decay, so even after removing the top rr eigenvalues the ratio λr+1/λn\lambda_{r+1}/\lambda_n can still be very large. Averaging only adds a factor of order n−rn-r over that worst tail ratio, so it cannot fix fast decay. If so, this instance is outside the outlier+bulk / power-law cases that motivate the theory, and the predicted bound is far above the observed iteration counts.

  4. Missing baselines. The paper only compares vanilla RSRN. At least, the paper should consider ASkotch (Rathore, JMLR'26) as a baseline, which shares a similar position to this paper. Comparison with the classical methods, Newton-CG and L-BFGS, are also encouraged.

  5. Global-to-Local switching not tested. The experiments use empirical momentum, Hessian-diagonal sampling instead of ARLS, and no LOCAL-CERT. So the ARLS construction, the certified switch, the safeguard, and the global bound get no experimental support.

Questions for authors
  1. How do you get mm in practice, and at what cost? For the KLR objective, the best simple bound is λregλmin⁡(K)\lambda_{\mathrm{reg}}\lambda_{\min}(K), which can be near zero. When is LOCAL-CERT cheap, and what should a user do when it is not?
  2. Can you add an experiment to show that the number of iterations tracks κˉr\bar\kappa_r rather than κ\kappa? And at the current size or the larger scale, can you add a full-Newton or Newton-CG baseline to show the RSRN is worth it?
Reviewer_2o5SOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper adds Nesterov momentum to randomized subspace regularized Newton (RSRN), a method for smooth, possibly nonconvex problems. At each step, RSRN solves a regularized Newton system in a random subspace of dimension s≪ns\ll n. Near a minimizer with positive definite Hessian, the paper proves a local iteration complexity of O~(nκˉr/r)\tilde O(n\sqrt{\bar\kappa_r}/r) with ss of order rr, compared with O~(nκ/r)\tilde O(n\kappa/r) for RSRN. Here κˉr\bar\kappa_r is the average of the Hessian eigenvalues beyond the top rr, divided by the smallest one. The result covers Gaussian sketches built from Hessian-vector products and coordinate sampling based on approximate ridge leverage scores (ARLS). In the global phase, an accelerated step is accepted only if it decreases the objective enough, and otherwise a plain RSRN step is taken; this safeguard gives an O(ϵ−2)O(\epsilon^{-2}) global guarantee for nonconvex problems. A certified test (LOCAL-CERT) then switches the method to the accelerated local phase. Experiments on kernel logistic regression (KLR) and a small CNN compare Acc-RSRN with RSRN, AGD and Adam.

Critical strengths
  1. Clear presentation. The main text is well organized. The progression from κ\kappa to κˉr\bar\kappa_r to κˉr\sqrt{\bar\kappa_r}, with the outlier and polynomial-decay examples in Sec. 1, makes the improvement easy to follow.
  2. Detailed local analysis. The proofs are detailed, and the steps I checked (Lemmas B.1–B.3, Theorems 3.5 and 3.6) are correct. The local analysis accounts for Hessian variation, the gradient-dependent regularizer, the line search and the probability of leaving the local region. The moment bounds for regularized projections with Gaussian sketches (Lemmas B.1–B.2) appear to be new.
  3. Certified switch between phases. The safeguard gives a global guarantee for nonconvex problems, and the one-time certified switch then removes it, so the safeguard cannot block acceleration in the local phase.
Critical weaknesses

W1. Limited novelty.

  • The improvement from κ\kappa to κˉr\bar\kappa_r (labeled "our RSRN bound" in Sec. 1) comes from the analysis, not from the algorithm. Lemma B.1 bounds the first moment of the projection through the tail of the spectrum, and the same proof works for η=0\eta=0. Hence the original RSRN of Fuji et al. (2025), analyzed with Lemma B.1, already has the local iteration complexity O~(nκˉr/r)\tilde O(n\bar\kappa_r/r). This is also known: for strongly convex objectives, Dereziński & Rebrova (2024, Corollary 3.14) give such a tail-dependent bound for randomized subspace Newton with Gaussian sketches, using the local analysis of Hanzely et al. (2020), and Corollary E.3 of the paper itself gives the η=0\eta=0 result for coordinate sampling.
  • From this viewpoint, the main contribution is to adapt Nesterov acceleration to subspace Newton, which turns κˉr\bar\kappa_r into κˉr\sqrt{\bar\kappa_r}. For quadratic problems, this step is also known. If ff is quadratic and the vanishing term c2∣∇f∣γc_2\\|\nabla f\\|^\gamma is dropped (as in Proposition A.1), the local phase of Acc-RSRN is accelerated sketch-and-project with regularized projections for the linear system H⋆x=bH_\star x=b. For this method, Dereziński et al. (2025, Theorem 5.1) already obtain the rate O~(nκˉr/r)\tilde O(n\sqrt{\bar\kappa_r}/r), with the same tail-average condition number and a ridge of the same form, using coordinate blocks after a randomized Hadamard transform. Their Lemma 2.3 uses the same energy, momentum parameters and contraction factor as Theorem 3.3. Hanzely et al. (2020) also list adding Nesterov momentum to subspace Newton as future work.
  • The paper cites these works, and it says that Proposition A.1 follows Dereziński et al. (2025, Lemma 2.3) and that the ARLS bounds are taken from Rathore et al. (2026). However, the introduction presents both rate improvements as results of this paper and does not say that they are already known in the cases above. The new parts are mainly the moment bounds for Gaussian sketches (Lemmas B.1–B.2), the ARLS construction on the shifted Hessian, the extension to non-quadratic objectives near the minimizer (Lemma 3.4 and the exit analysis), and the safeguarded global phase with the certified switch.

W2. No comparison with standard second-order methods. The local rate is compared only with other randomized subspace methods. I recommend comparing Acc-RSRN with Newton-CG (Martens, 2010), exact Newton and L-BFGS (Liu & Nocedal, 1989), both in the complexity discussion and in the experiments.

W3. The experiments are small and do not test the theory.

  • Both problems are small (KLR with 5,000 variables and a CNN with 1,710 parameters), so the full Hessian can be formed and factorized directly.
  • The main claim, that the rate depends on κˉr\bar\kappa_r rather than κ\kappa, is not checked: the Hessian spectrum at the solution is not reported, and no experiment varies κˉr\bar\kappa_r. I suggest adding an experiment showing that the iteration count of Acc-RSRN indeed scales with κˉr\sqrt{\bar\kappa_r}, and checking whether RSRN depends on κˉr\bar\kappa_r rather than κ\kappa, as I discussed in W1.
  • The CNN loss does not change when the same vector is added to all ten rows of the last weight matrix, since the softmax is invariant to a common shift of the logits. Its Hessian is therefore singular at every point, so Assumption 3.1 does not hold and the local theory does not apply to this problem.

Minor.

  • Some passages call results "old" without saying what they refer to, e.g., "the old all-good horizon" (App. D.4), "The old RLS result" (Corollary E.3) and "not a renaming of the old theorem" (Remark E.4). It is unclear whether they mean prior work or an earlier version of this paper.
  • The reproducibility statement says that all hyperparameters are given, but App. F.1 does not give c2c_2, γ\gamma, the Armijo and safeguard parameters or the momentum rule for KLR, and the stepsizes of AGD and Adam are not reported.

Summary. The paper is clearly written and the analysis is sound. However, the improvement from κ\kappa to κˉr\bar\kappa_r comes from the analysis rather than the algorithm, the accelerated rate is already known for quadratic problems, there is no comparison with Newton-CG or other standard second-order methods, and the small experiments do not test the dependence on κˉr\bar\kappa_r. Nevertheless, I still think this is a valuable paper, and I would be very glad to raise my score if the authors address my concerns and questions.

References

  • Michał Dereziński, Deanna Needell, Elizaveta Rebrova, and Jiaming Yang. Randomized Kaczmarz methods with beyond-Krylov convergence. SIAM Journal on Matrix Analysis and Applications, 46(4):2558–2588, 2025.

  • Michał Dereziński and Elizaveta Rebrova. Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition. SIAM Journal on Mathematics of Data Science, 6(1):127–153, 2024.

  • Terunari Fuji, Pierre-Louis Poirion, and Akiko Takeda. Theoretical analysis of the randomized subspace regularized Newton method for non-convex optimization. Open Journal of Mathematical Optimization, 6:8, 2025.

  • Filip Hanzely, Nikita Doikov, Yurii Nesterov, and Peter Richtárik. Stochastic subspace cubic Newton method. In Proceedings of the 37th International Conference on Machine Learning (ICML), PMLR 119:4027–4038, 2020.

  • Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45:503–528, 1989.

  • James Martens. Deep learning via Hessian-free optimization. In Proceedings of the 27th International Conference on Machine Learning (ICML), pp. 735–742, 2010.

  • Pratik Rathore, Zachary Frangella, Jiaming Yang, Michał Dereziński, and Madeleine Udell. Have ASkotch: A neat solution for large-scale kernel ridge regression. Journal of Machine Learning Research, 27(162):1–48, 2026.

Questions for authors
  1. Which parts of Theorems 3.3, 3.5 and 3.6 are new compared with Dereziński et al. (2025, Lemma 2.3 and Theorem 5.1), Dereziński & Rebrova (2024, Corollary 3.14) and Rathore et al. (2026, Lemma 10)? What is the main difficulty in moving from the quadratic case to a general ff?
  2. Near x⋆x_\star, the iteration count of Newton's method depends on neither the dimension nor the conditioning, whereas the local iteration counts of RSRN and Acc-RSRN contain the extra factors n/rn/r and κ\kappa (RSRN) or κˉr\sqrt{\bar\kappa_r} (Acc-RSRN). The factor n/rn/r is natural, because each iteration works in a subspace of dimension of order rr. Where does the additional dependence on κ\kappa or κˉr\bar\kappa_r come from? A short explanation in the paper would help the reader.
  3. If I understand correctly, n/rn/r iterations of Gaussian Acc-RSRN with s=2rs=2r use 2n2n Hessian-vector products, which is enough to form the full Hessian twice. Even so, to reduce the error by a factor of ϵ\epsilon in the local phase, Acc-RSRN needs O(nκˉrlog⁡(1/ϵ))O(n\sqrt{\bar\kappa_r}\log(1/\epsilon)) Hessian-vector products (Sec. 3.3.2), while exact Newton needs O(nlog⁡log⁡(1/ϵ))O(n\log\log(1/\epsilon)) near the minimizer. Why should one necessarily use the subspace version? Adding a discussion of this point to the paper, with concrete examples if necessary, would help show the value and necessity of this work.
  4. How can LOCAL-CERT be run in practice, and in particular how are the smallest eigenvalue, the Hessian-Lipschitz constant and the tail eigenvalue sum certified?
  5. What are κ\kappa and κˉr\bar\kappa_r at the solution of the KLR problem? How is f⋆f_\star computed in the two experiments?

References

  • Michał Dereziński, Deanna Needell, Elizaveta Rebrova, and Jiaming Yang. Randomized Kaczmarz methods with beyond-Krylov convergence. SIAM Journal on Matrix Analysis and Applications, 46(4):2558–2588, 2025.

  • Michał Dereziński and Elizaveta Rebrova. Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition. SIAM Journal on Mathematics of Data Science, 6(1):127–153, 2024.

  • Pratik Rathore, Zachary Frangella, Jiaming Yang, Michał Dereziński, and Madeleine Udell. Have ASkotch: A neat solution for large-scale kernel ridge regression. Journal of Machine Learning Research, 27(162):1–48, 2026.

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

This paper proposes Acc-RSRN, combining sharper spectral-tail analysis with Nesterov momentum to improve the local convergence guarantees of randomized subspace regularized Newton methods. Experiments on kernel logistic regression and a CNN illustrate empirical acceleration.

Critical strengths

The spectral-tail analysis and Nesterov acceleration provide meaningful improvements in local convergence guarantees. The framework covers nonlinear objectives and two Hessian access models. Experiments report both iteration counts and runtime, with repeated randomized runs providing encouraging evidence of efficiency gains over nonaccelerated RSRN.

Critical weaknesses
  1. The evaluation includes only one KLR instance and one small CNN with fixed data and initialization. Beyond the overall accelerated-versus-nonaccelerated RSRN comparison, there are no dedicated component ablations examining the ridge, sampling strategy, or momentum settings, nor controlled experiments testing the spectral-tail predictions. The sources of improvement and their connection to the central theoretical mechanism remain unclear.

  2. The experimental reference value f⋆f_\star, particularly for the CNN, is not clearly defined, making the reported objective gaps difficult to interpret. Reporting additional computational metrics, such as Hessian-vector product counts, FLOPs, and peak GPU memory usage where applicable, together with model accuracy under matched training-time budgets, would provide a more complete assessment of computational efficiency, acceleration benefits, and training performance.

Questions for authors
  1. How is f⋆f_\star obtained for each experiment, and is it shared across all methods and seeds?

  2. Could the authors provide targeted component ablations and controlled-spectrum experiments to clarify the sources of improvement and their relationship to the theoretical predictions?

Comments on the paper

1 comment

Thank you for the detailed response, and I have raised the score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.