Spectrum Is Not Enough: A Random-Matrix Account of Data-Free Preconditioning for Differentially Private Learning

Abstract

Data-free preconditioning builds the Kronecker factors of KFAC from synthetic probes instead of private data. DP-KFC validates a probe by matching the eigenvalue decay of the private factors; we turn this criterion into a random-matrix account of what a probe can reconstruct. A single dichotomy organizes it: in the factorization $ A \otimes G $, the error-signal factor $ G $ and the architecture-determined bulk of the activation factor $ A $ are reconstructible without data, while only the data-induced spikes of $ A $ are not. We prove the $ G $ half is data-insensitive up to an explicit error-energy bound, with zero violations over a full training trajectory across four modalities and a natural-image benchmark. We locate the failure boundary at a Baik-Ben Arous-P\'ech\'e threshold: a bulk-only probe suffers an exact damage $s^2/(1-s^2)$ from a data-induced spike, which becomes invisible once it exceeds $(d/n)^{1/4}$, confirmed on an injected-spike surrogate. Holding the probe spectrum fixed and varying only its eigenbasis, we show that spectral-shape matching is neither sufficient nor the operative object: a probe with a near-exact matched spectrum (log-ratio dispersion $0.02$) still inflates the residual $2 \times $-$90 \times $ when its eigenvectors are random. A closed-form whitened-volume law explains this and predicts the within-spectrum ordering of the critical volume, though not its cross-dataset magnitude. Downstream, per-layer tuning does not transfer to accuracy and the headroom is a small oracle-minus-white gap. Under a privacy mechanism the source ordering survives while learning does, then inverts at a noise cross-over where the flat probe overtakes the matched ones.