5 papers
Optimal Learning Under Tsybakov Noise
Steve Hanneke, Hongao Wang, Mingyue Xu
Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model, $\mathcal{H} \subseteq \{0,1\}^{\mathca…
Universal rates of ERM for agnostic learning
Steve Hanneke, Mingyue Xu
The universal learning framework has been developed to obtain guarantees on the learning rates that hold for any fixed distribution, which can be much faster than the ones uniforml…
Universal Rates of Empirical Risk Minimization
Steve Hanneke, Mingyue Xu
The well-known empirical risk minimization (ERM) principle is the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A…
A Theory of Optimistically Universal Online Learnability for General Concept Classes
Steve Hanneke, Hongao Wang
We provide a full characterization of the concept classes that are optimistically universally online learnable with labels. The notion of optimistically universal online…
Multiclass Transductive Online Learning
Steve Hanneke, Vinod Raman, Amirreza Shaeiri +1
We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2023b]…