Async-RED: A Provably Convergent Asynchronous Block Parallel Stochastic Method using Deep Denoising Priors
Authors: Yu Sun
Jiaming Liu
Yiran Sun
Brendt Wohlberg
Ulugbek Kamilov
Venue: ICLR 2021 Spotlight (2021)
Keywords: Regularization by denoising
Computational imaging
asynchronous parallel algorithm
Deep denoising priors

Abstract: Regularization by denoising (RED) is a recently developed framework for solving inverse problems by integrating advanced denoisers as image priors. Recent work has shown its state-of-the-art performance when combined with pre-trained deep denoisers. However, current RED algorithms are inadequate for parallel processing on multicore systems. We address this issue by proposing a new{asynchronous RED (Async-RED) algorithm that enables asynchronous parallel processing of data, making it significantly faster than its serial counterparts for large-scale inverse problems. The computational complexity of Async-RED is further reduced by using a random subset of measurements at every iteration. We present a complete theoretical analysis of the algorithm by establishing its convergence under explicit assumptions on the data-fidelity and the denoiser. We validate Async-RED on image recovery using pre-trained deep denoisers as priors.

Published as a conference paper at ICLR 2021
ASYNC-RED: A PROVABLY CONVERGENT ASYn- CHRONOUS BLOCK PARALLEL STOCHASTIC METHOD USING DEEP DENOISING PRIORS
Yu Sun', , Jiaming Liu', Yiran Sun', Brendt Wohlberg', Ulugbek Kamilov! Washington University in St. Louis, Los Alamos National Laboratory {sun. yu, jiaming. 1iu, yiran. an.s,, s, (amilovv](ww) edu, brendt@ieee.....
ABSTRACT
Regularization by denoising (RED) is recently developed framework for solving inverse problems by integrating advanced denoisers as image priors. Recent work has shown its state-of-the-arr performance when combined with pre-trained deep denoisers. However, current RED algorithms are inadequate for parallel processing on multicore systems. We address this issue by proposing a new asynchronous RED (ASYNC-RED) algorithm that enables asynchronous parallel processing of data, making it significantly faster than its serial counterparts for large-scale inverse problems. The computational complexity of ASYNC-RED RED is further reduced by using a random subset of measurements at every iteration. We present complete theoretical analysis of the algorithm by establishing its convergence under explicit assumptions on the data-fidelity and the denoiser. We validate ASYNC-RED on image recovery using pre-trained deep denoisers priors.
INTRODUCTION
Imaging inverse problems seek recover unknown image R" from its noisy measurements RT. Such problems arise in many fields, ranging from low-level computer vision to biomedical imaging. Since many imaging inverse problems are ill-posed, is common to regularize the solution
by using prior information on the unknown image. Widely-adopted image priors include total variation, low-rank penalties, and transform-domain sparsity (Rudin et al., 1992. Figueiredo &
Nowak 2001 2003
Hu et al. 2012 Elad & Aharon 2006).
There has been considerable recent interest in felug-anddplay priors (PnP) (Venkatakrishnan et al. 2013 Sreehari et al.] (2166) and regularization by denoising (RED) (Romano et al.) 2017). as frame- works for exploiting image denoisers as priors for image recovery. The popularity deep learning has led to wide adoption of deep denoisers within PnP/RED, leading to their state-of-the- the-hhr-rttt performance in a variety of applications, including image restoration (Mataev et al. 2019), phase retrieval (Metzler al. 2018), and tomographic imaging (Wu et al.) 2020). Their empirical success has also prompted a follow-up theoretical work clarifying the existence of explicit regularizers (Reehorst & Schniter 2019). providing new interpretations based on fixed-point projections (Cohen al.) (020), and analyzing their coordinate/online variants (Sun et al.) 2019a; Wu et al. 2020). Nonetheless, current PnP/RED algorithms are inherently serial. As illustrated in Fig. this makes them suboptimal on multicore systems that are often required for processing large-scale datasets (Recht et al., 2011 ) such
as those involving biomedical (Ong et al. 2020) and astronomical images (Akiyama et al.) 2019)
We address this gap by proposing novel asynchronous RED (ASYNC-RED) algorithm. The algorithm decomposes the inference problem into sequence of partial (block-coorddinate) updates on æ executed asynchronously in parallel over a multicore system. ASYNC-RED leads to a more efficient usage of available cores by avoiding synchronization partial updates. ASYNC-RED also scalable in terms of the number of measurements, since it processes only small random subset of at every iteration. We present two new theoretical results on the convergence of ASYNC-RED based on unified set of explicit assumptions the data-fidelity and the denoiser. Specifically, its fixed- -oint convergence in the batch setting and extend this analysis to the randomized minibatch scenario. Our results extend recent work serial block-coordinate RED (BC-RED) (Sun al.
establish

---

Published as a conference paper at ICLR 2021
Figure 1: Visual illustration of serial and parallel image recovery multicore system. (a) Serial processing uses only one core of the system for every iteration. (b) Synchronous parallel processing has to wait for the slowest core to finish before starting the next iteration. (c) Asynchronous parallel processing can continuously iterate using all the cores without waiting. (d) Asynchronous parallel processing using the stochastic gradient leads to additional flexibility. (a), (b), and (c) use all the corresponding measurements at every iteration, while (d) uses only a small random subset at a time. ASyNC-RED adopts the schemes shown in (c) and (d).
2019a) and are fully consistent with the traditional asynchronous parallel optimization methods (Lian al. 2015 Sun et al, 2017). We numerically validate ASYNC-RED on image recovery from linear and noisy measurements using pre- pre-trained deep denoisers as image priors.
BACKGROUND
Inverse problems. Inverse problems are traditionally formulated as composite optimization problem
Ø arg min g(æ) + I:(2r);
(1)
=ER"
where g is the data-fidelity term that ensures consistency of x: with the measured data y and is the regularizer that infuses the prior knowledge on æ. For example, consider the smooth l2 f--morm data-fidelity term g(x) ) yy- Ax which assumes linear observation model Aæ + e, and
the nonsmooth TV regularizer h(x))) T [Del] where 7 > 0 the regularization parameter and D
is the image gradient (Rudin et al. 1992).
Regularization by denoising (RED). RED is recent methodology for imaging inverse problems that seeks vectors x² E R² satisfying
G(x") Vg(x") + +
x² E =0 x'E zer(G) = {a E IR" G(x) = 0} (2)
where Vg denotes the gradient the data-fidelity term and D.r R - R an image denoiser parameterized by
0. Under additional technical assumptions, the solutions x. zer(G)
can be associated with an explicit objective function form ( Specifically, when D, is locally homogencous and has symmetric Jacobian satisfying strong passivity (Romano et al. 2017 Rechorst Schniter 2019). (zz) := x (x) corresponds to the gradient of convex regularizer
1
h(x)) T (x
simple strategy, known as GM-RED, for computing x" zer(G) is based on the first-order fixed-point iteration
x' 1-
with G: Rd R"
(4)
where 7 > 0 denotes the stepsize. this paper, we extend this first-order RED algorithm to design ASYNC-RED, Since many denoisers do not satisfy the assumptions necessary for having explicit objective (Reehorst & Schniter 2019). our theoretical analysis considers a broader setting where D, does not necessarily correspond to any explicit regularizer. The benefit of our analysis is that it accommodates powerful deep denoisers (such as DnCNN (Zhang et al. 2017a)) that have been shown
to achieve the state-of-the-art performance (Sun et al. 2019a Wu al. 2020 Cohen et al. 2020).
2

---

Published as a conference paper at ICLR 2021
Plug-and-play priors (PnP) and other related work. There other lines of works that combine the iterative methods with advanced denoisers. One closely-related framework is known as the deep mean-shift priors (Bigdeli et al., 2017). It develops an implicit regularizer whose gradient is specified by a denoising autoencoder. Another well-known framework is PnP, which generalizes proximal methods by replacing the proximal map with image denoiser (Venkatakrishnan al.
2013). Applications and theoretical analysis of PnP are widely studied in (Srechari et al. [2016] Zhang
al.
2017b; Sun al., 2019 Zhang et al. 2019; Ahmad al., 2020 Wei al. (020) and CChan
et al.
2017; Meinhardt et al. 2017; Buzzard et al. 2018 Sun et al., 2019b; Tirer & Giryes 2019
Teodoro al. 2019: Ryu al., 2019 Xu et al.) 2020), respectively. In particular, Buzzard al.
(2018) proposed a parallel extension of PnP called Consensus Equilibrium (CE), which enables synchronous parallel updates æ. Note that while we developed ASYNC-RED as a variant RED, our framework and analysis can be also potentially applied to PnP/CE. The plug-in strategy can be also applied to another family of algorithms known as approximate message passing (AMP) Metzler al. 20 Fletcher al. 2018p. The AMP-based algorithms are known be nearly-optimal for random measurement matrices, but are generally unstable for general A (Rangan et al. 2014 2015).
Asynchronous parallel optimization. There two main lines of work in asynchronous parallel optimization, the one involving the asynchrony in coordinate updates (lutzeler et al. 2013) Liu et al.
2015 Peng al. 2016; Bianchi al.) 2015 Sun al., 2017 Hannah & Yin 2018 Hannah et al.
2019)
and the other focusing on the study of various asynchronous stochastic gradient methods (Recht
al. 2011 Lian al.) 2015 Liu al. 2018 Zhou et al. 2018: Lian et al. 2018).
Our work contributes to the area by developing a novel deep-regularized asynchronous parallel method with provable convergence guarantees.
ASYNCHRONOUS RED
ASYNC-RED allows efficient processing of data by simultaneously considering the asynchronous partial updates of solution z and the use of randomized subset of measurements y. In this section, introduce the algorithmic details of our method. We start with the basic batch formulation of ASYNC-RED (ASYNC-RED-BO) followed by its minibatch variant (ASYNC-RED-SG),
3.1 ASYNC-RED USING BATCH GRADIENT
When the gradient uses all the measurements y RTM ASYNC- RED--RED-BL extension of the recent block-coordinate RED (BC-RED) algorithm (Sun et al. 2019a). Consider the decomposition of the variable space RR into b blocks
BDD--GG is the asynchronous
x = (#1, 2b)) E _ X ... RT = R" with n 11 + n22 +
+ An-
For each i Rn and its transpose U. that extracts the ith block from a vector in R This directly implies that
{1, (1....,0 bb. introduce the operator U, T R that injects vector in R into
1= U,U, + U,UT and ||>l|| = ar | ..... + || with 2, = UT xr.
(5)
In analogy to the RED operator G in we define the block-coordinas operator G; as
(z)z)= = U,U. G(z), with x E E and G. R" R
(6)
Due to the asynchrony in the block updates, the iterate might be updated several times by different cores during single update cycle of a core, which means that the evaluation of 2 relies on a stale iterate /
x k+1 xx -y, (**), with # == xx
Σ -x'- 11 SA
Here, we assume that the stale iterate & exits as a state of x in the shared memory, and the delay between them is bounded by finite number À E 24. These two assumptions are often referred to as the consistent read (Recht et al., 201T) and the bounded delay (Liu & Wright 2013) in the traditional asynchronous block coordinate optimization. Although implement the consistent read in ASYNC-Re RED, the algorithm never imposes global lock on =² We refer to Supplement A for the related diseussion.
3

---

Published as a conference paper at ICLR 2021
Algorithm ASYNC-RED-BG
1: input: x² E "RR,, > 0, T 0.
2: setup: A multicore system with shared memory storing and global iteration k.
3: for global k= 15=1,, 1,2,3..... do
4: x* (x)
5: (ā") t U G(
with random de {l,...,b)
Block Operation
6: xx 4- a))
7:
x x++1 f- x=
G (3*)
8: update the shared memory using a=++1
9: end for
The first variant, ASYNC-RED-BG, is summarized in Algorithm D where read(.) reads a block from the shared memory to the local memory. When the algorithm is run on single core system without parallelization (that is say x )) ), reduces to the normal BC-RED algorithm. Hence, our analysis is also applicable to BC-RED.
We specifically consider the random block selection strategy in ASYNC-RED-BG, namely that every block index i is selected an i.i.d random variable uniformly distributed over (1.....b) bb. Such strategy commonly adopted for simplifying the convergence analysis. Nevertheless, our method and analysis can be generalized to the scenario where ig follows some arbitrary probability P(ix = i) = ps specified by the user.
Compared with serial RED algorithms, ASYNC-REI- enjoys considerable scalability by dividing the computation of the full operator into parallel evaluation G; distributed across all cores. Thus, without any modification the algorithmic design, can easily improve the performance of the algorithm by simply integrating more cores into the system. Section S we experimentally demonstrate the significant speed-up and scale-up in solving the context of image recovery.
3.2 ASYNC-RED USING STOCHASTIC GRADIENT
The scale of measurements is another important factor influencing the computational complexity the large-scale inference tasks. ASYNC-RED- improves the applicability of ASYNC-RED to these cases by further considering the decomposition of the measurement space R into l blocks
(y), ,ye) _T x T
Rm with m, m2 m..
Hence, ASYNC-RED BG considers the following data-fidelity and its gradient Vg
(xx) Σ (5(
Vg(x)
(g)(
where each 9j is evaluated on the subset yj E RT of the full y. From we know that the computation of (z) is proportional to the total number f. To reduce the per-iteration cost, follow the idea of stochastic optimization to approximate the batch gradient by using the stochastic gradient that relies on a minibatch of w measurements
1
V 9i. (w),
where j, is picked from the set (1...., f i..d uniform random variable. Based the minibatch gradient, we define the block stochastic operator G. R - R as
G = G(x), with G = (((z) + r(x - (x)),, G R" + R".
(10)
Note that the computation of G, is now dependent on the minibatch size w that is adjustable to cope with the computation resources hand. SEYNC-RED-SC is summarized in Algorithm
The operation minibatchG(.) computes the estimate based on w randomly selected measurements. We clarify the difference between ASYNC- RED-SG and -SYNC-RED-BC via specific example.
4

---

Published as a conference paper at ICLR 2021
Algorithm 2 ASYNC-RED-SG
1: input: x² E ER, > 0, T,T 0.
2: setup: A multicore system with one shared memory storing and global iteration k.
3: for global k = 1,2,3,.... do
4: x read(a;)
5: G(T²) < minibatchG w) with random Iu E {I,...,{}
Minibatch Gradient Block Operation
6:
G.. (5t) + U G(T") with random de E {I,...,b]
7:
x* read(x))
8: k+1 +- =² G,
9: update in the shared memory using x=++1
10: end for
Consider the least-squares with a block-friendly operator and a block-efficient denoiser D,, We can write the update of ASYNC-REDD RED-BG regarding a single iteration as
( = (A, y:) + T(ē; - D(ē)))
(11)
where 전 is the delayed iterate for æ, and A; E IR is submatrix of A consisting of columns corresponding the ith blocks. Although the per-iteration complexity is reduced by roughly b = n/'n; times by working with A; instead of A, ASYNC-RED-BR BED-GGGued still needs to work with all the measurements yr related to the ith block at every iteration. Consider the corresponding update of ASYNC-RED-SG with one measurement used at a time
(5) AJ,( yjs)) +
(12)
where Yja denotes the jth measurement of I;, and Ajı E m is the submatrix crossed by the rows and columns corresponding to the jth measurement and the ith blocks. This indicates that the reduction of the per-iteration complexity from ASYNC-RED-BE f=m/mn m/m, times. the practice, common to use w > 1 measurements at time to optimize the total runtime. Note that if UT I, ASYNC-RED-SSS algorithm. In the next section, we will present a complete analysis of ASYNC-RED and theoretically discuss its connection to the related algorithms.
ASYNC-RED-SC can be up to
becomes the asynchronous stochastic RED
CONVERGENCE ANALYSIS OF ASYNC-RED
The proposed analysis is based on the following explicit assumptions. Note that these assumptions serve as sufficient conditions for the convergence.
Assumption 1. We assume bounded maximal delay co. Hence, during any update cycle of an agent, the estimate in the shared memory is updated at most X E Z, times by other cores.
The value of À is often dependent on the number of cores involved in the computation (Wright 2015). If every core takes similar amount of time to compute its update, À is expected to be multiple of the number of cores. Related work has investigated the convergence with unbounded maximal delays in the context of traditional optimization (Hannah & Yin 2018 Peng al. 2019 Zhou et al. 2018).
Assumption 2. The operator such that zer G) + Ø, and the distance of the initial x. E IR" to any element in zer(G) bounded, that is || x= S Ro for all x² zer(G) with Ro co.
This assumption ensures the existence of solution for the RED problem and is related to the existence of minimizers in traditional coordinate minimization (esterov 2012 Beck & Tetruashvili 2013
Assumption 3. (a) Every component function ga is convex differentiable and has Lipschitz continu- ous gradient of constant L; > (b) At every update, the stochastic gradient is unbiased estimator of V g that has bounded variance;
22 w
E
[g(z)) = g(x).
E
DER"
V> 0.
The first part of the assumption implies that is also convex and has Lipschitz continuous gradient with constant I. max T.,,.., T.z). The second part is standard assumption the unbiasedness
5

---

Published as a conference paper at ICLR 2021
10:
.5
jazht"nczhh
SNR (ID)
10
104
itoratiom
8000 0
Úice (second)
Figure 2: Convergence of RED-BG for different numbers of accessible cores ne (2. 2, 6, 8). The left figure plots the average normalized distance to zer(G) against the iteration number; the middle and right figures plot these values, as well as SNR, plotted against the actual runtime in seconds. The shaded areas represent the range of values attained over the test images.
and variance of the stochastic gradient Lian al 2015 Ghadimi & Lan 2016). Our final assumption is related to the deep denoiser used in ASYNC-RED RED.
Assumption 4. The denoiser D is nonexpansive operator (m) D2 (y)l
x 3/1-
Compared with the conditions stated in Section 2 (namely, that it is locally homogencous with symmetrie Jacobian), our requirement on the denoiser is milder. One can train a nonexpansive D, by constraining the Lipschitz constant of D, via the spectral normalization, which is an active area
of research in deep learning (Miyato et al. 2018 Sedghi et al. 2019 Anil al. 2019 2020).
Terris et al.
We can now state the theorems on ASYNC-RED.
Theorem 1. Let Assumptions 7 hold true. Run ASYNC-RED-BG for 0 iterations with uniform
i.idd block selection using a fixed step-size E (0, (0,1/((11 + 2A) + 2r) Then, the iterates of the algorithm satisfy
D
(L + 2r)b RC
min E [II((=*) 0skst-1
<
+ b
(13)
y
where D = 222/21 2)2 is constant.
Theorem establishes the convergence of ASYNC-RED-BG to the fixed-point set zer(G) at the rate of O(1/t). Our result is consistent with the existing results in the literature. In particular, when the algorithm adopts serial block updates, that is x and ž² = x², the recovered convergence is nearly the same BC-RED (Sun et al. 2019a) scaled by some constant. On the other hand, our convergence rate (1/1)) is also consistent with the rate proved for the asynchronous block coordinate descent in nonconvex optimization (Sun et al. 2017).
Theorem 2. Let Assumptions 4 hold true. Run ASYNC-RED-SO SG for t >> 0 iterations with uniform i. selections of blocks and meusurements using a fixed step-size y E (0, + 21) + 2r))]- Then, the iterates of the algorithm satisfy
min 0skst-1
[[]G(a * >1
<
D b
+
(L+
2T)6
RS
+
2D b
+
-c w
(14)
76
where C- (L 2)v² and D 2X /1 + X)2 are constants.
Theorem states that ASYNC-RED-SS approximates the solution obtained by ASYNC-RED-BR up finite error that decreases for larger values of the minibatch size w. This relationship is consistent with the recent theoretical results on the online PnP and RED algorithms (Sun et al. 2019b Wu ct al. 2020p. In practice, the selection or must balance the actual memory capacity of the system and the desired runtime for obtaining reasonable solution. Our numerical evaluation in Section demonstrates the excellent approximation of ASYNC-RED-SG to the aatch-gradient solution by using a small subset of data.
By carefully choosing the stepsize 7, we can state the following remark on Theorem 2 Remark 1. Set the stepsize to be 7 = 1/vwt. the maximal delay satisfies À < (1/2)[/wt//C 0 iterations have
2r) - 1]. then after
D b
(L
2T
2D b
C
min o
E [|]G(('))''
<
+
R
+
+ 2
(15)
wc
Vwl

---

Published as a conference paper at ICLR 2021
35
Ascoodlti-die 1120
Aere #0(wDR)
Takeo Seed of Aene BST coeposed BID
(ap-) BAS
speedsp
20,11 mm
Antro RRD 7008 mee!
29.01 dm
6.1x
Aayas RERT (03)koo)))
14.15 (R
15.8 min
4.4%
103
Ineractinn
500
(second)
Figure 3: Left: Evolution of the convergence accuracy of ASYNC- as the minibatch size increases. The average distance is plotted against the number of iterations with the shaded areas representing the range of values attained over the test images. Middle & Right: Comparison of convergence speed between ASYNC- ASYNC-RED-BOL RED-BG/SG and other baselines. The right table summarizes the total runtime and the speed-up compared with GM-RED for all algorithms.
This establishes the fixed-point convergence to the set zer(G) at the rate of O(1/ Vurt under specific conditions. we treat entire æ as a block, namely that = UT = and b b- 1, ASYNC-RED-SG then becomes the asynchronous stochastic RED algorithm. Hence, the proposed remark immediately holds true for the later. Note that our convergence rate (11/v wnt) is consistent with the rate proved
for the serial @Nemirovski et al. 2009) and parallel (Dekel et al. 2012 Lian et al. 2013) stochastic gradient methods.
All the proof' are presented in the supplement. We note that the analysis above does not assume the existence of an explicit regularizer associated with the operator D.. Moreover, it does not require D, to be a Gaussian denoiser. Our analysis is hence applicable to all nonexpansive operators, such as the traditional proximal operators or the more recent ratifalttremoval operators (Zhang al. 2019.
NUMERICAL VALIDATION
We now present numerical validation of ASYNC-RED. Our goals are first to validate the proposed theorems in Section 4 and then to demonstrate the effectiveness and the efficiency of our algorithm on the large-scale problem. We consider two image recovery tasks that have the form y Ax + c, where the measurement matrix A corresponds to either the random matrix in compressive sensing (CS) or the Radon transform in computed tomography (CT), and the noise assumed be additive white Gaussian (AWGN). In particular, the random matrix is implemented with the block-diagonal structure A diag([A, ..., As) for fast validation, while the Radon transform is used as its full matrix form to demonstrate the effectiveness of ASYNC-RED for overcoming the computation bottleneck. Our deep neural net prior adapts the DrCNN architecture (Zhang et al.) 2017a). We used the signal- to-noise ratio (dB) to quantify the quality of the reconstructed images. For each experiments, we selected the denoiser that achieves the best SNR performance from the ones corresponding to five noise levels E {5, 10, 15, 20, 25). The value of is fixed across all iterations of the algorithm. Supplement D provides additional technical details.
5.1 CONVERGENCE BEHAVIOR
We validate our theorems on the CS task with 6 test images selected from the Set 12 dataset Zhang et al. 2017ab. Each test image is rescaled to the size of 240 x 240 pixels (see Fig, in the supplement for the visualization). The block-diagonal matrix A is set to consist of submatrices, corresponding to a 3 x 3 grid of blocks with the size of 80 x 80 pixels in every image. The elements in A are i.dd zero-mean Gaussian random variables of variance of 1/m, and the compression ratio is set to be m/n 0.7, which indicates that the total number of measurements is 4480 for each block. We obtain the measurements by multiplying A with each vectorized image and adding additional noise corresponding to the input SNR of 30 dB. Finally, [[(== to quantify the fixed-point convergence, with block updates grouped as one iteration. The distance is expected to approach zero the algorithm converges average performance of all methods is obtained by running a single trial for each image.
the normalized distance
fixed point. The
Theorem I establishes the convergence of ASYNC-RED RED-BG to the fixed point set zer This is illustrated in Fig. for four different numbers of accessible cores n. E (2, 4, 6, 8). In the left figure, the average normalized distance is plotted against the iteration number, while the middle and
7

---

Published as a conference paper at ICLR 2021
FRP (15.56
LEYNC-RED-SC (23.29 ci3)
ASVMC-RED-RG (22.25
Gx-RED (21.45 AR)
Figure 4: CT reconstruction with time budget of 1 hour by ASYNC-RED-BG/SS and GM-RED. The colormap is adjusted for the best visual quality.
right figures plot the corresponding distance and SNR values against the actual runtime in seconds. The shaded areas representing the range of values attained across all test images. We also plot the results serial BC-RED using the dashed line as reference. to be run asynchronously on multiple cores, while BC-RED only use one core perform the computation. The left figure highlights the fixed-point convergence of ASYNC-RED-Be in iteration for different Ple, with all variants agreeing with the serial BC-RED. Since ESYNC-RED-IE more cores, the middle and right figures demonstrate the significantly faster in-time convergence of DSYYNC-EE-JE
is implemented
than BC-RED to the same SNR value. Specifically, BC-RED takes 1.8 hours to achieve 29.00 dB, while SSYNC-RED-BE BG (n. = 8) takes only 17.9 minutes to obtain the same value, corresponding to a 6x improvement computation time.
Theorem establishes the convergence of ASYNC-RED-SC to zer(G) up some error term, which inversely y proportional to the minibatch size w. This illustrated in Fig. (left) for three different minibatch sizes w E (1120, 2240, 3360). As before, we plotted the average distance against the iteration number with the shading area representing the variance. Note that the log-scale of y- axis highlights the change for smaller values. Fig. demonstrates the improved convergence of ASYNC-RED RED-SG to zer(G) )) for larger w, which is consistent with our theoretical analysis. Fig. (middle) compares the convergence speed between RGM-RED), and synchronous parallel RED (SYNC-RED). For ESYNC-RED-- -SG we use w = 1120. In particular, ASSYCC-RE--SSS
gradient-method RED
takes fewer total runtime (from 17.9 min 13.0 min) obtain the similar result (29.01 dB and 28.03 dB) and achieves 8.4 speedup compared with GM-RED. The table Fig. summarizes the detailed results.
5.2 EFFECTIVENESS FOR COMPUTATIONAL IMAGING
We additionally demonstrate the effectiveness of our algorithm by reconstructing 800 x 800 CT image from 180 projections. For block parallel updates, the image is decomposed into 16 blocks, each having the size of 200 x 200 pixels. The Radon matrix used in the experiment corresponds to 180 angles with 1131 detectors, and the noise level is set to 70 dB. We refer to Supplement D.2 for additional technical details. Fig. shows the visual illustration of the reconstructed images by ASYNC-RED RED-RED--CCC RED-BG//S and GM-RED, Each algorithm starts from the filtered back projection (FBP) of the measurements and runs for hour. Here, ASYNC-RI RED-SG randomly uses one-third of the total measurements at every iteration. Given the same amount time, SEYNC-RRE-BGGSE mitigates the noise-artifacts, while the result of GM-RED still noisy. particular, the per-iteration and GM-RED is 5.23, 3.21, and 19.19 19 seconds, respectively. This
successfully
time cost of experiment clearly illustrates the fast processing speed of the asynchronous procedure.
CONCLUSION
Asynchronous parallel methods have gained increasing importance in optimization for solving large- scale imaging inverse problems. We have introduced ASYNC-RED RED as an extension of the recent RED framework and theoretically analyze its convergence in batch and stochastic settings. We have
8

---

Published as a conference paper at ICLR 2021
validated its convergence guarantees and demonstrated its effectiveness in CT image reconstruction. We note that this work is complementary to traditional acceleration strategies, such as Nesterov acceleration and variance-reduction, commonly used in optimization. Future work will investigate ASYNC-RED with Nesterov acceleration (as was done in (Hannah et al. 2019) for traditional asynchronous block-coordinate algorithms) and variance-reducctinn (as was done in (Johnson & Zhang 2013) for traditional stochastic gradient method) to better understand the tradeoff' between acceleration and scalability multicore systems. We will additionally investigate theoretical limits of ASYNC-RED in the unbounded maximal delay setting.
ACKNOWLEDGEMENT
Research presented in this article was supported by NSF award CCF-1813910 and the Laboratory Directed Research and Development program of Los Alamos National Laboratory under project number 2020006IDR.
REFERENCES
R. Ahmad, C. A. Bouman, G. T. Buzzard, S. Chan, S. Liu, E. T. Reehorst, and P. Schniter. Plug-and- play methods for magnetic resonance imaging: Using denoisers for image recovery. IEEE Signal Processing Magazine, 3751):005-116, 2020.
K. Akiyama, A. Alberdi, W. Alef, K. Asada, R. Azulay, A.K. Baczko, D. Ball, M. Baloković, Barrett, D. Bintley, et al. First m87 event horizon telescope results. iv. imaging central supermassive black hole. The Astrophysical Journal Letters, 875(1):L4, 2019.
C. Anil, J. Lucas, and R. Grosse. Sorting Lipschitz function approximation. In Proc. 36th Int. Conf. Machine Learning (ICML), pp. 291-301, Long Beach, California, USA, 09-15 Jun 2019.
H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2 edition, 2017.
A. Beck and L. Tetruashvili. On the convergence of block coordinate descent type methods. SIAM J. Optim., 2344):2037-2060 October 2013.
P. Bianchi, W. Hachem, and F. lutzeler. A coordinate descent primal-dual algorithm and application to distributed asynchronous optimization. IEEE Transactions on Automatic Control, 61(10): 2947-2957, 2015.
S. A. Bigdeli, M. Jin, P. Favaro, and M. Zwicker. Deep mean-shift priors for image restoration. In Proc. Advances Neural Information Processing Systems 30, Long Beach, CA, USA, Dec 2017.
Boyd and L. Vandenberghe. Convex Optimization. Cambridge Univ. Press, 2004.
G. T. Buzzard, S. H. Chan, S. Srechari, and C. A. Bouman. Buu--and-lay unplugged: Optimiza- tion free reconstruction using consensus equilibrium. SIAM Imaging Sci., 1133:2001122000, September 2018
S. H. Chan, X. Wang, and O. A. Elgendy. Plug-and-play ADMM for image restoration: Fixed-point convergence and applications. IEEE Trans. Comp. Imag., 3(1):84-0))) 98, March 2017.
R. Cohen, M. Elad, and Milanfar. Regularization by denoising via fixed-point projection (RED- PRO). arXiv:2008.0022 00226 [eess./V], 2020.
O. Dekel, R. Gilad-Bachhach. O. Shamir, and L. Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(D):165202,, 2012.
M. Elad and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Image Process.. 15(12):3736-37 December 2006.
M. A. T. Figueiredo and R. D. Nowak. Wavelet-based image estimation: An empirical Bayes approach using Jeffreys' noninformative prior. IEEE Trans. Image Process., 10<9):1322-13: 1131, September 2001.

---

Published as a conference paper at ICLR 2021
M. A. T. Figueiredo and R. D. Nowak. An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process., 12(8):906 916, August 2003.
A. K Fletcher, P. Pandit, S. Rangan, S. Sarkar, and P. Schniter. Plug-in estimation in high-dimensional linear inverse problems: A rigorous analysis. In Advances in Neural Information Processing Systems 31, pp. 7451-7461 Montreal, QC, Canada, Dec. 2018.
S. Ghadimi and G. Lan. Accelcrated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program. Ser: A, 156(1):59-99) March 2016.
R. Hannah and W. Yin. On unbounded delays in asynchronous parallel fixed-point algorithms. Journal of Scientific Computing, 76(1):299-33) Jul 2018.
R. Hannah, E. Feng, and W. Yin. A2BCD: Asynchronous acceleration with optimal complexity. In International Conference Learning Representations, 2019.
Y. Hu, S. G. Lingala, and M. Jacob. A fast majorize-minimize algorithm for the recovery of sparse and low-rank matrices. IEEE Trans. Image Process., 21(2):742-75,, February 2012.
lutzeler, Bianchi, Ciblat, and W. Hachem. Asynchronous distributed optimization using a randomized alternating direction method of multipliers. In 52nd IEEE conference decision and control, pp. 3671-3676. IEEE, 2013.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, pp. 315-323, 2013.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015. arXiv:1412.6960 [cs.LG].
X. Lian, Y. Huang, Y. Li, and J. Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems 28, pp. 2737-2745. Montreal, QC, Canada, 2015.
X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. In Proc. 35th Int. Conf. Machine Learning (ICML), pp. 3043-3052, Stockholmsmässan Stockholm Sweden, 10-15 Jul 2018
Liu and Wright. Asynchronous stochastic coordinate descent: Parallelism and convergence properties. SIAM Journal on Optimization, 25(1):351-375 2015.
J. Liu, S. J. Wright, C. Ré, V. Bittorf, and S. Sridhar. An asynchronous parallel stochastic coordinate descent algorithm. Mach. Learn. Res., 16(1):285-322, January 2015.
Liu, S. Li, Shi, Zhou, and Zhao. Towards understanding acceleration tradeoff between mo- mentum and asynchrony in nonconvex stochastic optimization. In Advances in Neural Information Processing Systems 31, pp. 3682-3692. Montreal, QC, Canada, Dec 2018.
D. Martin, C. Fowlkes, D. Tal, and Malik, A database human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proc. IEEE Int. Conf. Comp. Vis. (ICCV), pp. 116,423, Vancouver, Canada, July 7-14, 2001.
G. Mataev, P. Milanfar, and M. Elad, Deepred: Deep image prior powered by red. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV) Workshops, Oct 2019.
T. Mcinhardt, M. Moeller, C. Hazirbas, and D. Cremers. Learning proximal operators: Using denoising networks for regularizing inverse imaging problems. In Proc. IEEE Int. Conf. Comp. Vis. (ICCV), pp. 1799-1808. Venice, Italy, October 22-29, 2017.
C. Metzler, P. Schniter, A. Veeraraghavan, and R. Baraniuk. prDeep: Robust phase retrieval with a flexible deep network. In Proc. 35th Int. Conf. Machine Learning (ICML), pp. 3501-3510, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018.
C. A. Metzler, A. Maleki, and R. Baraniuk. BM3D-PRGAMP- Compressive phase retrieval based on BM3DD denoising. In Proc. IEEE Int. Conf. Image Proc. (ICIP), pp. 2504-2505 Phoenix, AZ, USA, September 25-28, 2016a.
10

