4 papers · 1 filter
Self-Directed Apple Tasting
Tanmay Devale, Reed Phillips, Arvind Ramaswami
We study the classical apple-tasting setting, a partial feedback model in which the learner observes the true label only when it predicts . A combinatorial characterization for…
Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the S…
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Idan Attias, Steve Hanneke, Arvind Ramaswami
We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitra…
Sample Compression Scheme Reductions
Idan Attias, Steve Hanneke, Arvind Ramaswami
We present novel reductions from sample compression schemes in multiclass classification, regression, and adversarially robust learning settings to binary sample compression scheme…