  In traditional models of supervised 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$) of
the best fitting concept from some class. In order to escape strong hardness
results for learning even simple concept classes, we introduce a
smoothed-analysis framework that requires 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.
  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(\frac{\log k}{\epsilon \gamma}) }$ where $\gamma$ is the
margin parameter. Before our work, the best-known runtime was exponential in
$k$ (Arriaga and Vempala, 1999).
