Efficient Denoising Diffusion via Probabilistic Masking

Thanks for your constructive comments.

Q1: As far as I know, there is typically a trade-off between sampling speed and sample quality. Having fewer sampling steps usually improves the sampling speed but often results in a decline in the quality of generated samples. This observation has been discussed in numerous studies focused on accelerating diffusion sampling. Why does Figure 1 indicate an enhancement in sample quality when the number of sampling steps is very low? Is this a consequence of randomness or an mean outcome? Is there a qualitative explanation?

A1: It is a misunderstanding. The x-axis in Figure 1 means the index of the removed step (e.g., 1-st step, 2-nd step), instead of the number of removed steps. We give this result to highlight redundant sampling steps in the denoising process. Removing these steps has a negligible effect on the quality of the samples or may even improve the sample quality.

Q2: If I didn't miss it, the article doesn't employ the L0 norm. If that's the case, I recommend not introducing L0 in the notation section. Additionally, in Equation 6 and subsequent formulas, if you are using the L2 norm, I suggest explicitly writing it as $||\cdot||_2$ not $||\cdot||$.

A2: Thanks. We have improved the writing accordingly in the revision.

Q3: Under section 3, "In this section, for the convenience of presenting our method DDPM......", I think it should be EDDPM.

A3: Thanks. We have corrected it in the revision.

Q4: Regarding the mask variable, m_t, I understand it to be the t-th entry of the vector m. Following tradition, a single random variable should not be represented in bold form, and it is recommended to write as m_t.

A4: Thanks. We have modified these notations in the revision.

Q5: Under Eq.(9), $\tilde{\mathbf{u}}(\mathbf{x}_t, \mathbf{x}_0),\tilde{\beta}_t$ should be written as $\tilde{\mathbf{u}}_t(\mathbf{x}_t, \mathbf{x}_0,\mathbf{m})$, $\tilde{\beta}_t(\mathbf{m})$, because they depend on $\mathbf{m}$.

A5: Thanks. We have corrected these typos in the revision.

Q6: Under Eq.(9), in the definition of $\tilde{\beta}_t$, it has an extra “t" in the lower right corner.

A6: Thanks. We have corrected it in the revision.

Q7: Due to the L1 constraint on $\mathbf{s}$, most entries in will be pushed to 0. But why are the other entries pushed towards 1? Are there situations where some are around 0.5? In such cases, how should step $t$ be handled? Is there any explanation?

A7: Actually, our constraint on $\mathbf{s}$ enforces most of $s_i$ converge to either 0 or 1. The detailed explainations are given in A3 of Reviewer MPYQ . In Figure 3 of the revision, we present more results on the histogram of the values of $s_i$ on CIFAR-10. In all our experiments, we observed that few elements of $s_i$ do not converge to 0 and 1, which can hardly been seen in the histogram. The elements are always close to 0 or 1, introducing negligible randomness in our final sampled denoising steps, i.e., when fully trained our denoising trajectory is almost deterministic.

Q8: Under Eqn.(11), it should be $\nabla_{\mathbf{\theta}} \Phi(\theta, \mathbf{s})$ and $\nabla_{\mathbf{s}} \Phi(\theta, \mathbf{s})$.

A8: Thanks. We have corrected it in the revision.

Q9: Eqn.(12) is confusing because $\gamma_e$ is not used in the algorithm. Is this a typo? Is it the case that $K=\gamma_e$ * T, and $\gamma_e$ is expressed as in equation 12?

A9: A more detailed expression of $\gamma_e$ is given in Eqn.(12) in the revision. $\gamma_e$ is used to define the constraint region in the current epoch $e$ and we use the projected gradient descent to update $\mathbf{s}$ and gradient descent to train $\theta$. That is,

$\theta = \theta - \eta \nabla_{\theta}\Phi (\theta, \mathbf{s}) \mbox{ and } \mathbf{s} = proj_{\mathcal{S}}\left(\mathbf{s} - \eta \nabla_{\mathbf{s}} \Phi (\theta, \mathbf{s})\right),$

where $\mathcal{S} = \\{ \mathbf{s}\in \mathbb{R}^T: ||\mathbf{s}||_1\leq K_e, \mathbf{s}\in [0,1]^T \\}$ with $K_e = \gamma_e T.$

$proj_{\mathcal{S}}(\cdot)$ is the projection on $\mathcal{S}$. The projection can be efficiently computed with the details added in Theorem 1 in the appendix of the revision. How the constraint induces sparsity on $\mathbf{s}$ is explained in A3 of Reviewer MPYQ.

