CS Paper Radar

Instance-Specific Sharp Convergence Rate of the Add-$λ$ Estimator via Feature Space Decomposition

Zong Shang

cs.IT math.ST ·submitted 2026-11-01 11:57 UTC · v1

Abstract

Using the Feature Space Decomposition framework, we establish non-asymptotic matching upper and lower bounds for the expected Kullback-Leibler estimation error of the Add-$λ$ estimator of a discrete probability distribution, for any signal, any dimension, any sample size, and any $λ>0$.

Closest papers

Nearest neighbours by meaning across the whole index.

A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization

cs.IT math.STmath.PRstat.ML ·2026-10-15 ·Hanuka Eshima, Amedeo Roberto Esposito, Andrea Paudice
similarity 0.54
Abstract

We revisit McDiarmid's inequality, a central tool in statistical learning theory and algorithm analysis. We show that large deviations above the mean are exponentially unlikely for functions of independent random variables that are almost surely bounded above and satisfy a conditional moment assumption of order $p\in(1,2]$. When $p<2$, the result applies even when the function has infinite variance. Our proof relies on a new tensorization inequality for the Kullback--Leibler divergence, termed reverse KL tensorization, which may be of independent interest. Applications include concentration of the sample mean and median-of-means estimator, and one-sided uniform risk bounds for unbounded losses.

0.22

Identication and Estimation of Nonsymmetric Determinantal Point Processes

cs.LG stat.ML ·2026-10-10 ·Christian Gouriéroux, Yang Lu
similarity 0.54
Abstract

Determinantal point processes (DPPs) provide tractable distributions for nite random sets, but the usual symmetric-kernel specication imposes nonpositive pairwise dependence. Statistical research on nonsymmetric DPPs, which can accommodate positive dependence, remains limited. We study identication and estimation for this class. First, we establish the equivalence of two sucient conditions for a nonsymmetric kernel to dene a valid DPP. Second, we develop the identication theory for nonsymmetric DPPs. Third, we develop cardinality-truncated maximum-likelihood estimation and estimation by averaged stochastic gradient descent. Under suitable identication and regularity conditions, we establish consistency and asymptotic normality for both estimators. Simulations examine identication, the eects of truncation, and the nite-sample performance of the estimators. We illustrate the methods with two cyber applications at markedly dierent sampling frequencies: weekly sector-by-breach data and second-by-second enterprise authentication data with more than ve million set observations.

0.37

Sample-Optimal Estimation of the Fréchet Inception Distance

cs.LG cs.CVcs.DSmath.ST+1 ·2026-10-05 ·Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
code/datahot direction similarity 0.52
Abstract · Our code is available at https://github.com/zys996/sample-optimal-fid-estimation

The Fréchet Inception Distance (FID) is widely used to evaluate generative models, but its empirical plug-in estimator suffers from finite-sample bias [BSAG18, CF20]. We study the sample complexity $n$ of estimating FID to error $ε$ between $d$-dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. Our contributions are threefold. (1) We establish tight finite-sample $Θ(\frac{d^2}{n})$ bias and $Θ(\frac{d}{n} + \frac {d^2} {n^2})$ variance bounds for the empirical plug-in estimator, establishing a $\gtrsim d^2$ sample complexity. (2) To debias the empirical plug-in estimator, we generalize the ${\rm FID}_\infty$ estimator of [CF20] to extrapolation methods of arbitrary order $k$. We further prove tight bias and variance bounds of $Θ(\frac{d^{k + 2}}{n^{k + 1}})$ and $Θ(\frac d n + \frac{d^2}{n^2})$ for any order-$k$ extrapolation under our framework. (3) We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm using debiasing techniques inspired by U-statistics. We show that RTD achieves an $O(\frac d {ε^2})$ sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians validate the predicted residual bias and support the tightness of our bounds. On ImageNet with Inception embeddings, RTD achieves the lowest mean estimation error at the standard 50K sample budget, while our second-order variance-aware extrapolation estimator (VALE$_2$) uses only 10K samples to achieve accuracy comparable to FID$_\infty$ at 50K samples.

0.46

How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence

cs.LG stat.ML ·2026-10-05 ·Guni Sharon, Alan Kuhnle
theory similarity 0.51
Abstract

Natural gradient descent (NGD) underlies common methods in ML. For dually flat families, idealized NGD on the forward Kullback--Leibler objective follows the mixture geodesic which is often longer than the shortest Fisher--Rao path. We quantify this overhead by the inefficiency ratio \(R \ge 1\), the Fisher length of the mixture geodesic divided by the Fisher--Rao distance, and bound its supremum over endpoint pairs as a function of the parameter dimension \(d\). A tensor criterion identifies the regime (I) families, with \(R=1\) everywhere: exactly those with quadratic potential or dimension one, such as fixed-covariance Gaussians. For non-quadratic families, we prove two further regimes: (II) bounded third-order skewness plus finite Fisher--Rao diameter yields a dimension-independent bound; and (III) for products of scale families---including Gaussian covariances and Gamma rates---\(R\) grows as \(Θ(\sqrt{\log d})\), unbounded in \(d\). Under a per-step Fisher-chord budget, \(R\) translates to a practical computational cost: NGD requires asymptotically at least \(R\) times as many steps as an optimizer following the Fisher--Rao geodesic. Experiments confirm all three regimes: \(R=1\) to machine precision for quadratic-potential families (I), the categorical bound \(π/(2\sqrt{2})\) is approached but not attained (II), and sampled scale-product \(R\) grows with \(d\), reaching \(R \approx 1.5\) for long, high-dimensional moves (III).

