Speaker: Guy Blanc (MIT)

Title: Robust Learning with Optimal Error

Abstract: We construct algorithms with optimal error for learning with 
adversarial noise. The overarching theme of this work is that 
the use of randomized hypotheses can substantially improve 
upon the best error rates achievable with deterministic 
hypotheses.

For η-rate malicious noise, we show the optimal error is 1/2 · 
η/(1 − η), improving on the optimal error of deterministic 
hypotheses by a factor of 1/2. This answers an open question 
of Cesa-Bianchi et al. (JACM 1999) who showed randomness 
can improve error by a factor of 6/7.

For η-rate nasty noise, we show the optimal error is 3/2 · η
for distribution-independent learners and η for fixeddistribution learners, both improving upon the optimal 2η 
error of deterministic hypotheses. This closes a gap first 
noted by Bshouty et al. (Theoretical Computer Science 2002) 
when they introduced nasty noise and reiterated in the 
recent works of Klivans et al. (NeurIPS 2025) and Blanc et al. 
(SODA 2026).

For η-rate agnostic noise and the closely related nasty 
classification noise model, we show the optimal error is η, 
improving upon the optimal 2η error of deterministic 
hypotheses.

All of our learners have sample complexity linear in the VCdimension of the concept class and polynomial in the inverse 
excess error. All except for the fixed-distribution nasty noise 
learner are time efficient given access to an oracle for 
empirical risk minimization.

Biography:

Guy is a Nobert Wiener postdoc at MIT mentored by Ankur 
Moitra. Prior to that, he received his PhD in theoretical 
computer science at Stanford advised by Li-Yang Tan.