Reproduce “Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Shai Ben-David, Steve Hanneke, Farnam Mansouri, Amirreza Shaeiri

The paper studies PAC learning with deterministic labels when the target rule may lie outside the predictor class. It combines empirical risk minimization with memorization, retaining observed labels and using the selected class member on unseen inputs. For finite VC dimension d and diameter K, its upper bound includes K^(1/3)d^(2/3)/ε; matching lower bounds hold for some classes, not all.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.