Uniform Convergence of Gradients for Non-Convex Learning and Optimization
We investigate 1) the rate at which refined properties of the empirical risk-in particular, gradients-converge to their population counterparts in standard nonconvex 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 nonconvex 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.
This paper studies the uniform convergence of gradients for non-convex ERM problems. The results are applied to function satisfying Kurdyka-Łojasiewicz conditions and in particular certain classes of generalized linear models, to get risk bounds based on the empirical gradient at the output points. The main tools for the analysis are normed and vector-valued Rademacher complexity. The key technical contribution is a chain rule, which bounds the normed Rademacher complexity of the gradient of composite function, using their Lipschitz parameters and the vector-valued/normed Rademacher complexities of the gradient of each functions. This serves the role of contraction lemma in the proof of uniform convergence of function values.  I think this is an okay paper with legitimate contribution, but perhaps not novel enough for NIPS. There are several minor flaws, which further weaken its publishability. The use of contraction-type arguments to bound vector norm Rademacher complexities is interesting. However, the comparison to [33] (Mei, Bai and Montanari, 2016) is not well-justified. In particular, for low-dimensional setup, this paper assumes data points to be uniformly bounded in an $\ell_2$ ball, and the bound has bad dependence on its radius; in [33], assumption on data points is sub-Gaussian on each direction, which gives a $\sqrt{d}$ radius with high probability. If the authors are going to make comparisons, they should rescale their radius parameter to $\sqrt{d}$.  Technical comments: 1. The concentration results looked weird. In Proposition 1, they get $O(\log 1/\delta/n)^\alpha$ for $alpha\in[1,2]$, and in Proposition 2, the dependence on failure probability gives $O(\log 1/\delta/n)$. This seems to be much better than standard Hoeffding or McDiarmid inequalities, but in the proof, the author seems to be using nothing more than those. So I don't think these bounds are possible in terms of concentration term. 2. If K-Ł is satisfied, is uniform convergence actually necessary? Does localized empirical process give better rates? Intuitively we can show proximity to population optimal, and only need to do localized arguments within a small ball, which could possibly lead to localized rates.