TL;DR
This paper provides the first provable guarantees for training a single ReLU gate in linear time under very mild data distribution assumptions. Crucially, the authors introduce a simple iterative algorithm that remains robust even when an adversary "poisons" the training labels, showing that accuracy degrades gracefully rather than collapsing under attack.
What Problem Does This Paper Address?
While deep learning is incredibly successful in practice, we still lack a complete mathematical understanding of why simple heuristics like Stochastic Gradient Descent (SGD) work so well. Even for a single "neuron" (a ReLU gate), proving that an algorithm will converge to the global optimum usually requires very restrictive assumptions, such as the input data following a perfect Gaussian distribution.
Furthermore, most existing theories fall apart if the data is "noisy" or intentionally corrupted by an adversary. The authors set out to bridge this gap by finding more general conditions for fast convergence and demonstrating robustness against "data-poisoning" attacks, where an online adversary additively distorts the true labels.
Methods
The paper focuses on two main algorithmic approaches:
- Re-analyzing GLM-Tron: The authors first revisit an existing algorithm called GLM-Tron, proving it can minimize risk for any Lipschitz-continuous activation function (with a constant < 2) under almost no distributional assumptions, even with adversarial noise.
- Modified Mini-batch SGD (Algorithm 2): The core contribution is a "gradient proxy" algorithm for ReLU gates. While standard SGD uses the current model's state to decide which samples to learn from, this algorithm uses the labels themselves. Specifically, it only updates weights using samples where the label $y$ exceeds a certain threshold $\theta_*$. This "non-gradient" approach allows the algorithm to focus on the linear region of the ReLU, effectively turning a non-convex problem into a solvable one.
The analysis is comprehensive, accounting for the effects of mini-batching and providing explicit bounds on how convergence time scales with batch size.
Datasets
The authors primarily use synthetic datasets to rigorously test their theoretical bounds:
- High-dimensional Gaussian data: Inputs $\mathbf{x}$ are sampled from a standard normal distribution in $n=500$ dimensions.
- Compact and Non-compact distributions: They provide examples using Uniform distributions on a hypercube and univariate Gaussian distributions to show their "mild distributional condition" holds in diverse settings.
- Adversarial Setup: They simulate a data-poisoning attack where labels are corrupted with a probability $\beta$ and a magnitude $\theta_*$.
Key Insights and Ideas
- Linear Convergence is Possible: The paper shows that you can reach $\epsilon$-accuracy in $O(\log(1/\epsilon))$ time—a hallmark of training smooth, strongly convex functions—even though the ReLU objective is neither smooth nor convex.
- Label-Based Filtering: The "aha moment" is using the label $y$ to filter updates. By only looking at samples where $y > \theta_*$, the algorithm bypasses the "dead" region of the ReLU where the gradient is zero, ensuring every update is meaningful.
- Distributional Flexibility: Unlike previous work that required inputs to be Gaussian, this theory only requires a mild "subspace eigenvalue condition" (essentially that the data isn't all squashed into a tiny corner of the space).
- SGD Mimicry: Surprisingly, despite the theoretical differences, the proposed algorithm's training trajectory is "strikingly similar" to standard SGD in experiments. This suggests that the provable properties of their algorithm might actually explain why standard SGD is so robust in practice.
Key Results
- Provable Linear Time: In the "realizable" setting (no noise), the algorithm is guaranteed to recover the true weights in linear time.
- Robustness to Poisoning: Under a data-poisoning attack, the recovery error is shown to be nearly optimal in the worst case. The accuracy degrades gracefully as the probability of attack ($\beta$) or the magnitude of distortion ($\theta_*$) increases.
- Mini-batch Efficiency: The authors quantify exactly how larger mini-batches speed up convergence, a detail often overlooked in theoretical deep learning papers.
Limitations and Future Work
The primary limitation is that the results are currently restricted to a single ReLU gate (one neuron). While this is a fundamental building block, real-world networks have millions of neurons across many layers.
The authors suggest that their work opens a path toward rigorously proving that the stochastic process induced by standard SGD is a "close approximant" of their provably convergent algorithm. Extending these guarantees to multi-layer networks remains the "holy grail" for future research in this direction.
Summary updated