Abstract
In the analysis of massive datasets, sketching techniques are frequently employed to reduce computational overhead by compressing the sample size from $n$ to $m$. However, traditional sketching theory often relies on the assumption of homoskedasticity—constant error variance—which is rarely met in econometric applications. This paper investigates the performance of sketching in the presence of heteroskedasticity and endogeneity. We demonstrate that while random sampling preserves the heteroskedasticity of the original data (necessitating complex robust standard errors), random projections act as a "blender," homogenizing the data. This effect allows researchers to perform valid inference using standard, non-robust formulas, effectively providing a "free lunch" for big data inference in Two-Stage Least Squares (2SLS) frameworks.
Introduction
As datasets grow into the millions of observations, the computational cost of traditional regression analysis becomes a significant bottleneck. Sketching—a dimensionality reduction technique that multiplies a large data matrix by a random matrix $\Pi$—has emerged as a primary solution. By creating a smaller "sketch" of the data, researchers can perform regressions in a fraction of the time.
Despite its popularity, the theoretical foundations of sketching have largely ignored two pillars of causal inference: heteroskedasticity and endogeneity. In fields like economics, the assumption that error terms have constant variance is almost always violated. Furthermore, predictors are often correlated with the error term, requiring the use of Instrumental Variables (IV) and Two-Stage Least Squares (2SLS). This research addresses whether sketching remains a viable tool under these realistic, "messy" conditions.
The Sketching Framework: Sampling vs. Projection
The paper distinguishes between two primary categories of sketching:
- Random Sampling: This involves selecting a subset of the original rows (e.g., via Bernoulli or Uniform sampling). While computationally simple, this method preserves the underlying structure of the data, including its heteroskedasticity.
- Random Projections (RP): This involves creating linear combinations of all original observations. The study focuses on methods such as CountSketch (CS), Gaussian Projections (GP), and the Subsampled Randomized Hadamard Transform (SRHT).
Using the theory of degenerate U-statistics, the authors extend the analysis of these methods from Ordinary Least Squares (OLS) to the more complex 2SLS estimator. The goal is to determine how these different sketching strategies affect the validity of subsequent statistical tests.
The "Free Lunch" of Homogenization
The central discovery of this research is the Homogenization Effect. When using random projections, the act of taking linear combinations of many observations smooths out the varying variances of individual errors. Mathematically, the sketched estimator behaves as if the original errors were homoskedastic, with a variance that converges toward the average error variance of the full sample.
This leads to a significant practical advantage: Simplified Inference. In a standard heteroskedastic environment, researchers must use robust standard errors (such as the White estimator) to avoid false positives. However, because random projections homogenize the data, the simplest versions of $t$-tests and $F$-tests remain valid on the sketched data. This property is particularly valuable for 2SLS, where first-stage $F$-tests are critical for assessing instrument strength.
Empirical Validation
Monte Carlo Simulations
The authors conducted simulations with $n = 10^6$ and $m = 500$, introducing high levels of heteroskedasticity. The results were stark:
- Random Sampling (Bernoulli/Uniform) exhibited massive size distortions. When the null hypothesis should have been rejected only 5% of the time, these methods showed rejection rates as high as 31% when using standard errors.
- Random Projections (CountSketch/SRHT) maintained a near-perfect 5% rejection rate using simple standard errors, confirming the theoretical homogenization effect.
Application: The Return to Education
To test the theory on real-world data, the authors re-examined the classic Angrist and Krueger (1991) study on the economic returns to education. Using a dataset of $n = 247,199$ observations, they used quarter-of-birth as an instrument for schooling.
Sketching with $m \approx 61,000$ for 2SLS yielded estimates nearly identical to the full-sample results. Crucially, for the projection methods, the standard and robust error estimates converged, demonstrating that the "blender" effect holds even in complex socioeconomic datasets where heteroskedasticity is a known factor.
Conclusion and Future Directions
This research establishes that random projections are not just a tool for speed, but a tool for statistical simplification. By naturally transforming heteroskedastic problems into homoskedastic ones, projections allow for valid inference without the added complexity of robust estimators.
While the study provides a robust framework for linear OLS and 2SLS, several avenues for future work remain. Formal proofs for the SRHT and Subsampled Randomized Fourier Transform (SRFT) are still needed due to the lack of independence between their columns. Additionally, exploring whether this homogenization effect extends to non-linear models, such as the Generalized Method of Moments (GMM) or Logit regressions, represents a promising frontier for big data econometrics.
Summary updated