Least Squares Estimation Using Sketched Data with Heteroskedastic Errors

Sokbae Lee, Serena Ng

Abstract

Researchers often perform regressions using a "sketch" of data of size $m$ instead of the full sample of size $n$ to alleviate computational burdens. This paper investigates the behavior of sketched estimators when regression errors exhibit heteroskedasticity—a condition where error variance is non-constant across observations. We demonstrate that estimates derived from data sketched via random projections (RP) behave as if the underlying errors were homoskedastic, a property not shared by random sampling (RS) methods. This "homogenization" effect occurs because sketched estimates in the RP context can be expressed as degenerate $U$-statistics, which, under specific conditions, are asymptotically normal with homoskedastic variance. We verify these conditions for both Ordinary Least Squares (OLS) with exogenous covariates and Instrumental Variables (IV) estimation. Our findings imply that inference, including first-stage $F$-tests for instrument relevance, can be significantly simplified when using appropriate sketching schemes.

Introduction

In modern econometrics and data science, the sheer volume of data often makes traditional estimation techniques computationally prohibitive. Sketching—a dimensionality reduction technique that compresses a dataset from $n$ observations to a smaller representative sample $m$—has emerged as a vital solution. However, most existing literature on sketching assumes homoskedasticity (constant error variance). In practice, empirical data is frequently heteroskedastic, requiring the use of robust standard errors to ensure valid inference.

This paper identifies a surprising "free lunch" associated with specific sketching techniques. We show that while random sampling preserves the heteroskedasticity of the original data, random projections effectively "mix" the observations in a way that averages out individual variances. This results in a sketched dataset that behaves as if it were homoskedastic, allowing researchers to use simpler, standard inference tools without the usual size distortions associated with non-constant variance.

Methodology: Sampling vs. Projection

The study compares two primary approaches to data reduction:

  1. Random Sampling (RS): This involves selecting a subset of the original rows (e.g., via Bernoulli or Uniform sampling). Because RS is data-preserving, the heteroskedastic nature of the original errors remains intact in the sketch.
  2. Random Projections (RP): This involves multiplying the data by a random matrix to create "synthetic" observations that are linear combinations of the original ones. The authors specifically examine CountSketch (CS) and the Subsampled Randomized Hadamard Transform (SRHT).

By treating the sketched estimates as degenerate $U$-statistics, the authors prove that random projections act as a statistical equalizer. Because each sketched observation is a weighted sum of many original observations, the individual variances are homogenized in the limit. This theoretical framework is extended from standard OLS to Two-Stage Least Squares (2SLS), which is critical for addressing endogeneity in econometric models.

Empirical Evidence and Simulations

Monte Carlo Simulations

To test the theory, the authors generated synthetic datasets with $n = 1,000,000$ observations and $p = 6$ regressors, incorporating extreme heteroskedasticity where error variance was tied exponentially to a specific variable.

The results were stark:

  • Random Sampling methods (Bernoulli/Uniform) exhibited "size distortions" as high as 31%. This means they falsely identified significant results at a 31% rate when the nominal target was 5%.
  • Random Projections (CountSketch and SRHT) maintained a size of 5% using simple, non-robust standard errors. This confirms that RP effectively eliminates the need for complex robust variance estimators in the sketched space.

Empirical Illustration: Return to Education

The authors re-evaluated the landmark study by Angrist and Krueger (1991) on the economic returns to education. Using a dataset of approximately 247,000 observations and quarter-of-birth as an instrumental variable, they applied sketching to the 2SLS model. With a sketch size of $m \approx 61,000$, the RP-sketched estimates were remarkably close to the full-sample results. Crucially, the "homoskedastic-only" standard errors in the RP sketch were nearly identical to the robust standard errors, validating the homogenization theory in a real-world setting.

Key Insights

  • Simplified Inference: For data sketched via RP, standard $F$-tests for instrument relevance (checking for "weak instruments") can be performed using the "naive" homoskedastic version without fear of distortion.
  • Efficiency: Sketching via random projections can be more efficient than sampling because it incorporates information from the entire original sample into the compressed synthetic observations.
  • Computational Speed: CountSketch is particularly advantageous for large-scale applications because it is a sparse projection, making the computation time $O(nnz(A))$, where $nnz$ is the number of non-zero elements.

Conclusion and Future Directions

While this paper establishes the homogenization property for linear OLS and 2SLS models, several avenues for future research remain. The current proofs for asymptotic normality specifically target the i.i.d. column structure of matrices like CountSketch; extending these formal proofs to the more structured SRHT matrix is a logical next step. Additionally, while the authors suggest that this property may extend to non-linear models like logistic regression, formal theoretical verification is required. Finally, while the paper provides guidance on choosing the sketch size $m$ for valid inference, balancing statistical power with computational savings remains a practical challenge for the end-user.

Summary updated

Abstract

Researchers may perform regressions using a sketch of data of size $m$ instead of the full sample of size $n$ for a variety of reasons. This paper considers the case when the regression errors do not have constant variance and heteroskedasticity robust standard errors would normally be needed for test statistics to provide accurate inference. We show that estimates using data sketched by random projections will behave `as if' the errors were homoskedastic. Estimation by random sampling would not have this property. The result arises because the sketched estimates in the case of random projections can be expressed as degenerate $U$-statistics, and under certain conditions, these statistics are asymptotically normal with homoskedastic variance. We verify that the conditions hold not only in the case of least squares regression when the covariates are exogenous, but also in instrumental variables estimation when the covariates are endogenous. The result implies that inference, including first-stage F tests for instrument relevance, can be simpler than the full sample case if the sketching scheme is appropriately chosen.
BibTeX
@inproceedings{lee2022least,
  author = {Sokbae Lee and Serena Ng},
  title = {{Least Squares Estimation Using Sketched Data with Heteroskedastic Errors}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=-AR7IC5bYM},
}
Figure