📊 statistics

Minimax Quantile Bounds via Information Measures

This paper introduces a unified information-theoretic framework based on a loss-adapted Neyman–Pearson metaconverse to derive sharp minimax quantile lower bounds by tailoring specific information measures—such as Maximal Leakage, Sibson information, and Amemiya norms—to the interplay between recovery resolution and likelihood-ratio tail behavior.

Original authors: Amedeo Roberto Esposito

Published 2026-08-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Amedeo Roberto Esposito

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of statistics, scientists often face a problem of uncertainty: they have a hidden truth, like the location of a ship at sea or the identity of a specific gene, and they must guess it based on noisy, imperfect data. For decades, the standard way to judge how well a guessing strategy works has been to look at the average error. If a method is wrong by a mile half the time and right the rest of the time, it might be considered good enough if the average mistake is small. However, this average view can be misleading. It hides the risk of a catastrophic failure, where the guess is wildly off the mark. In many critical situations, from diagnosing a rare disease to securing a communication network, the average performance matters less than the worst-case scenario. Researchers care deeply about knowing exactly how large an error can be while still keeping the chance of a total failure below a specific, safe limit. This is the question of the "minimax quantile": finding the smallest possible error radius that guarantees a high probability of success, no matter how the data behaves.

A researcher has developed a new, unified way to answer this difficult question. Instead of treating every estimation problem as unique, they created a single, flexible framework that acts like a master key for unlocking the limits of what can be known from noisy data. Their approach starts with a fundamental idea from probability theory: comparing the likelihood of the true signal against a random guess. They realized that the difficulty of an estimation problem comes from two distinct sources. The first is the shape of the problem itself—how many possible answers there are and how close they are to one another. The second is the statistical power of the data—how clearly the noise allows one to distinguish the true answer from the others. By separating these two factors, the researcher built a method that can be adjusted to fit different types of problems, from finding a single specific item to estimating a value within a small range.

The power of this new framework lies in its ability to swap out different mathematical tools depending on the nature of the task. The researcher showed that for problems where the goal is to find an exact answer, such as identifying which community a person belongs to in a social network, one specific tool works perfectly. This tool, known as Maximal Leakage, measures the maximum amount of information that could possibly be extracted from the data. In these exact-recovery scenarios, this tool provides a precise, unshakeable limit on how well anyone can do. However, the researcher also discovered that this perfect tool fails when the goal is less strict, such as finding an answer that is merely "close enough" to the truth. In these approximate recovery situations, a different tool, based on a concept called Sibson information, proves to be far more powerful. By tuning this tool to a specific setting, the researcher found it could reveal limits that the exact-recovery tool completely missed, showing that the best way to measure difficulty changes depending on how much error is allowed.

The researcher tested their framework on several complex, real-world scenarios to prove its utility. In one case, they applied it to a model of community detection in networks, where the goal is to separate a group of people into two distinct clusters based on the strength of their connections. Previous methods could only tell researchers when a solution was theoretically possible in the long run, but this new approach provided exact, finite-sample bounds. It told them precisely how the size of the network and the strength of the signals interact to determine the probability of success, even before the network becomes infinitely large. In another application, they tackled the problem of cleaning up a blurry image of a low-rank matrix, which is a common task in data science. Here, the noise was not random in the usual sense but was confined to a specific, bounded shape. Traditional methods that rely on measuring the distance between probability distributions failed completely in this setting because the distributions did not overlap in a way those methods could measure. The new framework, however, used a geometric approach to calculate the volume of the possible error space, successfully deriving tight limits on how well the matrix could be recovered.

Perhaps the most striking finding was how the framework revealed the importance of the "tail" of the probability distribution—the rare, extreme events that happen very infrequently. In a problem involving the localization of a single signal among many, the researcher found that standard tools, which look at average behavior, were too weak to capture the true difficulty. These tools suggested that the error would vanish slowly, but the new method, which used a specialized norm adapted to the heavy tails of the data, showed that the error would vanish much faster. This demonstrated that to get the sharpest possible answer, one must choose a measuring stick that fits the specific shape of the noise. If the noise has heavy tails, a standard ruler will give a misleadingly pessimistic view of the problem's difficulty.

The researcher's work does not just offer a new formula; it offers a new way of thinking about the limits of knowledge. They proved that there is no single "best" way to measure the difficulty of an estimation problem. Instead, the right tool depends entirely on the resolution of the goal and the behavior of the noise. For exact identification, a tool that looks at the worst-case information gain is ideal. For approximate answers, a tool that balances the volume of possible errors with the likelihood of the data is better. And for problems with rare, extreme outliers, a tool that specifically accounts for those tails is necessary. By unifying these different approaches under one roof, the researcher has provided a clear path for determining exactly how much we can know, and how confident we can be, in the face of uncertainty. Their results show that by matching the right information measure to the specific nature of the problem, we can move from vague approximations to precise, finite-sample guarantees.

Technical Summary: Minimax Quantile Bounds via Information Measures

Problem Statement
The paper addresses the problem of establishing lower bounds for the minimax quantile risk in statistical estimation. Unlike classical minimax theory, which typically focuses on the expected loss (risk), this work investigates the confidence-dependent question: for a prescribed failure probability $\delta \in (0, 1)$ , what is the smallest error radius $\rho$ such that the worst-case probability of the estimation error exceeding $\rho$ is at most $\delta$ ? This formulation, introduced systematically in prior work [34], retains the tail behavior of the loss distribution, allowing for the distinction between experiments that share the same expected-risk rate but differ significantly in their probability of large estimation errors.

