Papers for
statistical signal processors
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Bayesian methods link functional inequalities to estimation limits
Functional inequalities from the fundamental limits of Bayesian estimation
Abstract: We develop a Bayesian information-theoretic framework for proving functional inequalities for log-concave measures. Motivated by Klartag and Ordentlich, we establish a unified equivalence between $Φ$-Sobolev inequalities and Bayesian estimation lower bounds: for a large class of smooth convex $Φ$, a log-concave measure $μ$ satisfies a $Φ$-Sobolev inequality with constant $C>0$ if and only if for $X\simμ$, any $t>0$, and any real-valued measurable $f$, the Bayes risk of estimating $f(X)$ under the $Φ$-Bregman loss from the Gaussian additive observation $Y_t=\sqrt tX+G, G\sim N(0,I_n)$ is at least a $1/(1+Ct)$-fraction of that of the trivial estimator. Combining it with direct information-theoretic arguments, such as testing-to-estimation reductions, we obtain old and new functional inequalities: - For the Poincaré inequality, corresponding to $Φ(x)=(x-1)^2$, we give a simple static information-theoretic proof that the Poincaré constant of an isotropic log-concave measure on $\mathbb{R}^n$ is $O(n^{1/2})$, first proven via stochastic localization in the seminal work of Lee and Vempala. - For the log-Sobolev inequality, corresponding to $Φ(x)=x\log x$, we prove that all smooth $K$-subgaussian log-concave measures $μ$ satisfy $C_{\mathrm{LS}}(μ)\lesssim K^2n^{1/4}$, surpassing the recent state-of-the-art bound of $O(K^2n^{1/2})$ by Bizeul. In parallel and independent work, OpenAI claimed the optimal bound $O(K^2)$ in their October 6, 2026 release of 722 papers. - Finally, we give a Bayesian reformulation of the common structure of the three recent proofs of the Kannan--Lovász--Simonovits conjecture, a dimension-free Poincaré bound for isotropic log-concave measures [BK26; BKL26; SZ26]. Tools from the study of the "low-degree MMSE" in computational complexity of statistical inference motivate and recast key steps and quantities of these proofs.
Gradient descent favors sparse solutions in deep linear networks
Implicit Bias of (Stochastic) Gradient Descent on Deep Linear Diagonal Networks
Abstract: Modern machine learning models are often overparameterized, i.e., have more parameters than training data. This typically implies that the loss function admits multiple minimizers so that training methods (and their hyperparameter choices) have significant influence on the computed solution. We study this so-called implicit bias phenomenon in the context of training deep linear diagonal networks. Previous work has shown that the gradient flow for learning such networks converges to (almost) sparse solutions when initialized small. For an arbitrary number of layers, we extend this analysis to the practically more realistic (stochastic) gradient descent iterations. Our approach identifies (stochastic) gradient descent as a perturbed (stochastic) mirror gradient descent. This allows us to establish convergence and characterize the limiting solution, relating it to weighted $\ell_1$-minimization. Moreover, we provide sufficient conditions on the step sizes and quantify the influence of the step sizes on the implicit bias.
Estimating diffusion process scores with shallow neural networks efficiently
Diffusion Score Estimation with Shallow Neural Networks: Regularity, Approximation, and Finite-Sample Rates
Abstract: We study the sample complexity of estimating Ornstein--Uhlenbeck diffusion scores in $\mathbb R^d$ using denoising score matching (DSM) with finite-width shallow ReLU networks, and its implications for reverse-process sampling. Under weak differentiability and polynomial-growth conditions on normalized derivatives of the initial density, we combine complementary estimates from the Gaussian transition kernel and the initial density to obtain explicit Sobolev bounds that are uniform in time on each fixed ball. Combining these bounds with existing shallow-network approximation theory gives explicit control of the approximation error and a sufficient path-norm budget. We then use truncation and localized Rademacher complexity to establish high-probability risk bounds for path-norm-constrained empirical DSM minimizers with unbounded inputs and labels. Under additional bounded-density and sub-Gaussian assumptions, suitable choices of network width and path-norm budget yield squared $L^2(P_t)$ score risk $\widetilde O(n^{-(d+3)/(2d+3)})$ at each fixed time $t>0$, where $n$ is the number of independent training samples and $P_t$ is the forward marginal. The nonasymptotic bounds retain explicit dependence on diffusion time and the regularity and tail parameters of the initial distribution. Aggregating the score errors over a time grid and applying existing sampling theory together with an early-stopping bound yields a high-probability total-variation error $\widetilde O(n^{-(d+3)/(4d+6)})$ between the generated and original data distributions under suitable sampling parameters. Here $\widetilde O$ suppresses logarithmic factors for fixed dimension, confidence level, and initial distribution.
Bounds on information and complexity in gaussian mixtures improve estimation
Fisher Information and Support Complexity of Gaussian Mixtures
Abstract: We study lower bounds on the Fisher information of Gaussian location mixtures and their applications to estimation problems. First, for a discrete mixing distribution, we derive a universal positive-semidefinite lower bound on the Fisher information matrix in terms of the Rényi entropy of order two. For a mixing distribution supported on $K$ points, this bound scales as $\log(K)/K^2$, improving by a logarithmic factor on the support-size dependence obtained from Stam's inequality. We then develop dimension-aware trace bounds using classical Sobolev inequalities. These bounds are expressed in terms of Sibson's $α$-mutual information and yield the scaling $K^{-2/n}$ in dimension $n$. A complementary bound involving the $α$-mutual information of order $1/2$ is obtained using the sharp Young convolution inequality. The derived inequalities are further specialized to rotationally invariant mixing distributions supported on discrete spherical shells. In this setting, an intrinsic-dimensional bound on Sibson mutual information leads to lower bounds on the Fisher information in terms of the number of occupied shells. As applications, we study least favorable priors for bounded Gaussian mean estimation. In the scalar case, we show that the least favorable prior on $[-R,R]$ has at least $Ω(R\sqrt{\log R})$ support points and that each of its probability masses is of order at most $1/R$. In the vector case, we show that the number of occupied shells grows at least linearly with $R$. Finally, Brown's identity and the I-MMSE relationship are used to translate the Fisher-information inequalities into upper bounds on the MMSE and mutual information.
Reverse diffusions contract divergences and guarantee local stationarity
First-Order Stationarity of Reverse Diffusions
Abstract: Recent literature has shown a strong connection between optimization and sampling. We develop the corresponding first-order theory for diffusion models. First, the SDE-based reverse-time flows of overdamped and underdamped Langevin diffusions contract relative Fisher divergences at explicit exponential rates whenever the stationary potential of the forward process is strongly convex---a condition on the noising process one chooses, not on the data. This is a unique advantage of SDE-based reverse diffusion, absent in the reverse process based on ODEs. Second, we incorporate discretization and establish averaged first-order stationarity bounds---the sampling analog of averaged gradient-norm guarantees in nonconvex optimization---for samplers of both overdamped and underdamped diffusion models. As in nonconvex optimization, the convexity-free certificate is local: it guarantees score consistency, not global mode weights.
Random matrix eigenvalue approximation depends on polynomial degree threshold
Eigenvalue and Eigenvector Approximation for Random Matrices Using Low-Degree Polynomials
Abstract: We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = λvv^\top + X $, we identify $ d_\star = \frac{\log(n)}{2\log(λ)} $ to be the critical degree threshold above which accurate approximation of the top eigenvalue and eigenvector is possible. This sharpens the common belief that spectral methods can be implemented by $ O(\log(n)) $-step power iterations and offers a precise connection between spectral methods and low-degree polynomial algorithms, a popular proxy for all polynomial-time algorithms. For GOE $X$, we identify $ d_\star = n^{1/3+o(1)} $ to be the critical degree threshold for top eigenvector approximation, whereas constant degree suffices for top eigenvalue approximation. Moreover, in the limit where $ d/n^{1/3} $ converges to a positive finite constant, we compute the exact asymptotic eigenvector approximation accuracy in terms of the expected squared overlap. These results significantly improve upon predictions made in randomized numerical linear algebra for deterministic data matrices that the iteration count of power methods is governed by the inverse spectral gap. Technically, our analyses leverage extremal properties of Chebyshev polynomials and draw upon the rich literature of random matrix theory.
Gaussian maxima reach highest likelihood in regular simplex pattern
Stochastic Domination of Gaussian Maxima by the Regular Simplex
Abstract: Let $n\ge2$, and let $X=(X_1,\ldots,X_n)$ be a centered Gaussian vector with $\mathrm{Var}(X_i)=1$ for every $i$. Let $Z_1,\ldots,Z_n$ be independent standard Gaussians, and put $\overline{Z}=(Z_1+\cdots+Z_n)/n$. We prove $\mathbb{P}\{\max_i X_i\le t\}\ge\mathbb{P}\{\sqrt{n/(n-1)}\,\max_i(Z_i-\overline{Z})\le t\}$ for every $t\in\mathbb{R}$, and for each fixed $t>0$ equality holds only when $\mathrm{Cov}(X_i,X_j)=-1/(n-1)$ for all $i\ne j$. The right side is the distribution function of the maximum of the regular simplex vector. Equivalently, among all simplices containing a given centered ball, the regular simplex circumscribed about the ball has the least standard Gaussian measure, as conjectured by Balitskiy, Karasev, and Tsigler. In our preceding paper we proved this comparison after both maxima are smoothed by independent Gaussian noise of variance $1/(n-1)$, which suffices for the Weak Simplex Conjecture; here we remove the smoothing, which is what probabilities at a single threshold require. As an application we consider $n$ equally likely signals of equal energy in Gaussian noise, where the transmitter may also send nothing. At every positive false-alarm level, and for every law of a common nonnegative random amplitude not concentrated at zero, the regular simplex uniquely maximizes the average probability of correct identification whenever the signal dimension is at least $n-1$. A Lean formalization is available at https://github.com/abhmul/full-simplex-conjecture-lean.
Exact threshold found for entropy concavity in Bernoulli sums
The Sharp Rényi and Tsallis Threshold in the Shepp--Olkin Concavity Problem
Abstract: Let $B_1,\ldots,B_n$ be independent Bernoulli random variables with parameters $p_1,\ldots,p_n$, and let $S=\sum_i B_i$. Hillion and Johnson proved that the Shannon entropy of $S$ is jointly concave in the parameter vector and proposed corresponding critical-order conjectures for R'enyi and Tsallis entropies, with predicted thresholds $2$ and approximately $3.65986$, respectively. We determine both thresholds exactly. For every $0<q<1$, the power sum $\sum_k \mathbb P(S=k)^q$ is jointly concave in $(p_1,\ldots,p_n)$, and strictly concave on the open parameter cube. Consequently, the R'enyi and Tsallis entropies of order $q$ are jointly concave. At $q=1$ this agrees with the Shannon theorem. For every $q>1$, joint concavity fails already for the sum of two Bernoulli variables: a transverse interpolation in which the two parameters move in opposite directions gives strict local convexity for both entropies. Hence the universal joint-concavity range for both families is exactly $0<q\leq 1$. Below order one, the proof combines the Hillion--Johnson transport inequality with an explicit nonlinear telescoping correction. The corrected local curvature reduces to a two-dimensional quadratic form. An exact Riccati identity, together with a one-sided zero-crossing argument, proves positivity of its determinant throughout the full range $0<q<1$.
Precise limits on consistent convergence speed for noisy gradient descent
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Abstract: We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-α$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
Sharp link established between message passing and polynomial estimation
Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
Abstract: We prove a sharp lower bound for growing-degree polynomial estimation in the Gaussian planted submatrix model. The observation is $$ \boldsymbol{Y}= \fracλ{\sqrt{n}} \boldsymbolθ \boldsymbolθ^{\top}+\boldsymbol{W}, $$ where the coordinates of $\boldsymbolθ$ are independent $\mathsf{Ber}(ρ)$ variables and $\boldsymbol{W}$ is symmetric with independent standard Gaussian upper-triangular entries. For every fixed $λ>0$ and $ρ\in(0,1)$, we give an explicit finite-dimensional bound implying that every sequence of polynomial estimators of degree $D(n)=o(n^{1/60})$ has normalized mean-square error with limit inferior at least $ρ-q_{\mathsf{amp}}/λ$, the limiting error of Bayes approximate message passing (AMP). This extends the constant-degree result of Montanari and Wein~\cite{montanari2025equivalence} for the Bernoulli prior. Combined with their polynomial approximation of fixed-iteration AMP, the bound identifies the exact limiting low-degree MMSE whenever $D(n)\to\infty$ within this range. It therefore resolves the Bernoulli rank-one case of the growing-degree AMP-equivalence question discussed in~\cite{wein2025computational, maleki2026high}. The proof constructs a low-degree certificate using \emph{conditional} joint cumulants of the signal coordinates and their products. Specifically, we condition on an auxiliary Gaussian channel $\boldsymbol{R}$ calibrated to the AMP fixed point. This retains signal dependence that is lost in unconditional cumulant bounds and produces the cancellations needed for quantitative control as the degree grows. Most of the arguments in this paper were generated using GPT-6 Astra.