Nearly d-linear convergence bounds for diffusion models via stochastic localization
Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming L 2 -accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or requ...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
OpenReview
2024
|
| _version_ | 1826312706162950144 |
|---|---|
| author | Benton, J Bortoli, VD Doucet, A Deligiannidis, G |
| author_facet | Benton, J Bortoli, VD Doucet, A Deligiannidis, G |
| author_sort | Benton, J |
| collection | OXFORD |
| description | Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming L 2 -accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or required strong smoothness assumptions. We provide the first convergence bounds which are linear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most O˜( d log2 (1/δ) ε 2 ) steps to approximate an arbitrary distribution on R d corrupted with Gaussian noise of variance δ to within ε 2 in KL divergence. Our proof extends the Girsanov-based methods of previous works. We introduce a refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization. |
| first_indexed | 2024-03-07T08:23:50Z |
| format | Conference item |
| id | oxford-uuid:dfd10a57-1bc3-47b7-9532-bf3fde0c620e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-04-09T03:59:13Z |
| publishDate | 2024 |
| publisher | OpenReview |
| record_format | dspace |
| spelling | oxford-uuid:dfd10a57-1bc3-47b7-9532-bf3fde0c620e2024-04-08T11:11:04ZNearly d-linear convergence bounds for diffusion models via stochastic localizationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:dfd10a57-1bc3-47b7-9532-bf3fde0c620eEnglishSymplectic ElementsOpenReview2024Benton, JBortoli, VDDoucet, ADeligiannidis, GDenoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming L 2 -accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or required strong smoothness assumptions. We provide the first convergence bounds which are linear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most O˜( d log2 (1/δ) ε 2 ) steps to approximate an arbitrary distribution on R d corrupted with Gaussian noise of variance δ to within ε 2 in KL divergence. Our proof extends the Girsanov-based methods of previous works. We introduce a refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization. |
| spellingShingle | Benton, J Bortoli, VD Doucet, A Deligiannidis, G Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title | Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title_full | Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title_fullStr | Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title_full_unstemmed | Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title_short | Nearly d-linear convergence bounds for diffusion models via stochastic localization |
| title_sort | nearly d linear convergence bounds for diffusion models via stochastic localization |
| work_keys_str_mv | AT bentonj nearlydlinearconvergenceboundsfordiffusionmodelsviastochasticlocalization AT bortolivd nearlydlinearconvergenceboundsfordiffusionmodelsviastochasticlocalization AT douceta nearlydlinearconvergenceboundsfordiffusionmodelsviastochasticlocalization AT deligiannidisg nearlydlinearconvergenceboundsfordiffusionmodelsviastochasticlocalization |