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.

Wed 4 NovInformation Theory
The gist
Some mathematical inequalities help describe how certain shapes in space behave. This paper shows that these inequalities are connected to how well one can guess hidden information using noisy signals. By using ideas from Bayesian statistics and information theory, the authors find new ways to prove these inequalities and improve previous results, especially for shapes called log-concave measures. They also relate their findings to some big open problems in mathematics and statistics.
Open → 2611.05831v1

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.

Thu 29 OctMachine Learning
The gist
Machine learning models often have more parameters than data, meaning many equally good solutions exist. The authors study how gradient descent, a common training method, chooses solutions in deep linear diagonal networks. They show that gradient descent tends to pick sparse solutions, meaning solutions with fewer nonzero parameters, especially when starting small. This work extends previous results to the more realistic stochastic gradient descent and explains how step sizes affect these choices.
Open → 2610.39717v1

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.

Mon 19 OctMachine Learning
The gist
Estimating how data changes over time in a diffusion process is important for generating new data samples. The authors analyze how well simple neural networks (with one hidden layer) can learn these changes from limited data. They provide mathematical guarantees on the accuracy and reliability of these networks under certain smoothness and growth conditions of the data. This helps in understanding how many samples and how large a network are needed to generate new data distributions closely matching the original.
Open → 2610.27206v1

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.

Thu 15 OctInformation Theory
The gist
Estimating unknown averages when the data is noisy is tricky, especially when possible values cluster in complex ways. The authors found new mathematical limits on how much information these mixtures contain, depending on how complex their structure is. These limits help understand how hard it is to estimate the average accurately. They also studied which difficult scenarios make estimation hardest, revealing that more complex underlying structures lead to tougher estimation problems.
Open → 2610.21726v1

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.

Fri 25 SeptMachine Learning
The gist
This paper studies how certain random processes called reverse diffusions behave when used to generate data. The authors show these reverse processes shrink a measure of difference between probability distributions at a steady exponential rate when the added noise has a particular mathematical property called strong convexity. They also analyze how discretizing these continuous processes still leads to stable results that locally match the correct data patterns. This helps understand how these methods produce realistic samples and relates closely to ideas in optimization.
Open → 2609.31612v1

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.

Wed 23 SeptData Structures and Algorithms
The gist
Finding the top eigenvalue and eigenvector of large random matrices is important but challenging. This paper shows that using polynomial functions of the matrix, with degree above a certain threshold, can accurately approximate these quantities. The threshold depends on the matrix type and size, and their findings improve on common assumptions about how many steps iterative methods need. They use advanced math tools to precisely describe when and how well these approximations work.
Open → 2609.28781v1

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.

Wed 23 SeptInformation Theory
The gist
This paper studies how the maximum values among correlated Gaussian variables compare to a special, balanced arrangement called a regular simplex. The authors show that the chance that all variables stay below a certain level is always at least as big as for the regular simplex configuration, and the only time they are equal is when the variables have a very specific pattern of negative correlations. This result confirms a conjecture about Gaussian probabilities linked to geometric shapes and helps understand optimal signal designs in noisy communication systems.
Open → 2609.28452v1

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$.

Wed 23 SeptInformation Theory
The gist
This paper studies how a certain measure of randomness, called entropy, behaves when you combine many simple yes/no random events, like coin flips with different probabilities. The authors find the precise range of parameters where the measure stays nicely curved downwards, meaning it's mathematically concave, which is important for understanding and analyzing randomness. They prove that this property holds exactly when a shape-related parameter q is between zero and one, and fails for larger values. Their work settles previous guesses by giving exact answers and explains the math behind why the property holds or fails.
Open → 2609.27433v1

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.

Tue 8 SeptMachine Learning
The gist
This paper studies how quickly a common method called stochastic gradient descent (SGD) can reliably find good solutions when trying to minimize smooth convex functions, even when there is randomness or noise involved. The authors show that the best possible speed for consistent accuracy over time is very close to, but slightly slower than, a certain mathematical rate involving the square root of log n divided by n. They also describe exactly when such a speed can be achieved using specific schedules for running SGD and explain why other schedules cannot do better, even in very simple cases. This result sharpens our fundamental understanding of the limits of how fast SGD can reliably work under noise.
Open → 2609.08537v1

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.

Mon 7 SeptData Structures and Algorithms
The gist
This paper studies a math problem where you try to find a hidden pattern in noisy data using polynomial functions. The authors show that a certain kind of method called approximate message passing (AMP) matches the best possible error achievable by such polynomial methods, even as the polynomial degree grows slowly with data size. They extend previous results by carefully analyzing dependencies in the variables involved, using a new technique based on conditional joint cumulants. This work clarifies exactly how well polynomial algorithms can estimate the hidden signal compared to AMP methods.
Open → 2609.06988v1