Learning Minimax Estimators via Online Learning
  We consider the problem of designing minimax estimators for estimating the
parameters of a probability distribution. Unlike classical approaches such as
the MLE and minimum distance 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 mixed-strategy Nash equilibrium of general
non-convex non-concave zero-sum games. Our algorithm requires access to two
subroutines: (a) one which outputs a Bayes estimator corresponding to a given
prior probability distribution, and (b) one 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 approach, we use it to construct provably minimax
estimators for classical problems such as estimation in the finite Gaussian
sequence model, and linear regression.
