To understand the theoretical underpinnings of deep learning, researchers often study the simplest possible building block: a single neuron, mathematically represented as $x \mapsto \sigma(w^\top x)$. While learning a single neuron is well-understood when the data perfectly matches the model (the realizable setting) or when the input data follows very specific distributions, the agnostic setting remains a significant challenge. In the agnostic setting, absolutely no assumptions are made about the true relationship between the inputs $x$ and the labels $y$.
This paper demonstrates that vanilla gradient descent can successfully learn a single neuron in this worst-case agnostic setting, achieving competitive population risk without relying on convex surrogates or algorithmic modifications.
The Challenge of the Agnostic Setting
In the agnostic PAC learning framework, an algorithm must find a set of weights that performs almost as well as the best possible single neuron, which has a baseline error denoted as $\text{OPT}$.
The primary hurdle is the activation function $\sigma$ (e.g., ReLU, Sigmoid), which makes the squared loss landscape nonconvex and, in some cases, nonsmooth. Because of this, it is notoriously difficult to prove that standard gradient descent applied to the empirical risk will not get trapped in suboptimal local minima. The authors ask a fundamental question: Can vanilla gradient descent actually find a globally competitive solution despite these geometric hurdles?
Methodology and Theoretical Approach
The authors analyze the theoretical trajectory of full-batch gradient descent applied directly to the empirical squared loss. To prove convergence on a nonconvex landscape, they introduce an auxiliary error metric that measures how well the gradient aligns with the direction of the optimal weights.
Using mathematical induction, they prove that as long as the current risk is significantly higher than the optimal risk, the gradient continues to point in a "good" direction, forcing the loss to decrease. To handle the nonsmooth, flat region of the ReLU activation—where the gradient is zero and learning halts—they introduce a "marginal spread" assumption. This ensures that the input data distribution isn't perfectly aligned to "hide" entirely within the dead zone of the ReLU.
Key Findings and Complexity Bounds
The authors show that nonconvexity is not a dealbreaker for vanilla gradient descent, though the shape of the activation function dictates the strength of the guarantees:
- Strictly Increasing Activations: For functions like Leaky ReLU or Sigmoid, gradient descent achieves a population risk of $O(\text{OPT}) + \epsilon$. The sample complexity is $O(\epsilon^{-2})$ and the runtime is $O(\epsilon^{-1})$.
- ReLU Activation: Due to its flat "dead zone," the math is more challenging, resulting in a weaker $O(\text{OPT}^{1/2}) + \epsilon$ guarantee. This requires a sample complexity of $O(\epsilon^{-4})$ and a runtime of $O(\epsilon^{-2})$, provided the data satisfies the marginal spread assumption.
- The "Noisy Teacher" Boost: If the agnostic assumption is relaxed to assume the data was generated by a single neuron but corrupted by zero-mean noise (the Generalized Linear Model setting), the guarantees improve dramatically. Gradient descent achieves exactly $\text{OPT} + \epsilon$ risk for both ReLU and strictly increasing activations, with $\tilde{O}(\epsilon^{-2})$ sample and runtime complexity.
Crucially, the runtime and sample complexity bounds derived by the authors are remarkably independent of the input dimension $d$. They rely primarily on the boundedness of the data distribution, making the theory highly scalable.
Limitations and Future Work
The authors acknowledge that the $O(\text{OPT}^{1/2})$ bound for ReLU in the agnostic setting is sub-optimal compared to the $O(\text{OPT})$ bound achieved for strictly increasing functions. Because the optimization landscape is highly nonconvex, it remains an open question whether this weaker bound is a fundamental limitation of gradient descent itself or simply an artifact of their mathematical proof technique.
For future work, they pose the open question of whether gradient descent can provably achieve exactly $\text{OPT} + \epsilon$ risk for non-ReLU activations in the fully agnostic setting, without needing the "noisy teacher" assumption. They also suggest exploring if tighter bounds can be found for ReLU without resorting to convex surrogate losses.
Summary updated