4 papers
Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
Bogdan Chornomaz, Yonatan Koren, Shay Moran +1
We study the problem of learning in the presence of an adversary that can corrupt an fraction of the training examples with the goal of causing failure on a specific test poin…
Spherical dimension
Bogdan Chornomaz, Shay Moran, Tom Waknine
We introduce and study the spherical dimension, a natural topological relaxation of the VC dimension that unifies several results in learning theory where topology plays a key role…
On Reductions and Representations of Learning Problems in Euclidean Spaces
Bogdan Chornomaz, Shay Moran, Tom Waknine
Many practical prediction algorithms represent inputs in Euclidean space and replace the discrete 0/1 classification loss with a real-valued surrogate loss, effectively reducing cl…
Dual VC Dimension Obstructs Sample Compression by Embeddings
Zachary Chase, Bogdan Chornomaz, Steve Hanneke +2
This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddin…