CS Paper Radar

Minimax Estimation of Discrete Distributions under Hockey-stick Divergence

Manaka Ueno, Geoffrey Wolfer

cs.LG stat.MLmath.ST ·submitted 2026-11-15 01:19 UTC · v1
theory

Abstract

We initiate the study of estimating a discrete distribution with respect to the hockey-stick divergence from independent samples. We provide non-asymptotic upper and lower bounds on the minimax expected loss in terms of the alphabet size, the number of samples, and the divergence parameter. The upper bounds are achieved by add-constant estimators, while the lower bound is derived via a Bayes risk argument. Both upper bounds and lower bounds reveal a transition between polynomial and exponential regimes as the parameters of the problem vary.

Closest papers

Nearest neighbours by meaning across the whole index.

On Minimum Divergence for Distribution Reconstruction

cs.IT math.ST ·2026-10-15 ·Justin Bec, Thomas Le Corre, Aurélien Garivier
similarity 0.58
Abstract

We study the possibility of generalizing maximum-entropy reconstruction, which approximately recovers a probability distribution from finitely many (generalized) moments by minimizing the Kullback--Leibler (KL) divergence to a reference measure. The reconstruction lies in an exponential family and is also the best KL approximation of the unknown distribution within that family: moment matching and information projection coincide. Replacing KL by a smooth f-divergence, the reconstruction still exists in an associated family, but the best approximation property does not. Specifically, a family is called entropy-adapted if the projection of any distribution matches its moments. We show that, up to equivalence, KL is the only $C^2$ f-divergence that is entropy-adapted, whatever the choice of the generalized moments. We illustrate the consequences of this failure numerically.

0.22

Phase Transitions in Heavy-Tailed Mean Estimation under $\ell_p$ Norms

cs.LG math.ST ·2026-11-15 ·Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Mikael Møller Høgsgaard, Kasper Green Larsen, Nikita Zhivotovskiy
top venuebenchmarktheory similarity 0.58
Abstract · Accepted at NeurIPS 2026

We study the problem of estimating the mean of a random vector in $\mathbb R^d$ under $\ell_p$ norms, assuming only the existence of a covariance matrix. In the Euclidean norm, the sample mean is already optimal in expectation, and robust estimators are usually needed only to obtain high-probability tails. Our results show that this picture changes for $\ell_p$ norms with $p>2$: robustification is already necessary even for the expected risk. We prove that the minimax risk exhibits a sharp phase transition, controlled by the interaction between the sample size $n$, the dimension $d$, and the norm parameter $p$. In the large-sample regime, the classical Gaussian rate remains achievable. In the complementary regime, heavy-tailed distributions create a genuinely non-Gaussian obstruction. Furthermore we show that the simple estimator: coordinate-wise median of means whose number of buckets chosen according to the geometry of the loss, optimally tracks this phase transition in its expected risk minimax. We also show that natural projection-based median-of-means estimators for general norms, despite achieving the optimal confidence trade-off relative to the sample-mean benchmark of Lugosi and Mendelson (Probab. Theory Relat. Fields, 2019), can be polynomially suboptimal for $\ell_p$ norms even in the constant-probability regime.

0.38

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

cs.LG stat.ML ·2026-10-06 ·Dongsun Yoon, Saptarshi Chakraborty
similarity 0.56
Abstract

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size $s_n(P_0)$, a sample-size-dependent measure of distributional complexity. Given $n$ independent and identically distributed (i.i.d.) samples from an unknown data distribution $P_0$ on $[K]^d$, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as $O(\sqrt{s_n(P_0)/n})$, while the expected Kullback--Leibler (KL) divergence is bounded by $O(\frac{1}{n}s_n(P_0)\log(eK^d/s_n(P_0))\log n)$. Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of $\log n$. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through $s_n(P_0)$, while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

0.28

Robustness of Diffusion Models under Distribution Shift

cs.LG math.STmath.PRstat.ML ·2026-09-23 ·Wei Luo, Neil K. Chada, Shijie Zhang, Lu Yu
similarity 0.55
Abstract · 13 pages, 2 figures

