Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence

Xue Chen, Michał Dereziński

Consider a regression problem where the learner is given a large collection of $d$-dimensional data points, but can only query a small subset of the real-valued labels. How many qu…