A Study of Neural Training with Iterative Non-Gradient Methods

In this work, we demonstrate provable guarantees on the training of depth-$2$ neural networks in new regimes than previously explored. (1) First we give a simple stochastic algorithm that can train a $\rm ReLU$ gate in the realizable setting in linear time while using significantly milder conditions on the data distribution than previous results. Leveraging some additional distributional assumptions we also show approximate recovery of the true label generating parameters when training a $\rm ReLU$ gate while a probabilistic adversary is allowed to corrupt the true labels of the training data. Our guarantee on recovering the true weight degrades gracefully with increasing probability of attack and it's nearly optimal in the worst case. Additionally, our analysis allows for mini-batching and computes how the convergence time scales with the mini-batch size. (2) Secondly, we focus on the question of provable interpolation of arbitrary data by finitely large neural nets. We exhibit a non-gradient iterative algorithm "${\rm Neuro{-}Tron}$" which gives a first-of-its-kind poly-time approximate solving of a neural regression (here in the $\ell_\infty$-norm) problem at finite net widths and for non-realizable data.