Agnostic Learning of a Single Neuron with Gradient Descent

Spencer Frei, Yuan Cao, Quanquan Gu

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:

  1. Non-convexity: The square loss landscape for a single neuron can contain spurious local minima that might trap gradient-based algorithms.
  2. 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

Abstract

We consider the problem of learning the best-fitting single neuron as measured by the expected square loss $\mathbb{E}_{(x,y)\sim \mathcal{D}}[(\sigma(w^\top x)-y)^2]$ over some unknown joint distribution $\mathcal{D}$ by using gradient descent to minimize the empirical risk induced by a set of i.i.d. samples $S\sim \mathcal{D}^n$. The activation function $\sigma$ is an arbitrary Lipschitz and non-decreasing function, making the optimization problem nonconvex and nonsmooth in general, and covers typical neural network activation functions and inverse link functions in the generalized linear model setting. In the agnostic PAC learning setting, where no assumption on the relationship between the labels $y$ and the input $x$ is made, if the optimal population risk is $\mathsf{OPT}$, we show that gradient descent achieves population risk $O(\mathsf{OPT})+\epsilon$ in polynomial time and sample complexity when $\sigma$ is strictly increasing. For the ReLU activation, our population risk guarantee is $O(\mathsf{OPT}^{1/2})+\epsilon$. When labels take the form $y = \sigma(v^\top x) + \xi$ for zero-mean sub-Gaussian noise $\xi$, we show that the population risk guarantees for gradient descent improve to $\mathsf{OPT} + \epsilon$. Our sample complexity and runtime guarantees are (almost) dimension independent, and when $\sigma$ is strictly increasing, require no distributional assumptions beyond boundedness. For ReLU, we show the same results under a nondegeneracy assumption for the marginal distribution of the input.
BibTeX
@inproceedings{frei2020agnostic,
  author = {Spencer Frei and Yuan Cao and Quanquan Gu},
  title = {{Agnostic Learning of a Single Neuron with Gradient Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=0BFYgU4Gf_M},
}
Figure