acceptodds
Under review as a conference paper at ICLR 2027

Principal-Subspace Newton–Gradient Methods with Curvature Tracking and Reuse

11 views

Abstract

A few large Hessian eigenvalues can restrict the stepsize of gradient descent and slow progress in flatter directions, while full Newton steps can be too costly in high dimensions. We analyze principal-subspace Newton-gradient (PSNG) methods, which combine Newton steps in an approximate leading Hessian eigenspace with gradient steps in its orthogonal complement. On strongly convex quadratics, we show that a fixed, sufficiently accurate subspace preserves spectral acceleration: the iteration bound depends on the condition number of the remaining spectrum rather than that of the full Hessian. For objectives with a varying Hessian, we first consider updating the subspace and projected Hessian at every iteration. Under suitable local conditions, warm starts enable linear convergence with a fixed Hessian-vector product (HVP) budget per iteration after initialization. We then propose lazy PSNG, which reuses both quantities until accumulated step length reaches a prescribed threshold. Under corresponding local conditions, lazy PSNG retains linear convergence with a finite total HVP bound independent of the target accuracy, for fixed initialization and parameters. With additional global strong convexity and smoothness, an Armijo phase and a prescribed local restart extend this guarantee to arbitrary starting points. Experiments on quadratics and strongly convex logistic regression illustrate spectral acceleration and reduced HVP costs.

Primary area:
optimization
Keywords:
second-order optimization, subspace tracking, curvature reuse, Hessian-vector products, convergence guarantees

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_RNuiOpenReview ↗
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 κ⊥\kappa_{\bot}, 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 rr, 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 Q0Q_0 has full-rank overlap with the leading eigenspace, i.e. that P∗⊤Q0P_*^\top Q_0 is invertible. How can this be guaranteed in practice without knowing P∗P_*?
  • Assumption 4.3 assumes that the tangent of the largest principal angle of H0H_0 is bounded by a known Γ<∞\Gamma < \infty. 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 rr?

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
AuthorsOpenReview ↗

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,000d=10{,}000, compared with the original d=120d=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 dd and rr (Appendix F.2, Table 1), making the dimensional costs of PSNG and the baselines transparent.

AuthorsOpenReview ↗

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 d=10,000d=10{,}000 benchmark provides a favorable regime with a changing Hessian and pronounced spectral separation: at the minimizer, the full condition number is 10410^4, while the remaining-spectrum condition number is 10.

Results from Table 2 (relative-gradient target 10−610^{-6}):

MethodMedian iterationsMedian scalar HVPsMedian time to target (s)
Lazy PSNG592761.775
Fresh PSNG582,1847.494
Newton–CG61421.970
FOSI-GD124962.819
L-BFGS39406.065
SONIA1358,64023.395
NAG1,185029.304
GD5,000 (cap)0Not reached

GD did not reach the target on any seed; all other methods reached it on all five.

At relative-gradient target 10−610^{-6}, 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:

BaselineMedian paired speedup (baseline/lazy)Seeds where lazy PSNG is faster
Newton–CG1.389×4/5
FOSI-GD1.944×5/5
Fresh PSNG4.222×5/5
L-BFGS3.890×5/5
SONIA14.583×5/5
NAG18.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 G∈Rd×rG\in\mathbb R^{d\times r} and set Q0=orth⁡(G)Q_0=\operatorname{orth}(G). For any fixed leading basis P⋆P_\star, the square matrix P⋆⊤GP_\star^\top G is Gaussian and invertible almost surely; orthonormalization preserves this overlap. Thus no knowledge of P⋆P_\star 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 Q0=orth⁡(G)Q_0=\operatorname{orth}(G), the overlap matrix P⋆⊤Q0P_\star^\top Q_0 is invertible almost surely. Hence, the largest principal angle satisfies ϑ0<π/2\vartheta_0<\pi/2, 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 dd, rr, and a chosen failure probability p∈(0,1)p\in(0,1):

\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).
AuthorsOpenReview ↗

Response to Reviewer RNui (Part 3)

6. Q3: Why is an eigengap needed at the rank-rr cutoff?