Q10: In the context of image synthesis, the baseline comparison is limited. There are many acceleration sampling algorithms proposed for image synthesis, such as DPM-solver (Lu et al., 2022). While these works are mentioned in the related work section, they are not compared in the experiments.

A10: Due to the space limitation, we add 4 latest sampling acceleration methods in Table 1 for comparison. Our EDDPM has more significant superiority when using fewer denoising steps, especially achieves 4.89 FID with 5 steps.

Thanks for the authors' feedback. Most of my concerns are addressed, and I decide to increase the score to 6.

Thanks for your constructive comments.

Q1: There are some typos and citation errors to be fixed. For example: two periods appear at the end of the first paragraph, [Bao et al., 2022a] and [Bao et al., 2022b] are duplicates, etc.

A1: Thanks for your detailed review. We have revised them in the new version.

Q2: Is the sparse masking result (like Fig. 2 (b)) pervasive across different datasets?

A2: Yes, the constraint on $\mathbf{s}$ enforces most of the mask scores converge to either 0 or 1. The reasons are discussed in A3 of Reviewer MPYQ. We also presented the results on CIFAR-10 dataset in the appendix. In all our experiments, we observed that few elements of $s_i$ do not converge to 0 and 1, which can hardly been seen in the histogram. The elements are always close to 0 or 1, introducing negligible randomness in our final sampled denoising steps, i.e, when fully trained our denoising trajectory is almost deterministic.

Q3: I am wondering how you deal with the l-1 norm constraint on s during training. Is it through projection? Is the training stable with the stochastic gradient estimator in Eq. (11)?

A3: Yes, we adopt projected gradient descent to update $\mathbf{s}$ in each iteration. We would like to point out that the projection can be computed efficiently, whose details are given in Theorem 1 in the appendix of the revision. The training is stable since the dimension of $\mathbf{s}$ is relatively low compared with the model weights $\theta$.

Q4: Do you have plans to release the code for open access?

A4: Yes, we will release the code soon.

Thanks for your constructive comments.

Q1: The policy-gradient-based update for the prob masking is more like reinforcement learning, rather than the Bayesian variational inference. As the classical VI-based update is also feasible for inferring the Bern distribution, more discussion is encouraged on why adopting the policy-gradient-based update.

A1: Our considerations in choosing the gradient estimators are as follows.

(1) Bayesian method could not be a perfect choice for our training problem. The reason is that its performance is sensitive to the selection of priors. In the case of the Bernoulli distribution, the Beta distribution serves as the conjugate prior, displaying significant variation for different parameters, $\alpha$ and $\beta$. In the early stage, an inappropriate prior could make the model difficult to converge.

(2) In contrast, for policy gradient, we design a schedule that gradually increase the masking ratio and we can update the model by projected gradient descent efficiently.

Thanks for your suggestion and we will conduct an in-depth exploration on the combination of Bayesian methods and our framework in the future.

Q2: For the constrain K of the total step, can the "Gradually Increasing Masking Rate" trick guarantee theoretically that the final learned step is constrained by $K$? My understanding is it controls the prob $p$ of the Bern distribution and the final steps are based on the random samples. Also, it's not very clear to me why the learned $s$ is doomed to be almost 0 or 1 . The L1 constraint can do it for sure. However, it seems the training procedure doesn't include the L1 constraint explicitly, but uses the "Gradually Increasing Masking Rate" trick. Clarification on these points is encouraged.

A2: As most elements in $\mathbf{s}$ converge to either 0 or 1, the length of the final learned denoising procedure is well constrained by K. The explanation of how the constraint induces sparsity on $\mathbf{s}$ is provided in A3 of Reviewer MPYQ.

We impose the constrains on the training process as follows. For each epoch, we define the following constraint region $\mathcal{S} = \\{ \mathbf{s}\in \mathbb{R}^T: ||\mathbf{s}||_1\leq K_e, \mathbf{s}\in [0,1]^T \\},$ where $K_e = \gamma_e T$ with $\gamma_e$ defined in Eqn.(12). This allows us to control the sparsity of the mask $\mathbf{m}$ by managing the sum of the probabilities $s_i$. In each iteration, we adopt the projected gradient descent to update $\mathbf{s}$ based on the constraint region above. The details are given in Eqn.(13) in the revision. As demonstrated by Theorem 1 in the appendix of the revision, this projection can be computed efficiently. As training progresses, $K_e$ gradually decreases to the targeted $K= \gamma_f T$, leading to a reduction in the number of sampling steps involved.

Q3: There are some typos and missing things that should be fixed. The equation 12, what's the meaning of $e_1$?

