Abstract
We investigate the rate at which refined properties of the empirical risk—specifically, gradients—converge to their population counterparts in standard non-convex learning tasks, and the consequences of this convergence for optimization. Following 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. For non-smooth models, we show that even for a single ReLU it is not possible to obtain dimension-independent convergence rates for gradients in the worst case, though it is possible under a new type of distributional assumption.
Introduction
In machine learning, the goal is typically to minimize the "population risk" (error on unseen data), yet we only have access to the "empirical risk" (error on training data). For non-convex models like neural networks, finding the global minimum of the empirical risk is often computationally intractable. However, standard optimization algorithms like Stochastic Gradient Descent (SGD) are remarkably effective at finding approximate stationary points—regions where the gradient of the empirical risk is near zero.
This research addresses two fundamental questions:
- Gradient Uniform Convergence: Does a near-zero gradient on training data imply a near-zero gradient on the true population distribution?
- Optimization Consequences: Does finding a stationary point on the population distribution guarantee low overall error (excess risk)?
Crucially, while previous bounds often scaled with the dimension $d$ (the number of parameters), this work provides dimension-independent guarantees, which are essential for modern high-dimensional regimes.
Theoretical Framework
To achieve dimension-independent bounds, the authors utilize norm-based capacity control rather than parameter counting.
Vector-Valued Rademacher Complexities
The authors adapt Rademacher complexity to measure the complexity of the gradients of a function class. This enables proofs of uniform gradient convergence that depend on the norms of the data and model weights rather than the dimension $d$.
A Chain Rule for Rademacher Complexity
A novel mathematical "chain rule" is introduced to decompose the complexity of composed functions, such as linear predictors passed through non-linear activation functions.
Gradient Domination (GD) Condition
The Gradient Domination condition (related to the Polyak-Łojasiewicz inequality) ensures that a model's excess error is bounded by the magnitude of its gradient. The authors demonstrate that the population risk of certain models satisfies this condition, even if the empirical risk does not, meaning any stationary point is effectively a global minimum.
Key Insights
- Population vs. Empirical Risk: The training loss landscape does not need to be perfectly behaved. If the population risk satisfies the GD condition, algorithms finding stationary points on training data will generalize effectively.
- Dimension-Free Bounds for Smooth Models: For smooth loss functions, the sample complexity for gradient convergence depends on weight and data norms, explaining why overparameterized models generalize well.
- Non-Smooth Model Divergence: For non-smooth models like those using ReLU activations, dimension-independent gradient convergence is mathematically impossible in the worst case.
- The Role of Margins: To address the ReLU limitation, the authors propose a "soft-margin" distributional assumption. If data points avoid the non-smooth "kink" of the ReLU, dimension-independent bounds are restored.
Sample Complexity and Optimization Results
The paper establishes optimal sample complexity for several standard non-convex tasks. For Generalized Linear Models (GLMs) and Robust Regression, the authors prove that finding an $\varepsilon$-approximate stationary point requires $O(1/\varepsilon^2)$ samples in the norm-bounded regime.
As shown in the table above, the proposed bounds (Proposition 3) provide a unified approach that matches or exceeds the performance of existing algorithms like GLMtron, particularly in infinite-dimensional or norm-based settings where previous methods were often not applicable (n/a).
Furthermore, the authors establish a lower bound of $\Omega(\sqrt{dn} \wedge n)$ for the gradient convergence of a single ReLU, formally demonstrating that dimension dependence cannot be avoided in the worst case for non-smooth models without additional distributional assumptions.
Limitations and Future Work
While the results are significant, they rely on the assumption that models like GLMs are "well-specified" (the data distribution matches the model family). Furthermore, the non-smooth analysis is currently limited to a single ReLU; extending these margin-based bounds to deep, multi-layer networks remains an open challenge. Future research may explore whether the Gradient Domination property applies to other non-convex models such as ResNets or matrix factorization.
Summary updated