Near-optimal Coresets For Least-Squares Regression

Abstract

We study (constrained) least-squares regression as well as multiple response least-squares regression and ask the question of whether a subset of the data, a coreset, suffices to compute a good approximate solution to the regression. We give deterministic, low order polynomial-time algorithms to construct such coresets with approximation guarantees, together with lower bounds indicating that there is not much room for improvement upon our results.

To appear in IEEE Transactions on Information Theory

References in corpus (1)

• Principal Component Analysis and Higher Correlations for Distributed Data

Cited by in corpus (16)

• Random projections for Bayesian regression
• Column Selection via Adaptive Sampling
• Active Regression via Linear-Sample Sparsification
• DimmWitted: A Study of Main-Memory Statistical Analytics
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
• Coresets for Gaussian Mixture Models of Any Shape
• Improved Coresets for Euclidean $k$-Means
• Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more
• Reverse iterative volume sampling for linear regression
• Robust approximate linear regression without correspondence
• Robust Coreset Construction for Distributed Machine Learning
• Coresets for Kernel Regression
• Semi-supervised Active Regression
• Training Data Subset Selection for Regression with Controlled Generalization Error
• Coresets for Regressions with Panel Data
• A note on restricted invertibility with weighted columns