142 citations · 330 across the 18 of their papers we have counts for
5 papers · 1 filter
Every Layer Counts: An Exponential Depth Hierarchy for ReLU Networks
Itay Safran
We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all , we construct a globally -valu…
On the Rate of Convergence of GD in Non-linear Neural Networks: An Adversarial Robustness Perspective
Guy Smorodinsky, Sveta Gimpleson, Itay Safran
We study the convergence dynamics of Gradient Descent (GD) in a minimal binary classification setting, consisting of a two-neuron ReLU network and two training instances. We prove…
The Median is Easier than it Looks: Approximation with a Constant-Depth, Linear-Width ReLU Network
Abhigyan Dutta, Itay Safran, Paul Valiant
We study the approximation of the median of inputs using ReLU neural networks. We present depth-width tradeoffs under several settings, culminating in a constant-depth, linear-…
A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory
Itay Safran
We consider the problem of exact computation of the maximum function over real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width $Ω\big(d^{1+\frac{1}…
To Grok Grokking: Provable Grokking in Ridge Regression
Mingyue Xu, Gal Vardi, Itay Safran
We study grokking, the onset of generalization long after overfitting, in a classical ridge regression setting. We prove end-to-end grokking results for learning over-parameterized…