- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This work analyzes principal-subspace Newton-gradient (PSNG) methods, which combines Newton steps in an approximate leading Hessian eigenspace with gradient steps in its orthogonal complement, on strongly convex quadratic functions as well as strongly convex functions in general.
The authors show that the convergence rate of PSNG on strongly convex quadratics is determined by the condition number of the orthogonal complement , which can be much smaller than the condition number of the full Hessian.
The paper also proposes lazy PSNG, which updates the projected Hessian until an accumulated step length is reached. Under the assumption of local regularity and local spectral conditions, the authors show local linear convergence, which they extend to global convergence guarantee under global strongly convexity.
The paper complements its theoretical results with empirical experiments on a quadratic function and L2-regularized logistic regression with synthetic data, showing that the total number of required scalar Hessian-vector products is independent of the required tolerance.
Critical strengths
The work studies a family of hybrid optimization methods which serve as a compromise between first- and second order methods and show that this method guarantees local linear convergence.
Also, the appendix provides thorough ablations on spectral diagnostics, convergence, subspace dimensionality , and refresh policies under changing spectra.
Critical weaknesses
- The theoretical results are limited only to the strongly convex setting, while the experiments are also only limited to a synthetic logistic regression experiment in a few hundred dimensions. I think the work would benefit from an experiment evaluating how the method scales with dimensionality and validating the method on real-world data, e.g. from LIBSVM (for instance epsilon, usps etc.).
- The only experiment which measures wall-clock times (Fig. 7) does not show the benefit of PSNG or hybrid methods in general, as Newton and Newton-CG are faster. It would be more convincing to include a setting where Newton-CG is not feasible or considerably slower.
- In the experiments, the authors only compared their method to FOSI-GD in the appendix, but not with another hybrid method SONIA.
Questions for authors
I have some questions regarding some assumptions made in the paper:
- Assumption 3.3 assumes that the initial orthonormal basis has full-rank overlap with the leading eigenspace, i.e. that is invertible. How can this be guaranteed in practice without knowing ?
- Assumption 4.3 assumes that the tangent of the largest principal angle of is bounded by a known . How does one compute this tangent and what is the complexity of this?
Could you also provide some intuition why one requires Assumption 4.2, namely that the Hessian at the minimizer has a positive eigengap at rank ?
How does the iteration complexity of the method scale with the dimensionality of the problem? And how does this compare with the other methods compared in the work (GD, NAG, L-BFGS, Newton-CG)?
What would be theoretical challenges to extend the results to the general convex and non-convex setting?
10 comments
Response to Reviewer RNui (Part 2)
2. W2: The original timings do not show a wall-clock advantage over Newton–CG.
This is correct for the original logistic benchmarks, which we retain. The new benchmark provides a favorable regime with a changing Hessian and pronounced spectral separation: at the minimizer, the full condition number is , while the remaining-spectrum condition number is 10.
Results from Table 2 (relative-gradient target ):
| Method | Median iterations | Median scalar HVPs | Median time to target (s) |
|---|---|---|---|
| Lazy PSNG | 59 | 276 | 1.775 |
| Fresh PSNG | 58 | 2,184 | 7.494 |
| Newton–CG | 6 | 142 | 1.970 |
| FOSI-GD | 124 | 96 | 2.819 |
| L-BFGS | 394 | 0 | 6.065 |
| SONIA | 135 | 8,640 | 23.395 |
| NAG | 1,185 | 0 | 29.304 |
| GD | 5,000 (cap) | 0 | Not reached |
GD did not reach the target on any seed; all other methods reached it on all five.
At relative-gradient target , lazy PSNG is faster than Newton–CG on four of five seeds, with a median paired speedup of 1.39×. Its paired speedup over L-BFGS is 3.89×, with wins on all five seeds (Tables 2–3; Figures 3–4). These ratios are formed within each seed after aggregating timing repetitions. Timings include initialization, oracle evaluations, curvature refreshes, and line searches.
Paired speedups from Table 3:
| Baseline | Median paired speedup (baseline/lazy) | Seeds where lazy PSNG is faster |
|---|---|---|
| Newton–CG | 1.389× | 4/5 |
| FOSI-GD | 1.944× | 5/5 |
| Fresh PSNG | 4.222× | 5/5 |
| L-BFGS | 3.890× | 5/5 |
| SONIA | 14.583× | 5/5 |
| NAG | 18.468× | 5/5 |
The result is about actual elapsed time, so it demonstrates that inexpensive reuse can offset slower outer convergence in a favorable regime. Compared with fresh PSNG, lazy preserves almost the same iteration count while reducing median scalar-HVP work by 87.4%.
3. W3: A direct comparison with SONIA is missing.
We have added SONIA to the new eight-optimizer benchmark. Appendix F.3 specifies its memory, spectral truncation, pseudoinverse tolerance, and Armijo settings. In this experiment, SONIA reaches the target on all five seeds, with median runtime 23.395 s versus 1.775 s for lazy PSNG; the median paired speedup is 14.58× in favor of lazy PSNG. FOSI-GD is included in the same comparison. These are results for the documented local implementations and configurations, not a claim of universal superiority over either hybrid method.
4. Q1: How can full-rank overlap be guaranteed without knowing the leading eigenspace?
The new Lemma C.2 answers this directly. Draw an independent standard Gaussian and set . For any fixed leading basis , the square matrix is Gaussian and invertible almost surely; orthonormalization preserves this overlap. Thus no knowledge of is needed. At a restart, the same argument holds conditionally when the new Gaussian draw is independent of the preceding history.
5. Q2: Must the largest principal angle be computed to obtain the overlap bound, and what does this cost?
No angle computation is required. With independent Gaussian initialization , the overlap matrix is invertible almost surely. Hence, the largest principal angle satisfies , and its tangent is finite almost surely.
To select the initialization budget in advance, we need a known upper bound rather than the unknown realized angle. Lemma C.2 supplies this bound using only , , and a chosen failure probability :
\qquad \Pr\{\tan\vartheta_0\le\Gamma_p\}\ge1-p.$$ We can therefore set $\Gamma=\Gamma_p$ in the bootstrap budget (4.2), without knowing $P_\star$ or computing $\vartheta_0$. This budget achieves the required initial subspace accuracy with probability at least $1-p$, under the stated spectral conditions. Sampling and orthonormalizing $G$ costs $O(dr^2)$ arithmetic and no HVPs. Running the initial block-power iterations and forming the projected Hessian requires $r(K_{\mathrm{boot}}+1)$ scalar HVPs. On the successful initialization event, subsequent warm-start refreshes preserve the required accuracy under the remaining theorem conditions, with no further probability loss (Appendix C.2).Response to Reviewer RNui (Part 3)
6. Q3: Why is an eigengap needed at the rank- cutoff?
The gap makes the subspace being tracked stable. When and are separated, a small Hessian change produces a controlled rotation of the leading subspace; the previous basis remains a useful warm start. If these eigenvalues cross, the selected rank- space can change abruptly even under a small matrix perturbation. The gap also controls the convergence rate of block power iteration (Appendix C.1 and Lemma C.3).
Only the gap at the cutoff is required; repeated eigenvalues within either spectral group are allowed. This assumption belongs to the computation and tracking guarantees, not to every convergence statement: Theorem 3.1's contraction bound and the global Armijo guarantees do not require an eigengap.
7. Q4: How does complexity depend on ambient dimension, relative to the other methods?
Corollary 4.6 gives local outer iterations, with no additional explicit factor of when the spectral and regularity quantities are held fixed. This is not dimension-independent total computation: those quantities can change with , and the Gaussian bootstrap budget also depends on through .
The new Table 1 in the revised manuscript separates update work, curvature calls, and storage. Writing for one gradient cost and for one scalar-HVP cost:
| Method | Main computation cost per update |
|---|---|
| GD / NAG | |
| L-BFGS, history | |
| Newton–CG, inner iterations | |
| PSNG between refreshes |
A PSNG refresh additionally costs , including orthogonalization and projected-Hessian factorization. Its state costs , compared with for matrix-free CG and for L-BFGS. Hence, low-rank curvature is not automatically a memory saving over these baselines. The benefit sought is to amortize curvature computation while retaining a favorable outer rate; gradients and projection work still accumulate as accuracy increases.
8. Q5: Theoretical challenges to extend the results to the general convex and non-convex setting.
For general convex objectives, removing the positive lower-curvature bound can make the projected Newton system singular and no longer supplies the geometric error decay used in our proof of finite total path length. Thus, neither the current update nor the finite-refresh argument transfers unchanged; regularized subspace solves and a different path-length analysis would be needed.
For general nonconvex objectives, an indefinite projected Hessian can produce a non-descent Newton direction. Moreover, tracking only the largest positive eigenvalues may miss negative-curvature directions in the orthogonal complement. Establishing second-order stationarity therefore requires both a stabilized subspace step and a mechanism to detect relevant negative curvature outside it; cubic regularization is discussed as a direction in Section 6.
Our local results require strong convexity only near the minimizer, whereas the arbitrary-start guarantee requires global strong convexity. The broader extensions remain separate theoretical questions. Within the present setting, the analysis isolates a concrete contribution: fixed-quality approximate curvature can preserve spectral acceleration, and its computation can eventually stop while optimization continues toward arbitrarily high accuracy.
Response to Reviewer RNui (Part 1)
Thank you for recognizing the soundness of the analysis and the value of the spectral and refresh-policy diagnostics. We have expanded the computational evaluation, added SONIA, and supplied an explicit random-initialization guarantee. All references below refer to the revised manuscript, where major changes are highlighted in blue.
1. W1: Limited scopes of theoretical and experimental results.
i) Theoretical Scope:
Strongly convex optimization has substantial value in its own right. It includes important regularized estimation problems and can still be severely ill-conditioned. Our theory-focused contribution is not simply to establish convergence, but to determine how accurately and how often curvature must be computed to retain spectral acceleration. Strong convexity alone does not answer these questions: subspace approximation and outdated curvature can weaken the benefit of preconditioning. We quantify these effects and show that, under the stated conditions, lazy PSNG retains the remaining-spectrum iteration bound with a finite total HVP bound independent of the target accuracy, for fixed initialization and parameters (Theorem 4.5 and Corollary 4.6).
Our local results do not require global strong convexity. Assumption 4.1 imposes strong convexity only near the minimizer, so the objective may be nonconvex elsewhere. Any twice continuously differentiable objective with a positive-definite Hessian at the minimizer ensures strong convexity in a certain neighborhood. Our local guarantees apply when the additional spectral, regularity, and initialization conditions hold; global strong convexity is imposed separately for the arbitrary-start guarantees in Section 4.3.
These results therefore provide both standalone guarantees for an important problem class and insight into the local behavior of broader nonconvex objectives. By identifying how subspace error and curvature reuse affect convergence and computational cost, the analysis also provides a concrete foundation for studying more complex landscapes, where singular or negative curvature introduces additional challenges.
ii) Additional Experiments:
We have substantially expanded the evaluation with a nonquadratic strongly convex benchmark at d=10,000, compared with the original d=120 logistic problems (Appendix F.3). PSNG computes its rank-12 subspaces through HVPs rather than receiving the leading eigenvectors, and the Hessian changes along the optimization trajectory. We compare eight optimizers across five objective seeds, with three timing repetitions per seed.
This experiment tests whether curvature reuse delivers a computational benefit after paying for subspace construction and maintenance. The reported wall-clock times include initialization, curvature computations, refreshes, and line searches. Lazy PSNG achieves the lowest median runtime among the methods reaching the target in this benchmark (Tables 2–3). Compared with fresh PSNG, it reduces median HVP work by 87.4% while requiring nearly the same number of iterations. These results show that the reuse mechanism can translate into actual runtime savings at a substantially larger dimension.
The evaluation remains synthetic: controlled spectra and changing curvature let us directly examine when low-dimensional curvature correction is beneficial and whether reuse preserves that benefit. This serves the paper's theoretical focus by connecting the predicted mechanisms to measured computation. We also provide an explicit comparison of arithmetic costs, HVP costs, and storage as functions of d and r (Appendix F.2, Table 1), making the dimensional costs of PSNG and the baselines transparent.