The Sum-of-Squares Method
I will discuss recent advances in algorithmic private statistics, in particular in using the sum-of-squares method to design algorithms with information-theoretically and/or computationally optimal sample complexity guarantees. Recent applications include an optimal algorithm for private mean estimation and a conjecturally-optimal (in some parameter regimes) for private sparse mean estimation; we anticipate that the techniques will see substantial further applications.
Along the way, I will touch on connections between private and robust statistics, and how these connections can be used for algorithmic benefits.
Joint works with Gautam Kamath, Mahbod Majid, Kristian Georgiev, Shayam Narayanan.