CS Paper Radar

How Many Directions Must a Truncated Diffusion Sampler Retain? Matching Bounds Under Power-Law Spectra

Radmehr Karimian, Ali Mohades, Johannes Lederer

cs.LG math.STstat.ML ·submitted 2026-10-07 14:32 UTC · v1
theory

Abstract

Diffusion samplers can reduce computation by generating selected spectral coordinates and filling the remaining directions with noise. How many directions must they retain? We study this question for data with power-law covariance spectra. For Gaussian data compared to a smoothed target, we prove matching bounds on the required number of retained directions, provided that the ambient dimension is sufficiently large. The truncation error depends on the combined Wiener gains of the omitted directions, regardless of the accuracy of the sampler on the retained coordinates. Keeping only directions whose signal exceeds the output noise level can therefore leave a non-vanishing error: many individually weak directions remain significant in aggregate. Combining this characterization with a diffusion convergence bound yields sufficient sampling-step complexity under exact scores. The upper bounds also extend to estimated principal components and, componentwise, to Gaussian mixtures. The practical prescription is to select the retained subspace using an aggregate spectral-tail error budget, then to choose the diffusion noise level accordingly.

Closest papers

Nearest neighbours by meaning across the whole index.

Inference and Uncertainty Quantification for Streaming $r$-PCA

cs.LG stat.ML ·2026-08-18 ·Haoshu Xu, Hongzhe Li
theory similarity 0.60
Abstract

We address two open questions in streaming PCA via Oja's algorithm: sharp operator-norm convergence for general rank under sub-Gaussian data, and distributional inference for the resulting subspace estimator. Existing convergence analyses, even in the rank-one case, either assume bounded data or leave non-vanishing remainder terms that prevent adaptation to a polynomially vanishing tail spectrum, while existing distributional results are confined to the rank-one case. Our convergence theory removes these remainder terms and yields a sharp rate. In the dense-tail spiked covariance regime, this rate matches the minimax rate up to logarithmic factors. More generally, we prove a matching lower bound, up to logarithmic factors, across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. The analysis yields a linearization of Oja's iterates, which in turn enables a high-dimensional Gaussian approximation for the general-rank subspace estimation error with an explicit limiting covariance. We also establish a row-wise Gaussian approximation over convex sets for the aligned difference, recovering prior rank-one results as special cases. For practical inference, we develop an online multiplier bootstrap algorithm and prove its consistency. Beyond streaming PCA, our techniques contribute to Gaussian approximation and bootstrap inference for nonconvex stochastic approximation.

0.43

Lower Bounds for Parallel Diffusion Sampling

cs.DS cs.AIcs.CCcs.LG+1 ·2026-10-06 ·Yiwen Kou, Yimeng Wang
theoryhot direction similarity 0.58
Abstract

Standard diffusion samplers generate samples through sequential evaluations of a learned score function, with each query depending on previous answers. Parallel samplers seek to accelerate this process by making multiple score queries simultaneously. We ask how many adaptive rounds are necessary when each round allows polynomially many queries. We establish the first polynomial lower bounds on the round complexity of diffusion sampling with approximate scores satisfying a mean-square accuracy guarantee. Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $\mathbb{R}^d$, and (2) a tight $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. Our near-isotropic construction follows the blockwise approach of earlier lower bounds for parallel matroid search and discrete sampling \cite{KUW85,AGR24}. We use independent coordinate blocks containing random codebooks with well-separated rates and construct approximate score oracles whose responses in each block depend on consistency tests in earlier blocks. Together, the rate separation and these tests ensure that each round reveals information about at most one additional block with high probability.

0.50

EigDiff: Eigensample Diffusion - or how to significantly reduce training dataset size with marginal performance variation?

cs.CV cs.AIcs.LG ·2026-10-14 ·Andrei Jarca, Vlad Hondru, Florinel-Alin Croitoru, Radu Tudor Ionescu
similarity 0.57
Abstract

Diffusion models are notoriously expensive to train, requiring large-scale datasets to learn how to gradually reverse the noise from images over multiple small denoising steps. Current approaches focus on distilling the number of diffusion steps, neglecting potential redundancies of the training data. In this paper, we explore the potential of harnessing eigensamples to train diffusion models on significantly smaller datasets, while preserving model performance. To mitigate the sensitivity to affine transformations of eigenimages, we harness the latent space of a pre-trained CLIP model. We next compute latent eigenvectors by performing principal component analysis (PCA) in CLIP space. Further, we employ eigenvectors as reference points to guide the selection of a representative training set comprising comprising both exemplars (images whose embeddings are closest to eigenvectors) and diverse images. Our comprehensive experiments with different diffusion models applied on multiple datasets indicate that our approach (EigDiff) can reduce training data by up to 14x and accelerate subset selection by up to 1607x, with marginal performance differences.

0.19

Classification-oriented adaptive sensing via posterior sampling

eess.SP cs.CV ·2026-09-18 ·Andriy Enttsel, Maxime Rousselot, Vincent Corlay
similarity 0.57
Abstract

Recent advances in diffusion models have enabled high-performance, instance-adaptive compressed sensing through posterior sampling, without task-specific policy training. Existing methods select sensing probes by maximizing total posterior signal variance and are therefore primarily reconstruction-driven. We introduce a classification-driven extension motivated by the closed-form posterior covariance of a class-conditional Gaussian mixture model, which decomposes into within-class and between-class uncertainty. Using calibrated soft classifier outputs, we estimate these uncertainty terms from diffusion posterior samples and propose a classification-oriented criterion for selecting the dominant sensing direction in the unmeasured subspace. Experiments on MNIST and CIFAR-10 compare the resulting classification accuracy, measurement cost, and reconstruction quality with those of reconstruction-oriented counterparts. The results identify regimes in which semantic posterior uncertainty yields a more favorable classification--measurement trade-off and quantify the associated reconstruction cost.

