Simons Institute: Theoretical Foundations of Modern Machine Learning

This talk explores the foundational role of theoretical computer science (TCS) in shaping modern machine learning paradigms and applications, drawing insights from Google's perspective.

Katrina Ligett discusses the pivotal contributions and ongoing challenges for theoretical computer science in advancing the state of modern machine learning.

Adam Klivans presents new learning models where algorithms either certify accuracy or abstain, moving beyond traditional distributional assumptions toward provably correct, reliable machine learning.

This lecture examines the application of computational thinking principles to a variety of learning models, highlighting their structural properties and theoretical limits.

Nikhil Bansal discusses recent progress on the Komlós conjecture, including an improved O((log n)^{1/4}) bound for discrepancy of unit vectors and its relation to the Beck-Fiala conjecture.

Nika Haghtalab introduces multi-objective learning as a unifying framework, providing an algorithmic toolbox for learning models with guarantees across diverse tasks, enhancing fairness and robustness in ML.

R Ravi explores Woodall's conjecture on dijoins, proving that digraphs with minimum dicut size $\tau$ contain $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying graph has a nowhere-zero k-flow.

This session features a series of concise 'lightning talks' by multiple speakers, highlighting diverse contemporary topics and emerging research in theoretical computer science and machine learning.

Jon Kleinberg discusses the societal implications and interaction challenges as AI systems become increasingly integrated into the real world, examining ethical and algorithmic considerations.

Prabhakar Raghavan explores challenges and novel approaches in navigating new data landscapes and problem domains within the field of modern machine learning.

Robert Schapire introduces 'Astral Space,' a compact extension of Euclidean space for analyzing minimizers of convex functions at infinity, developing a robust theoretical framework.

Ron Rivest discusses critical aspects of AI safety, exploring methods and theoretical frameworks to ensure robust, secure, and reliable operation of artificial intelligence systems.

Lenore Blum introduces the Conscious Turing Machine (CTM), aligning it with major theories of consciousness and demonstrating how TCS provides insights into potential machine consciousness.

Manuel Blum formally defines the Conscious Turing Machine (CTM) as a 7-tuple model for consciousness, offering theoretical insights into the binding problem and the generation of pain.

Nina Balcan explores the multifaceted theoretical underpinnings of modern AI, integrating learning theoretic, game theoretic, and algorithmic perspectives to explain AI's capabilities and limitations.

John Langford investigates a novel Occam's Razor principle for transformer models, suggesting that simpler learned states lead to vastly improved generalization and extrapolation, challenging traditional PAC theory.

Santosh Vempala presents a simple algorithm for separating red and blue points in n-dimensional space, improving complexity for separation by an intersection of k halfspaces under a soft margin.

Ravi Kannan introduces the 'Subset Smoothed' polytope K' for learning latent variable models, addressing challenges where data points lie far outside the latent polytope K due to significant perturbations.

Les Valiant proposes a principled and efficient approach to enhance reasoning in Large Language Models, aiming to justify trust in content generation beyond fluent prose and improve reliability.