Near-optimal Coresets For Least-Squares Regression
This addresses computational efficiency in regression for machine learning practitioners, though it appears incremental as it builds on existing coreset methods.
The paper tackles the problem of efficiently constructing coresets for least-squares regression, providing deterministic polynomial-time algorithms with approximation guarantees and showing lower bounds that indicate near-optimality.
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.