Recorded 27 February 2024. Vasilis Kontonis of the University of Texas at Austin presents "Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension" at IPAM's EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization. Abstract: In the well-studied agnostic model of learning, the goal of a learner-- given examples from an arbitrary joint distribution on Rd×{±1} -- is to output a hypothesis that is competitive (to within ϵ ) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes in this model, we introduce a smoothed analysis framework where we require a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Perhaps surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of k -halfspaces in time k\poly(logkϵγ) where γ is the margin parameter. Before our work, the best-known runtime was exponential in k . Learn more online at: https://www.ipam.ucla.edu/programs/workshops/encore-workshop-on-computational-vs-statistical-gaps-in-learning-and-optimization/?tab=overview