Timezone: »

 
Poster
A General Method for Robust Learning from Batches
Ayush Jain · Alon Orlitsky

Wed Dec 09 09:00 PM -- 11:00 PM (PST) @ Poster Session 4 #1189
in Poster Session 5 »

In many applications, data is collected in batches, some of which may be corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating finite distributions in this setting. We develop a general framework of robust learning from batches, and determine the limits of both distribution estimation, and notably, classification, over arbitrary, including continuous, domains.

Building on this framework, we derive the first robust agnostic: (1) polynomial-time distribution estimation algorithms for structured distributions, including piecewise-polynomial, monotone, log-concave, and gaussian-mixtures, and also significantly improve their sample complexity; (2) classification algorithms, and also establish their near-optimal sample complexity; (3) computationally-efficient algorithms for the fundamental problem of interval-based classification that underlies nearly all natural-1-dimensional classification problems.

Author Information

Ayush Jain (UC San Diego)
Alon Orlitsky (University of California, San Diego)

More from the Same Authors