arXiv 3 Jul 2019 · Econometrics · publishedAnnual Review of Economics (2020) · 2 citations (OpenAlex)
arXiv:1907.01954 · PDF · DOI · OpenAlex · Extracted main text
Datasets that are terabytes in size are increasingly common, but computer bottlenecks often frustrate a complete analysis of the data. While more data are better than less, diminishing returns suggest that we may not need terabytes of data to estimate a parameter or test a hypothesis. But which rows of data should we analyze, and might an arbitrary subset of rows preserve the features of the original data? This paper reviews a line of work that is grounded in theoretical computer science and numerical linear algebra, and which finds that an algorithmically desirable sketch, which is a randomly chosen subset of the data, must preserve the eigenstructure of the data, a property known as a subspace embedding. Building on this work, we study how prediction and inference can be affected by data sketching within a linear regression setup. We show that the sketching error is small compared to the sample size effect which a researcher can control. As a sketch size that is algorithmically optimal may not be suitable for prediction and inference, we use statistical arguments to provide 'inference conscious' guides to the sketch size. When appropriately implemented, an estimator that pools over different sketches can be nearly as efficient as the infeasible one using the full sample.
appendix boundary found by appendix_command · 66% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Sarlos (2006) Improved Approximation Algorithms for Large Matrices via Random Projections, Proceedings of the 47 IEEE Symposium on Foundations… | 1.000 | 5 | 4 | 100% |
| 2 | Nelson and Nguyen (2013) OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings, Proceedings of the 54th Annual IEEE Symposium… | 1.000 | 5 | 3 | 100% |
| 3 | Woodruff (2014) Sketching as a Tool for Numerical Linear Algebra, Foundations and Trends in Theoretical Computer Science 10(1-2), 1–157 | 0.843 | 3 | 3 | 100% |
| 4 | Drineas, Mahoney and Muthukrishnan (2006) Sampling Algorithms for L2 Regression and Applications, Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms… | 0.737 | 3 | 2 | 100% |
| 5 | Ahfock, Astle and Richardson (2017) Statistical Properties of Sketching Algorithms, arXiv:1706.03665v1 | 0.644 | 2 | 2 | 100% |
| 6 | Drineas, Mahoney, Muthukrishnan and Sarlos (2011) Faster Least Squares Approximation, Numerical Mathematics 117, 219–249 | 0.644 | 2 | 2 | 100% |
| 7 | Drineas, Kannan and Mahoney (2006) Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplications, SIAM Journal on Computing 36, 132–157 | 0.644 | 2 | 2 | 100% |
| 8 | Geppert, Ickstadt, Munteanu, Quedenfeld and Sohler (2017) Random Projections for Bayesian Regression, Statistics and Computing 27(1), 79–101 | 0.644 | 2 | 2 | 100% |
| 9 | Meng and Mahoney (2013) Low Distortion Subspace Embeddings in Input-Sparsity time and Applications to Robust Linear Regression, Proceedings of the 45th… | 0.644 | 2 | 2 | 100% |
| 10 | Wang, Gittens and Mahoney (2018) Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging, Proceedings of the 34th Inter… | 0.644 | 2 | 2 | 100% |
Showing the top 10 of 74 scored citations.
arXiv econ.EM papers that cite this one, ranked by how heavily they lean on it.
| Citing paper | Intensity | Mentions | Sections | |
|---|---|---|---|---|
| 1 | Algorithmic Subsampling under Multiway Clustering | 0.899 | 11 | 3 |
| 2 | On the Subbagging Estimation for Massive Data | 0.644 | 4 | 1 |
| 3 | Least Squares Estimation using Sketched Data with Heteroskedastic Errors | 0.644 | 2 | 2 |
| 4 | Fast Inference for Quantile Regression with Tens of Millions of Observations | 0.511 | 2 | 1 |
| 5 | SLIM: Stochastic Learning and Inference in Overidentified Models | 0.000 | 1 | 1 |