Provable Training of a ReLU Gate with an Iterative Non-Gradient Algorithm

Sayar Karmakar, Anirbit Mukherjee

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:

  1. 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.
  2. 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

Abstract

In this work, we demonstrate provable guarantees on the training of a single ReLU gate in hitherto unexplored regimes. We give a simple iterative stochastic algorithm that can train a ReLU gate in the realizable setting in linear time while using significantly milder conditions on the data distribution than previous such results. Leveraging certain additional moment assumptions, we also show a first-of-its-kind approximate recovery of the true label generating parameters under an (online) data-poisoning attack on the true labels, while training a ReLU gate by the same algorithm. Our guarantee is shown to be nearly optimal in the worst case and its accuracy of recovering the true weight degrades gracefully with increasing probability of attack and its magnitude. For both the realizable and the non-realizable cases as outlined above, our analysis allows for mini-batching and computes how the convergence time scales with the mini-batch size. We corroborate our theorems with simulation results which also bring to light a striking similarity in trajectories between our algorithm and the popular S.G.D. algorithm - for which similar guarantees as here are still unknown.
BibTeX
@article{karmakar2022provable,
  author = {Sayar Karmakar and Anirbit Mukherjee},
  title = {{Provable Training of a ReLU Gate with an Iterative Non-Gradient Algorithm}},
  journal = {Neural Networks},
  year = {2022},
  doi = {10.1016/j.neunet.2022.03.040},
}

Loading related content...

Figure