- 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 to , where and 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
- Good main idea. is too pessimistic when only a few eigenvalues are large. The tail average is the right quantity, and the gain is shown for outliers-plus-bulk and power-law spectra.
- 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.
- 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.
- 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
-
The switch test needs a provable lower bound on the smallest Hessian eigenvalue, and the paper never says how to get one. For the KLR objective used here the Hessian is with , so the best simple bound is . However, kernels usually have near-zero eigenvalues. The test then implies and a ball of radius , which is triggered only when the iterate is already very close to the solution. The "return false" line and the budget do not apply when is intractable (Definition C.3). The cost of choosing or certifying the spectral parameters is considered nowhere.
-
The experiments are far below the motivation in scale and never look at the spectrum. In KLR and CNN experiments, 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.
-
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 eigenvalues the ratio can still be very large. Averaging only adds a factor of order 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.
-
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.
-
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
- How do you get in practice, and at what cost? For the KLR objective, the best simple bound is , which can be near zero. When is LOCAL-CERT cheap, and what should a user do when it is not?
- Can you add an experiment to show that the number of iterations tracks rather than ? 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?
Thank you for the detailed response, and I have raised the score.