Distributed Sketching on Data Partitions for OLS Regression
Provides theoretical guarantees for a computationally cheaper distributed OLS method, but the result is incremental as it extends existing sketching theory to partitioned data.
This paper studies distributed sketching for OLS regression on partitioned data, showing that the excess loss of the averaged estimator is comparable to sketching on the whole data when subset covariances diverge little.
This paper studies distributed sketching for ordinary least squares (OLS) regression, an approach that distributes small sketches of a large data set over multiple machines to separately construct OLS estimators and average them. Unlike prior studies that consider sketching on the whole data set, we consider sketching on partitioned subsets to further reduce computational cost. Under the fixed design setting, we characterize the exact excess loss of the averaged OLS estimator. Results show that this loss is comparable to the established loss for sketching on the whole data set when the divergence among subset covariances is small.