Efficient Discrepancy Testing for Learning with Distribution Shift Gautam Chandrasekaran UT Austin Adam R. Klivans UT Austin Vasilis Kontonis UT Austin Konstantinos Stavropoulos

Our approach generalizes and improves all prior work on TDS learning: (1) we obtain universal learners that succeed simultaneously for large classes of test distributions, (2) achieve near-optimal error rates, and (3) give exponential improvements for constant depth circuits.