0.47

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

cs.LG stat.ML ·2026-10-08 ·Adam Perbost, Francis Bach, Pierre Marion
hot direction similarity 0.56
Abstract · 49 pages (10 main + appendix), 3 figures

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes achieve a sampling error of $O(\sqrt{dλ_{\max}}\log N/N)$, where $d$ is the dimension, $N$ the number of sampling steps, and $λ_{\max}$ the largest eigenvalue of the target covariance matrix. Unadjusted and underdamped Langevin dynamics suffer from an additional $\sqrtκ$ factor, where $κ$ is the condition number. These rates follow from spectral bounds which are sharp: we confirm them via matching first-order asymptotics as $N\rightarrow\infty$. Our analysis provides a rigorous characterization, in the Gaussian setting, of how time-dependent score trajectories remove condition-number dependence during sampling. By contrast, in the learning phase, we show that estimating the unnoised score by gradient descent leads to essentially the same estimator as estimating a noisy score, which suggests that the benefits of noising do not come from the learning phase.

0.35

Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models

cs.LG stat.ML ·2026-10-09 ·Qiuyun Zhu
similarity 0.56
Abstract · 31 pages

We establish finite-sample guarantees for conditional diffusion models learned from data and implemented with finitely many denoising steps. Our approach aligns the score-training objective with the sampling grid, allowing statistical estimation and numerical discretization errors to be analyzed together. Under a smooth conditional density model, we derive high-probability bounds on the generated distribution's error and quantify the required number of score evaluations. For every smoothness index $β>0$, a suitable grid yields averaged conditional Kullback--Leibler (KL) divergence $\widetilde O_p(n^{-2β/(d_x+d_y+2β)})$ relative to the original target with or without early stopping. Both the full and early-stopped samplers attain average target total-variation (TV) error $\widetilde O_p(n^{-β/(d_x+d_y+2β)})$. Here $n$ is the sample size, $d_x,d_y$ are the data and conditioning dimensions, and errors are averaged over the conditioning variable. The total-variation bound matches the rate established in existing conditional distribution-estimation theory, up to logarithmic factors.

0.32

Error accumulation in reverse diffusion with an imperfect score: beyond path-space analyses

cs.LG cs.DSmath.PR ·2026-11-17 ·George Giapitzakis, Ankur Moitra, Andrej Risteski, Dhruv Rohatgi
similarity 0.56
Abstract

Diffusion modeling is a popular method of sampling from a complex, high-dimensional distribution $p$ using learned approximations of its (noised) score functions. Generating a single sample requires simulating the reverse diffusion process, which requires many queries to the learned scores. Thus, a priori, the learning errors can easily compound. Indeed, in existing theoretical analyses, the sampling error (as measured in total variation distance to $p$) accumulates polynomially with the horizon of the stochastic process. This is a consequence of bounding the error of the output law by the error of the law of the entire reverse diffusion path. In this paper, we demonstrate that by circumventing the "path-space" analysis, the error accumulation of the diffusion sampler can be mitigated when $p$ satisfies a Poincaré inequality. Moreover, we achieve this result as a special case of a broader framework that applies to any distribution $p$, but relaxes the error metric from total variation distance to a weaker metric capturing all sample statistics that do not "witness" the multimodality of $p$. We then zoom out from analyzing the diffusion sampler to the information-theoretic question: given a learned score with some error bound, how accurately can we identify $p$? We show that, for any given bound on the Poincaré constant of $p$, the diffusion sampler already nearly achieves optimal total variation error.

0.18

Diffusion Posterior Sampling with Uncertain Forward Models

cs.CV ·2026-10-21 ·Wentao Shangguan, Vivek K Goyal
similarity 0.55
Abstract

Diffusion posterior samplers reconstruct signals by combining a pretrained diffusion prior with a measurement likelihood specified by a forward model and a noise model. Calibration and reference data can characterize uncertainty in the forward model's parameters, such as blur kernels or detector responses. Fixing these parameters at estimated values leaves their uncertainty out of the likelihood, and parameter errors are thus absorbed into the reconstruction. We introduce an uncertainty-aware likelihood (UAL), a Gaussian approximation to the marginal likelihood obtained by integrating over the uncertain parameters. For each candidate signal, UAL propagates parameter uncertainty into a structured measurement covariance, reducing the quadratic penalty along residual directions that parameter variation can explain. Existing samplers can use UAL in their data updates while retaining their pretrained diffusion priors and sampling schedules. Under a fixed Gaussian nuisance model, we bound likelihood error from linearization and average divergence between the exact marginal and UAL posteriors. We compare samplers with and without UAL across six inverse problems spanning Gaussian and motion deblurring, CT, MRI, ultrasound, and fluorescence microscopy, and find improvements in reconstruction and ensemble prediction. UAL reduces geometric mean MSE by 9% to 20% across samplers in the main Gaussian-deblurring setting and by 51% to 92% in motion deblurring when non-blind samplers use the population-mean kernel. In motion deblurring, DAPS and PnP-DM with UAL also give 6.2 to 6.4 dB higher ensemble-mean PSNR than published BlindDPS and Fast Diffusion EM. On the ablation set, UAL outperforms trace-matched isotropic inflation for PnP-DM in both deblurring tasks; in motion deblurring, it also exceeds the best-tested fixed scalar data weighting by 3.3 dB for PnP-DM and 4.2 dB for DAPS in average PSNR.

0.10