Optimal Linear Regression Without a Variance

We study high-probability linear regression in the infinite variance regime, where the regression noise has only a finite conditional $\alpha$-moment $\nu$ for an unknown $\alpha \in (1,2)$, and the covariates may also be heavy-tailed. We give a black-box reduction that converts finite-variance regression procedures into weak-moment procedures. The reduction is based on empirical residual pruning and is agnostic to the moment exponent, the noise scale, the covariance, and the design moment constant. Under a finite fourth-moment condition on the covariates, any finite-variance subroutine with the sub-Gaussian rate yields the following for all $n$ above a suitably defined threshold: $\Vert \hat{\theta }-{\theta }^{\ast }{\Vert }_{\Sigma }{\lesssim }_{\alpha }{\nu }^{1/\alpha }{\left(\frac{d+\log (1/\delta )}{n}\right)}^{\frac{\alpha -1}{\alpha }}$ with probability at least $1-\delta$, without knowing $\alpha$ or $\nu$. We further prove a matching minimax lower bound that holds under the same conditions. The reduction is computationally efficient whenever the finite-variance subroutine is. We also obtain a distribution-free prediction guarantee under a bounded raw $\alpha$-moment assumption on the response, and give an analogous $\alpha$-agnostic reduction for mean estimation.