Near-Optimal Coresets for Least-Squares Regression

DOI10.1109/TIT.2013.2272457zbMATH Open1364.62170OpenAlexW1992065791MaRDI QIDQ5346331FDOQ5346331

Authors Christos Boutsidis, Malik Magdon-Ismail, Petros Drineas 

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.3505

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Learning and adaptive systems in artificial intelligence (68T05) Parametric inference under constraints (62F30)

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.

Cited in

(6)

• Random projections for Bayesian regression
• Jointly evolving and compressing fuzzy system for feature reduction and classification
• Reverse iterative volume sampling for linear regression
• Core-elements for large-scale least squares estimation
• Generating neural archetypes to instruct fast and interpretable decisions
• Making sense of economics datasets with evolutionary coresets

This page was built for publication: Near-Optimal Coresets for Least-Squares Regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346331)