Speaker: Arun Sai Suggala

Abstract: We consider the problem of designing minimax estimators for estimating the parameters of a probability distribution. Unlike classical approaches such as MLE, M-estimators, we consider an algorithmic approach for constructing such estimators.

We view the problem of designing minimax estimators as finding a mixed strategy Nash equilibrium of a zero-sum game. By leveraging recent results in online learning with non-convex losses, we provide a general algorithm for finding a Nash equilibrium of the statistical game. Our algorithm requires access to two subroutines, namely, a Bayes estimator subroutine which outputs a Bayes estimator corresponding to a given prior probability distribution, and a subroutine which computes the worst-case risk of any given estimator. Given access to these two subroutines, we show that our algorithm outputs both a minimax estimator and a least favorable prior. To demonstrate the power of this technique, we use it to construct provably minimax estimators for classical problems such as estimation in finite Gaussian sequence model, linear regression.