Optimal Experimental Design in Heavy Tailed Linear Regression

Optimal experimental design concerns the selection and allocation of measurements from a given action set for accurate estimation. In this paper, we study and essentially resolve the heavy tailed linear regression setting, where the observation noise only has a bounded $\alpha$ moment for some $1<\alpha \le 2$. We give a novel design criterion $M_{\alpha }(\lambda ;\mathcal{A})$ evaluating a design $\lambda$ on an action set $\mathcal{A}$, and prove that it tightly characterizes the estimation error rate: with the design $\lambda$, a suitable estimator achieves error proportional to $M_{\alpha }(\lambda ;\mathcal{A}{)}^{1/\alpha }{n}^{-(\alpha -1)/\alpha }$, while no estimator applied to this design $\lambda$ can yield better error rate up to constants. This new quantity $M_{\alpha }(\lambda ;\mathcal{A})$ coincides with the classical $G$-optimal design criterion when $\alpha =2$, and is convex in $\lambda$ with an efficiently-computable optimizer ${\lambda }^{\ast }$. We further demonstrate a qualitative separation between ${\lambda }^{\ast }$ and the $G$-optimal design by a factor of $\tilde{\Omega }(d^{1/\alpha -1/2})$ difference in the error. Lastly, we address the problem of finding a (near-)optimal design without knowledge of $\alpha$. We construct a single $\alpha$-agnostic design whose error matches that of the known-$\alpha$ design up to an $O(\sqrt{\log d})$ factor, and we provide a lower bound showing that an $\Omega \left(\sqrt{\log d/\log \log d}\right)$ factor is unavoidable.