Abstract
We give tight bounds up to logarithmic factors on the number of labels that need to be read for active lp regression for every value of p, as a function of the number d of variables and accuracy eps. Previously tight bounds were only known for p in {1,2}. We then extend these ideas to a large class of M-estimator loss functions, obtaining the first non-trivial bounds for such loss functions.
Based on joint works, one with Musco, Musco, and Yasuda (FOCS '22) and another with Yasuda (STOC '23).