Attribute Efficient Linear Regression with Distribution-Dependent Sampling

We consider a budgeted learning setting, where the learner can only choose and observe a small subset of the attributes of each training example. We develop efficient algorithms for Ridge and Lasso li