Research map / Image generation / Fast diffusion sampling

U-Nets as Belief Propagation: Efficient Classification, Denoising, and Diffusion in Generative Hierarchical Models

ICLR 2025 · Image generation › Fast diffusion sampling · approach: Distributional control of diffusion · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically that U-Nets can implement belief propagation denoising in tree-structured generative hierarchical models, giving polynomial sample complexity for learning the denoiser and related results for ConvNet classification and diffusion.

Problem

Lacking theoretical explanation for U-Net architecture design (encoder-decoder, long skip connections, pooling/up-sampling); how well U-Nets can learn denoisers and diffusion score functions in generative hierarchical models.

Approach

Shows that the upward-downward belief propagation denoising algorithm in tree-structured generative hierarchical models maps directly onto U-Net structure (downward encoder pass, upward decoder pass reusing intermediate messages via skip connections), and approximates its log-sum-exp message updates with ReLU networks, yielding sample complexity bounds via ERM.

Key results

• Theorem: U-Net ERM learns the Bayes denoiser with D2^2 error bound polynomial in d and 1/epsilon; for S=2 and m>=3, sample complexity n = Θ̃(L^2 m d^{2+2log_m 18}/ε^6) ≤ Θ̃(L^2 m d^8/ε^6).
• ConvNet ERM for classification achieves polynomial sample complexity, n = Θ̃(L^2 m d^{2+2log_m 3}/ε^6) for S=2.
• Approximation theorems show BP/message passing with log-sum-exp can be represented by two-hidden-layer ReLU blocks inside the U-Net, with width D = O(S^3 K^2 d 18^L/δ).

Limitations

• Results are for discrete variables in [S]^d; continuous extension left open.
• Convolution and normalization operators differ from practical implementations; the sample complexity exponents are likely loose.
• Analysis does not consider optimization; only approximation and generalization of ERM.

Experimental setup

Builds on: belief propagation stochastic localization DDPM U-Net

Closest papers by meaning

• U-KAN Makes Strong Backbone for Medical Image Segmentation and Generation (AAAI 2025 · similarity 0.89)
• UDT: Reconciling U-Nets and Diffusion Transformers with Data-Adaptive Token Reduction (NeurIPS 2026 · similarity 0.88)
• Neural Residual Diffusion Models for Deep Scalable Vision Generation (NeurIPS 2024 · similarity 0.88)
• Factorized Diffusion Architectures for Unsupervised Image Generation and Segmentation (NeurIPS 2024 · similarity 0.88)
• FreeU: Free Lunch in Diffusion U-Net (CVPR 2024 · similarity 0.88)
• End-to-End Training for Unified Tokenization and Latent Denoising (NeurIPS 2026 · similarity 0.87)