0.18

Sample complexity of weak-signal latent-variable models

cs.IT math.STeess.SP ·2026-10-17 ·Amnon Balanov, Tamir Bendory, Dan Edidin
theory similarity 0.51
Abstract

We study parametric estimation in latent-variable models in the weak-signal regime, where a small signal-strength parameter $β$ controls the dependence of the observations on the unknown parameter. At $β=0$, this dependence disappears, so all parameter values induce the same observed distribution, which we call the null law. We develop a unified framework for analyzing sample complexity in the weak-signal regime by expanding the likelihood ratio around this shared null law in powers of $β$. We prove that if the unknown parameter is first globally identifiable at order $r$ in this expansion, then estimation to fixed accuracy requires at least on the order of $β^{-2r}$ samples. We further identify a likelihood-separation stability condition that is necessary for any estimator to attain this rate and, under mild regularity conditions, sufficient for both maximum likelihood and method-of-moments estimators to attain it. We also study the regime in which the target accuracy vanishes together with the signal strength, and show that global localization and local refinement may be governed by different likelihood orders, leading to distinct statistical scales. Finally, we apply our framework to broad classes of algebraically structured latent-variable models, including additive-noise channels and exponential-family models.

0.25

A Poisson Transition and Bias Law for KSG Mutual-Information Estimation

cs.IT ·2026-10-27 ·Abhiram Gorle, Tsachy Weissman
theory similarity 0.50
Abstract

We quantify the error of the strict-radius Kraskov--Stögbauer--Grassberger (KSG-1) mutual-information estimator on a Gaussian channel as the sample size \(n\) grows and the channel becomes nearly deterministic. For fixed dimension \(p\) and neighbor index \(k\), we define the resolution parameter \(u_n=ne^{-I_n}\), where \(I_n\) is the true mutual information in nats. When \(u_n\to u\in(0,\infty)\), we prove that the estimation error converges in mean square to a computable deterministic bias \(B_{p,k}(u)\). Sampling fluctuations therefore vanish, while an additive bias can persist. We derive this bias from an explicit marked-Poisson law for the neighborhood counts, characterize its small-\(u\) asymptotics, and show that it tends to zero as \(u\to\infty\). The same law describes how often neighborhoods saturate, meaning that they make the largest possible contribution to the estimate. The limiting saturation probability decreases continuously and strictly from one to zero, allowing a Gaussian-model bias correction on fixed critical intervals. Finite-sample experiments show substantial bias even when the true information lies below the estimator's logarithmic ceiling and saturated neighborhoods are rare. Saturation-based correction reduces estimation error in these experiments, though recovering the resolution parameter from the observed saturation fraction can remain difficult when saturation is rare.

0.23

Almost Instance Optimal Sum and Moment Estimation Using Weighted Sampling

cs.DS ·2026-10-06 ·Anup Bhattacharya, Suryendu Mondal, Pinki Pradhan
theoryunusual similarity 0.50
Abstract

We design an almost instance optimal algorithm for the sum estimation problem using weighted sampling. We show that the sample complexity for sum estimation is closely related to the $\ell_2$ norm of the weighted sampling distribution. We show an almost instance optimal lower bound for this problem as well. We also study the moment estimation problem and design an algorithm that has better instance-wise sample complexity bounds.

0.27

Bayes Estimators with Performance Comparable to Empirical Bayes Estimators and Improved Local Robustness

eess.SY stat.ME ·2026-09-06 ·Yue Ju, Ying Wang, Jiabao He, Bo Wahlberg, Håkan Hjalmarsson
similarity 0.50
Abstract

Bayes estimation has been extensively studied and widely used in statistics, decision theory, signal processing, machine learning, and system identification. Among its variants, empirical Bayes (EB) estimation has attracted considerable attention due to its favorable estimation performance and computational tractability. However, the direct plug-in dependence of an EB estimator on hyperparameters can make it locally sensitive to hyper-parameter perturbations. This paper considers the linear regression model and focuses on the EB estimator by employing the marginal maximum likelihood hyper-parameter estimator. For conciseness, this estimator is simply referred to as the EB estimator. Given a family of EB weighting functions, a generalized Bayes estimator is constructed with the same excess mean squared error (XMSE) as the corresponding EB estimator. Here, the XMSE is a second-order asymptotic measure of the mean squared error difference between the estimator of interest and the maximum likelihood estimator. Furthermore, the EB estimator is shown to be at most firstorder sensitive to hyper-parameter perturbations, whereas the constructed Bayes estimator is at most second-order sensitive, making it locally more robust. The computational complexities of these two estimators are also analyzed. In some cases, the constructed Bayes estimator can be computationally comparable to, or more efficient than, the EB estimator. These theoretical results are further supported by numerical simulations.

0.25