The gap makes the subspace being tracked stable. When λr\lambda_r and λr+1\lambda_{r+1} 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-rr 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 O(κ⊥log⁡(V0/ε))O(\kappa_\perp\log(V_0/\varepsilon)) local outer iterations, with no additional explicit factor of dd when the spectral and regularity quantities are held fixed. This is not dimension-independent total computation: those quantities can change with dd, and the Gaussian bootstrap budget also depends on dd through Γp\Gamma_p.

The new Table 1 in the revised manuscript separates update work, curvature calls, and storage. Writing CgC_g for one gradient cost and CHC_H for one scalar-HVP cost:

MethodMain computation cost per update
GD / NAGCg+O(d)C_g+O(d)
L-BFGS, history mmCg+O(md+d)C_g+O(md+d)
Newton–CG, jtj_t inner iterationsCg+jtCH+O((jt+1)d)C_g+j_tC_H+O((j_t+1)d)
PSNG between refreshesCg+O(dr+r2+d)C_g+O(dr+r^2+d)

A PSNG refresh additionally costs r(K+1)CH+O((K+1)dr2+r3)r(K+1)C_H+O((K+1)dr^2+r^3), including orthogonalization and projected-Hessian factorization. Its state costs O(dr+r2+d)O(dr+r^2+d), compared with O(d)O(d) for matrix-free CG and O(md+d)O(md+d) 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.

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

This paper proposed the principal-subspace Newton-gradient (PSNG) method, which is a hybrid first-order and second-order method. It can achieve a linear convergence rate depending on the condition number of the complementary spectrum for a quadratic objective function and varying Hessians. It also provides numerical experiments to validate the effectiveness of the proposed method.

Critical strengths
  1. The paper is well-written, and easy to follow.

  2. The theoretical analysis of the proposed method is sound and the proof is correct.

  3. It perform numerical experiments to validate the effectiveness of the proposed method.

Critical weaknesses
  1. It lacks a direct comparison with the NewSamp method (Erdogdu & Montanari, 2015) in the main paragraph, their method is very similar to the NewSamp method. NewSamp method also achieves a linear convergence rate depending on the condition number of the complementary spectrum. So such a convergence rate is not new.

  2. The choice of stepsize in Corollary 3.2 depends on λr+1\lambda_{r+1}, how do you get such this value in practice?

  3. The global convergence rate in Section 4.3 is worse than the gradient descent method. So the improvement of convergence rate is local over a very small region.

  4. The name of the varying Hessian setting is weird, it is just a standard convex optimization problem setting.

  5. The algorithm implementation is more involved than vanilla gradient descent, but the improvement is not that significant.

Questions for authors

See above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer T4MH (Part 1)

Thank you for the positive assessment of the theoretical analysis and experimental validation. We have clarified the relationship to prior spectral methods, made the condition-number dependence explicit, and added computational evidence. All references below refer to the revised manuscript, where major changes are highlighted in blue.

1. W1: It lacks a direct comparison with the NewSamp method.

We thank the reviewer for pointing us to this relevant precedent. We now discuss NewSamp directly in the Introduction, as well as Appendix A.2. NewSamp combines a subsampled Hessian with spectral truncation, and its convergence bounds reflect the remaining spectrum and sampling error.

Our contribution is to quantify how accurately curvature must be computed and how long it can be reused while retaining that spectral benefit. Theorem 3.1 bounds the contraction loss caused by approximate principal subspaces; Corollary 3.2 converts this into an accuracy requirement independent of the final tolerance. Proposition 4.4 and Theorem 4.5 then connect this requirement to warm-start HVP budgets and joint reuse of the basis and projected Hessian as the Hessian changes. The new Corollary 4.6 makes the resulting nonlinear local O(κ⊥log⁡(1/ε))O(\kappa_\perp\log(1/\varepsilon)) bound explicit.

The distinction is therefore not another statement that exact spectral preconditioning improves conditioning. It is a quantitative account of preserving this improvement with approximate, reused curvature and finite total curvature work. A fixed approximation need not become exact: current gradients continue reducing the optimization error after the final refresh.

2. W2: How is the eigenvalue-dependent complementary stepsize obtained in practice?

