Error, Measurement, and Computational Tradeoffs via Adaptive Sampling

• Activity Number: 622
• Type: Invited
• Date/Time: Thursday, August 13, 2015 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Aarti Singh*
• Companies: Carnegie Mellon University
• Keywords: adaptive sampling ; active learning ; tradeoffs in machine learning ; clustering ; matrix completion ; latent trees

Abstract

Adaptive sampling has been used in many settings to reduce the number of measurements needed to achieve a target error. While the tradeoffs between error and measurement have been well-studied, particularly in the supervised setting of active learning, in this talk I will present results in three unsupervised settings (hierarchical clustering, low-rank matrix completion, and learning latent trees) where adaptive sampling can be used to obtain runtime improvements, in addition to reducing the number of measurements needed. Furthermore, by specifying a sampling parameter, the adaptive sampling algorithms can operate along an entire tradeoff curve in the three-dimensional space of error, measurement and computational complexity.