L1 Regression with Lewis Weights Subsampling

2021/05/19 by Parulekar, Aditya, Parulekar, Advait, Price, Eric · 1 citation
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2105.09433

Abstract

We consider the problem of finding an approximate solution to ℓ₁ regression while only observing a small number of labels. Given an n × d unlabeled data matrix X, we must choose a small set of m ≪ n rows to observe the labels of, then output an estimate \widehatβ whose error on the original problem is within a 1 + ε factor of optimal. We show that sampling from X according to its Lewis weights and outputting the empirical minimizer succeeds with probability 1-δ for m > O((1)/(ε²) d log (d)/(ε δ)). This is analogous to the performance of sampling according to leverage scores for ℓ₂ regression, but with exponentially better dependence on δ. We also give a corresponding lower bound of Ω((d)/(ε²) + (d + (1)/(ε²)) log\frac1δ).

Cited by

• Active Regression for Single-Index Models with Unknown Link Functions

Related

• ℓ_p Row Sampling by Lewis Weights
• ℓ₁ Regression using Lewis Weights Preconditioning and Stochastic Gradient Descent
• Sharpened Error Bounds for Random Sampling Based ℓ₂ Regression
• Subsampling for Ridge Regression via Regularized Volume Sampling
• Optimal Subsampling Approaches for Large Sample Linear Regression