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: $ \lVert \widehat\theta-\theta^* \rVert_\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.