Presenter

Details

  • Date: Monday, March 11, 2024
  • Time: 12:00 PM
  • Location: EECS, room 2311

Abstract

In online binary classification under apple tasting feedback, the learner only observes the true label if it predicts “1”. First studied by Helmbold et al., we revisit this classical partial-feedback setting and study online learnability from a combinatorial perspective. We show that the Littlestone dimension continues to prove a tight quantitative characterization of apple tasting in the agnostic setting, closing an open question posed by Helmbold et al. In addition, we give a new combinatorial parameter, called the Effective width, that tightly quantifies the minimax expected mistakes in the realizable setting. As a corollary, we use the Effective width to establish a trichotomy of the minimax expected number of mistakes in the realizable setting. In particular, we show that in the realizable setting, the expected number of mistakes for any learner under apple tasting feedback can only be Θ(1), Θ(T), or Θ(T).

Registration

Please fill out this survey to RSVP for pizza!

For any additional questions or inquiries, please contact us at speecs.seminar-requests@umich.edu