Reduced label complexity for tight linear regression
Alex Gittens · Rensselaer Polytechnic Institute
Thu, Jun 29, 2023 · 18:30 UTC
Alex Gittens studies how many data points must be labelled to fit a linear regression model with nearly the predictive power of a fully labelled dataset. Existing coreset and iterative approaches handle constant-factor approximations, but tighter approximations that improve with dataset size need different methods. The talk presents a polynomial-time algorithm that reduces label complexity by an additive O(sqrt(n)), using a sharp analysis of regression error for a coreset formed by backward selection.