The new Remark F.1 gives a guaranteed fixed rule for regularized logistic regression. Since

λI⪯H(w)⪯H(0)=λI+A⊤A/(4n),\lambda I\preceq H(w)\preceq H(0)=\lambda I+A^\top A/(4n),

any L⊥≥λr+1(H(0))L_\perp\ge\lambda_{r+1}(H(0)) gives a valid complementary stepsize η=2/(λ+L⊥)\eta=2/(\lambda+L_\perp) for all iterates. The computable bound L⊥=λ+∥A∥F2/[4n(r+1)]L_\perp=\lambda+\|A\|_F^2/[4n(r+1)] requires no HVPs, although it may be conservative. Our experiments use a sharper initial Lanczos estimate with offline verification and its computation cost included in each run (Appendix F.2). Corollary 3.2's optimal quadratic stepsize is a theoretical choice; the implementation does not assume access to exact unknown eigenvalues.

3. W3: The global bound is worse than GD, and the faster rate is local.

We now state the global O(κG2log⁡(1/ε))O(\kappa_G^2\log(1/\varepsilon)) bound explicitly after Theorem 4.8. We did not claim a global iteration advantage over GD. The improved dependence is local for nonquadratic objectives, but global on strongly convex quadratics.

Corollary 4.6 now identifies the local gain precisely: the iteration bound depends on the remaining-spectrum condition number κ⊥=L^⊥/μ^\kappa_\perp=\widehat L_\perp/\widehat\mu, rather than the full-spectrum condition number L^/μ^\widehat L/\widehat\mu. The local radius is a sufficient bound determined by curvature variation, spectral separation, and approximation accuracy, not a characterization of the largest convergence region. Our additional Corollary 4.9 also establishes global convergence with finite total HVP work for lazy Armijo PSNG without a local restart; the sharper local rate requires the stronger local conditions. This separates global safety from spectral acceleration.

4. W4: “Varying Hessian” should not suggest a nonstandard optimization setting.

We have clarified the terminology. The setting is a smooth, strongly convex objective, locally or globally as specified. “Varying Hessian” only describes the distinction from a quadratic: as the iterate moves, both the leading eigenspace and its projected curvature can change. Tracking and reuse are the algorithmic issues being analyzed, not a new class of optimization problems.

AuthorsOpenReview ↗

Response to Reviewer T4MH (Part 2)

5. W5: The additional implementation cost needs a more significant benefit.

We have added an oracle, arithmetic, and storage cost comparison in Appendix F.2 (Table 1). To assess the practical benefit, we have also added a nonquadratic benchmark with d=10,000d=10{,}000, including Newton–CG, L-BFGS, SONIA, and FOSI-GD (Appendix F.3). The main experimental results are summarized below.

Results from Table 2 (relative-gradient target 10−610^{-6}):

MethodMedian iterationsMedian scalar HVPsMedian time to target (s)
Lazy PSNG592761.775
Fresh PSNG582,1847.494
Newton–CG61421.970
FOSI-GD124962.819
L-BFGS39406.065
SONIA1358,64023.395
NAG1,185029.304
GD5,000 (cap)0Not reached

GD did not reach the target on any seed; all other methods reached it on all five.

Lazy PSNG has the lowest median time among the methods reaching the target. Across five seeds, its median paired speedups are 1.39× over Newton–CG, 3.89× over L-BFGS, and 1.94× over FOSI-GD. It is faster than Newton–CG on four seeds and the latter two methods on all five. Paired speedups use the median runtime of three repetitions within each seed.

Paired speedups from Table 3 of the revised manuscript:

BaselineMedian paired speedup (baseline/lazy)Seeds where lazy PSNG is faster
Newton–CG1.389×4/5
FOSI-GD1.944×5/5
Fresh PSNG4.222×5/5
L-BFGS3.890×5/5
SONIA14.583×5/5
NAG18.468×5/5

The comparison with fresh PSNG isolates the benefit of our reuse policy: median iterations are 59 versus 58, while scalar HVPs decrease from 2,184 to 276 and median runtime from 7.494 s to 1.775 s. Thus the extra subspace machinery can pay off when a small set of directions causes poor conditioning and the computed curvature remains useful across updates. We retain the original results where Newton–CG is faster and do not claim superiority outside favorable regimes.

