142 citations · 330 across the 18 of their papers we have counts for
19 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…
No Prior, No Leakage: Revisiting Reconstruction Attacks in Trained Neural Networks
Yehonatan Refael, Guy Smorodinsky, Ofir Lindenbaum +1
The memorization of training data by neural networks raises pressing concerns for privacy and security. Recent work has shown that, under certain conditions, portions of the traini…
Provable Privacy Attacks on Trained Shallow Neural Networks
Guy Smorodinsky, Gal Vardi, Itay Safran
We study what provable privacy attacks can be shown for trained 2-layer ReLU neural networks, focusing on two types of attacks: membership inference and data reconstruction. We pro…
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
Itay Safran, Daniel Reichman, Paul Valiant
We prove an exponential size separation between depth 2 and depth 3 neural networks (with real inputs), when approximating a -Lipschitz target function to constant…
How Many Neurons Does it Take to Approximate the Maximum?
Itay Safran, Daniel Reichman, Paul Valiant
We study the size of a neural network needed to approximate the maximum function over inputs, in the most basic setting of approximating with respect to the norm, for con…
On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias
Itay Safran, Gal Vardi, Jason D. Lee
We study the dynamics and implicit bias of gradient flow (GF) on univariate ReLU neural networks with a single hidden layer in a binary classification setting. We show that when th…
Optimization-Based Separations for Neural Networks
Itay Safran, Jason D. Lee
Depth separation results propose a possible theoretical explanation for the benefits of deep neural networks over shallower architectures, establishing that the former possess supe…
Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
Itay Safran, Ohad Shamir
Recently, there has been much interest in studying the convergence rates of without-replacement SGD, and proving that it is faster than with-replacement SGD in the worst case. Howe…
The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks
Itay Safran, Gilad Yehudai, Ohad Shamir
We study the effects of mild over-parameterization on the optimization landscape of a simple ReLU neural network of the form $\mathbf{x}\mapsto\sum_{i=1}^k\max\{0,\mathbf{w}_i^{\to…
How Good is SGD with Random Shuffling?
Itay Safran, Ohad Shamir
We study the performance of stochastic gradient descent (SGD) on smooth and strongly-convex finite-sum optimization problems. In contrast to the majority of existing theoretical wo…
Depth Separations in Neural Networks: What is Actually Being Separated?
Itay Safran, Ronen Eldan, Ohad Shamir
Existing depth separation results for constant-depth networks essentially show that certain radial functions in , which can be easily approximated with depth netw…
A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance
Adi Shamir, Itay Safran, Eyal Ronen +1
The existence of adversarial examples in which an imperceptible change in the input can fool well trained neural networks was experimentally discovered by Szegedy et al in 2013, wh…
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
Itay Safran, Ohad Shamir
We consider the optimization problem associated with training simple ReLU neural networks of the form with…
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks
Itay Safran, Ohad Shamir
We provide several new depth-based separation results for feed-forward neural networks, proving that various types of simple and natural functions can be better approximated using…
On the Quality of the Initial Basin in Overspecified Neural Networks
Itay Safran, Ohad Shamir
Deep learning, in the form of artificial neural networks, has achieved remarkable practical success in recent years, for a variety of difficult machine learning applications. Howev…