125 citations · 346 across the 41 of their papers we have counts for
5 papers · 1 filter
Learning Boolean Circuits with Neural Networks
Eran Malach, Shai Shalev-Shwartz
While on some natural distributions, neural-networks are trained efficiently using gradient-based algorithms, it is known that learning them is computationally hard in the worst-ca…
On the Optimality of Trees Generated by ID3
Alon Brutzkus, Amit Daniely, Eran Malach
Since its inception in the 1980s, ID3 has become one of the most successful and widely used algorithms for learning decision trees. However, its theoretical properties remain poorl…
ID3 Learns Juntas for Smoothed Product Distributions
Alon Brutzkus, Amit Daniely, Eran Malach
In recent years, there are many attempts to understand popular heuristics. An example of such a heuristic algorithm is the ID3 algorithm for learning decision trees. This algorithm…
Decoupling Gating from Linearity
Jonathan Fiat, Eran Malach, Shai Shalev-Shwartz
ReLU neural-networks have been in the focus of many recent theoretical works, trying to explain their empirical success. Nonetheless, there is still a gap between current theoretic…
Is Deeper Better only when Shallow is Good?
Eran Malach, Shai Shalev-Shwartz
Understanding the power of depth in feed-forward neural networks is an ongoing challenge in the field of deep learning theory. While current works account for the importance of dep…