Learning Minimax Estimators via Online Learning
This work addresses the challenge of constructing minimax estimators for statisticians and machine learning practitioners, offering a novel algorithmic approach that is incremental in leveraging online learning techniques for non-convex games.
The authors tackled the problem of designing minimax estimators for parameter estimation by framing it as finding a mixed-strategy Nash equilibrium in a zero-sum game, and they developed a general algorithm that outputs both a minimax estimator and a least favorable prior, demonstrating its application in classical problems like the finite Gaussian sequence model and linear regression.
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.