Together, the theory and experiments clarify the contribution: not simply using a hybrid update, but determining when its spectral advantage survives approximation and how to maintain it without repeatedly paying for curvature computation.

Reviewer_QgZvOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2(+1)
Presentation
2(+1)
Soundness
2
Read review
Paper summary

PSNG takes a Newton step in an approximate leading Hessian eigenspace and a gradient step in its orthogonal complement; the subspace is computed by block power iteration using Hessian–vector products (HVPs). On strongly convex quadratics, a fixed subspace with projector error δ\delta gives q≤ρ⊥+Cηδ2q\le\rho_\perp+C_\eta\delta^2, so an ε\varepsilon-independent accuracy preserves an iteration bound governed by κ⊥=λr+1/λd\kappa_\perp=\lambda_{r+1}/\lambda_d instead of κ=λ1/λd\kappa=\lambda_1/\lambda_d. Fresh PSNG warm-starts block power iteration at every step with a fixed HVP budget. Lazy PSNG reuses the basis and projected Hessian until the accumulated step length reaches ω\omega, which gives local linear convergence with a total HVP count independent of the target accuracy. Theorem 4.7 adds an Armijo phase with global linear convergence, followed by a gradient-test entry and a prescribed local restart. Experiments use quadratics and ℓ2\ell_2-regularized logistic regression with d=120d=120.

Critical strengths

(1) The problem setting is interesting. Rather than relying only on the extreme curvature constants μ\mu and LL, the paper attempts to exploit the structure of the Hessian spectrum, namely a small leading eigenspace and the remaining spectrum, for nonlinear objectives along the optimization trajectory. Trying to make convergence depend on κ⊥=λr+1/λd\kappa_\perp=\lambda_{r+1}/\lambda_d rather than on κ=L/μ\kappa=L/\mu beyond the quadratic case is a worthwhile direction. (2) The analysis appears technically correct as far as I checked, and the step-length trigger for curvature reuse is a simple, HVP-free rule. However, the quadratic perturbation bound (Theorem 3.1) follows from standard block-perturbation arguments. As discussed below, in the nonlinear case the dependence on the spectral structure is never made explicit in the main results, so neither point is sufficient to outweigh the weaknesses.

Critical weaknesses

(1) In its current form, I could not extract from the paper what the main results actually achieve. I honestly struggled to understand what the main theorems say. To read off the local rate in Theorems 4.5 and 4.7, I had to go to Proposition 4.4, where qlocq_{loc} is defined as (1+qtar)/2(1+q_{tar})/2. Then I had to find that qtarq_{tar} is constrained by (4.3) through ρˉ\bar\rho, and that ρˉ\bar\rho is introduced only in Assumption 4.2. To understand what happens in the main theorems, one must not miss a single piece of notation introduced in intermediate lemmas and propositions. This is far more convoluted than it needs to be. Once the chain is unwound, the results are, in my view, not what the paper suggests:

  • Global phase. In Theorem 4.7, αmin⁡≈2β(1−cA)μ/L\alpha_{\min}\approx 2\beta(1-c_A)\mu/L and qG≈1−4βcA(1−cA)μ2/L2q_G\approx 1-4\beta c_A(1-c_A)\mu^2/L^2 (for 1/L≤η≤1/μ1/L\le\eta\le 1/\mu). This gives O(κ2log⁡(1/ε))O(\kappa^2\log(1/\varepsilon)) globally and an entry time of O(κ2log⁡(L2Δ0/(μ2R2)))O(\kappa^2\log(L^2\Delta_0/(\mu^2R^2))). The factor κ2\kappa^2 is very hard to see in the statement, but it is certainly there. Plain GD reaches the same region in O(κlog⁡(⋅))O(\kappa\log(\cdot)) iterations, so it is not clear to me why one should use this method rather than GD to enter the local region.
  • Local phase. In the best case, ρˉ≈(κ⊥−1)/(κ⊥+1)\bar\rho\approx(\kappa_\perp-1)/(\kappa_\perp+1) and 1−qloc≲1/(κ⊥+1)1-q_{loc}\lesssim 1/(\kappa_\perp+1), i.e., a GD-type linear rate with κ⊥\kappa_\perp instead of κ\kappa and an extra factor of 2. This is never stated in Section 4; the link to κ⊥\kappa_\perp appears explicitly only for quadratics (Cor. 3.2). In terms of the constants μ,L\mu, L of Assumption 4.1, the theorems give nothing better than gradient descent. Any gain rests entirely on the condition λr+1(H(x))≪L\lambda_{r+1}(H(x))\ll L on N\mathcal{N}, which is hidden inside ρˉ<1\bar\rho<1 and cannot be verified. So the method uses a second-order oracle, and what the theorems guarantee is a linear rate that becomes better than GD only under an implicit spectral assumption. Meanwhile, Newton–CG is locally superlinear and is faster in the paper's own experiments.

