Research map / Learning theory and algorithms / Matrix and tensor methods

Fast and Stable Gradient Approximation for Bilinear Forms of Hermitian Matrix Functions

NeurIPS 2026 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a forward-only approximate gradient for Lanczos quadratic forms u^T f(A(θ))u that differentiates only the small tridiagonal problem and lifts sensitivities via VJPs of matrix-vector products, with error bounded by the Lanczos residual β_m.

Problem

Differentiating Lanczos-based approximations of bilinear/quadratic forms of matrix functions with respect to parameters is costly and unstable without reorthogonalization when using backpropagation or adjoint recurrences.

Approach

Reuse the forward Lanczos pass: compute the sensitivity G of the small projected matrix function via the Fréchet divided-difference formula, drop basis-variation terms, and contract W = VG with matrix-vector product VJPs. The dropped error is shown to be proportional to the final residual coefficient β_m.

Key results

• On graph sensitivity at m=32, the method is 1.55x-2.64x faster than modified Arnoldi (KO) with near machine-precision relative gradient error (e.g., 1e-14 on com-Amazon TN).
• On Hamiltonian learning (L=8), m=50 gives relative gradient error 5.62e-7 and final parameter error 1.05e-7, while running 10.4x faster than the dense Fréchet baseline.
• At m=80 on the log-determinant experiment with full reorthogonalization, relative gradient difference from the adjoint gradient drops to about 2.4e-8.

Surprising findings

• On graph sensitivity at m=16, the method is less accurate than KO on ca-HepTh/SC (1e-1 vs 1e-2), showing the approximation can be worse at low depth.
• The paper reports the adjoint-based gradient becomes unstable after m=100 in the log experiment, while the proposed method remains stable without reorthogonalization.

Limitations

• Only Hermitian/symmetric matrices; non-Hermitian extension left open.
• Requires storing all Lanczos vectors, a memory bottleneck for large m and n.
• Analysis limited to scalar objectives u^T f(A)v; does not cover derivatives of f(A)v vectors; prototype implementation has Python overhead.

Experimental setup

Datasets: synthetic Gaussian-process regression data (n=15000 kernel matrix) UCI Protein SNAP ca-HepTh SNAP com-Amazon synthetic transverse-field Ising Hamiltonian data (L=8)

Benchmarks: log-determinant single-probe gradient (n=15000) SNAP graph sensitivity TN/SC Hamiltonian learning L=8 Protein GP training

Metrics: relative gradient error relative value error speedup final parameter error test RMSE relative logdet error

Baselines: Lanczos adjoint (matfree) modified Arnoldi (KO) GPyTorch Lanczos log-det gradient dense Fréchet derivative

Builds on: Lanczos quadrature Fréchet derivative block-triangular identity Kressner and Oehme modified Arnoldi Kramer et al. adjoint Lanczos GPyTorch

Closest papers by meaning

• Nearly Optimal Approximation of Matrix Functions by the Lanczos Method (NeurIPS 2024 · similarity 0.88)
• Gradients of Functions of Large Matrices (NeurIPS 2024 · similarity 0.86)
• Perturbation Bounds for Low-Rank Inverse Approximations under Noise (NeurIPS 2025 · similarity 0.85)
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.85)
• Learning to Discover Iterative Spectral Algorithms (NeurIPS 2026 · similarity 0.85)
• Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.84)