Research map / Learning theory and algorithms / Matrix and tensor methods
MAP Estimation with Denoisers: Convergence Rates and Guarantees
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 that a MMSE-averaging denoiser recursion provably converges to the proximal operator of -ln p for log-concave priors at rate Õ(1/k), and uses it inside an inexact proximal gradient method for MAP estimation.
Problem
Plug-and-play and denoiser-based iterative schemes use pretrained denoisers as surrogates for the proximal operator of the negative log-prior, without theoretical justification that they solve the MAP problem.
Approach
An MMSE-averaging recursion (weighted average of denoised current iterate and observation) is rewritten via Tweedie's formula as gradient descent on smoothed proximal objectives F_sigma with decreasing noise; under log-concavity and a third-derivative bound, iterates converge to the exact proximal point at rate Õ(1/k) independent of the smoothness constant of -ln p.
Key results
- Under log-concavity and bounded third derivative of -ln p, MMSE averaging iterates converge to the proximal point at rate (ln k + 7)/(k+1) times problem constants, independent of smoothness L of -ln p.
- For Gaussian priors the iterates satisfy x_k - prox = (y - prox)/(k+1) exactly, versus linear rate (1-mu_F/L_F)^{k/2} for naive GD whose iteration complexity scales with L.
- Approximate proximal gradient descent with inner loop k_n = c n^{1+eta} achieves O(1/n) averaged objective gap for MAP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MMSE Averaging with α_k = 1 /(k+2) and σ_k² = τ/(k+1) | Proximal operator approximation under a log-concave prior with bounded third derivative · Proximal operator convergence | distance to proximal point: ((ln k) + 7)/(k+1) | Helped |
| Use smoothing with the schedule σ_k² = τ/(k+1) instead of direct gradient descent on F | Proximal objective with a Gaussian prior · Gaussian prior | iteration complexity: L · log(1/ε) -> O(1 / ε) | Helped |
| Increase the smoothing noise level σ | Smoothed proximal objective F_σ · Smoothed proximal objective | condition number: 1 + τ / σ² | Helped |
| Set σ = √τ | Smoothed proximal objective F_σ · Smoothed proximal objective | condition number: κ_{√τ} = 2 | Helped |
| Replace the exact score with an approximation having uniformly bounded error ||ξ_k|| ≤ ξ | MMSE Averaging · Approximate-score proximal operator | distance to proximal point: + √(3/2) τ ξ | Hurt |
| Restrict the prior support to an affine subspace of dimension r | MMSE Averaging convergence bound · Affine-subspace-supported prior | dimension in convergence bound: d replaced by r | Helped |
| Use the Cold Diffusion weighting schedule instead of the analyzed schedule | Denoising-based iterative scheme · Cold Diffusion | stability with increasing iterations | Hurt |
| Use an increasing inner-loop count k_n = floor(c · n^(1 + η)) for approximate proximal steps | Approx PGD · MAP estimation | average MAP objective error: O(1/n) | Helped |
Surprising findings
- Naive gradient descent on the unsmoothed proximal objective is slower than the smoothed scheme on ill-conditioned Gaussian priors, since rate depends on L of -ln p.
Limitations
- Requires log-concave, strictly positive prior supported on all of R^d.
- Requires bounded third derivative of -ln p (constant M), and exact score or bounded score error assumption.
- Experiments limited to a toy 2D Gaussian prior; no image experiments reported in the text.
Experimental setup
Metrics: convergence rate distance to proximal point objective gap
Baselines: naive gradient descent on F Plug-and-Play Cold Diffusion PnP-SGD
Builds on: Cold Diffusion Plug-and-Play priors proximal gradient descent Tweedie formula FISTA
Closest papers by meaning
- Unleashing the Denoising Capability of Diffusion Prior for Solving Inverse Problems (NeurIPS 2024 · similarity 0.89)
- Diffusion Priors for Variational Likelihood Estimation and Image Denoising (NeurIPS 2024 · similarity 0.89)
- Exact Posterior Score Estimation for Solving Linear Inverse Problems (NeurIPS 2026 · similarity 0.88)
- Provable Posterior Sampling with Denoising Oracles via Tilted Transport (NeurIPS 2024 · similarity 0.88)
- Divide-and-Conquer Posterior Sampling for Denoising Diffusion priors (NeurIPS 2024 · similarity 0.88)
- Learning Cocoercive Conservative Denoisers via Helmholtz Decomposition for Poisson Imaging Inverse Problems (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.