Asymptotic efficiency of simple decisions for the compound decision problem

Eitan Greenshtein, Ya’acov RitovarXiv 2008 · DOI · arXiv

TL;DR

In the world of big data estimation, "simple" rules—where you estimate each parameter using only its corresponding observation—are surprisingly powerful. This paper proves that for a large class of problems, these simple rules are nearly as efficient as much more complex "permutation invariant" rules, with the total risk difference remaining constant even as the number of observations grows to infinity.

What Problem Does This Paper Address?

Imagine you have $n$ independent observations (like sensor readings), and you know they come from a specific set of $n$ parameters (like true temperatures), but you don't know which reading belongs to which parameter. This is known as a compound decision problem.

Statisticians typically look at two ways to solve this:

  1. Permutation Invariant Rules: These estimators look at the entire batch of data. Because the order doesn't matter, the rule treats the data as a set. This is the "gold standard" for this type of problem but can be mathematically and computationally complex.
  2. Simple Symmetric Rules: These are much more restrictive. Here, the estimate for the $i$-th parameter depends only on the $i$-th observation. It’s like having $n$ people in separate rooms each making a decision based only on the piece of paper in front of them.

The central question is: How much accuracy do we lose by being "simple"? While "folklore" in statistics suggested they were similar, this paper seeks to rigorously quantify that gap.

Methods

The authors use a theoretical framework based on Bayesian models and decision theory. They treat the unknown ordering of parameters as a random permutation (uniformly distributed).

The key mathematical tools include:

  • Comparison of Experiments: Using Markov kernels and Jensen’s inequality to bound the difference in information between different setups.
  • De Finetti’s Theorem Logic: Leveraging the idea that exchangeable sequences (like their permuted parameters) behave like independent samples from a mixture distribution as $n$ gets large.
  • Risk Analysis: They specifically analyze the "total squared error risk" and use Martingale theory (specifically reversed $L_2$ martingales) to prove convergence rates.

Datasets

Not discussed in the paper. As a theoretical statistics paper, it relies on mathematical proofs and symbolic distributions (like the Normal distribution $N(\mu, 1)$) rather than empirical datasets.

Key Insights and Ideas

  • The $O(1)$ Difference: The most striking finding is that the difference in total risk between the complex rule and the simple rule is $O(1)$. In many asymptotic studies, "equivalent" means the difference grows slower than $n$ (e.g., $o(n)$). Finding that the difference stays bounded by a constant even as $n \to \infty$ is a much stronger result.
  • Oracle Equivalence: The paper shows that an "Oracle" who knows the set of parameters but not their order doesn't gain much by looking at the whole dataset versus looking at observations one by one.
  • The "Dense" Parameter Condition: The results hold particularly well when the parameters are "dense"—meaning they aren't so widely separated that the data points clearly "cluster" around specific values. If parameters are too far apart, the batch-processing rule could theoretically perform much better by "matching" points to clusters, but the authors show that under mild conditions, this advantage vanishes.

Key Results

  • Two-Valued Case: If parameters can only take two values (e.g., 0 or 1), the simple rule is $O(1)$ close to the optimal permutation invariant rule, provided the variance of the likelihood ratio is finite.
  • Normal Shift Model: For the common case where observations follow a Normal distribution with bounded means, the simple symmetric rule is asymptotically efficient.
  • General Theorem (5.1): Under two technical conditions (G1 and G2) which essentially ensure the parameters don't "separate" too much and that each observation can be reasonably explained by many different parameters, the $O(1)$ risk equivalence is guaranteed.

Limitations and Future Work

  • Known Parameter Set: The paper assumes the set of parameters $\mu$ is known (up to permutation). In real-world "Empirical Bayes" scenarios, this set is usually unknown and must be estimated from the data itself.
  • Squared Error Loss: The proofs are tailored to squared error loss. While this is standard, the results might differ for other loss functions (like absolute error or 0-1 loss).
  • Symmetry Requirements: The results rely heavily on the symmetry (permutation invariance) of the problem. If there is structural information or ordering in the parameters that the estimator could exploit, simple symmetric rules would likely fall behind.

Summary updated

Abstract

We consider the compound decision problem of estimating a vector of $n$ parameters, known up to a permutation, corresponding to $n$ independent observations, and discuss the difference between two symmetric classes of estimators. The first and larger class is restricted to the set of all permutation invariant estimators. The second class is restricted further to simple symmetric procedures. That is, estimators such that each parameter is estimated by a function of the corresponding observation alone. We show that under mild conditions, the minimal total squared error risks over these two classes are asymptotically equivalent up to essentially O(1) difference.
BibTeX
@misc{greenshtein2008asymptotic,
  author = {Eitan Greenshtein and Ya’acov Ritov},
  title = {{Asymptotic efficiency of simple decisions for the compound decision problem}},
  year = {2008},
  eprint = {0802.1319},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0802.1319},
  howpublished = {arXiv},
}

Loading related content...

Figure