A constrained risk inequality for general losses

John C. Duchi, Feng Ruan

Abstract

We provide a general constrained risk inequality that applies to arbitrary non-decreasing losses, extending a result of Brown and Low [Ann. Stat. 1996]. Given two distributions $P_0$ and $P_1$, we find a lower bound for the risk of estimating a parameter $\theta(P_1)$ under $P_1$ given an upper bound on the risk of estimating the parameter $\theta(P_0)$ under $P_0$. The inequality is a useful pedagogical tool, as its proof relies only on the Cauchy-Schwartz inequality, it applies to general losses, and it transparently gives risk lower bounds on super-efficient and adaptive estimators.

Introduction

In statistical estimation, the search for an "optimal" estimator is often a search for balance. While it is tempting to seek estimators that perform exceptionally well across all scenarios, fundamental mathematical constraints often make this impossible. This paper formalizes a "no free lunch" theorem for statistical estimators, demonstrating that "super-efficiency"—performing exceptionally well at a specific distribution—necessarily results in poor performance at nearby distributions.

By extending the classic Brown-Low inequality, the authors provide a transparent, pedagogical framework to quantify these trade-offs. Unlike previous tools that were often restricted to specific loss functions like squared error ($L_2$), this new inequality applies to any non-decreasing loss function, including absolute error, 0-1 loss, and even non-convex losses.

The Geometry of Statistical Risk

The core of the paper’s contribution is a constrained risk inequality that relates the performance of an estimator at two different probability distributions, $P_0$ and $P_1$. The difficulty of distinguishing between these two distributions is captured by two primary metrics:

  • $\chi^2$-affinity ($\rho$): A measure of similarity between $P_0$ and $P_1$. High affinity indicates that the distributions are difficult to tell apart.
  • Separation ($\Delta$): The distance between the parameters we wish to estimate under each distribution.

If an estimator is constrained to have a very small risk (error) at $P_0$ (denoted as $\le \delta$), the inequality provides a lower bound for the risk at $P_1$. This bound is a function of the separation $\Delta$ and the affinity $\rho$, proving that as we force the error down at one point, it must inevitably rise at another.

Methodology: The Cauchy-Schwarz Approach

The authors’ approach is notable for its mathematical elegance. Rather than relying on the complex machinery often found in asymptotic statistics, the proof relies primarily on the Cauchy-Schwarz inequality.

This simplicity serves a pedagogical purpose, making the "hardest one-dimensional subproblem" argument more accessible. The logic is straightforward: to find a lower bound for a complex, high-dimensional problem, one only needs to identify a single pair of distributions (a one-dimensional subproblem) that is difficult to distinguish. If an estimator fails to maintain low risk across this subproblem, it cannot be considered robust for the broader problem.

Key Results and Applications

General Lower Bounds

The paper establishes that for a convex loss $\ell$, if the risk at $P_0$ is $\le \delta$, the risk at $P_1$ is bounded below by: $$(\sqrt{\Delta} - \sqrt{\rho \delta})_+^2$$ This formula provides a quantitative tool for evaluating the limits of any estimator under general loss functions.

The Cost of Super-efficiency

The paper applies this theory to the famous Hodges' estimator. While this estimator is known for performing perfectly when the true parameter is zero, it is notorious for its poor performance elsewhere. The authors provide a quantitative proof showing that the Hodges' estimator's risk can be as bad as $1/n^{1/4}$, which is significantly worse than the standard $1/\sqrt{n}$ rate achieved by traditional estimators.

Gaussian Mean and Nonparametric Models

In Gaussian mean estimation, the authors show that if an estimator's error probability is forced to nearly zero at the origin, its error probability must converge to 1 (total failure) on specific local alternatives. Furthermore, they demonstrate that these bounds are not limited to simple parametric models; by using influence functions (local derivatives for statistical functionals), the bounds can be applied to complex nonparametric models.

Conclusion and Limitations

While the method is highly general and transparent, the authors note that it may not always provide the "sharpest" constants when compared to more specialized techniques like Le Cam–Hájek theory. However, the universality of the trade-off—showing that super-efficiency is essentially a "set of measure zero" phenomenon—provides a vital perspective for researchers developing adaptive estimators in high-dimensional statistics and machine learning. The inequality serves as a reminder that in the pursuit of local efficiency, global risk must always be accounted for.

Summary updated

Abstract

We provide a general constrained risk inequality that applies to arbitrary non-decreasing losses, extending a result of Brown and Low [Ann. Stat. 1996]. Given two distributions $P_0$ and $P_1$, we find a lower bound for the risk of estimating a parameter $θ(P_1)$ under $P_1$ given an upper bound on the risk of estimating the parameter $θ(P_0)$ under $P_0$. The inequality is a useful pedagogical tool, as its proof relies only on the Cauchy-Schwartz inequality, it applies to general losses, and it transparently gives risk lower bounds on super-efficient and adaptive estimators.
BibTeX
@inproceedings{duchi2021constrained,
  author = {John C. Duchi and Feng Ruan},
  title = {{A constrained risk inequality for general losses}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}
Figure