6 papers · 1 filter
The Sample Complexity of Multiclass and Sparse Contextual Bandits
Liad Erez, Fan Chen, Alon Cohen +4
We study contextual bandits in the stochastic i.i.d.\ setting, where a learner observes contexts drawn from an unknown distribution, selects actions from a finite set , and aims…
Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back
Alon Cohen, Liad Erez, Steve Hanneke +4
The fundamental theorem of statistical learning states that binary PAC learning is governed by a single parameter -- the Vapnik-Chervonenkis (VC) dimension -- which determines both…
Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
Orin Levy, Liad Erez, Alon Cohen +1
We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over actions in the presence of delayed feedback, a scenario where loss observati…
The Real Price of Bandit Information in Multiclass Classification
Liad Erez, Alon Cohen, Tomer Koren +2
We revisit the classical problem of multiclass classification with bandit feedback (Kakade, Shalev-Shwartz and Tewari, 2008), where each input classifies to one of possible lab…
Fast Rates for Bandit PAC Multiclass Classification
Liad Erez, Alon Cohen, Tomer Koren +2
We study multiclass PAC learning with bandit feedback, where inputs are classified into one of possible labels and feedback is limited to whether or not the predicted labels ar…
Locally Optimal Descent for Dynamic Stepsize Scheduling
Gilad Yehudai, Alon Cohen, Amit Daniely +3
We introduce a novel dynamic learning-rate scheduling scheme grounded in theory with the goal of simplifying the manual and time-consuming tuning of schedules in practice. Our appr…