12:30–1:30 pm
Searle 240A 5735 S. Ellis Avenue
CAM & Stats Student Seminar
Tuesday, January 16, 2024, at 12:30 PM, in Searle 240A, 5735 S. Ellis Avenue
Erasmo Tani, Department of Computer Science, The University of Chicago
"Recent Progress on Learning Partitions with a Faulty Same-Cluster Oracle"
Abstract
Learning cluster structure is a fundamental task in Machine Learning. In this talk, we focus on partitioning a finite set. We consider the active setting in which one gains information about the clusters exclusively by asking potentially expensive questions of the form: “Are u and v part of the same cluster?” The main question of interest is: how many queries are needed to guarantee full recovery of the underlying partition if a fixed number of questions could return an erroneous answer? We will discuss recent progress on the problem, including an algorithm that achieves provably optimal query complexity up to constant factors.