acceptodds
Under review as a conference paper at ICLR 2027

Spectral Reuse under Squaring: A Sharp Locality Threshold

Abstract

Cached curvature responses support reliable update-length decisions only with an inverse-square guarantee; a quadratic-form guarantee alone is insufficient. We identify a sharp transition governed by spectral locality: for a Loewner approximation factor and log-spectral coupling width , the optimal inverse-amplification norm over all dimensions and condition numbers is finite exactly when . We derive this optimal norm and construct an asymptotically sharp chain whose amplification grows linearly with dimension at the threshold and exponentially above it. Numerical scans of finite chains show all three regimes. For unrestricted coupling, an exact square-distortion law gives the complementary condition , where and bounds the reference condition number. Together, these bounds give an update-length interval that accounts for asymmetric inputs, damping, and nonzero spectral tails. For example selection on synthetic logistic data with local spectral coupling, this interval reduces Hessian–vector products by a factor of ( to per batch) relative to global exact screening. It also reduces selection time by ( to  ms). On 1024-dimensional digits features, global exact screening reduces total time from to  s over 32 training steps with cache refreshes. Direct Cholesky is faster in the evaluated cold-start and banded settings.

Primary area:
optimization
Keywords:
Spectral approximation, Matrix squaring, Spectral locality, Curvature reuse

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_CMA8OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper examines how accurately a cached curvature matrix AA can approximate a nearby matrix BB when estimating the norm of a curvature-preconditioned vector. Since this quantity involves inverse squares, non-commutativity plays an important role.

Under a spectral locality assumption, Theorem 4.1 establishes a tight bound independent of the matrix dimension and condition number, and characterizes when this bound remains finite. Theorem 5.1 further derives an exact worst-case bound for unrestricted spectral coupling, while a corollary extends the analysis to approximate locality.

The authors evaluate the proposed bounds through a screening procedure for logistic regression using synthetic data, random Fourier features, and frozen MLP and Pythia-70M features. Cached curvature estimates provide bounds on ∥H−1g∥\|H^{-1}g\|, with PCG applied only to cases that cannot be resolved directly. Computational efficiency is assessed using HVP counts and wall-clock time, with comparisons against global screening, Chebyshev-based bounds, and direct Cholesky factorization.

Critical strengths
  1. Tight theoretical bounds. The paper establishes matching upper and lower bounds, including an asymptotically tight construction under spectral locality and an exact characterization for unrestricted coupling. I also checked the main formulas numerically and found no apparent errors, which supports the theoretical validity of the results.

  2. Clear acknowledgment of limitations. The authors report that direct Cholesky is faster in the evaluated settings, include a relevant Chebyshev-based baseline, and acknowledge that their experiments are limited to fixed-feature models. I appreciate this transparency, although these findings also raise questions about the practical significance of the proposed approach.

Critical weaknesses
  1. Limited novelty and empirical improvement over existing bounds. The sharp locality threshold can already be obtained from a Chebyshev expansion, as the authors acknowledge (pp. 2–4). Related decay results are also well established, and Appendix J notes that Janas et al. (2018) recover the sharp scalar-chain norm. The main theoretical contribution therefore appears to be a constant-factor improvement (less than 2×) and a generalization to arbitrary spectral configurations. The unrestricted result similarly improves the constant rather than the asymptotic dependence.

    The empirical gains are modest. Compared with the Chebyshev baseline, HVP counts decrease by only 2.1–5.5% (Table 5), with very small differences in runtime (Table 6). The local method is also slower than global screening on dense features (Tables 14–15). The reported 3.1× HVP reduction is relative to a baseline that does not exploit structure, while direct Cholesky remains faster in the evaluated settings. Overall, I find the improvement over existing methods too limited to establish a substantial contribution.

  2. Insufficient evidence of practical relevance. Reusing cached curvature information could be useful for methods such as Shampoo/SOAP, K-FAC, or influence-function estimation. However, the experiments are restricted to fixed-feature logistic regression, with dimensions up to 1024 and Pythia-70M as the largest backbone. All experiments run on a single CPU thread in float64 (Appendix K). It remains unclear whether the proposed bounds offer meaningful advantages in realistic large-scale settings.

    Moreover, the screening task is defined specifically for this paper, without demonstrating benefits for actual training or data selection. The experiments therefore do not establish when the method would be preferable to existing approaches.

    The presentation also needs improvement. Several appendices contain extensive numerical results with limited interpretation or material whose relevance to the main contribution is unclear. Appendix O retains revision artifacts and indicates that some raw records and plotting scripts needed for reproduction are missing. These issues make the empirical results difficult to assess and reproduce.

