Generalization and optimization guarantees on the population loss in machine
learning often rely on uniform convergence based analysis, typically based on
the Rademacher complexity of the predictors. The rich representation power of
modern models has led to concerns about this approach. In this paper, we
present generalization and optimization guarantees in terms of the complexity
of the gradients, as measured by the Loss Gradient Gaussian Width (LGGW).
First, we introduce generalization guarantees directly in terms of the LGGW
under a flexible gradient domination condition, which we demonstrate to hold
empirically for deep models. Second, we show that sample reuse in finite sum
(stochastic) optimization does not make the empirical gradient deviate from the
population gradient as long as the LGGW is small. Third, focusing on deep
networks, we present results showing how to bound their LGGW under mild
assumptions. In particular, we show that their LGGW can be bounded (a) by the
$L_2$-norm of the loss Hessian eigenvalues, which has been empirically shown to
be $\tilde{O}(1)$ for commonly used deep models; and (b) in terms of the
Gaussian width of the featurizer, i.e., the output of the last-but-one layer.
To our knowledge, our generalization and optimization guarantees in terms of
LGGW are the first results of its kind, avoid the pitfalls of predictor
Rademacher complexity based analysis, and hold considerable promise towards
quantitatively tight bounds for deep models.

通过 Loss Gradient Gaussian Width (LGGW) 的复杂度度量，我们提出一种直接基于 LGGW 的泛化保证方法，在梯度支配条件下实现，其在深度模型中进行实证研究并证明其有效性。同时，我们展示了有限和优化的样本重用并不会导致经验梯度偏离总体梯度，只要 LGGW 较小。这些基于 LGGW 的优化和泛化保证是首次提出的，避免了基于预测器 Rademacher 复杂性的分析缺陷，并对深度模型的定量界限提供了重要前景。