Methodology: The Loss-Adapted Neyman–Pearson Metaconverse
The core methodological contribution is a unified information-theoretic framework centered on a loss-adapted Neyman–Pearson (NP) metaconverse. The approach proceeds as follows:

Geometric Separation: The framework introduces an auxiliary prior $P_W$ over the parameter space $\Theta$ . It defines a "small-ball" function $L_W(\rho)$ , representing the maximum prior mass of any loss ball of radius $\rho$ . This separates the geometric constraints of the parameter space and loss function from the statistical distinguishability of the experiment.
Binary Testing Reduction: The success event $A_\rho = \{ \ell(\hat{\theta}(X), W) < \rho \}$ is analyzed under the true joint law $P_{WX}$ versus a product reference law $P_W Q_X$ . By the Neyman–Pearson lemma, the probability of this event under $P_{WX}$ is bounded by the inverse NP function $\beta^\circ(P_{WX}, P_W Q_X)^{-1}(L_W(\rho))$ .
Optimization and Inversion: The bound is optimized over the auxiliary output distribution $Q_X$ . Inverting this bound with respect to the radius $\rho$ yields a lower bound on the minimax quantile for any confidence level $\delta$ .
Relaxations: The exact NP testing bound is relaxed in various ways to generate tractable converses based on different information measures:
- $f$ -informativity: Via binary $f$ -divergence inversion.
- Sibson Information ( $I_\alpha$ ): Via binary Rényi divergence inversion.
- Maximal Leakage: The limit as the Rényi order $\alpha \to \infty$ .
- Amemiya Norms: Via generalized Hölder duality in Orlicz spaces, utilizing Young functions to control likelihood-ratio tails.

Classical lower bounds, such as Fano's inequality and Le Cam's two-point method, are recovered as specific specializations of this single metaconverse framework.

Key Contributions and Results

Unified Framework (Theorems 3.1–3.13): The paper establishes that the Neyman–Pearson function serves as a common primitive for diverse converse bounds. It demonstrates that classical inequalities (Fano, Le Cam) and modern measures (Sibson information, Maximal Leakage, Amemiya norms) are not competing theories but rather different relaxations of the same binary-testing bound, tailored to different regimes.
Exactness of Maximal Leakage (Theorem 4.1): The author proves that for symmetric finite packing problems where the Maximum A Posteriori (MAP) estimator is an equalizer, the Maximal Leakage converse is exact. Specifically, the minimax success probability equals $\exp\{L(W \to X)\} / M$ $exp {L (W \to X)} / M$ , where $M$ $M$ is the size of the packing.
- Application 1 (Stochastic Block Models): This identity is used to derive the first finite-sample, two-sided bounds on the exact-recovery risk for the balanced Gaussian weighted stochastic block model. The bounds explicitly capture the dependence on network size and signal strength, reducing the recovery curve to Gaussian extreme-value probabilities.
- Application 2 (Low-Rank Matrix Estimation): The framework provides the first two-sided finite-sample minimax-quantile bounds for low-rank matrix estimation under isotropic bounded-energy (uniform Frobenius-ball) noise. In this setting, standard KL-based Fano arguments fail because pairwise divergences are infinite; however, Maximal Leakage yields a non-vacuous bound by relating the problem to the volume of a tubular neighborhood (Steiner formula).
Strict Separation of Information Measures (Theorems 4.7–4.9): The paper demonstrates that no single information measure is uniformly optimal.
- Approximate Recovery: In a heterogeneous binary channel model for approximate Hamming recovery, an optimized finite-order Sibson information ( $I_\alpha$ ) yields a strong converse (exponentially vanishing success probability), whereas the Maximal Leakage specialization ( $\alpha \to \infty$ ) yields a trivial bound. This highlights that finite orders better exploit the distribution of probability mass over larger success sets (Hamming balls).
Tail-Adapted Bounds via Amemiya Norms (Theorem 4.11): For one-coordinate Poisson localisation, the paper shows that fixed-power moments (standard $L_\alpha$ norms) and classical Fano bounds are strictly weaker than a bound derived using a Bennett-type Young function through its Amemiya norm. The Amemiya norm captures the non-polynomial tail of the likelihood ratio, recovering the exact success-probability scale of $\frac{\log M}{M \log \log M}$ , whereas Fano only establishes that success vanishes at a much weaker rate.

Significance and Claims
The paper claims that sharp minimax-quantile converses require adapting the information control to two specific factors:

Recovery Resolution: Exact recovery problems (singletons) are best suited to Maximal Leakage, while approximate recovery (neighborhoods) may require finite-order Sibson information.
Likelihood-Ratio Tail: When the likelihood ratio has heavy or non-polynomial tails, standard divergence measures or fixed moments may obscure the correct scale. In such cases, tail-adapted Amemiya norms provide sharper bounds.

The work positions the Neyman–Pearson metaconverse not merely as a tool for deriving new inequalities, but as a unifying lens that clarifies why different information measures are appropriate for different statistical regimes. It provides the first explicit finite-sample bounds for exact recovery in weighted stochastic block models and for minimax quantiles in low-rank matrix denoising with bounded noise, demonstrating the practical utility of this theoretical unification.

Technical Summary: Minimax Quantile Bounds via Information Measures

More like this