  We investigate 1) the rate at which refined properties of the empirical
risk---in particular, gradients---converge to their population counterparts in
standard non-convex learning tasks, and 2) the consequences of this convergence
for optimization. Our analysis follows the tradition of norm-based capacity
control. We propose vector-valued Rademacher complexities as a simple,
composable, and user-friendly tool to derive dimension-free uniform convergence
bounds for gradients in non-convex learning problems. As an application of our
techniques, we give a new analysis of batch gradient descent methods for
non-convex generalized linear models and non-convex robust regression, showing
how to use any algorithm that finds approximate stationary points to obtain
optimal sample complexity, even when dimension is high or possibly infinite and
multiple passes over the dataset are allowed.
  Moving to non-smooth models we show----in contrast to the smooth case---that
even for a single ReLU it is not possible to obtain dimension-independent
convergence rates for gradients in the worst case. On the positive side, it is
still possible to obtain dimension-independent rates under a new type of
distributional assumption.
