Learning ReLUs via Gradient Descent

The evolution of deep learning has been marked by empirical successes and theoretical challenges. Early works like Hinton’s deep autoencoders and Krizhevsky’s AlexNet demonstrated the power of neural networks, yet their training lacked rigorous understanding. Recent advances in high-dimensional statistics, such as compressed sensing and sparse recovery, introduced tools like Gaussian width and geometric analysis to quantify sample complexity. Theoretical models like single index models (SIMs) and shallow neural networks have been studied, but often under restrictive assumptions or convex relaxations. The complexity of non-convex landscapes in neural networks remains a major obstacle. This paper builds on these foundations, aiming to rigorously analyze the dynamics of simple yet representative models—ReLU units—using high-dimensional geometric tools, to understand how gradient-based algorithms can succeed with minimal data.

The core challenge is to establish conditions under which gradient-based methods can reliably learn ReLU functions in high-dimensional, limited-sample regimes. Existing theories often assume convexity or rely on strong distributional assumptions, which do not hold in typical neural network training. The non-convexity of ReLU models, combined with the high-dimensional setting where parameters far exceed samples, makes the landscape riddled with saddle points and local minima. How to guarantee convergence from a trivial initialization, such as zero, and with a sample size close to the information-theoretic minimum, remains unresolved. Addressing this problem is crucial for both theoretical understanding and practical algorithm design, especially for training deep networks efficiently and reliably.

The main innovations include:

1) Geometric analysis of the descent cone associated with the regularizer, quantifying the structure of the signal space.

2) Application of Gaussian width to determine the minimal sample complexity needed for accurate recovery.

3) Rigorous proof that projected gradient descent, starting at zero, converges linearly under near-minimal sample conditions, even with non-convex regularizers.

4) Integration of high-dimensional probability tools, such as concentration inequalities and escape from mesh lemmas, to control the stochastic behavior of the gradient estimates.

This approach departs from classical convex analysis, providing a unified geometric framework applicable to a broad class of structured high-dimensional models.

• �� Assumption: Input features are i.i.d. Gaussian vectors, labels generated by a planted weight vector.
• �� Loss function: Non-convex least squares with ReLU activation, regularized by a structured prior R(w).
• �� Geometric tools: Descent cone CR(w*), Gaussian width ω(CR(w*) ∩ Bd).
• �� Sample complexity: Defined via the minimal number n0 = ω^2(CR(w*) ∩ Bd).
• �� Algorithm: Starting from w0=0, perform projected gradient updates w_{t+1} = P_{K}(w_t - μ_t ∇L(w_t)), with μ_t=1.
• �� Theoretical analysis: Show that under n ≥ c n0, the error reduces geometrically, leveraging concentration inequalities for Gaussian matrices and geometric bounds on the descent cone.
• �� Key steps: Bound stochastic gradients, control the geometry of the signal space, and establish a contraction mapping ensuring linear convergence.

Synthetic experiments simulate high-dimensional Gaussian data with planted sparse or structured weights. Varying sample sizes around the theoretical threshold n0, the authors measure the convergence rate and error decay. Results show that with n close to n0, the error decreases exponentially, reaching below 10^-3 within a few iterations. Additional tests with different dimensions and noise levels confirm robustness. The experiments validate the theoretical bounds, demonstrating that the geometric analysis accurately predicts the sample complexity and convergence behavior in practice.

Empirical data aligns with theoretical predictions: near the minimal sample size n0, PGD achieves linear convergence, reducing error from initial values to below 10^-3 within approximately 10 iterations. The convergence rate matches the O(log(1/ε)) bound, confirming the optimality of the sample complexity. Larger dimensions and structured signals do not impair performance, indicating the geometric framework's broad applicability. These results outperform traditional gradient methods that often get trapped in local minima, highlighting the effectiveness of the proposed approach.

Immediate applications include high-dimensional sparse signal recovery, feature selection in neural networks, and compressed sensing. The theoretical guarantees enable practitioners to design training protocols with provable efficiency, especially in resource-constrained scenarios. Long-term, this framework could inform the development of deep architectures with guaranteed convergence properties, facilitating more reliable and data-efficient training in real-world tasks such as image recognition, natural language processing, and scientific data analysis.

The analysis assumes Gaussian inputs, which may not hold in real data. Extending to sub-Gaussian or more complex distributions remains a challenge. The geometric approach relies on specific regularizers, limiting generality for unstructured or highly nonlinear models. Additionally, the current theory does not explicitly address noise robustness or model mismatch, which are critical in practical scenarios. Future work should focus on relaxing distributional assumptions and incorporating robustness considerations.