17 citations · 61 across the 9 of their papers we have counts for
22 papers · 1 filter
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim, Amit Daniely, Yishay Mansour +1
We study a generalization of boosting to the multiclass setting. We introduce a weak learning condition for multiclass classification that captures the original notion of weak lear…
Most Neural Networks Are Almost Learnable
Amit Daniely, Nathan Srebro, Gal Vardi
We present a PTAS for learning random constant-depth networks. We show that for any fixed and depth , there is a poly-time algorithm that for any distribution on $\sqrt{d}…
Approximate Description Length, Covering Numbers, and VC Dimension
Amit Daniely, Gal Katzhendler
Recently, Daniely and Granot [arXiv:1910.05697] introduced a new notion of complexity called Approximate Description Length (ADL). They used it to derive novel generalization bound…
From Local Pseudorandom Generators to Hardness of Learning
Amit Daniely, Gal Vardi
We prove hardness-of-learning results under a well-studied assumption on the existence of local pseudorandom generators. As we show, this assumption allows us to surpass the curren…
Most ReLU Networks Suffer from Adversarial Perturbations
Amit Daniely, Hadas Schacham
We consider ReLU networks with random weights, in which the dimension decreases at each layer. We show that for most such networks, most examples admit an adversarial perturbat…
Hardness of Learning Neural Networks with Natural Weights
Amit Daniely, Gal Vardi
Neural networks are nowadays highly successful despite strong hardness results. The existing hardness results focus on the network architecture, and assume that the network's weigh…