A3: We have provided more detailed expression for $\gamma_e$ in Eqn.(12). $e_1$ is a positive integer indicating that we train the entire denoising steps in the first $e_1$ epochs.

Thanks for your constructive comments.

Q1: The motivation part of this paper is not persuasive. The authors said that prior works often involve manual selection or the use of handcrafted rules, such as uniform skipping, to determine denoising steps. It is not entirely true for all efficient sampling methods. The authors are referred to check this survey [r1]. The authors may need to narrow down the scope of comparison.

A1: When referring to learning-free efficient sampling methods, it is common for them to rely on handcrafted rules. We appreciate your reminder. In our revision, we have adhered to the survey [r1], which categorizes existing studies into learning-free and learning-based methods. Specifically, we have focused on reviewing the most relevant approaches, particularly the learning-based ones, in the related work section.

It is worth noting that learning-free methods often employ handcrafted rules, whereas learning-based methods decouple the training and inference schedules. This decoupling allows for separate learning of the training and sampling schedules. However, both approaches have the potential to result in suboptimal performance.

Q2: The literature review part of “Acceleration of DPMs” is not well-written. The authors fail to position their work in the literature and summarize the issues of prior work because their chosen scope is too wide.

A2: We appreciate your valuable suggestion. Given the extensive range of efficient sampling studies available, it is challenging to review all of them in the related work section. To ensure a comprehensive overview, we adhere to the survey [r1], which categorizes existing studies into learning-free and learning-based methods. In the revised version, we position our work within the realm of learning-based efficient sampling methods and focus on reviewing the most relevant studies in the related work section.

Q3: Why is it true? “Due to the constraints on $\mathbf{s}$, i.e., $\|\mathbf{s}\|_1 \leq K$ and $\mathbf{s}\in [0,1]^T$, the optimal would be sparse and most of its components would be either 0 or 1.”

A3: It is true and we would like to explain this property in the following three aspects:

1. Prof. Robert Tibshirani, the author of the well-known sparse learning method lasso, provides an explanation of this property from a geometric perspective in pages 10-12 (Fig.2.2) of his book titled Statistical Learning with Sparsity: The Lasso and Generalizations. To be precise, the optimization problem of lasso is equivalent to the following one with some $t$: $\min_{\mathbf{\beta}}|| \mathbf{y}- \mathbf{X}\mathbf{\beta}||^2, \mbox{ s.t. } \sum_{i=1}^p |\beta_i| \leq t.$ Note that the constraint region above is a diamond ($p=2$) or a rhomboid ($p>2$). The optimal solution is the point, where the elliptical contours of the loss hit this constraint region. When the dimension $p=2$, “the diamond has corners; if the solution occurs at a corner, then it has one parameter $\beta_j$ equal to 0. When $p>2$, the diamond becomes a rhomboid, and has many corners, flat edges, and faces; there are many more opportunities for the estimated parameters to be zero" (refer to page 12 of the above book). The situation in our problem is essentially the same with lasso, the only difference is that our constraint region $\sum_{t=1}^T |s_t| \leq K, \mathbf{s}\in [0,1]^T$ has more corners (i.e., the coordinates are 0 or 1) than that of lasso, therefore, the optimal $s_t$ has a high probability to be either 0 or 1.

2. We can also understand this property from the Complementary slackness in KKT condition, which says “$=$" has to be hold in the “$\leq$" inequality constraints ($s_t \leq 1$ and $-s_t \leq 0$ in our problem) has to be hold as long as the corresponding dual variables are nonzero. The dual variables have a high probability to be nonzero, as they are not imposed with sparse constraints. Please refer to wiki page "https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions". for more details.

3. We empirically verified this property in Fig.2(b).

Q4: Section 4.2: Should the masking rate decrease gradually instead? In Eqn.(12), $\gamma_e$ also decreases as $e$ increases from $e_1$ to N. The smaller K is, the fewer the number of steps is. In addition, what is $e_1$?

A4: 1) $\gamma_e$ is the ratio of the remaining steps in the current epoch $e$. We have provided more detailed expression in Eqn.(12). 2) We train the full denoising sequence in the first $e_1$ epochs and then the remaining ratio $\gamma_e$ decreases gradually to the targeted ratio $\gamma_f$ according to Eqn.(12).

Dear Reviewer MPYQ,

According to your suggestion, we have included A3 into Section C of the appendix and updated the submission. Thanks.

Authors

I thank the authors for patiently reading and responding to all my questions. I found that my concern was adequately addressed. In addition, the revised paper has improved in terms of both the related works and methodology parts.

Further note: The authors should add A3 to the appendix to ease the understanding of the paper.

I would like to increase my score to 6 and incline to an acceptance.