42 citations · 46 across the 12 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.LG2018★ 1 cited
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…
cs.LG2018
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…
cs.LG2018★ 1 cited
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…