Talk by Pranjal Awasthi (Google) (SIMONS-TCS-ML)
38:15Talk by Katrina Ligett (Hebrew University of Jerusalem) (SIMONS-TCS-ML)
36:41Efficient Algorithms for Reliable Machine Learning (SIMONS-TCS-ML)
37:26Computational Thinking on Learning Models (SIMONS-TCS-ML)
38:30On the Komlós Conjecture (SIMONS-TCS-ML)
33:41Multi-objective Learning: An Algorithmic Toolbox for Optimal Predictions Anytime Anywhere! (SIMONS-TCS-ML)
37:40Approximately Packing Dijoins Via Nowhere-Zero Flows (SIMONS-TCS-ML)
33:46Lightning Talks! (SIMONS-TCS-ML)
56:01Venturing out into the world with AI (SIMONS-TCS-ML)
44:41Unfamiliar Terrain (SIMONS-TCS-ML)
29:51Astral Space: Convex Analysis at Infinity (SIMONS-TCS-ML)
44:01AI and Safety (SIMONS-TCS-ML)
29:26The Role of TCS in Understanding (AI) Consciousness (SIMONS-TCS-ML)
43:21The Conscious Turing Machine (CTM), a formally defined Theoretical model of Consciousness (SIMONS-TCS-ML)
45:00Theory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives (SIMONS-TCS-ML)
40:41An Occam's Razor Principle for Transformers? (SIMONS-TCS-ML)
39:55Red Points and Blue Points (SIMONS-TCS-ML)
38:15Latent Variable models and Subset Smoothing (SIMONS-TCS-ML)
29:26Enhanced and Efficient Reasoning in Large Language Models (SIMONS-TCS-ML)
36:16Red Points and Blue Points (SIMONS-TCS-ML)
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.
Santosh Vempala (Georgia Institute of Technology)
The Role of TCS in Modern Machine Learning
Given points in n-dimensional space drawn independently from an arbitrary (unknown) distribution and labeled red or blue so that the colors can be separated by an (unknown) intersection of k halfspaces, can you efficiently compute (learn) a rule to separate the colors? Avrim posed this question in my first meeting with him 33 years ago, and I've been (happily) struggling with it since. In this talk, I'll describe a simple algorithm with complexity exponential in \sqrt{n \log(1/\rho) \log k}), assuming a (soft) margin \rho. This improves known results (which are exponential in either k or 1/\rho) and matches statistical query and cryptographic lower bounds up to the logarithmic factors in k and 1/rho.
An Occam's Razor Principle for Transformers? (SIMONS-TCS-ML)
Next · Lecture 18Latent Variable models and Subset Smoothing (SIMONS-TCS-ML)
Seminar notes & discussion
No public seminar notes on this lecture yet.