Irregular-spectrum residual preconditioner
Implementation & benchmark of arXiv:2608.09884 — Widom factors for Chebyshev and residual polynomials on semi-regular subsets of $\mathbb{R}$
Source paper: Widom factors for Chebyshev and residual polynomials on semi-regular subsets of $\mathbb{R}$ arXiv:2608.09884 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use a low-degree residual polynomial of the neural-network Hessian rather than an interval-only Chebyshev polynomial, with the polynomial minimized over the bulk Hessian spectrum and isolated outlier eigenvalues simultaneously. The method should reduce oscillation caused by rare sharp directions without shrinking the learning rate for the bulk spectrum.
Formulas
Mathematical statement
For a compact non-polar spectral set E of positive logarithmic capacity Cap(E), the monic Chebyshev polynomial T_n is the degree-n monic polynomial minimizing the supremum norm ||T_n||_E = sup_{lambda in E}|T_n(lambda)|. Its Widom factor is W_n(E) = ||T_n||_E / Cap(E)^n, removing the leading exponential scale. For a semi-regular E, whose regular boundary points E^reg form a closed set, the paper defines IR(E,x_*) = sum_{x in E\\E^reg} G_E(x,x_*), where x_* is outside E and G_E(.,x_*) is the Green function of the complement of E with pole x_*. The bounds sup_n W_n(E,x_*) <= 2 exp(PW(E^reg,x_*) + IR(E,x_*)) and liminf_{n->infinity} W_n(E,x_*) >= 2 exp(IR(E,x_*)) show that isolated or irregular spectral components create a multiplicative worst-case penalty. Adapt this to a Hessian residual polynomial p_n(lambda) with p_n(0)=1: minimize rho_n = max_{lambda in E_hat}|p_n(lambda)| over an empirical spectral set E_hat consisting of bulk intervals plus detected outliers. Applying p_n(H) to a gradient multiplies the eigen-component with curvature lambda by p_n(lambda), allowing the polynomial to damp isolated sharp directions while preserving progress on the bulk.
Implementation notes
(1) Integration point: modify the optimizer update immediately after computing the minibatch gradient g_t and before the parameter update. Use a degree-n polynomial p_n(H_t) with p_n(0)=1, where H_t is a Hessian or Gauss-Newton operator at the current parameters. Do not materialize H_t; use automatic-differentiation Hessian-vector products. The update is theta_{t+1} = theta_t - eta p_n(H_t)g_t. A residual formulation computes p_n(H_t)g_t = c_0g_t + c_1H_tg_t + ... + c_nH_t^ng_t.
(2) Pseudocode: every M optimizer steps, estimate a spectral support E_hat for H_t. Run stochastic Lanczos for 20-40 iterations on several minibatches, collect Ritz values, cluster the central values into J bulk intervals [a_j,b_j], and retain separated values xi_k as outliers. On a dense grid Lambda contained in E_hat, parameterize p(lambda)=1+sum_{r=1}^n c_r lambda^r and solve the linear program minimizing rho subject to -rho <= p(lambda) <= rho for every lambda in Lambda. Refine Lambda by inserting approximate extrema of the current polynomial, then resolve. During training, compute v_0=g_t, v_{r+1}=H_tv_r using one HVP per degree, and return u_t=sum_{r=0}^n c_rv_r.
(3) Mathematics versus estimates: the minimax objective, normalization p(0)=1, Widom factor, and irregularity interpretation come from the paper. Capacity, the Green function, and the Parreau-Widom term need not be computed in the first implementation. Estimate practical irregularity by comparing rho_n(E_hat) with rho_n(E_bulk), where E_bulk is the interval hull, and optionally approximate G_E(xi_k,x_*) using a discretized harmonic solve. Recompute coefficients when the estimated Ritz spectrum changes substantially.
(4) First experiment: train a two-layer MLP on CIFAR-10 or a small transformer on a language-model corpus. Compare SGD or AdamW, an ordinary Chebyshev polynomial designed on the interval [lambda_min,lambda_max], and the disconnected-support minimax polynomial at degrees 2, 4, and 8. Recompute coefficients every 100-500 steps and report training loss versus optimizer FLOPs, gradient-norm spikes, validation accuracy or perplexity, maximum observed curvature, and stable learning-rate range. Use a synthetic quadratic with a bulk spectrum plus one rank-one outlier as a cheap unit test. Success means faster loss descent at equal HVP cost, fewer instability spikes, or a larger stable learning-rate range than interval Chebyshev acceleration.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.