As a result, I do not think the paper, as written, conveys a clear new understanding of when and why this approach helps.

(2) Algorithm 1 is not the algorithm that is analyzed or used, and the switch between phases is not implementable. It is very unclear from the text at which point the local method replaces the global one. The entry test ∥gt∥2≤μR/L\Vert g_t\Vert_{2}\le\mu R/\sqrt{L} appears only in the prose of Section 4.3, and it depends on RR, which is defined through (4.4) via LHL_H, csc_s, ClocC_{loc}, γ\gamma and the neighborhood radius. None of these can be computed in practice. The restart also requires a basis with a known overlap bound Γ\Gamma (Assumption 4.3), which proximity to the minimizer does not provide. I also do not understand why the Armijo line search is not part of Algorithm 1, and why the two phases (with and without line search) are not written out explicitly. As it stands, Algorithm 1 has no line search (line 7 sets xt+1=xt+dtx_{t+1}=x_t+d_t), no entry test and no restart. The step αt\alpha_t, the modified accumulator ℓ←ℓ+αt∥dt∥\ell\leftarrow\ell+\alpha_t\Vert d_t\Vert and the restart are described only in Section 4.3 and Appendix E. The experiments then run yet another variant: single-phase Armijo without the restart (Appendix F.3: "No certified local radius or explicit restart test is used"). It is also not explained why the algorithm cannot switch to the local regime by itself. The choice of η\eta has the same issue. Assumption 4.2 requires max⁡i>r∣1−ηλi(H(x))∣≤ρˉ<1\max_{i>r}\lvert 1-\eta\lambda_i(H(x))\rvert\le\bar\rho<1 on all of N\mathcal{N} (Appendix C.1 suggests 0<η<2/λr+1(H(x⋆))0<\eta<2/\lambda_{r+1}(H(x^\star))). No practical rule is discussed; the experiments set η\eta from a Lanczos estimate at the initial point, which does not certify the assumption on N\mathcal{N}. Finally, the practical benefit is not demonstrated: Newton–CG is fastest and L-BFGS competitive on every logistic benchmark, the problems are tiny (d=120d=120), and a fixed initial curvature pair is nearly as good as refreshing except in a purpose-built setting.

Questions for authors

(a) Could you state the global and local iteration complexities explicitly in terms of κ\kappa, κ⊥\kappa_\perp and ε\varepsilon? Is the O(κ2)O(\kappa^2) dependence of the global phase an artifact of the analysis, and why should one prefer the PSNG Armijo phase over GD for reaching the local region? (b) How is the entry test evaluated in practice when RR depends on unknown constants, and how is Assumption 4.3 ensured at the restart point? Why can the method not switch to the local regime automatically within a single procedure? (c) How should η\eta be chosen so that Assumption 4.2 holds on N\mathcal N without knowing λr+1\lambda_{r+1} and λd\lambda_d there? (d) In which regime (dd, cost of an HVP relative to a gradient) does PSNG beat Newton–CG or L-BFGS in wall-clock time?

Suggestions on presentation: (e) I would strongly recommend writing the full method as an explicit algorithm (Armijo phase, entry test, restart, local fresh/lazy phase) with short comments on what each step does. I would also ask you to state the main results directly in terms of the problem parameters you introduce in your assumptions (μ\mu, LL, LHL_H, the eigengap γ\gamma, the stepsize η\eta), rather than through auxiliary quantities such as qlocq_{loc}, qtarq_{tar} and ρˉ\bar\rho defined in intermediate statements. Then the reader can see what the rates actually are without tracing notation through the whole paper.

