Introduction: The "Free Lunch" of Data Sketching
In the era of "Big Data," researchers often face severe bottlenecks in storage and computation. Sketching has emerged as a popular solution, where a massive dataset of size $n$ is compressed into a smaller "sketch" of size $m$ using a random matrix. While previous work has heavily focused on the algorithmic speed of these methods, their statistical implications—especially regarding heteroskedasticity—have remained less clear.
This paper reveals a surprising "free lunch" in data sketching: when using random projections (like CountSketch) to compress large datasets for regression, the resulting estimates behave as if the original errors were homoskedastic (having constant variance). This means researchers can perform valid statistical inference on compressed data using simple, standard formulas without needing complex heteroskedasticity-robust corrections.
The Challenge of Heteroskedasticity
In real-world econometrics and data science, regression errors rarely have constant variance. Usually, if you ignore this heteroskedasticity, your "t-stats" and "p-values" become unreliable, leading to false discoveries. Standard practice requires using "robust" standard errors (like the White estimator) to correct for this. The authors investigate whether sketching preserves this statistical headache or, unexpectedly, solves it.
Sketching Methods: Sampling vs. Projection
The authors analyze two main classes of sketching schemes:
- Random Sampling (RS): Selecting a subset of the data (e.g., Bernoulli or Uniform sampling).
- Random Projection (RP): Multiplying the data by a dense or sparse random matrix (e.g., Gaussian Projections, CountSketch, or the Subsampled Randomized Hadamard Transform - SRHT).
They provide a theoretical framework treating the difference between full-sample and sketched estimates as degenerate U-statistics. This allows them to derive the asymptotic distribution of the estimators for both standard Ordinary Least Squares (OLS) and Two-Stage Least Squares (2SLS), the latter being crucial for handling endogenous variables where predictors are correlated with the error term.
Key Insights: The "As-If" Property
The most striking finding is that random projections "homogenize" the error variance. Even if the original data is wildly heteroskedastic, the sketched estimate behaves as if it came from a homoskedastic model.
- Decoupling via Projections: In random sampling, the sketching process preserves the relationship between the regressors and the error variance. However, in random projections, the leading term in the error distribution is a U-statistic where the error variance and the regressor variance decouple, effectively "averaging out" the heteroskedasticity.
- Inference Simplification: Because of this homogenization, researchers do not need robust standard errors when working with random projections. Standard, simpler variance estimators work perfectly fine.
- A Sharp Divide: The paper highlights a critical distinction: Random sampling does not have this property. If you use sampling, you still need robust standard errors to avoid massive "size distortions" (false positives).
Key Results: OLS and 2SLS Performance
The paper's theoretical findings are backed by extensive Monte Carlo simulations and an empirical re-examination of the classic Angrist & Krueger (1991) "return to education" study.
OLS Size Distortions: In simulations with heteroskedastic errors, using standard (non-robust) errors with Bernoulli sampling led to a rejection rate of ~31% for a nominal 5% test—a massive error. In contrast, random projections like CountSketch and SRHT maintained a near-perfect 5% rejection rate using the same simple formulas.
2SLS Performance: The homogenization results also hold for instrumental variable models. Random projection methods provide accurate inference for endogenous regressors without needing robust corrections, whereas sampling methods fail drastically if standard errors are used.
Limitations and Future Work
- Sketch Size ($m$): While the paper provides guides for choosing $m$, the optimal size remains a trade-off between computational gain and statistical precision. Notably, for 2SLS, the required $m$ is larger than for OLS to maintain accuracy.
- Formal Proofs for SRHT: While simulations show SRHT and SRFT behave identically to CountSketch, formal proofs for their asymptotic normality are more difficult because their columns are not independent.
- Beyond Linear Models: The current work focuses strictly on OLS and 2SLS. Extending this "homogenization" theory to non-linear models (like GMM or Logit) remains an open and promising area for future research.
Summary updated