Learning Minimax Estimators via Online Learning

Kartik Gupta, Arun Sai Suggala, Adarsh Prasad, Praneeth Netrapalli, Pradeep RavikumararXiv 2020 · OpenReview

Abstract

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.

Introduction

In statistical decision theory, the minimax principle is a fundamental criterion for evaluating the performance of an estimator. A minimax estimator is one that minimizes the maximum possible risk over a parameter space, providing a robust performance guarantee even when "nature" chooses the most difficult parameters. While the principle is conceptually elegant, finding minimax estimators has historically been a bespoke mathematical challenge. For many complex or high-dimensional models, statisticians have relied on manual proofs or specific heuristics, as no general-purpose "recipe" existed to construct these estimators automatically.

This paper introduces a general algorithmic framework that transforms the search for minimax estimators from a theoretical derivation into a computational optimization problem. By reframing the problem as a zero-sum game and applying techniques from online learning, we provide a unified method to "learn" optimal estimators and their corresponding least favorable priors.

The Minimax Game

The core of our approach is viewing minimax estimation as a zero-sum game between two players:

  1. The Statistician: Aims to choose an estimator $\delta$ to minimize the risk.
  2. Nature: Aims to choose a parameter distribution (a "prior") $\pi$ to maximize the statistician's risk.

A minimax estimator corresponds to a mixed-strategy Nash equilibrium of this game. To find this equilibrium, we employ a repeated play strategy based on Online Learning:

  • Nature's Strategy: Nature utilizes the Follow the Perturbed Leader (FTPL) algorithm. In each iteration, Nature observes the estimators used by the statistician in previous rounds, adds a random perturbation to the cumulative risk, and selects a distribution that would have performed best against those estimators.
  • The Statistician's Strategy: The statistician plays a Best Response. Given Nature's current distribution, the statistician computes the Bayes estimator—the estimator that minimizes the average risk for that specific prior.

Computational Efficiency via Group Invariance

Searching the space of all possible estimators is computationally intractable due to its infinite-dimensional nature. To overcome this, we leverage Group Invariance. If a statistical problem possesses inherent symmetry (e.g., rotation or translation invariance), the optimal minimax estimator must also respect these symmetries. By restricting the search to invariant estimators, we can collapse complex, high-dimensional problems into lower-dimensional optimization tasks (often 1D or 2D) that are efficiently solvable via grid search or standard optimization subroutines.

Our framework requires two primary "oracles":

  1. Bayes Oracle: Computes the Bayes estimator for a given prior.
  2. Worst-case Risk Oracle: Computes the maximum risk of a given estimator.

Experimental Validation

We evaluated the framework across several fundamental statistical models to demonstrate its versatility and performance compared to classical baselines.

Finite Gaussian Sequence Models

In estimating the mean of a normal distribution, our algorithm successfully identified estimators with lower worst-case risk than the Maximum Likelihood Estimator (MLE) and the James-Stein estimator, particularly in high-dimensional settings. Notably, the learned estimator provides provable minimaxity across the entire parameter space radius, filling a gap where previous analytical solutions were only approximate.

Entropy Estimation

Entropy estimation is a notoriously difficult problem requiring specialized estimators. Our general-purpose algorithm matched the performance of the JVHW estimator, a state-of-the-art method specifically designed for this task. This demonstrates that our framework can rediscover highly specialized statistical tools without problem-specific tuning.

Linear Regression

In linear regression scenarios where the number of samples is close to the number of dimensions, the learned minimax estimator outperformed standard Ridge Regression. The algorithm effectively balanced the bias-variance tradeoff to minimize the maximum possible error across the bounded regression vector space.

Key Insights

  • Simultaneous Discovery: The algorithm identifies both the minimax estimator and the Least Favorable Prior (LFP), providing insight into which regions of the parameter space are most difficult for estimation.
  • Neural Networks as Heuristics: For problems lacking clear group symmetries, we demonstrate that neural networks can serve as universal function approximators within our framework to find high-performing heuristic estimators.
  • Convergence: We empirically observed the "duality gap" (the difference between the maximum risk and the Bayes risk) shrinking toward zero, confirming that the algorithm converges to a true Nash Equilibrium.

Limitations and Future Work

While the framework is powerful, its efficiency depends on the availability of the Bayes and Worst-case Risk oracles. In the absence of symmetry, these subroutines can become computationally expensive. Future research may focus on finding "rate-optimal" estimators—those that are minimax within a constant factor—to alleviate the computational burden of finding exact solutions in non-symmetric, high-dimensional spaces.

Summary updated

Abstract

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.
BibTeX
@misc{gupta2020learning,
  author = {Kartik Gupta and Arun Sai Suggala and Adarsh Prasad and Praneeth Netrapalli and Pradeep Ravikumar},
  title = {{Learning Minimax Estimators via Online Learning}},
  year = {2020},
  eprint = {2006.11430},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.11430},
}
Figure