9 comments
AuthorsOpenReview ↗

Response to Reviewer QgZv (Part 1)

Thank you for the detailed review and for recognizing the relevance of exploiting Hessian spectral structure and the technical correctness of the analysis you checked. Your comments prompted us to make the implications of the results explicit and strengthen the connection between theory and implementation. All references below refer to the revised manuscript, where major changes are highlighted in blue.

1. W1 / Q(a,e): The main results should explain what is gained.

Our main result combines two guarantees: under the stated local conditions, lazy PSNG retains a remaining-spectrum iteration bound while requiring only finitely many HVPs, with initialization and parameters fixed as the target accuracy decreases. The analysis answers three connected questions.

How accurate must the subspace be? On strongly convex quadratics, Theorem 3.1 bounds the possible increase over a fixed positive exact-subspace contraction factor by Cηδ2C_\eta\delta^2, where δ\delta is the projector error. This quadratic order is sharp in general (Appendix B.3). Corollary 3.2 then gives an explicit subspace tolerance, independent of the final target accuracy, that preserves the remaining-spectrum iteration bound. Thus, improving the optimization accuracy does not require continually improving the subspace accuracy.

Does this benefit survive when the Hessian changes? Proposition 4.4 and Theorem 4.5 establish sufficient conditions for maintaining the required contraction through tracking and curvature reuse. The added Corollary 4.6 makes the resulting nonlinear local rate explicit. On the fixed neighborhood N\mathcal N, define

\widehat L_\perp=\sup_{x\in\mathcal N}\lambda_{r+1}(H(x)),\qquad \kappa_\perp=\widehat L_\perp/\widehat\mu.$$ With $\eta=2/(\widehat L_\perp+\widehat\mu)$ and the stated accuracy, initialization, and refresh conditions, both fresh and lazy PSNG satisfy $$V_t\le\left(1-\frac{1}{2(\kappa_\perp+1)}\right)^tV_0, \qquad T\le\left\lceil2(\kappa_\perp+1)\log(V_0/\varepsilon)\right\rceil,$$ where $V_t=\lVert x_t-x^{\star}\rVert_{H_t}$ and $0 \lt \varepsilon \lt V_0$. The GD comparison uses the same starting point and error measure, with *full-spectrum* condition number $\widehat L/\widehat\mu$, where $\widehat L=\sup_{x\in\mathcal N}\lambda_1(H(x))$ (Appendix D.4). The favorable regime is therefore explicit: a few large eigenvalues cause poor conditioning, while the *remaining spectrum* is much better conditioned. ***How much curvature computation is needed to retain this rate?*** Fresh PSNG uses a fixed HVP budget per iteration after initialization (Proposition 4.4). Lazy PSNG retains the local rate with a finite total HVP bound *independent* of $\varepsilon$ (Theorem 4.5 and Corollary 4.6). The key is to control both subspace error and the mismatch between stored and current projected Hessians. Accumulated step length bounds these changes without additional HVPs for monitoring; the analysis ensures that reuse preserves the required contraction and each refresh restores accuracy within a fixed budget. The resulting trajectory has finite length, so a fixed positive path threshold triggers only finitely many refreshes. The initialization and curvature-work constants can still depend on the full spectrum, eigengap, and Hessian regularity. The contribution is therefore **not merely convergence with frozen curvature, but retaining the remaining-spectrum rate with a finite, explicitly bounded amount of curvature maintenance**. ### 2. W1 / Q(a): The global bound has a $\kappa^2$ dependence, so why use PSNG rather than GD for the initial phase? We now state this dependence directly after **Theorem 4.8**. For $\kappa_G=L/\mu$, $1/L\le\eta\le1/\mu$, and the stated parameter range, $$q_G=1-\frac{4\beta c_A(1-c_A)}{\kappa_G^2}.$$ The resulting bounds are $O(\kappa_G^2\log(\Delta_0/\varepsilon))$ for the objective gap and $O(\kappa_G^2\log\max\\{1,2L^2\Delta_0/(\mu^2R^2)\\})$ for certified local entry. We do not claim that this global phase improves upon GD, or that the dependence has been proved to be merely an analysis artifact. Its role is to provide a safe, unified procedure from arbitrary starting points. The spectral acceleration claim concerns the local phase; the global guarantee does not require accurate eigenspaces.
AuthorsOpenReview ↗

