Reconstructing Mean of a Sample with Adversary Errors - April 29, 2024

Explore a 2-hour lecture on statistical reconstruction techniques focusing on how to recover the mean of a vector-valued distribution when faced with adversarial data corruption. Learn about handling samples where an adversary has altered an e-fraction of data points, with the goal of reconstructing the average within O(sqrt(e)) precision. Discover why attempting to correct O(e) values to maintain a bounded covariation matrix, while theoretically effective, is computationally intensive. Delve into an elegant solution utilizing sum-of-squares proof techniques and semidefinite programming to create an efficient Ersatz-version that achieves the same results without exhaustive sample correction.