Sublinear-Time Algorithms in Learning

As part of the recent workshop on Extroverted Sublinear Algorithms, Ronitt Rubinfeld (MIT) surveyed two directions in which sublinear-time algorithms are impacting the design and use of learning algorithms. In the first direction, sublinear-time algorithms are used to convert learning algorithms into “proper” learning algorithms — namely, algorithms that output a hypothesis from the concept class. In the second direction, sublinear sample algorithms provide a way of “safely” using learning algorithms that are designed for specific data distributions, even when the user is not sure whether the data comes from the assumed distribution. This talk described joint works with Jane Lange and Arsen Vasilyan.