Loss Gradient Gaussian Width based Generalization and Optimization Guarantees
This work addresses the problem of tight theoretical guarantees for deep learning models, offering a novel approach that could lead to more quantitative bounds, though it appears incremental in refining complexity analysis.
The paper tackles the challenge of deriving generalization and optimization guarantees for modern models by introducing a new complexity measure called Loss Gradient Gaussian Width (LGGW), showing that it provides bounds under gradient domination conditions and remains stable with sample reuse in gradient descent.
Generalization and optimization guarantees on the population loss 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 includes the popular PL (Polyak-Łojasiewicz) condition as a special case. Second, we show that sample reuse in iterative gradient descent does not make the empirical gradients deviate from the population gradients as long as the LGGW is small. Third, focusing on deep networks, we bound their single-sample LGGW 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, and hold considerable promise towards quantitatively tight bounds for deep models.