When Do Worst Cases Align? Exact Covariance Contact in Volume Sampling
Abstract
We give the exact contact geometry of the universal covariance ceiling in volume-sampled least squares. Consider ordinary fixed-size volume sampling for unweighted least squares. Only the subset draw is random, while the design and response are fixed. We assume positive residual loss and no rank-critical row. The full contact space is the kernel of an explicit positive semidefinite operator. This space is unchanged across all strict-interior subset sizes. We show that varying the residual yields a finite orthogonal family of nonzero contact spaces. This family gives exact criteria for whole-query contact and the existence of a contact direction. Beyond exact contact, we quantify departure from the covariance ceiling. A leave-one-out quantity gives two-sided bounds on the normalized gap across all such subset sizes. These bounds also apply to designs with no contact direction. We also use this geometry to build certificates for expected query-MSE excess over the full-data fit. On fixed regression workloads, added information reduces sufficient sample sizes on fixed grids. Lower bounds can also certify that selected sizes exceed the risk allowance.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.