Minimax Quantile Bounds via Information Measures
Amedeo Roberto Esposito
cs.IT, math.ST
2026-08-21
Neyman-Pearson metaconverse unifies quantile bounds via f-informativity, I_α, Maximal Leakage and Amemiya norms. SBM strong-converse at SNR=1; Hamming Leakage exponent 0 vs 0.0439.
Expected risk hides the tail. Two estimators can share a mean loss and still differ sharply in the chance of a large error. Minimax quantiles, introduced systematically by Ma, Verchand and Samworth, ask a confidence question: given a failure budget δ, how small can the error radius stay in the worst case.
Quantile forms of Fano and Le Cam already exist. They do not say which information measure to use once the success event changes. Exact identification, Hamming-neighbourhood recovery, and continuous low-rank estimation induce very different small-ball volumes. Likelihood ratios can be bounded, polynomial-tailed, or Poisson-like. The wrong converse is either vacuous or off by a factor of M. This paper treats those converses as relaxations of one binary test, then shows the matching choice on four models.
Success is the event that loss is below a radius ρ. Draw an auxiliary prior on the parameter, generate the observation, and compare the true joint law with a product reference PW QX. Under every product law the success event has probability at most LW(ρ), the largest prior mass of a loss ball. The Neyman-Pearson lemma turns that geometric cap into an upper bound on true success probability. Optimising the auxiliary output law QX yields Theorem 3.1; inverting in ρ gives a quantile lower bound at every confidence level.
Geometry and distinguishability separate. LW(ρ) depends only on the prior and the loss. The testing function depends only on how well observations split the joint from the product.
Relaxations of the same bound recover the usual toolkit:
Fano and Le Cam sit inside this diagram. They are not competing master theorems.
On a symmetric finite packing, if the uniform-prior MAP rule is an equaliser, minimax exact-recovery success equals exp{L(W→X)}/M. Maximal Leakage, the Neyman-Pearson envelope, and the true risk coincide.
For the balanced two-community Gaussian weighted stochastic block model, edge weights are Gaussian with a higher mean inside communities. The SNR is n(μ1−μ2)²/(8τ² log n), with the known first-order exact-recovery threshold at SNR=1. Theorem 4.2 sandwiches the finite-sample minimax risk between two Gaussian extreme-value probabilities. Corollary 4.3 is a strong converse: if SNRn→γ≠1, then Rn→1 for γ<1 and Rn→0 for γ>1.
Low-rank denoising under isotropic uniform Frobenius-ball noise makes every pairwise KL and Rényi divergence infinite, because translated noise balls are never nested. Packing-Fano is vacuous. Maximal Leakage reduces to the Steiner volume of a parallel body; the R^k leading terms cancel against the small-ball, and the bound stays finite. Up to universal constants the finite-sample quantile rate is σ² min{(sr + log(1/δ))/D, 1}, with sr=r(d1+d2−r) the dimension of the rank-r model and D=d1 d2. The dimension scaling is classical. The novelty is the noise model and the explicit δ dependence.
Approximate Hamming recovery needs a different order. In a heterogeneous binary channel the success set is a Hamming ball. Example 4.9 takes ν=½δ{0.05}+½δ{0.25} and ρ=0.05. Maximal Leakage's exponent is 0. An optimised finite Sibson order gives J≃0.0439 against a true exponent Iν≃0.0539. Success then decays as exp{−(0.0439+o(1))d}; the Leakage specialisation is the trivial bound 1.
For one-coordinate Poisson localisation, one tagged arrival is added to an unknown stream among M Poisson(λ) streams. A Bennett-type Young function through its Amemiya norm recovers the exact success scale log M/(M log log M). Classical Fano only shows that success vanishes, at scale 1/log M, a factor of order M log log M/(log M)² too large. Fixed powers give M^{-1+1/p}. An untailored exponential Young function gives (log M)/M. Both miss the 1/log log M.
| Setting | Measure | What it buys |
| Symmetric exact recovery | Maximal Leakage | Identity with NP and minimax risk |
| Low-rank ball noise | Maximal Leakage | Fano empty; rate σ² min{(sr+log(1/δ))/D,1} |
| Approximate Hamming | Finite Iα | Exponent 0.0439 vs Leakage's 0 |
| Poisson localisation | Bennett-Amemiya | log M/(M log log M) vs Fano's 1/log M |
Fano and Le Cam are the default lower-bound tools. The paper gives a selection rule: match the information control to the volume of the success event and to the likelihood-ratio tail. Exact identification cares about ess-sup densities. Neighbourhood recovery can use a finite Sibson order to trade ball volume against moments. Non-polynomial tails need a Young function, not a fixed power. The SBM and low-rank examples produce computable finite-sample quantile bounds, not only first-order thresholds.
This is a converse toolbox. There is no new estimator and no simulation. Practitioners training models will not get a recipe. People who write statistical lower bounds, community-detection thresholds, or high-probability matrix rates get a reason to pick the measure rather than a habit.
The authors leave three openings: when the Neyman-Pearson metaconverse is attained, how to choose the Sibson order or Young function systematically, and how to extend the argument to interactive, sequential, or constrained rules. Exactness of Maximal Leakage needs the equaliser symmetry; it is not claimed for every recovery problem. The low-rank noise is uniform on a Frobenius ball, not i.i.d. Gaussian entries. The Hamming separation is a two-point mixture, not a network that arises in applications. In the Poisson example Amemiya does not beat Maximal Leakage in the abstract: Leakage is also exact, and the Young function is a way to evaluate the envelope at the right scale.