Abstract
This paper investigates the fundamental problem of learning a single neuron—defined by the model $x \mapsto \sigma(w^\top x)$—using vanilla gradient descent (GD) on the empirical square loss. We focus on the agnostic PAC learning setting, where no assumptions are made regarding the relationship between labels $y$ and inputs $x$. For an arbitrary Lipschitz and non-decreasing activation function $\sigma$, we demonstrate that gradient descent, despite the non-convex and potentially non-smooth nature of the optimization landscape, achieves a population risk of $O(\text{OPT}) + \epsilon$ for strictly increasing activations and $O(\text{OPT}^{1/2}) + \epsilon$ for the ReLU activation. Crucially, our complexity guarantees are largely dimension-independent, providing a theoretical basis for the efficacy of gradient-based methods in high-dimensional learning tasks.
1. Introduction
In modern machine learning, gradient descent is the workhorse of optimization. However, a significant gap persists between its empirical success and our theoretical understanding of its behavior on non-convex objectives. Most existing literature on learning neurons relies on the "realizable" assumption, where a ground-truth weight vector is assumed to exist such that the error can reach zero. This paper addresses the more realistic and challenging agnostic setting, where the goal is to perform nearly as well as the best possible neuron in the class, even if the data is noisy or the model is misspecified.
2. Problem Formulation
We consider the problem of minimizing the population risk: $$F(w) = \mathbb{E}_{(x,y)\sim \mathcal{D}}[(\sigma(w^\top x)-y)^2]$$ where $\mathcal{D}$ is an unknown joint distribution over $\mathbb{R}^d \times [-1, 1]$. The activation function $\sigma$ is assumed to be $L$-Lipschitz and non-decreasing. Let $\text{OPT} = \min_{\|v\| \le 1} F(v)$ be the minimum possible risk achievable by any weight vector $v$ within the unit ball.
The optimization challenge arises from two factors:
- Non-convexity: The square loss landscape for a single neuron can contain spurious local minima that might trap gradient-based algorithms.
- Non-smoothness: Activations like the Rectified Linear Unit (ReLU) are not differentiable at the origin, complicating standard convergence analysis.
3. Theoretical Framework
To analyze the convergence of gradient descent, the authors introduce a framework centered on the inductive bias of the algorithm when initialized at the origin ($w_0 = 0$).
3.1 Auxiliary Error Functions
The analysis utilizes two auxiliary functions, $G(w)$ and $H(w)$, which serve as proxies to relate the gradient of the empirical risk to the distance from the optimal weights $v$. These functions help prove that the gradient maintains a significant component in the direction of the optimal solution, preventing the algorithm from becoming permanently stuck in flat regions or local minima.
3.2 Distributional Assumptions
While the results for strictly increasing activations (like sigmoid or tanh) require no distributional assumptions beyond boundedness, the ReLU activation requires a nondegeneracy condition (Marginal Spread). This ensures that the input distribution is sufficiently "spread out" so that the neuron does not reside entirely in the flat (zero-gradient) region of the ReLU function, which would otherwise lead to the "dying ReLU" problem.
4. Main Results
The paper proves that gradient descent effectively minimizes the population risk in polynomial time and sample complexity. A summary of the population risk guarantees is provided below:
| Setting | Activation | Population Risk Guarantee | Runtime / Sample Complexity |
|---|---|---|---|
| Agnostic | Strictly Increasing | $O(\text{OPT}) + \epsilon$ | $O(\epsilon^{-1})$ time / $O(\epsilon^{-2})$ samples |
| Agnostic | ReLU | $O(\text{OPT}^{1/2}) + \epsilon$ | $O(\epsilon^{-2})$ time / $O(\epsilon^{-4})$ samples |
| Noisy Teacher | Any (Inc./ReLU) | $\text{OPT} + \epsilon$ | $\tilde{O}(\epsilon^{-2})$ |
| Realizable | Any (Inc./ReLU) | $\epsilon$ | $O(\epsilon^{-1})$ (using SGD) |
4.1 Dimension Independence
A key highlight of this work is that the sample and time complexities are (almost) independent of the input dimension $d$. This suggests that the difficulty of learning a single neuron is governed more by the desired precision $\epsilon$ and the inherent noise $\text{OPT}$ than by the dimensionality of the feature space.
4.2 The Noisy Teacher Setting
In the specific case where labels are generated by a "noisy teacher" ($y = \sigma(v^\top x) + \xi$ for zero-mean sub-Gaussian noise $\xi$), the bounds improve significantly. In this regime, gradient descent achieves $\text{OPT} + \epsilon$, matching the best possible theoretical risk.
5. Discussion and Limitations
While this work provides strong guarantees for single neurons, several avenues for future research remain:
- The ReLU Gap: The $O(\text{OPT}^{1/2})$ bound for ReLU is weaker than the $O(\text{OPT})$ bound for strictly increasing functions. It remains an open question whether this is a fundamental limitation of ReLU's flat landscape or an artifact of the current proof techniques.
- Multi-Layer Networks: The current analysis is restricted to a single neuron. Extending these agnostic guarantees to multi-layer architectures, where neurons interact and create more complex non-convexities, is a significant next step.
- Initialization Regimes: The proofs rely on initialization near the origin. Exploring the behavior of GD in "large initialization" regimes, such as those analyzed in Neural Tangent Kernel (NTK) literature, would provide a more complete picture of neural optimization.
6. Conclusion
This paper demonstrates that vanilla gradient descent is a robust learner for single neurons even in agnostic settings. By showing that the algorithm can overcome non-convexity and non-smoothness to achieve near-optimal population risk with dimension-independent complexity, the authors provide a rigorous theoretical foundation for a common practice in machine learning.
Summary updated