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":
- 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.
- 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.
- 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.
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.
- 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