Feature selection and low test error in shallow low-rotation ReLU networks

Matus TelgarskyICLR 2023 · OpenReview

This paper provides a theoretical bridge between the "lazy training" regime—where neural networks behave like simple linear kernels—and true "feature learning," where networks actively adapt their internal representations. By analyzing shallow ReLU networks through the lens of margins, the work demonstrates how gradient-based methods can perform feature selection and achieve low test error even when neurons do not rotate significantly.

The Mystery of Automatic Feature Learning

A central mystery in deep learning theory is understanding how gradient methods adjust lower-layer weights to extract useful information from data. For years, theorists relied heavily on the Neural Tangent Kernel (NTK) to explain network behavior. However, the NTK assumes weights barely move from their random initialization (an $\mathcal{O}(1)$ change), essentially treating the network as a linear model operating over frozen, randomized features.

This lazy training perspective fails to explain why deep learning vastly outperforms traditional kernel methods on complex tasks. For example, in the "2-sparse parity" problem—identifying which two bits in a high-dimensional vector are XORed—kernel methods require $d^2$ samples. In contrast, a network that genuinely "learns" to select the right features should only need $d$ samples. This paper seeks to prove how and when networks achieve this improved "beyond-kernel" performance by exiting the NTK regime.

Methodology: Margins and Low-Rotation Regimes

The author analyzes two-layer ReLU networks trained with Gradient Flow (GF) and Stochastic Gradient Descent (SGD). The core analysis technique relies on margin maximization—the principle that a robust classifier doesn't merely separate data, but does so with a wide "safety buffer."

The paper investigates three specific training regimes where weights exhibit "low rotation":

  1. Near-Initialization: Weights are allowed to move by $\mathcal{O}(\sqrt{m})$ (where $m$ is the network width). This is significantly further than the $\mathcal{O}(1)$ motion permitted by the NTK, giving the network enough flexibility to "select" features while remaining mathematically tractable.
  2. Neural Collapse (NC): A setting where data is organized into well-separated clusters. The author analyzes the entire training trajectory from random initialization to convergence, showing how weights naturally gravitate toward these cluster centers.
  3. Rotation-Free Networks: A stylized, artificially constrained setting where inner weights can change their magnitude (norm) but cannot rotate. This isolates the effect of "feature selection" purely via norm growth.
Weight trajectories illustrating the low-rotation phenomenon and neural collapse.

Key Insights

Exiting the NTK and Escaping Bad Points

The paper shows that allowing weights to move by $\mathcal{O}(\sqrt{m})$ is the theoretical "sweet spot." It provides enough movement to perform meaningful feature selection—thereby improving over NTK baselines—without losing the analytical benefits of being near initialization. A major contribution is proving that Gradient Flow does not get stuck in "bad" KKT points (local optima of the margin objective). Instead, GF attains a margin at least as good as the NTK margin, successfully escaping nearby bad points that have arbitrarily small margins.

The "Low-Rotation" Phenomenon

Surprisingly, empirical tests on MNIST and parity problems reveal that as networks get wider, their neurons actually rotate less. This suggests that the "low-rotation" assumption isn't merely a mathematical convenience for theorists; it is a natural property of wide networks in practice.

Norm as Selection

In the rotation-free regime, the network learns by simply "turning up the volume" on useful random features and "muting" useless ones. This simple mechanism of norm growth is sufficient to hit the optimal sample complexity for hard feature-selection tasks like sparse parity.

Key Results and Sample Complexity

The theoretical guarantees provided in this work represent a significant leap over prior bounds, particularly regarding sample complexity and network width requirements.

Comparison of sample complexity and width requirements across different algorithms and regimes.
  • Sample Complexity: For the 2-sparse parity problem, the author proves that while NTK-style analysis requires $d^2/\epsilon$ samples, analyzing low-rotation networks yields the optimal $d/\epsilon$ sample complexity.
  • Width Requirements: The paper establishes low test error guarantees for networks with width $m \approx \Omega(1/\gamma_{ntk}^2)$. This is a massive improvement over prior works, which required widths scaling as $1/\gamma_{ntk}^8$.
  • Global Convergence: In both the Neural Collapse and rotation-free settings, the paper proves that GF converges to a solution that maximizes the global margin, ensuring high generalization.

Limitations and Future Work

While the paper makes significant strides, several limitations remain:

  • Exponential Width: Some of the global convergence results require network widths that scale exponentially with the input dimension $d$ (e.g., $d^{d/2}$), which is impractical for real-world, large-scale models.
  • Forced Constraints: The "rotation-free" results rely on an artificial constraint applied to the architecture. A major open question is proving that this optimal low-rotation behavior happens naturally in standard networks without being explicitly forced.
  • Loss Function Gaps: The SGD analysis currently only holds for the logistic loss. The exponential loss makes gradient norms too volatile to concentrate effectively.
  • The Pareto Frontier: The author notes that the complex trade-offs between network width, sample complexity, and computational time are not yet fully mapped out, leaving room for future theoretical exploration.

Summary updated

Abstract

This work establishes low test error of gradient flow (GF) and stochastic gradient descent (SGD) on two-layer ReLU networks with standard initialization scale, in three regimes where key sets of weights rotate little (either naturally due to GF and SGD, or due to an artificial constraint), and making use of margins as the core analysis technique. The first regime is near initialization, specifically until the weights have moved by $\mathcal{O}(\sqrt m)$, where $m$ denotes the network width, which is in sharp contrast to the $\mathcal{O}(1)$ weight motion allowed by the Neural Tangent Kernel (NTK); here it is shown that GF and SGD only need a network width and number of samples inversely proportional to the NTK margin, and moreover that GF attains at least the NTK margin itself and in particular escapes bad KKT points of the margin objective, whereas prior work could only establish nondecreasing but arbitrarily small margins. The second regime is the Neural Collapse (NC) setting, where data lies in well-separated groups, and the sample complexity scales with the number of groups; here the contribution over prior work is an analysis of the entire GF trajectory from initialization. Lastly, if the inner layer weights are constrained to change in norm only and can not rotate, then GF with large widths achieves globally maximal margins, and its sample complexity scales with their inverse; this is in contrast to prior work, which required infinite width and a tricky dual convergence assumption.
BibTeX
@inproceedings{telgarsky2023feature,
  author = {Matus Telgarsky},
  title = {{Feature selection and low test error in shallow low-rotation ReLU networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=swEskiem99},
}
Figure