42 citations · 147 across the 42 of their papers we have counts for
6 papers · 1 filter
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…
Anti-concentration in most directions
Anup Rao, Amir Yehudayoff
We prove anti-concentration bounds for the inner product of two independent random vectors. For example, we show that if are subsets of the cube with $|A| \cdot…
An isoperimetric inequality for Hamming balls and local expansion in hypercubes
Zilin Jiang, Amir Yehudayoff
We prove a vertex isoperimetric inequality for the -dimensional Hamming ball of radius . The isoperimetric inequality is sharp up to a constant factor for…
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…
On the Covariance-Hessian Relation in Evolution Strategies
Ofer M. Shir, Amir Yehudayoff
We consider Evolution Strategies operating only with isotropic Gaussian mutations on positive quadratic objective functions, and investigate the covariance matrix when constructed…
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…