Dualizing Le Cam's method, with applications to estimating the unseens

Yury Polyanskiy, Yihong WuarXiv 2019 · OpenReview

Abstract

This paper establishes a fundamental connection between statistical lower bounds and optimal estimators through the lens of convex duality. By dualizing the classic Le Cam’s method, the authors demonstrate that the maximum lower bound for estimating functional properties is often exactly matched by the performance of a simple linear estimator. This framework provides sharp minimax rates for several long-standing problems in "estimating the unseens," including the distinct elements problem and Fisher’s species problem, while identifying critical phase transitions in estimation difficulty.

Introduction

In statistical estimation, researchers typically operate on two separate fronts. On one side, they seek lower bounds to prove the fundamental limits of any possible estimator, often employing Le Cam’s "two-point method." On the other, they construct upper bounds by designing specific estimators and proving their efficacy. Historically, a gap often persists between these two: Le Cam’s method is frequently perceived as "loose," providing lower bounds that do not reach the error rates of the best known estimators.

This work addresses a central question: When is Le Cam’s bound actually tight? By applying convex duality, the authors reveal that the search for the most difficult pair of distributions (the lower bound) is mathematically equivalent to optimizing the bias-variance tradeoff for a class of linear estimators. This bridge allows for the automatic derivation of optimal estimators from the math of the lower bound itself.

The Duality Framework

The core contribution of the paper is the dualization of the modulus of continuity. The authors relate the minimax risk of an estimation problem to how much a functional can change relative to the distance (such as $\chi^2$-divergence) between two distributions.

They show that the maximization problem used to find the "least favorable" pair of distributions for a lower bound is the mathematical dual of a minimization problem that optimizes a linear estimator of the form $\hat{T} = \frac{1}{n} \sum g(X_i)$. When there is no duality gap, the lower bound is tight, and the optimal function $g$ is revealed through the dual solution. This framework is remarkably robust, covering i.i.d. settings, deterministic parameters, and exponential families.

Methodology

To solve the resulting optimization problems for specific applications, the authors utilize sophisticated tools from complex analysis, including:

  • Hadamard’s Three-Lines Theorem: Used to bound the growth of analytic functions.
  • Paley-Wiener Theorem: Employed to characterize the properties of the estimators in the transform domain.

These tools allow the authors to provide bounds that are tight up to universal constants, a significant improvement over previous frameworks that were less applicable to high-dimensional settings where the dimension might scale with the sample size.

Estimating the Unseens: Applications and Results

The methodology is applied to three classic problems involving "unseen" data, yielding sharp minimax rates and revealing "elbow effects"—points where the problem's difficulty shifts dramatically.

1. Distinct Elements Problem

When estimating the number of unique elements in a population based on a sample, the authors prove the optimal error rate is proportional to $n^{- \frac{1}{2} \min\{\frac{p}{1-p}, 1\}}$, where $p$ is the sampling fraction. This reveals a sharp phase transition at $p = 1/2$. If more than half the population is sampled, the estimation rate improves significantly.

2. Fisher’s Species Problem

This problem involves predicting how many new species will be discovered in $r \cdot n$ future observations given $n$ current observations. The paper identifies an optimal error rate of $n^{-\min\{\frac{1}{r+1}, \frac{1}{2}\}}$. Here, the "elbow" occurs at $r=1$, the point where one attempts to predict as many future samples as have already been observed.

3. Population Recovery

The framework also provides sharp results for estimating distributions from lossy or erased data, further demonstrating the power of linear estimators even for complex, non-linear functionals.

Discussion and Limitations

The findings suggest that linear estimators—simple empirical averages of a carefully chosen function $g$—are surprisingly powerful, often achieving the optimal minimax rate even for non-linear problems.

However, the framework has specific requirements:

  • Convexity: The current theory relies on the parameter space being convex and compact. If the parameter space is a union of disjoint sets, the duality may fail.
  • Quadratic Loss: The primary focus is on squared error, though the authors suggest potential extensions for high-probability bounds.
  • Computation: While the paper proves the existence of an optimal $g$, constructing it for continuous models may require solving large-scale linear programs via discretization.

This work provides a unified theoretical foundation for functional estimation, bridging the gap between the hardness of a problem and the construction of its solution.

Summary updated

BibTeX
@misc{polyanskiy2019dualizing,
  author = {Yury Polyanskiy and Yihong Wu},
  title = {{Dualizing Le Cam's method, with applications to estimating the unseens}},
  year = {2019},
  url = {https://openreview.net/forum?id=rPSeM7_-MB},
}
Figure