Response to Reviewer QgZv (Part 2)

3. W2 / Q(b,e): Which algorithm is analyzed and used, and is an explicit phase switch necessary?

The no-restart algorithm actually has direct guarantees. We have added Algorithm 2 (Appendix E.1), which explicitly specifies Armijo backtracking, accumulation of accepted step lengths, and an optional curvature restart. The logistic experiments use this algorithm with the restart disabled; numerical implementation settings are documented in Appendix F.2.

Under global strong convexity and smoothness, Theorem 4.8 and Corollary 4.9 directly establish global linear convergence and a finite total HVP bound for the no-restart lazy procedure. These results allow any starting point and any orthonormal initial basis, with fixed positive stepsize and path-threshold parameters and fixed finite power budgets. The HVP bound includes initialization and subsequent curvature refreshes and is independent of the target accuracy when initialization and parameters are fixed. Neither the algorithm nor these global guarantees require a local radius RR, an entry test, or a known initial-overlap bound.

Armijo can accept full steps without an explicit phase switch. Proposition E.1 shows that, under its local regularity assumptions, if the curvature approximation continues to satisfy the stated contraction condition, Armijo eventually accepts αt=1\alpha_t=1 at every iteration. This is a result about full-step acceptance, not a guarantee of the sharper local spectral rate.

The optional restart provides a certified route to the local guarantees. Proposition E.2 combines a gradient-based entry test with curvature reinitialization at the same iterate. The test certifies that the iterate is sufficiently close to the minimizer; restart establishes the required subspace accuracy. With the prescribed local parameters, the subsequent steps satisfy Armijo and inherit the local convergence and HVP bounds. This route requires valid local bounds, including RR, but these are needed only to certify the stronger local guarantee—not to run or establish global convergence of the no-restart procedure.

4. W2 / Q(b): How is the required overlap obtained at initialization or restart?

The new Lemma C.2 provides an explicit Gaussian-initialization guarantee. For Q0=orth⁡(G)Q_0=\operatorname{orth}(G) with an independent Gaussian GG, full-rank overlap holds almost surely. For any specified failure probability pp, the lemma gives a bound Γp(d,r,p)\Gamma_p(d,r,p) with probability at least 1−p1-p, which can be inserted into the bootstrap budget without knowing the leading eigenvectors or computing their angle. The same statement holds conditionally at a restart when the Gaussian draw is independent of the preceding history (Appendix E.4). This resolves the quantitative overlap requirement, although the certified local rate still requires the other regularity and spectral bounds.

5. W2 / Q(c): How can a fixed complementary stepsize be selected without knowing the spectrum throughout the neighborhood?

Exact spectral information throughout the neighborhood is not required. The new Remark F.1 exploits the structure of regularized logistic regression:

=\lambda I+\frac{A^\top A}{4n} \qquad\text{for every }w.$$ Thus, any finite upper bound $L_\perp\ge\lambda_{r+1}(H(0))$ gives an admissible interval $0<\eta<2/L_\perp$ in which the complementary contraction condition holds globally. In particular, $\eta=2/(\lambda+L_\perp)$ gives $$\sup_w\max_{i>r}|1-\eta\lambda_i(H(w))| \le\frac{L_\perp-\lambda}{L_\perp+\lambda}<1.$$ A fully computable choice is $$L_\perp=\lambda+\frac{\|A\|_F^2}{4n(r+1)},$$ which requires one pass over the data and no HVPs. Although this bound can be conservative, it provides a guaranteed choice without knowing the minimizer or computing spectra along the trajectory. **The stepsize can also be tuned and then held fixed.** The spectral formula is a sufficient choice, not a mandatory implementation rule; tuning within the admissible interval preserves the complementary contraction condition. Separately, under global strong convexity and smoothness, Theorem 4.8 guarantees global convergence of Armijo PSNG for any fixed $\eta>0$. Here $\eta$ sets the relative scale of the complementary update, while Armijo selects the overall step coefficient $\alpha_t$. In the logistic experiments, we use Lanczos once at $w_0=0$ to choose $\eta$, then keep it fixed throughout optimization without a stepsize search. We slightly increase the estimated eigenvalue, and offline checks confirm that the resulting value is an upper bound on $\lambda_{r+1}(H(0))$ for the reported instances. Since $H(w)\preceq H(0)$ for every $w$, **this stepsize satisfies the complementary contraction condition throughout optimization, not just at initialization**. The cost of the initial Lanczos computation is included in each run (Appendix F.2).
AuthorsOpenReview ↗

