Linear Regression with Limited Observation
This addresses the problem of efficient learning with limited data access for practitioners in machine learning, offering incremental improvements in attribute efficiency.
The paper tackles linear regression variants (Ridge, Lasso, Support-vector) under limited observation constraints, showing that for Lasso and Ridge, algorithms achieve comparable accuracy with the same total attributes as full-information methods, while for Support-vector regression, they require exponentially fewer attributes, resolving an open problem.
We consider the most common variants of linear regression, including Ridge, Lasso and Support-vector regression, in a setting where the learner is allowed to observe only a fixed number of attributes of each example at training time. We present simple and efficient algorithms for these problems: for Lasso and Ridge regression they need the same total number of attributes (up to constants) as do full-information algorithms, for reaching a certain accuracy. For Support-vector regression, we require exponentially less attributes compared to the state of the art. By that, we resolve an open problem recently posed by Cesa-Bianchi et al. (2010). Experiments show the theoretical bounds to be justified by superior performance compared to the state of the art.