Publications by Ido Nachum | EPFL Graph Search

Finite Littlestone Dimension Implies Finite Information Complexity

Michael Christoph Gastpar, Aditya Pradeep, Ido Nachum

We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of ...

2022

A Johnson-Lindenstrauss Framework for Randomly Initialized CNNs

Michael Christoph Gastpar, Jan Hazla, Ido Nachum

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 answers this question for linear fully-connected neural networks (FNNs), stat ...

2022

Almost-Reed-Muller Codes Achieve Constant Rates for Random Errors

Emmanuel Abbé, Jan Hazla, Ido Nachum

This paper considers "delta-almost Reed-Muller codes", i.e., linear codes spanned by evaluations of all but a delta fraction of monomials of degree at most d. It is shown that for any delta > 0 and any epsilon > 0, there exists a family of delta-almost Ree ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

On Symmetry and Initialization for Neural Networks

Ido Nachum

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 functions, one can choose initial conditions so that standard SGD training ef ...

Springer Nature2020