Questions for authors
  1. Beyond the less than 2× improvement in the constant, are there settings where the new locality bound meaningfully changes screening decisions or reduces runtime compared with the Chebyshev bound? If possible, please quantify this using existing logs, including how often the bound is finite, the magnitude of the weighted spectral tails, and which bound determines the final interval.

  2. Could the authors evaluate the proposed method in a more realistic setting where curvature reuse matters, such as delayed Shampoo/SOAP or K-FAC updates, or influence-function estimation with EK-FAC? Comparisons with Chebyshev and a simple periodic-refresh baseline would be helpful. It would also be useful to know whether spectral locality holds empirically in these settings.

  3. What practical benefit does the proposed screening task offer over random selection or using all examples?

  4. Could the authors provide instructions to reproduce the main tables from a clean environment and clarify which results depend on historical raw data that are no longer available?

Reviewer_jAQ8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of reusing cached inverse-curvature information for update-length estimation. The authors claism that existing spectral approximation guarantees may not be sufficient for accurate update-length estimation. To address this problem, the paper provides theoretical analysis and derives several bounds on the estimation error. Based on these results, the authors further propose a method for estimating update lengths with certified intervals and apply it to example selection.

Critical strengths
  • The paper identifies and resolves a meaningful theoretical distinction.

  • The theoretical results are supported by proofs, and the derived bounds are tight.

Critical weaknesses
  1. Limited discussion of the practical impacts. Although the paper provides tight theoretical bounds, it is still unclear how these results can guide practical cache reuse strategies. Discussion or application on using the derived bounds in real optimization problems are limited in this paper.

  2. Applicability of the assumptions are unclear. Proposed theoretical results rely on the log-spectral locality assumption. However, it is unclear how easily this assumption can be satisfied in practical scenarios.

  3. Limited analysis of computational overhead. The computational cost of obtaining and maintaining these guarantees is not clear. It would be helpful to analyze the additional computational and memory overhead, especially for large-scale applications.

Questions for authors
  1. How can the log-spectral locality assumption be satisfied in real-world optimization problems, and Is it easy to check this assumption in practice?

  2. How can the proposed theoretical bounds help decide when to reuse cached information?

Reviewer_qJyhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work studies curvature reuse for deciding update‑length thresholds given Loewner‑sandwiched positive‑definite curvature matrices A and B, identifying a sharp phase transition controlled by log‑spectral locality. It derives optimal distortion bounds both for spectrally‑local perturbations and for the unrestricted high‑condition‑number setting, then combines these bounds to build an interval‑based screening procedure for example selection in logistic regression training. The method validates theoretical phase‑transition predictions and measures practical runtime and Hessian‑vector‑product reductions across synthetic and real‑world feature datasets.

Critical strengths

The derivations in the paper are rigorous. The paper derives an exact threshold separating bounded dimension‑independent inverse amplification from linear/exponential norm growth, and provides matching constructive chain examples, advancing prior work on squared‑system preconditioning.

Critical weaknesses
  1. For general dense random‑feature cases, the overhead of estimating spectral tails may erase HVP savings, limiting its real‑world utility.

  2. More comparisons against recent curvature‑reuse optimizers are needed.

Questions for authors
  1. If this spectral‑reuse machinery were to be extended to end-to-end neural network training, what would be the primary obstacles?

  2. Can the proposed screening mechanism be integrated as a sub-routine within existing frameworks (e.g., K-FAC, Shampoo, SOAP)?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.