Seminars

View all Seminars  |  Download ICal for this event

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians

Series: Bangalore Theory Seminars

Speaker: Anay Mehrotra, Yale University

Date/Time: Aug 28 11:00:00

Location: CSA auditorium [Room No. 104], ground floor

Abstract:
In many scientific disciplines, data collection processes introduce systematic biases, leading to challenges in accurately learning from this data. In this talk, we study statistical estimation under systematic bias, focusing on estimating the parameters of an exponential family distribution when samples are only shown if they fall in an unknown subset S of R^d.

Previous work by Kontonis et al. (FOCS 19) gave a d^poly(1/ε) algorithm for estimating ε-accurate parameters in the case of Gaussian distributions with diagonal covariance matrices. Recently, Diakonikolas et al. (COLT 24) demonstrated that this exponential dependence on 1/ε is necessary, even for well-behaved classes of S.

These works leave the following open problems: Can we generalize these results to arbitrary Gaussians or beyond? Can we develop algorithms with poly(d/ε) runtime when S is a simple set, such as a halfspace? This talk presents new algorithms addressing these challenges, based on joint work with Jane H. Lee and Manolis Zampetakis. A draft of this work is available at Link

Microsoft teams link:

Link

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


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar