Challenges in Unsupervised Learning - Statistical-Computational Trade-offs - Part 1

Explore the fundamental challenges in unsupervised learning through this mathematical lecture that examines the critical intersection of statistics and machine learning. Delve into the core problem of uncovering patterns in unlabeled data while balancing computational efficiency with statistical effectiveness. Learn about the significant progress made over the past decade in understanding statistical-computational trade-offs, particularly for canonical "vanilla" problems where achieving both statistical optimality and computational efficiency appears impossible. Discover how recent developments have surprisingly refuted many extensions of widely accepted conjectures when applied to slightly modified models that introduce exploitable additional structure. Examine a specific vanilla problem where statistical-computational trade-offs are strongly conjectured, then investigate ranking problems as a class of complex unsupervised learning challenges where standard conjectures have been proven false. Gain insights into the underlying mathematical reasons why certain structural modifications can bypass presumed computational limitations in unsupervised learning algorithms. This presentation was recorded during the "Meeting in Mathematical Statistics" thematic meeting at the Centre International de Rencontres Mathématiques in Marseille, France.