← Back to all news
arXiv Machine Learning

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

The paper investigates the sample complexity of noisy one‑bit compressed sensing for signals drawn from a prior distribution. By linking the prior’s effective distributional complexity to its approximate covering number, the authors prove that posterior sampling can recover signals accurately when the number of measurements scales with the logarithm of this covering number, modulo a one‑bit separation gap. They also show that the method remains reliable under learned prior mismatch measured in Wasserstein distance, provide a matching lower bound, and demonstrate practical performance using a diffusion‑based plug‑and‑play algorithm on FFHQ and ImageNet.

Related stories

arXiv Machine Learning
Sep 3

Full-Model Optimality for Tunable Linear Generative Priors in Compressed Sensing

The paper investigates compressed sensing using a family of tunable linear generative priors linked through their singular value decompositions. It proves that in noiseless Gaussian compressed sensing, the full-dimensional linear prior yields the lowest expected reconstruction error across the entire family, meaning lower-complexity priors do not improve performance in this idealized setting. This contrasts with denoising, where lower complexity priors can reduce error due to bias‑variance tradeoffs, suggesting that the experimental gains seen with neural network priors stem from their nonlinearities.

By Zhaoming Li, Paul Hand
safety
More like this →
arXiv Machine Learning
Sep 14

Tunable Latent Generative Priors for Compressed Sensing and Inverse Problems

The paper introduces tunable latent priors for diffusion models, normalizing flows, and variational autoencoders using nested dropout. These priors allow the latent dimensionality to adapt to each inverse problem, reducing reconstruction errors compared to fixed-complexity models across tasks such as compressed sensing, inpainting, denoising, and phase retrieval. In linear denoising, the authors derive the optimal latent complexity in closed form, linking it to noise level and signal spectrum.

By Sean Gunn, Jorio Cocola, Oliver De Candido, Vaggos Chatziafratis, Paul Hand
diffusion
More like this →
arXiv Machine Learning
Sep 21

Sparse Priors for Efficient Distribution Learning

arXiv:2609. 20883v1 Announce Type: new 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/\Theta(d)})$, though shown to be minimax optimal.

By Saumya Goyal, Barnab\'as P\'oczos
efficiency
More like this →
arXiv Machine Learning
Oct 8

Lower Bounds for Parallel Diffusion Sampling

The paper establishes the first polynomial lower bounds on the number of parallel rounds required for diffusion sampling with approximate scores. It proves a “~Ω(d^{1/3})” lower bound for sampling smooth, near‑isotropic Gaussian mixtures in ℝ^d, and an Ω(d) lower bound for uniform sampling from anisotropic axis‑aligned boxes inside the unit ball. These bounds apply to any randomized algorithm that can make polynomially many queries per round at arbitrary locations and noise levels, while maintaining inverse‑polynomial score error and constant total variation accuracy.

By Yiwen Kou, Yimeng Wang
diffusion
More like this →