Robust Learning From Untrusted Sources: The Best Things in Life Are (Almost) Free
Channel: UCIBrenICS
Date: 2023-04-10

Alon Orlitsky
UCSD

Abstract:
In many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, data are collected from multiple untrusted sources, some potentially corrupt, biased, or even adversarial. Learning algorithms for this setting have therefore garnered considerable recent attention. We develop a general framework for robust learning from untrusted sources, and determine the least number of samples required for robust density estimation and classification over both discrete and continuous domains. Perhaps surprisingly, we show that robust learning can be achieved with essentially the same number of samples as required for genuine data. For the important problems of learning discrete and piecewise-polynomial densities, and of interval-based classification, we achieve these limits with polynomial-time algorithms. Based on joint work with Ayush Jain.

Speaker Bio:
Alon Orlitsky received his M.Sc. and Ph.D. degrees in Electrical Engineering from Stanford University and he spent a decade at the Communications Analysis Research Department at Bell Laboratories before joining the University of California, San Diego, where he holds the Qualcomm Chair for Information Theory and its Applications. His research concerns information theory, statistical modeling, and machine learning, focusing on fundamental limits and practical algorithms for extracting knowledge from data. Orlitsky was the President of the Information Theory Society in 2016-17. He is an IEEE Fellow and a recipient of the 1992 IEEE W.R.G. Baker Award, and the 2021 Information Theory Society Claude E. Shannon Award.