Beyond Worst-Case Online Classification
Friday, September 19, 2025 3:00–4:00 PM
- LocationTyler Hall, 055
- DescriptionOmar Montasser, Assistant Professor in the Department of Statistics and Data Science at Yale revisits online binary classification by shifting the focus from competing with the best-in-class binary loss to competing against relaxed benchmarks that capture smoothed notions of optimality. Instead of measuring regret relative to the exact minimal binary error — a standard approach that leads to worst-case bounds tied to the Littlestone dimension — this work considers comparing with predictors that are robust to small input perturbations, perform well under Gaussian smoothing, or maintain a prescribed output margin. The algorithms achieve regret guarantees that depend only on the VC dimension and the complexity of the instance space (e.g., metric entropy), and notably, they incur only an O(log(1/γ)) dependence on the generalized margin γ. This stands in contrast to most existing regret bounds, which typically exhibit a polynomial dependence on 1/γ. We complement this with matching lower bounds. This work is based on joint work with Abhishek Shetty and Nikita Zhivotovskiy.
Montasser's research broadly explores theory and foundations of machine learning. Prior to joining Yale, Montasser was a FODSI-Simons postdoctoral fellow at UC Berkeley. He earned his Ph.D. from the Toyota Technological Institute at Chicago in 2023. - Websitehttps://events.uri.edu/event/beyond-worst-case-online-classification
- CategoriesLectures / Presentations, Classes / Workshops