42 citations · 46 across the 12 of their papers we have counts for
14 papers
Minimax Limits of k-Fold Cross-Validation via Majority
Ido Nachum, Rüdiger Urbanke, Thomas Weinberger
We study the mean-squared error of -fold cross-validation as a risk estimator, with particular emphasis on how its accuracy depends on the number of folds . Despite the wides…
The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits
Ido Nachum, Rüdiger Urbanke, Thomas Weinberger
Despite ongoing theoretical research on cross-validation (CV), many theoretical questions remain widely open. This motivates our investigation into how properties of algorithm-dist…
Batch Normalization Decomposed
Ido Nachum, Marco Bondaschi, Michael Gastpar +1
\emph{Batch normalization} is a successful building block of neural network architectures. Yet, it is not well understood. A neural network layer with batch normalization comprises…
Which Algorithms Have Tight Generalization Bounds?
Michael Gastpar, Ido Nachum, Jonathan Shafer +1
We study which machine learning algorithms have tight generalization bounds. First, we present conditions that preclude the existence of tight generalization bounds. Specifically,…
Fantastic Generalization Measures are Nowhere to be Found
Michael Gastpar, Ido Nachum, Jonathan Shafer +1
We study the notion of a generalization bound being uniformly tight, meaning that the difference between the bound and the population loss is small for all learning algorithms and…
Finite Littlestone Dimension Implies Finite Information Complexity
Aditya Pradeep, Ido Nachum, Michael Gastpar
We prove that every online learnable class of functions of Littlestone dimension admits a learning algorithm with finite information complexity. Towards this end, we use the no…
Regularization by Misclassification in ReLU Neural Networks
Elisabetta Cornacchia, Jan Hązła, Ido Nachum +1
We study the implicit bias of ReLU neural networks trained by a variant of SGD where at each step, the label is changed with probability to a random label (label smoothing bein…
A Johnson--Lindenstrauss Framework for Randomly Initialized CNNs
Ido Nachum, Jan Hązła, Michael Gastpar +1
How does the geometric representation of a dataset change after the application of each randomly initialized layer of a neural network? The celebrated Johnson--Lindenstrauss lemma…
Almost-Reed--Muller Codes Achieve Constant Rates for Random Errors
Emmanuel Abbe, Jan Hązła, Ido Nachum
This paper considers '-almost Reed-Muller codes', i.e., linear codes spanned by evaluations of all but a fraction of monomials of degree at most . It is shown that for an…
On Symmetry and Initialization for Neural Networks
Ido Nachum, Amir Yehudayoff
This work provides an additional step in the theoretical understanding of neural networks. We consider neural networks with one hidden layer and show that when learning symmetric f…
Average-Case Information Complexity of Learning
Ido Nachum, Amir Yehudayoff
How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension ? Previous works have shown that even for the amount of information m…
On the Perceptron's Compression
Shay Moran, Ido Nachum, Itai Panasoff +1
We study and provide exposition to several phenomena that are related to the perceptron's compression. One theme concerns modifications of the perceptron algorithm that yield bette…
A Direct Sum Result for the Information Complexity of Learning
Ido Nachum, Jonathan Shafer, Amir Yehudayoff
How many bits of information are required to PAC learn a class of hypotheses of VC dimension ? The mathematical setting we follow is that of Bassily et al. (2018), where the val…
Learners that Use Little Information
Raef Bassily, Shay Moran, Ido Nachum +2
We study learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term -bit info…