Response to Reviewer QgZv (Part 3)

6. W2 / Q(d): Is there a demonstrated wall-clock benefit over Newton–CG and L-BFGS?

Yes, in the newly added controlled nonquadratic benchmark with d=10,000d=10{,}000 and r=12r=12 (Appendix F.3, Tables 2–3 and Figures 3–4). Its Hessian changes along the trajectory; at the minimizer, the full and remaining-spectrum condition numbers are 10410^4 and 1010. We compare eight optimizers over five objective seeds, with three timing repetitions per seed, the same initial point and relative-gradient target 10−610^{-6}. Timing includes initialization, curvature computation, and line searches.

Results from Table 2 (relative-gradient target 10−610^{-6}):

MethodMedian iterationsMedian scalar HVPsMedian time to target (s)
Lazy PSNG592761.775
Fresh PSNG582,1847.494
Newton–CG61421.970
FOSI-GD124962.819
L-BFGS39406.065
SONIA1358,64023.395
NAG1,185029.304
GD5,000 (cap)0Not reached

GD did not reach the target on any seed; all other methods reached it on all five.

Lazy PSNG is faster than Newton–CG on four of five seeds, with a median paired speedup of 1.39×; the paired speedup over L-BFGS is 3.89×. Paired speedups are computed within each seed, not by dividing the aggregate median times. Lazy also reduces median HVP work by 87.4% relative to fresh PSNG, with nearly unchanged iteration counts.

Paired speedups from Table 3:

BaselineMedian paired speedup (baseline/lazy)Seeds where lazy PSNG is faster
Newton–CG1.389×4/5
FOSI-GD1.944×5/5
Fresh PSNG4.222×5/5
L-BFGS3.890×5/5
SONIA14.583×5/5
NAG18.468×5/5

This identifies a favorable measured regime, not universal superiority over Newton–CG. The quartic benchmark is not globally smooth, so it is a runtime test rather than a verification of the global theorem assumptions. Newton–CG remains fastest on the original small logistic benchmarks. The summary of Table 2 also shows why iteration counts and scalar-HVP equivalents alone do not determine runtime: Newton–CG uses fewer of both, but lazy PSNG has lower median elapsed time in this implementation. Appendix F.2 now separates oracle, arithmetic, and storage costs; batching and the cost of repeated linear solves matter alongside the spectrum.

Regarding the fixed-pair comparison, we agree that refreshing is unnecessary when the initial pair remains effective. The changing-curvature experiment addresses a different question: whether a few refreshes can preserve fresh PSNG's convergence when that pair becomes outdated. Across ten validation seeds, the fixed pair needs about 3.7× as many iterations as lazy, while lazy saves about 79% of fresh's HVPs (Appendix F.5). This supports selective maintenance rather than refreshing unconditionally.

7. Q(e): The method and rates should be readable without following a chain of auxiliary definitions.

We thank the reviewer for the constructive suggestion. We have rewritten the main local statements using the local spectral endpoints and an explicit contraction factor, added the direct condition-number bound in Corollary 4.6, stated the global κG2\kappa_G^2 dependence, and supplied the complete algorithm with comments. The revised introduction emphasizes the distinction between convergence quality, the curvature work needed to maintain it, and runtime. These changes expose both the contribution and its assumptions without requiring the reader to reconstruct them from intermediate lemmas.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.