Debiasing Sketched Ridge Regression: A Functional Estimation Perspective

We study sketched Ridge regression through the lens of functional estimation. The sketched solution is a plug-in estimator of a nonlinear function of a second-moment/covariance matrix. Within this framework, we analyze two classical bias-reduction principles---iterative Bootstrap and linear aggregation across multiple estimators. We show that these resampling-based procedures cancel low-order bias terms and yield higher-order bias decay in the sketch size without increasing the order of the computational complexity. Concretely, let $A\in\mathbb{R}^{n\times r}$ have full column rank $r$ and let the sketch size be $s$. For Gaussian sketching, a $k$-step iterative Bootstrap estimator achieves bias of order $(\sqrt{r/s})^{k+2}$. For linear aggregation over $m$ plug-in estimators with different sketch sizes, we obtain bias of order $(\sqrt{r/s})^{m+1}$ for Gaussian sketching and corresponding result for common discrete sketches, including uniform and leverage score sampling.