2026-07-23T22:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14742 2024-03-06T10:54:48Z ddc:004 open_access

L1 Regression with Lewis Weights Subsampling Parulekar, Aditya Parulekar, Advait Price, Eric Active regression Lewis weights 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 β̂ 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 1/(δ)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Parulekar and Advait Parulekar and Eric Price 2021 Is Part Of LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2021.49 urn:nbn:de:0030-drops-147422 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.49 eng https://creativecommons.org/licenses/by/4.0/legalcode