Seminars

View all Seminars  |  Download ICal for this event

Tackling Label Corruptions: Univariate Polynomial Regression and Generalized Linear Models

Series: Bangalore Theory Seminars

Speaker: Sushrut Karmalkar, University of Wisconsin Madison.

Date/Time: Jul 18 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Abstract:
Label corruptions pose a significant challenge in various machine learning tasks, affecting the accuracy and reliability of models. In this talk, we will address two distinct problems involving label corruptions, and present approaches to handle them effectively.

In this problem the goal is to recover a polynomial widehat p which is pointwise close to a polynomial p, given samples (x, y) where, with probability1-rho the samples are clean, i.e. satisfy |y - p(x)| < sigma; and with probability rho is corrupted, i.e. completely arbitrary. We propose an approach which can tolerate rho as large as any constant less than 1/2, which is the information theoretic limit for unique recovery of this problem.

In the second problem, we examine the challenge of learning a linear function composed with a generalized linear model, when upto 1-o(1) (i.e. all but a vanishingly small fraction) of the labels are corrupted via arbitrary independent and additive noise. We show that in this extremely challenging setting, it is always possible to recover a polynomial-sized list of candidates, one of which is arbitrarily close to the true answer. Moreover, if a certain mild identifiability condition holds, then it is possible to prune the list and return a single such candidate.


Microsoft teams link:

Link


We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, Rachana Gusain, Rahul Madhavan, KVN Sreenivas