Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality

• URL: http://arxiv.org/abs/2410.18784v2
• Date: Wed, 30 Oct 2024 02:55:47 GMT
• Title: Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality
• Authors: Zhihan Huang, Yuting Wei, Yuxin Chen,
• Abstract summary: We investigate how the DDPM can achieve sampling speed-ups through automatic exploitation of intrinsic low dimensionality of data. We prove that the iteration complexity of the DDPM scales nearly linearly with $k$, which is optimal when using KL divergence to measure distributional discrepancy.
• Score: 21.10158431913811
• License:
• Abstract: The denoising diffusion probabilistic model (DDPM) has emerged as a mainstream generative model in generative AI. While sharp convergence guarantees have been established for the DDPM, the iteration complexity is, in general, proportional to the ambient data dimension, resulting in overly conservative theory that fails to explain its practical efficiency. This has motivated the recent work Li and Yan (2024a) to investigate how the DDPM can achieve sampling speed-ups through automatic exploitation of intrinsic low dimensionality of data. We strengthen this line of work by demonstrating, in some sense, optimal adaptivity to unknown low dimensionality. For a broad class of data distributions with intrinsic dimension $k$, we prove that the iteration complexity of the DDPM scales nearly linearly with $k$, which is optimal when using KL divergence to measure distributional discrepancy. Notably, our work is closely aligned with the independent concurrent work Potaptchik et al. (2024) -- posted two weeks prior to ours -- in establishing nearly linear-$k$ convergence guarantees for the DDPM.

Related papers

• Breaking Boundaries: Balancing Performance and Robustness in Deep Wireless Traffic Forecasting [11.029214459961114]
  Balancing the trade-off between accuracy and robustness is a long-standing challenge in time series forecasting. We study a wide array of perturbation scenarios and propose novel defense mechanisms against adversarial attacks using real-world telecom data.
  arXiv  Detail & Related papers  (2023-11-16T11:10:38Z)
• Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution [67.9215891673174]
  We propose score entropy as a novel loss that naturally extends score matching to discrete spaces. We test our Score Entropy Discrete Diffusion models on standard language modeling tasks.
  arXiv  Detail & Related papers  (2023-10-25T17:59:12Z)
• Semi-Implicit Denoising Diffusion Models (SIDDMs) [50.30163684539586]
  Existing models such as Denoising Diffusion Probabilistic Models (DDPM) deliver high-quality, diverse samples but are slowed by an inherently high number of iterative steps. We introduce a novel approach that tackles the problem by matching implicit and explicit factors. We demonstrate that our proposed method obtains comparable generative performance to diffusion-based models and vastly superior results to models with a small number of sampling steps.
  arXiv  Detail & Related papers  (2023-06-21T18:49:22Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• The probability flow ODE is provably fast [43.94655061860487]
  We provide the first-time convergence guarantees for the probability flow ODE implementation (together with a corrector step) of score-based generative modeling. Our analysis is carried out in the wake of recent results obtaining such guarantees for the SDE-based implementation.
  arXiv  Detail & Related papers  (2023-05-19T16:33:05Z)
• Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
  We propose a novel approach to the problem of shared parallel computation. By combining two strategies into a unified framework, DPSGD is a better trade computation framework. The potential gains can be achieved by DPSGD on a deep learning (DRL) problem (Latent Diletrichal inference) and on a deep learning (DRL) problem (advantage actor - A2C)
  arXiv  Detail & Related papers  (2022-10-06T13:06:08Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  We propose to solve a regularized distributionally robust learning problem in the decentralized setting. By adding a Kullback-Liebler regularization function to the robust min-max optimization problem, the learning problem can be reduced to a modified robust problem. We show that our proposed algorithm can improve the worst distribution test accuracy by up to $10%$.
  arXiv  Detail & Related papers  (2022-08-29T18:01:42Z)
• Estimating the Optimal Covariance with Imperfect Mean in Diffusion Probabilistic Models [37.18522296366212]
  Diffusion probabilistic models (DPMs) are a class of powerful deep generative models (DGMs) Despite their success, the iterative generation process over the full timesteps is much less efficient than other DGMs such as GANs. We consider diagonal and full covariances to improve the expressive power of DPMs.
  arXiv  Detail & Related papers  (2022-06-15T05:42:48Z)
• Learning to Efficiently Sample from Diffusion Probabilistic Models [49.58748345998702]
  Denoising Diffusion Probabilistic Models (DDPMs) can yield high-fidelity samples and competitive log-likelihoods across a range of domains. We introduce an exact dynamic programming algorithm that finds the optimal discrete time schedules for any pre-trained DDPM.
  arXiv  Detail & Related papers  (2021-06-07T17:15:07Z)
• SUOD: Accelerating Large-Scale Unsupervised Heterogeneous Outlier Detection [63.253850875265115]
  Outlier detection (OD) is a key machine learning (ML) task for identifying abnormal objects from general samples. We propose a modular acceleration system, called SUOD, to address it.
  arXiv  Detail & Related papers  (2020-03-11T00:22:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.