Sublinear time algorithms in learning

This talk will survey 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 describes joint works with Jane Lange and Arsen Vasilyan.