A General Method for Robust Learning from Batches
This work addresses the challenge of handling batch-level corruption in data for machine learning applications, providing foundational algorithms with broad applicability across domains.
The paper tackles the problem of robust learning from batches with corrupt or adversarial data, determining the limits for classification and distribution estimation over arbitrary domains and deriving the first robust agnostic computationally-efficient algorithms for various tasks, such as piecewise-interval classification and distribution estimation for piecewise-polynomial, monotone, log-concave, and gaussian-mixture models.
In many applications, data is collected in batches, some of which are corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating discrete distributions in this setting. We consider a general framework of robust learning from batches, and determine the limits of both classification and distribution estimation over arbitrary, including continuous, domains. Building on these results, we derive the first robust agnostic computationally-efficient learning algorithms for piecewise-interval classification, and for piecewise-polynomial, monotone, log-concave, and gaussian-mixture distribution estimation.