POST-SELECTION CERTIFICATION OF GRADIENT CORESETS

Gradient sketches make coreset optimization tractable; valid post-selection certificates require accounting for how the residual was chosen. We give an exact characterization for Gaussian sketches. For least-squares reweighting over a fixed $k$-dimensional affine family, the selected residual’s sketch-to-exact squared-norm ratio is a scaled product of independent chi-square and beta variables. This law supplies an exact model-specific correction and identifies two distinct thresholds: relative distortion vanishes when $k=o(m)$, while uncorrected fixed-vector coverage can vanish when $\sqrt{m}\ll k\ll m$. For arbitrary selectors, a fresh Gaussian projection after commitment gives exact conditional intervals with rank-independent audit dimension. We also account for support-search multiplicity, numerical error, and fidelity to the deployed update. Experiments on Qwen2.5-1.5B/0.5B and GSM8K/MBPP tasks complement the theory with constrained real-model diagnostics: at 512 sketch rows, median residual distortion is 3.4% and ranking correlation is 0.95. Reweighting lowers the primary joint-subset exact residual by 23.6%, while increasing sketch optimism in 43 of 45 matched cells. Uniform bounds cover all 27 primary residuals, with six meeting the full-update tolerance. Together, these results distinguish accurate optimization from useful certification and provide calibrated routes to certifying the selected coreset update.