Skip to contentSkip to filters

We use cookies for analytics.

Reduced label complexity for tight linear regression

Alex Gittens

Rensselaer Polytechnic Institute

Abstract

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.

Topics