Score-based diffusion models are increasingly considered in settings where the underlying data distribution may differ from the training distribution, yet existing theoretical guarantees largely focus on the no-shift setting. In this work, we study robust score estimation under Wasserstein perturbations of a reference distribution. For the Ornstein--Uhlenbeck diffusion, we show that robust estimation decomposes into two fundamental components: the statistical cost of learning the reference distribution and the intrinsic cost of distribution shift. The latter scales quadratically with the Wasserstein radius, and this dependence is minimax optimal. We construct an explicit finite-sample estimator achieving the resulting robust minimax rate without knowing the shift radius. When the reference distribution lies on an unknown low-dimensional subspace, the statistical term adapts to the intrinsic dimension while the shift cost remains unchanged. Finally, we show that the same decomposition governs positive-time reverse sampling and obtain matching minimax guarantees in KL divergence. Together, these results characterize how finite data, intrinsic dimension, and distribution shift affect the robustness of score-based diffusion models.

0.22

Birthday Estimators Are Uniformly Optimal for Renyi Entropy

cs.IT cs.DSmath.PRmath.ST ·2026-10-20 ·Maciej Skórski
theory similarity 0.55
Abstract

Collisions are a basic probe of unknown distributions, used for testing and for counting substructures in graphs, and they underlie Rényi entropy, a fundamental measure of uncertainty with applications in cryptography, machine learning, physics, and biology. Motivated by this, we study the natural birthday estimator. We prove Bernstein-type concentration for it and show that it is minimax optimal, uniformly and jointly in alphabet size, order, accuracy, and confidence, with no sample splitting, clipping, or median aggregation. This, in particular, settles the sample complexity of integer-order Rényi entropy estimation up to absolute constants in all regimes, closing the gap between the best known upper and lower bounds. Our concentration bound rests on a sensitivity analysis of collision count, and the matching lower bound on a sharp analysis of detecting a hidden spike in a plateau distribution.

0.49

Sparse Priors for Efficient Distribution Learning

cs.LG math.ST ·2026-09-16 ·Saumya Goyal, Barnabás Póczos
theory similarity 0.55
Abstract

Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in $d$ dimensions from $n$ samples degrade as $O(n^{-1/Θ(d)})$, though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications. Consequently, we introduce the class of sparse priors and define the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions. We show that distribution learning under a $k$-sparse prior achieves a Bayesian risk lower bound of $Ω(\sqrt{k/n})$ under common distance metrics, and show a matching (up to logarithmic terms asymptotically in $n,k$) upper bound for the TV distance under mild additional assumptions. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well. While $k$ can still depend on the dimension $d$, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on $n$.

0.33

Minimax Rates for Conditional Generative Learning under Wasserstein Loss

cs.LG math.STstat.ML ·2026-10-26 ·Sungwon Park, Kyoung-Sook Moon, Hongjoong Kim
theory similarity 0.55
Abstract

We study minimax rates for conditional generative learning under integrated Wasserstein loss, with Hölder continuous conditional laws and an unrestricted covariate distribution. We evaluate unrestricted generators through their conditional output distributions. For expected Wasserstein loss, the minimax rate agrees with the rate under uniform covariates and follows from balancing localization bias against unconditional distribution estimation error. Higher moments of the loss can instead be dominated by unobserved covariate regions, which force an additional risk contribution of order $n^{-1}$, where $n$ is the sample size. An adaptive localization argument gives matching upper bounds. The results cover unrestricted response laws and possibly vanishing Besov densities for $W_1$, and extend to higher Wasserstein orders under uniform response density bounds and integrability conditions. A multiscale lower bound closes the logarithmic gap in unconditional $W_1$ minimax rates in dimension two for both unrestricted distributions and Besov density classes. We also establish minimax rates for conditional Brenier maps under density, integrability, and uniform curvature conditions.

0.12

Minimax bounds for watermarked and masked recursive discrete distribution estimation

cs.IT cs.LGmath.ST ·2026-08-31 ·Millen Kanabar, Michael Gastpar
theory similarity 0.54
Abstract · Shorter version to be published at the IEEE Information Theory Workshop 2026

Watermarking has been proposed as a way to identify synthetic samples in estimation settings where no metadata is available to distinguish them from real samples, but its precise effects remain unexplored. In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples. In this work, we study the minimax loss of such recursive discrete distribution estimation in the presence of watermarks in contrast to the unassisted and oracle-assisted losses. When the fraction of real samples vanishes asymptotically, we provide a lower bound that shows that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes. Additionally, we show that in most regimes, the worst-case losses of a sequence of simple deterministic estimators match the corresponding lower bounds up to constants. Finally, we propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap. We conjecture that a tighter lower bound argument can close this gap.

0.32