Abstract
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Vasilis Kontonis
University of Texas at Austin
In the well-studied agnostic model of learning, the goal of a learner—given examples from an arbitrary joint distribution on \( \mathbb{R}^d \times \{\pm 1\} \)—is to output a hypothesis that is competitive (to within \( \epsilon \)) with 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 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^{\operatorname{poly}\!\left(\frac{\log k}{\epsilon \gamma}\right)} \), where \( \gamma \) is the margin parameter. Before our work, the best-known runtime was exponential in \( k \).
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 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^{\operatorname{poly}\!\left(\frac{\log k}{\epsilon \gamma}\right)} \), where \( \gamma \) is the margin parameter. Before our work, the best-known runtime was exponential in \( k \).