Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper describes a novel implementation of RED, regularization by denoising, which better leverages multicore architectures to achieve a significant speedup. The proposed implementation splits the gradient step into smaller components, which can each be executed independently on different cores and then used to update a shared copy. The crucial result is two sets of convergence guarantees showing that this delayed update will not cause too much error, even if the updates from different cores arrive at different times. The speedups achieved range from 6× to 8× on two tasks (compressive sensing and computed tomography reconstruction).

The paper is well organized and the details are explained well. The numerical results are convincing and the analysis is adequate. The main weak point of the paper is motivating the problem. In other words, it is not clear why a multicore method is needed, although the numerical results demonstrate this later on. For example, Section 3 starts by stating that “ASYNC-RED addresses the computational bottleneck…”, but what that computational bottleneck consists of is never explained. Figure 1 helps in explaining this, but much is left unexplained at this stage. Some discussion of the regime where multicore processing makes sense would also be in order. That being said, I think the results are interesting enough and the description of the method compelling enough that I recommend this work be published as part of the proceedings.

There are some small issues:
– On p. 2, H(x) is never defined.
– On p. 2, G is defined twice: once in eq. (2) and one in eq. (4). Presumably these refer to the same non-linear mapping.
– There seems to be some mixup between BC-RED and GM-RED throughout. Are these different methods?

review_title: Well explained method and interesting results

final_score: rating: 6: Marginally above acceptance threshold
review_content: Due to the growth of data sets in a lot of applications, it is important to develop algorithms to achieve great performance but with significantly reduced computational cost. The paper proposes asynchronous type of parallel algorithms by combining the pre-trained deep denoisers. In particular, batch gradient and stochastic gradient are applied to the proposed algorithm framework by taking advantage of the coordinate separable structures of the problem. Convergence of the algorithms are guaranteed under the four specified assumptions. Numerical experiments on the CT image reconstruction have justified the proposed efficiency and significant improvement in terms of running time. The importance and contribution of this work in compressive sensing algorithms stand. However, the novelty of the methods look incremental. There are some other issues listed as follows. 

1. In p.1, is there any condition on the comparison, e.g., m<<n, required in the introduction?
2. The denoised version $D_\sigma(x^*)$ by some image denoiser essentially provides a more accurate estimate of $x^*$. Can this be replaced by other similar operators? Also, in the compressive sensing, the recovered image $x^*$ at the first few iterations may not be good enough, will the application of this operator make it worse? Does the parameter $\sigma$ need to tune or update dynamically in the iterations?
3. In Alg.1-2, the two operators read() and minibatch() should be explicitly defined. 
4. In the numerical experiments, discussion on the influence of the block/minibatch size on the performance could be strengthened. In the ASYNC-RED-SG, how many trials were conducted to get an average performance? Robustness to the noise could be analyzed. 
review_title: Review of "Async-RED: A Provably Convergent Asynchronous Block Parallel Stochastic Method using Deep Denoising Priors"

final_score: rating: 7: Good paper, accept
review_content: This paper proposed for the first time the asynchronous variants of deterministic and stochastic regularization-by-denoising (RED) algorithms which have become popular recently in image recovery and reconstruction applications since they leverage the power of  pretrained deep denoising neural networks into the traditional model-based schemes, and often achieve state-of-the-art recovery results. These new variants are aimed to fully utilize the multi-cores structure of computational devices and to maximize the practicality of PnP/RED methods in large-scale inverse problems. The authors provide gradient-norm convergence analysis for the proposed algorithms under standard assumptions, along with detailed numerical studies demonstrating practical advantageous of proposed methods. 

Overall the paper is well-written and has the potential to be a nice contribution to the community. The reviewer has several concerns about the current version which hopefully the authors would address and clarify:

(1) The proposed Async-RED methods apply the denoiser on blocks of the image, while the original RED applies the denoiser on the whole image. Intuitively, such a scheme may be suboptimal and somewhat compromise the recovery performance, since state-of-the-art DNN denoisers utilize non-local similarity across the image. Although the experiments in this work do not demonstrate such deficit, the reviewer suspects that, for some images, the Async-RED may not do well on the pixels near the edges of the blocks. The reviewer is a bit dubious about whether such type of block decomposition of denoiser in this line of work can be universally reliable.

(2) The comparative results shown in Fig 3 regarding compressed-sensing reconstruction appear to be somewhat unconvincing:

Firstly, the authors use a suboptimal GM-RED/Sync-RED for baseline, which is gradient descent RED without Nesterov acceleration, while it is well-known that the accelerated gradient descent  RED (AGD-RED) converges at a much better rate and the reviewer believes that this is a more sensible baseline. Maybe an important advantage of original RED and synchronous RED is that they are easier to be accelerated by momentum tricks? 

Secondly, Async-RED-SG seems to yield very limited acceleration in terms of convergence rate over the deterministic counterpart Async-RED-BG in CS example -- what is the minibatch size used in this experiment? Would reducing the minibatch size yield a faster convergence rate? Meanwhile the recovery result of Async-RED-SG is 1dB worse than the other methods, which seems a bit problematic (would a shrinking step-size help to fix this issue?).

It is highly suggested that the authors should also plot the convergence curves for the CT experiments as in the Fig.3.

******************** after rebuttal*********************

The authors have provided a responsive feedback and addressed the comments to satisfactory, therefore the reviewer votes for acceptance.






review_title: First asynchronous regularization-by-denoising algorithms for imaging with deep denoising priors

final_score: rating: 7: Good paper, accept
review_content: The main contribution is a combination of asynchronous processing and stochastic activation of blocks in a distributed computing environment. The framework is general, since the regularization/denoising operator is any nonexpansive operator; but focusing on the PnP/RED framework is a very relevant choice.
To my knowledge (I am not an expert of this particular area of optimization), the contribution is new and solid. 
I have the following questions/remarks:
* After Assumption 4: when mentioning the literature, I think you should include the paper "BUILDING FIRMLY NONEXPANSIVE CONVOLUTIONAL NEURAL NETWORKS" by Terris et al. and shortly discuss the relationship. In particular, nonexpansiveness is sufficient in your setting, whereas it is usually not sufficient in optimization, with averagedness/firm nonexpansiveness assumed. Why is it so?
* About asynchronous optimization, Franck Iutzeler has his PhD thesis and several papers on the topic. You might have a look and cite some of them, which are relevant in your setting.
* Theorem 2 shows that the "convergence" is not variance-reduced. I would appreciate a discussion on whether this is unavoidable or if this is an open question for future work, if there is relevant literature on this matter, and why it is difficult to derive a variance-reduced approach with similar features.
* the DnCNN architecture is used in the experiments: does it satisfy Assumption 4? More generally, are all assumptions met so that the theorems apply in the experiments? You should discuss the match between your theoretical results and the conditions of the practical experiments more closely.
review_title: A good paper on accelerating distributed computations by asynchronous and stochastic activation, with applications to regularized imaging problems

Meta-review: The reviewers agree that this paper overcomes a number of difficult algorithmic and technical challenges in parallelizing the RED method for image reconstruction.  
Decision: Accept (Spotlight)