---

Published as a conference paper at ICLR 2021
C. A. Metzler, A. Maleki, and R. G. Baraniuk. From denoising compressed sensing. IEEE Trans. Inf. Theory, 6219):5177-5144, September 2016b.
T. Miyato, Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim,, 19(4)1577-1609, 2009.
Y. Nesterov. Introductory Lectures on Conver Oplimization: Basic Course. Kluwer Academic Publishers, 2004.
Y. Nesterov. Efficiency of coordinate descent methods huge-scale optimization problems. SIAM J. Optim., 22(2):341-362, 2012.
F. Ong, X. Zhu, J. Y. Cheng, K. M. Johnson, P. E. Z. Larson, S. S. Vasanawala, and M. Lustig. Extreme mri: Large-scale volumetric dynamic imaging from continuous non-gated acquisitions. Magnetic Resonance in Medicine, 84(4):1763-1780 2020.
Z. Peng, Y. Xu, M. Yan, and W. Yin. Arock: An algorithmic framework for asynchronous parallel coordinate updates. SIAM Journal on Scientific Computing, 38(5):A2851-A287) 2016.
Z. Peng, Y. Xu, M. Yan, and W. Yin. On the convergence of asynchronous parallel iteration with unbounded delays. Journal of the Operations Research Society of China, 7(1):5 2019.
S. Rangan, P. Schniter, and A. Fletcher. On the convergence of approximate message passing with arbitrary matrices. In Proc. IEEE Int. Symp. Information Theory, pp. 236-240, Honolulu, HI, USA, June 29-July 4, 2014.
S. Rangan, A. K. Fletcher, P. Schniter, and U. S. Kamilov. Inference for generalized linear models via alternating directions and Bethe free energy minimization. Proc. IEEE Int. Symp. Information Theory, pp. 1640- 1644, Hong Kong, June 14-19, 2015.
B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems 24, pp. 693-701. Granada, Spain, Dec 2011.
E. T. Reehorst and P. Schniter. Regularization by denoising: Clarifications and new interpretations. IEEE Trans. Comput. Imag., 5(1):52-67, March 2019.
R. T. Rockafellar and R. J-B Wets. Variational Analysis. Springer, 1998.
Y. Romano, M. Elad, and P. Milanfar. The little engine that could: Regularization by denoising (RED). SIAM J. Imaging Sci., 1844):1804-1844, 2017.
L. I. Rudin, Osher, and E. Fatemi. Nonlinear total variation based noise removal algorithms. Physica D, 60(1-4):259-688 November 1992.
E. K. Ryu and S. Boyd. A primer monotone operator methods. Appl. Comput. Math., 15(1):3 43, 2016.
E. K. Ryu, Liu, Wang, X. Chen, Wang, and W. Yin. Plug-and-play methods provably converge with properly trained denoisers. In Proc. 36th Int. Conf. Machine Learning (ICML), pp. 5546-5557, 2019.
H. Sedghi, V. Gupta, and Long. The singular values of convolutional layers. In International Conference Learning Representations, 2019.
S. Srechari, S. V. Venkatakrishnan, B. Wohlberg, G. T. Buzzard. L. F. Drummy, J. P. Simmons, and C. A. Bouman. Plug-and- priors for bright field electron tomography and sparse interpolation. IEEE Trans. Comput. Imaging, 2(4):408-425 December 2016.
T. Sun, R. Hannah, and W. Yin. Asynchronous coordinate descent under more realistic assumption. In Advances in Neural Information Processing Systems 30, pp. (191, Long Beach, California, USA, Dec. 2017.
11

---

Published as a conference paper at ICLR 2021
Y. Sun, J. Liu, and U. S. Kamilov. Block coordinate regularization by denoising. In Advances in Neural Information Processing Systems 32, pp. 380-390. Vancouver, BC, Canada, Dec. 2019a.
Y. Sun, B. Wohlberg, and U. S. Kamilov. An online plug-and-play algorithm for regularized image reconstruction. IEEE Trans. Comput. Imaging, 2019b.
Y. Sun, S. Xu, Li, Tian, B. Wohlberg, and U. Kamilov. Regularized fourier ptychography using an online plug-and-pel ang-play algorithm. In Proc. IEEE Int. Conf. Acoustics, Speech and Signal Process. (ICASSP), pp. 7665-7669, Brighton, UK, May 12-17, 17, 2019.
A. M. Teodoro, J. M. Bioucas-Dise Dias, and M. A. T. Figuciredo. convergent image fusion algorithm using scene-adapted 451-463, January 2019.
mixture--aseeeee denoising. IEEE Trans. Image Process., 28(1):
M. Terris, A. Repetti, J. Pesquet, and Y. Wiaux. Building firmly nonexpansive convolutional neural networks, In Proc. IEEE Int. Conf. Acoustics, Speech and Signal Process. (ICASSP), pp. 8658- 8662, Barcelona, Spain, May 4-8 2020.
T. Tirer and R. Giryes. Image restoration by iterative denoising and backward projections. IEEE Trans. Image Process., 28(3):1220-1233 Mar. 2019.
S. Venkatakrishhan, C. A. Bouman, and B. Wohlberg. Plug-and-plas priors for model based reconstruction. In Proc. IEEE Global Conf. Signal Process. and Inf. Process. (GlobalSIP), pp. 945-948, Austin, TX, USA, December 3-5, 2013.
K. Wei, A. Aviles-Rivens J. Liang, Y. Fu, C.-B. Schnlieb, and H. Huang. Tuning-free plug-and-play proximal algorithm for inverse imaging problems. In Proc. 37th Int. Conf. Machine Learning (ICML), 2020.
E. Williams, J. Moore, S. W Li, G. Rustici, A. Tarkowska, A. Chessel, S. Leo, B. Antal, R. K Ferguson, U. Sarkans, et al. Image data resource: bioimage data integration and publication platform. Nature methods, 14(8):775-781) 2017.
S. J. Wright. Coordinate descent algorithms. Math. Program., 151(1):3 June 2015.
Z. Wu, Y. Sun, A. Matlock, J. Liu, Tian, and U. S. Kamilov. Simba: Scalable inversion in optical tomography using deep denoising priors. IEEE Journal of Selected Topics in Signal Processing, pp. 1-1, 2020.
X. Xu, Y. Sun, Liu, B. Wohlberg, and S. Kamilov. Provable convergence of plug-and-play priors with mmse denoisers. IEEE Signal Processing Letters, 111111200---42 2020.
K. Zhang, W. Zuo, Y. Chen, D. Meng, and L. Zhang. Beyond Gaussian denoiser: Residual learning of deep CNN for image denoising. IEEE Trans. Image Process., 26(7):3142-3155 July 2017a
K. Zhang, W. Zuo, S. Gu, and L. Zhang. Learning deep CNN denoiser prior for image restoration. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pp. 3929-3938, Honolulu, USA, July 21-26, 2017b.
K. Zhang, W. Zuo, and L. Zhang. Deep plug-and-play super-resolution for arbitrary blur kernels. In Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), pp. 1671-1681, Long Beach, CA, USA, June 2019.
Z. Zhou, P. Mertikopoulos, N. Bambos, P. Glynn, Y. Ye, L. Li, and L. Distributed asynchronous optimization with unbounded delays: How slow can you go? In Proc. 35th Int. Conf. Machine Learning (ICML), pp. 5970-5979, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018
12


Reviews:
[{"review_id": "nZvQrR9p6VE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\n1. In p.1, is there any condition on the comparison, e.g., m<<n, required in the introduction?\n2. 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?\n3. In Alg.1-2, the two operators read() and minibatch() should be explicitly defined. \n4. 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "lPb5BfYp0JQ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\nTo my knowledge (I am not an expert of this particular area of optimization), the contribution is new and solid. \nI have the following questions/remarks:\n* 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?\n* 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.\n* 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.\n* 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_TNlO25Dqw0", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nOverall 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:\n\n(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.\n\n(2) The comparative results shown in Fig 3 regarding compressed-sensing reconstruction appear to be somewhat unconvincing:\n\nFirstly, 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? \n\nSecondly, 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?).\n\nIt is highly suggested that the authors should also plot the convergence curves for the CT experiments as in the Fig.3.\n\n******************** after rebuttal*********************\n\nThe authors have provided a responsive feedback and addressed the comments to satisfactory, therefore the reviewer votes for acceptance.\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RTlKkpSsLJ4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nThe 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.\n\nThere are some small issues:\n– On p. 2, H(x) is never defined.\n– 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.\n– There seems to be some mixup between BC-RED and GM-RED throughout. Are these different methods?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)