We consider the problem of learning a function from samples with L2-bounded noise.  In the simplest agnostic learning setting, the number of samples required for robust estimation depends on a condition number that can be arbitrarily large.  We show how to improve this dependence in two natural extensions of the setting: a query access setting, where we can estimate the function at arbitrary points, and an active learning setting, where we get a large number of unlabeled points and choose a small subset to label.

For linear spaces of functions, such as the family of n-variate degree-d polynomials, this eliminates the dependence on the condition number.  The technique can also yield improvements for nonlinear spaces, as we demonstrate for the family of k-Fourier-sparse signals with continuous frequencies.