Provably Accelerated Imaging with Restarted Inertia and Score-based Image Priors
Authors: Marien Renaud
Julien Hermant
Deliang Wei
Yu Sun
Venue: ICLR 2026 Poster (2026)
Keywords: Image reconstruction
accelerated iterative algorithms
regularization by denoising
score-based image prior
restarted inertia
Primary area: optimization

Abstract: Fast convergence and high-quality image recovery are two essential features of algorithms for solving ill-posed imaging inverse problems.
Existing methods, such as regularization by denoising (RED), often focus on designing sophisticated image priors to improve reconstruction quality, while leaving convergence acceleration to heuristics. 
To bridge the gap, we propose Restarted Inertia with Score-based Priors (RISP) as a principled extension of RED.
RISP incorporates a restarting inertia for fast convergence, while still allowing score-based image priors for high-quality reconstruction.
We prove that RISP attains a faster stationary-point convergence rate than RED, without requiring the convexity of the image prior.
We further derive and analyze the associated continuous-time dynamical system, offering insight into the connection between RISP and the heavy-ball ordinary differential equation (ODE).
Experiments across a range of imaging inverse problems demonstrate that RISP enables fast convergence while achieving high-quality reconstructions.

Published as a conference paper at ICLR 2026
PROVABLY ACCELERATED IMAGING WITH RESTARTED INERTIA AND SCORE-BASED IMAGE PRIORS
Marien Renaud'; Julien Hermant's ; Deliang Wei?; Yu Sun? 'University of Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251, F-33400 Talence, France JJohns Hopkins University, Baltimore MD, USA (deliang, ysun214] y8jh.edu
mmarien.renaue julien. hermant ) @@ath. u- u-bordeaux.fr
ABSTRACT
Fast convergence and high-quality image recovery two essential features of al- gorithms for solving ill-posed imaging inverse problems. Existing methods, such regularization by denoising (RED), often focus on designing sophisticated im- age priors to improve reconstruction quality, while leaving convergence acceler- ation heuristics. To bridge the gap, we propose Restarted Inertia with Score- based Priors (RISP) as principled extension of RED. RISP incorporates restart- ing inertia for fast convergence, while still allowing score- baaee image priors for high-quality reconstruction. We prove that RISP attains faster cuttionary-poine convergence rate than RED, without requiring the convexity of the image prior. We further derive and analyze the associated continuous-time dynamical system, offering insight into the connection between RISP and the heavy-ball ordinary differential equation (ODE). Experiments across range of imaging inverse prob- lems demonstrate that RISP enables fast convergence while achieving high-quality reconstructions.
INTRODUCTION
Imaging inverse problems aim to recover an unknown image from its undersampled, noisy mea- surements. These problems arise in many domains, ranging from low-level computer vision to biomedical imaging. Since the measurements often cannot losslessly specify the underlying image, the problem is inherently ill-posed. standard remedy is incorporate image priors regularize reconstruction and promote high-quality solutions (Rudin et al. 1992 Mallat 1999 Elad & Aharon
2006).
There has been considerable interest in using image denoisers as priors in iterative reconstruction algorithms (Zhang al.) 20176). This interest continues to grow with the recognition of the con- ceptual link between denoisers and the score function used in generative diffusion models (Efron 2011 Song & Ermon 2019 Song et al. 202T). Regularization by denoising (RED) (Romano al,, 2017 is such a framework that uses off-the-shelf denoiser to approximate the score (i.e., the gra- dient of the log-density) of the implicit image prior encoded by that denoiser. When equipped with deep image denoisers, RED methods have been shown to achieve excellent imaging performance in various imaging problems (Metzler et al. 2018 Wu et al. 2020 Iskender et al. [2023] Guenned let al. (025). Similar results have also been achieved by closely related class of algorithms known
as plug-and-play priors (Venkatakrishnan et al. 2013 Sreehari et al. 2016).
However, RED methods inherently iterative optimization procedures and can need large num- ber of iterations; this can result in substantial runtime on problems that require real-time processing or involve large-scale data. While considerable interest has been devoted design sophisticated de- noising priors to improve reconstruction quality (Renaud et al. 2024 Wei et al. 2024 Martin et al.) 2024). fewer attention has been given to convergence acceleration and is often handled through heuristics (Sun et al. [019a]] Tang & Davies 2020). A key challenge is that incorporating learned priors typically renders the problem nonconvex, limiting the applicability of classical acceleration techniques developed for convex settings.
"Equal contribution.

---

Published as a conference paper at ICLR 2026
Contributions. In this work, address the gap by proposing a novel Restarted Inertia with Score- based Priors (RISP) method. RISP significantly extends RED by integrating a restarted inertia technique to provably accelerate convergence, while still allowing the use of advanced score-based priors for high-quality image reconstruction. We present two algorithmic instantiations of RISP, termed RISP-GM and RISP-Prox, based on gradient and proximal formulations, respectively. Under practical assumptions, we establish for both algorithms stationary-pote convergence at the rate of Onn=//7) surpassing the ((2) rate of RED. Notably, our analysis does not require score-based priors to be convex, thus accommodating those parameterized by deep neural networks. We further derive and analyze the continuous dynamical system underlying RISP, and show that RISP-GM and RISP-Prox correspond to alternative discretizations of the second-order heavy-hall ordinary differ- ential equation (ODE). We experimentally validate RISP across range of linear and nonlinear inverse imaging problems. In particular, our results show that RISP can enable substantial accelera- tion (up to 24x) for large-scale image reconstruction.
2 BACKGROUND
Inverse Problems. We consider the general inverse problem y A(x) + in which the goal to recover æ E Rd given the measurements y E RT The forward operator : Rd - R models the response of the imaging system, and E RT represents the measurement noise, which is often assumed to be additive white Gaussian noise (AWGN). One popular inference framework for solving inverse problems is based on the maximum a posteriori (MAP) estimation
i E arg max = arg argmin {F(z) == f(z) + g(z)); zER*
(1)
mERd
where f= llgpl(y-))) is often known as the data-fidelity term and g -log p as the regular- izer. Commonly, the data-fidelity is set to the least-square loss f(x) (A/2)lly A(x) 12 which
corresponds to the Gaussian likelihood y a ~ ((A(x)) (1/A)))
Regularization by denoising. RED is widely used framework that employs an image denoiser D : Rd - Rd model prior, where a > controls the denoising strength. In RED, the noise residual Du (z) is used as an surrogate for the gradient of an implicit regularizer. Two popular RED algorithms are the RED gradient method (RED-GM)
at + x 11 (v)()) + +(x - -D(()))
and the RED proximal method (RED-Prox)
x prox, , 17 =(x Dz)
(3)
where > O is the weighting parameter and r 0 the stepsize. The two algorithms differ in their treatment to f. where the former computes the gradient Vf. while the latter evaluates the proximal map prox,,)(2)
arg min f | - 2|| + (z())} The detailed formulations of both algorithms are summarized in Appendix G By Tweedie's formula (Efron, 201T). when D2 is the minimum mean squared error (MMSE) denoiser, the noise residual equals to the scaled version of the prior score
S(z) -a Dx)
where S Rd + RRd denotes the score induced by the denoiser. When we fix r = 1/a². RED can be
interpreted as a score-based method (Reehorst & Schniter 2019 Laumont et al. 2022. Sun et al. 2024). The empirical success has motivated theoretical work on the convergence properties of RED algorithms. Recent works have analyzed their fixed-point convergence (Cohen al.) 202T Sun
et al. 2021), ,, interpreted RED as a MAP estimator (Hurault et al.] 2022a Laumont et al. 2023) ) or established convergence guarantees for stochastic RED (Laumont et al.] 2023) Renaud et al. 2024).
Our work complements these efforts by providing formal analysis of accelerated convergence under restarted inertia.
Plug-and-play priors (PnP). PnP is an alternative framework that exploits denoisers priors, inspired by the mathematical connection between proximal operator and MAP denoiser (Venkatakr- ishnan et al. 2013). Its key idea is replace the proximal operator in an iterative algorithm directly
with D, to impose the prior information. The applications and theory of PnP have been widely
studied in (Zhang et al. 2017a| Ahmad et al. 2020 Wei al. 2020
Zhang al. 2022
Wei al.
2

---

Published as a conference paper at ICLR 2026
Algorithm RISP-GM
Algorithm 2 RISP-Prox
Require: x= x² E R.. K E N. 0.0
Require: x- x
RR. K E.N. 0.
(0, 11. and B 2 0
(0, 1J. and B 2
1: while 5 k < K do
while 0 S do
2:
z" = x² +
(2 xx-1) (Vf(z²) 5(x²))
2:
x² +11 (x xx x=-1) S]5((=)))
Inertia
3:
x k+ x² 17
*+1 prox,s
4:
h
k
4:
k = k
5:
if ff
+x 2/12> B² then
if D | xx 1//1
B then
6:
w x x k =0
6:
x x² hi ==b
Restart
end if 8: end while
8: end while
9: Ko = arg min $1 11a x²1
Kg = arg min 1. SASK
||x k++ x=1|
10: return 2 Ko+1 Σ Kg 2
10: return Ko+I Σ k=
2
k=0
2022 and (Chan et al. 2016 Buzzard et al. 2018 Ryu et al. 2019 Sun et al. 2019b] Sun et al.
2021 respectively; see also a review in (Kamilov al. 2023). Recently, (Park et al. (025) showed that the denoiser in PnP can also be formulated as score function, rendering PnP as basee method. While we develop RISP through the extension of RED, our framework and analysis can potentially be applied to PnP as well.
Inertial acceleration for RED/PnP. Several recent works have investigated the use of inertia (i.e. momentum) in RED/PnP (Kamilov al. 2018, He et al. 2019; Tan et al. 2024] Wu et al.) [024] Chow et al. 2024). These adaptations include an inertia update before applying the gradient and de- noiser, detailed discussion on these works strate the practical effectiveness of inertia, convergence analysis with an explicit accelerated rate remains missing. Our work fills the gap by establishing provable accelerated convergence rate.
provided in Appendix A While these works demon-
Proving such acceleration is challenging due to the nonconvex nature of the score-based priors. has been shown that the of inertia does not improve the worst-case convergence Lipschitiz-continnon gradients (Carmon et al., 2020). Our analysis is motivated by recent advances nonconvex optimization, which rely on the Lipschitz-onntinuuu Hessian condition (Carmon al. 2017b Jin et al. 20188] Li & Lin 2023); we discuss in Section 5 that such property is satisfied in many imaging applications. We note that the continuous-tine limit of inertial acceleration offers complementary insights et [ieee] Aujol et al.] [2023 [0223]2024b] /Attocc et al.) [202]] Shi et al. 202T; Li et al.] [0044] [eermant et al. 2024]] Gupta Wojtowytsch 2025). Our analysis further investigate this aspect by bridging the discrete RISP algorithms with the continuous-time
under general
heavy-ball ODE.
Relationship to diffusion models (DMs). DMs (Ho et al. 2020 Song et al. 2021) have recently emerged as a powerful tool for solving imaging inverse problems. Unlike PnP/RED, which seeks MAP estimate via optimization, DM-based solvers aim to sample from the posterior distribution ((=ly)) Recent works have investigated various strategies for incorporating the likelihood term
ply x:) into the diffusion process (Chung al. 2022a Zhu et al. 2023 Song et al. 2023 Mardani et al. 2023). Despite progress in linear inverse problems (Dou & Song 20244) provable posterior sampling under general settings remains open. A key element shared by both DM and RED is Tweedie's formula, which connects the score function with a denoiser. This implies that score networks from pre-trained diffusion models can be used within RISP.
RESTARTED INERTIA WITH SCORE-BASHE PRIORS
RISP addresses slow convergence by leveraging an inertia update paired with restarting mecha- nism. We begin by discussing this central component and then present two algorithmic instantiations of RISP.
3

---

Published as a conference paper at ICLR 2026
The first mechanism in RISP is inertial step. approach to accelerate convergence is given by
Consider RED-GM as example. A natural
2 = x (1 - -) x x7)
(4)
x = (Vf(z) ((()))
where accounts the inertia from the previous update = and parameter 0 E (0, 1] controls the inertial contribution. When RED-Prox variant follows analogously.
reduces to normal RED-GM. Note that the corresponding
Nevertheless, accumulated inertia can cause instabil- ity and undesirable overshooting, especially in noncon- vex cases (0 (O'dono Candes) 2013); this behavior causes the theoretical limitation in establishing faster con- vergence rates. The top panel of Figure I presents an in- tuitive illustration. To address the problem, RISP further employs a restarting mechanism (Li & Lin (223) that re- sets the inertia whenever the accumulated relative error since the last restart exceeds threshold
Terget
Region
shoot
RISP w/o Restart
Target Ragion
shoot
if
x
x²12
x'
B
(5)
then
x
RISP
where > is user-defined constant. Once triggered, (5) clears accumulated inertia and forces RISP to rely on the local gradient, which helps prevent overshooting and deviation from stationary points. The bottom panel of Figure conceepullll illustrates this behavior.
Figure I: Conceptual illustration of how restarting stabilizes inertial algorithms. Without restarting, accumulated inertia can cause overshooting and escape from stationary points (lop). Restarting clears inertia and enforces local gradient up- dates to prevent overshooting (bottom).
We derive RISP-GM and RISP-Prox as two algorithmic instantiations RIPS, extending RED-GM and RED-
Prox, respectively. The algorithmic details of both algo- rithms are summarized in Algorithms [ where the inertia and restarting steps are highlighted in color. Unlike the original RED algorithms in (2) and (3), RIPS directly employs pre-trained score function as the negative gradient of a regularizer, which streamlines both the theoretical anal- ysis and the empirical implementation. In the next section, analysis shows that the restarting mechanism enables provable accelerated convergence under the nonconvex score- score-based priors.
4 THEORETICAL ANALYSIS
In this section, we analyze the convergence behavior RISP. We first derive explicit convergence rates for RISP-GM and RISP-Prox, showing they reach stationary points faster than their RED counterparts. Next, we analyze the underlying continuous-time dynamics of RISP to provide com- plementary insights into its behavior.
4.1 CONVERGENCE RATES OF RISP-GM& & RISP-PROX
Assumption 1. The score function S R -> Rd is a gradient field, i.e., there exists a regularizer such that = Vg.
The assumption formally connects the score function with regularizer. In practice, one can imple- ment such deep score function using the gradient step denoiser technique proposed in (Hurault al. 2022a)
Assumption 2. (i) The data-fidelity term f has an Lipischhttz continuous gradient, i.e., for all a.y E Rd. [ Vf(y)) Lr|x -aaa-yll y (ii The score function S is Lipschitz continuous with constant Lii namely, regularizer has a L,- Lipschitz continuous gradient. Throughout the paper, set = T. T.g.
4

---

Published as a conference paper at ICLR 2026
Assumption 2(1) is standard condition that can be satisfied in most imaging applications. Assump- tion ii) is also practical because it only assumes the existence of the Lipschitz constant. One can enforce this condition by employing Lipschitz activation functions. We refer to Apendix G.1 for detailed discussion.
To facilitate discussion, present the convergence rate of RED as baseline. The following propo- sition states the result for RED-GM; the result for RED-Prox can be found in Appendix C
Proposition 1. Let Assumptions T 2 hold and ll I/T. Then, with most iterations, RED-GM outputs point a such that
Ao vn
IVF
= OOn
where Ao V and AF F(x²) min F. We recall that x. is the inifialization.
The detailed proof is provided in the appendix. The proposition shows that RED-GM approximates a stationary point at the rate of O(n 11/3). which consistent with classic nonconvex results for gradient descent. The same convergence rate also holds for RED-Prox.
We now establish faster convergence rates for the RISP algorithms. Our analysis requires an addi- tional assumption the second-order properties of the data-fidelity term and of the score function.
Assumption 3. (i) The data-fideltyy term f has an py-Lipschitz continuous Hessian, i.e. for all x. y E Rd | f(z) - f(yill S - yll- (ii) The score function is Lipschitz Jacobian con- tinuous with constant Pgi namely, regularizer g has a Pg -Lpischhiitz continuous Hessian. Throughout the paper, we set == Pf + Pg-
This assumption is standard in analyses of accelerated methods for nonconvex problems (Carmon et al. 2017a: Agarwal et al., 2017: Li & Lin 2023) Marumo & Takeda 2024). We note that As- sumption 3(1 holds for all linear inverse problems with AWGN. Even when the forward model is nonlinear, the assumption could also be satisfied; one example is the Rician denoising problem presented in Section
While Assumption Bi) may seem strong, we stress that the condition can be satisfied in practice by combining gradient-step denoisers and Lipschitz activation functions. In Appendix we present a proposition that formally establishes the existence of Pg for such score functions. Importantly, both Assumption 2 (i) and 3(ii) do not assume the convexity of score-based priors
G
Theorem 1. Let Assumptions
3 hold. Let n 1/(4L). B= Velp. 0 4(Epn)))//4 E (0, 1), and K 8-1. Then, with at most n. iterations, RISP-GM ouiputs a point such that
[VF < 82: On -/7),
where 24/T 4/7 p/7 + 1.2 1
The proof of the theorem is provided in Appendix D which extends that (Li & Lin 2023] Theorem 1) to the RISP setting. Theorem establishes that RISP- GM approximates stationary point the rate of OOn which is clearly faster than the (nn1/22 rate attained by RED.
The second theorem analyzes RISP-Prox. The proximal step introduces additional analytical chal- lenges. Specifically, it requires uniform lower bound on the curvature of the objective to control the proximal mapping. To address this issue, we introduce the following assumption.
Assumption 4. The data-fidelity term is convex, and the regularizer g is v-weakly convex, i.e., g + A/8 11-112 is convex.
Note that / convex for all linear inverse problems with AWGN. As g is already assumed to be Ly Lippschii,, it follows that g is weakly convex with v S Lg (Zhou 2018 Assumption 4 defines specific lower bound on the eigenvalues of the Hessian matrix of g.
Theorem 2. Let Assumptions 1 hold. Let v & 8(Ep) n 1/(8L), = (E)(
0 1(1p E (0, 1), and K 0-1, Then, with at most n iterations, RISP-Prox outputs a point
such that
[VF(2)] S 45c = 4n-7//),
where
( 71 41.
-4
5

---

Published as a conference paper at ICLR 2026
The proof of the theorem is provided in Appendix E Theorem establishes Theorrmm[stablishess comparable accelera- tion guarantee for RISP-Pre Prox to that given for RISP-GM, yielding the same O(n-1/7) convergence. Together, the two theorems rigorously show that both RISP-GM and RISP-Prox achieve improved convergence rates relative to their RED counterparts.
4.2 CONTINUOUS-TIME ANALYSIS
We further study the continuous--iig -ime system associated with RISP. We begin by first establishing the connection between RISP and the heavy ball ODE. Under Assumption [ we can show that inertial part of RISP algorithms (lines 2-3 in Algorithms 1 T is governed by
G + oze + V F (a:)) = O,
(6)
where a == (o and we recall that F = f + where g is defined by the score 5. A detailed derivation can be found in Appendix[[] Equation (6) defines the heavy ball equation (Polyak) 1964). whose solution (2;))22 can be thought as a rolling object on the landscape of F, subject to some friction parameterized by a.
However, the heavy ball ODE does not account for the restarting mechanism used in RISP. To address this, we introduce a restarted variant of (6). which is summarized in Algorithm 3 The system follows the heavy-ball dynamics until a restart criterion is met, which point the inertia (i.e., the velocity term) reset to zero. This continuous restarted ODE gen- eralizes the discrete RISP-GM and RISP-Prox al- gorithms and thus bridges the continuous and dis- crete perspectives. In particular, RISP-GM can be viewed as the Euler discretization of the continuous RISP dynamics, while RISP-Pro corresponds to the forward-backward discretization where the proximal step computes the backward gradient. We note that continuous RISP serves as a general formulation and can inspire the development of other dis- crete acceleration algorithms.
Algorithm 3 Continuous RISP
Initialize 20,0 E Rd. $o.0 = 0, k = 0. while mmax do
while t | ds S B² do
{ follows
Kt + a + V (F(x).)) =
end while
h = k 1. 1,t=
00, = Lt,hs L0,4+1 =0 end while
The following theorem establishes the convergence guarantee for continuous RISP.
Theorem 3. Let Assumptions and 3 hold. Consider the (xf)120 running for a total execution time T R4. Define the output & the average â Jo x. "EK T; dt, where Ko arg min, F [mm] | |
2.ll Set the parameters as (Ep) Tmax (Ep)-1/4 and B = Velp. Then, under these conditions, the gradient norm satisfies
FFF()]I < O(T-4/7),
AF with 2 24/T 4/7 4/T T- 1/7 2
T
The complete proof is provided in Appendix F3 Theorem 3 states that continuous RISP approxi- mate a stationary point at the rate of (7T-4/T) which is consistent with the (n-4//7 convergence achieved by discrete RISP algorithms. Note that the Lipschitz continuity of the gradient not re- quired in the theorem. In fact, this condition is often introduced in discrete analyses for selecting a stepsize that preserves the property of the continuous dynamics. However, the Musschtzz-eessine assumption is essential here, as it ensures that when the process stops, the final point has small gradient norm.
5 EXPERIMENTS
We now present our experimental results, which are organized around three goals. First, we vali- date the accelerated convergence of RISP on linear inverse problems that satisfy assumptions, providing empirical support for the theoretical guarantees. Second, we apply RISP to a nonlin- inverse problem where assumptions do not hold, demonstrating the method's robustness

---

Published as a conference paper at ICLR 2026
Deblurring
Inpainting
SISR
MRI
10
RISP-Prox 10
10
100
RISP-GM
RED-Prox
RED-GM
10
10
10
10
29
27
29
32
PSNR (dB)
18
13
24
Iterations 200 0
Iterations 1500
lterations 250
Iterations 500
Figure 2: Visualizations of the gradient-norm (top row) and PSNR (bottom row) curves for RISP and baseline methods on four linear inverse problems. All curves are averaged over the test dataset, and the z-axis shows the iteration number. By employing the restarted inertia, RISP achieves faster convergence without compromising the performance.
beyond the ideal setting. Third, evaluate RISP a large-scale image reconstruction task to highlight its practical efficiency. All hyperparameters are manually tuned to maximize the peak signal-to-noise ratio (PSNR); additional experimental results, hyperparameter robustness studies, and implementation details are provided in Appendix G The source code is publicly available at https:/// com/ Hopkins
con//ookins CIG/RISP
5.1 LINEAR INVERSE PROBLEMS
We validate our theorems on four linear inverse problems including image deblurriig, inpainting, single image super--esolutton (SISR), and magnetic resonance imaging (MRI). In these tasks, the data-fidelity terms satisfy all the assumptions under AWGN, We refer to Appendix G.2 for the technical details and additional results.
Experimental setup. We set the inertia parameter to 8 = 0.2 for RISP algorithms. We note that RISP is robust to this choice the restart mechanism enhances stability; Figure [6 in appendix. We employ a score function defined as S = V The associated regularizer is given by Go (ax) - 2/22 [==)) where N, is the DRUNet (Zhang al., 2021). Note that this implementation of fulfills all required assumptions: see Proposition 2 in appendix for a formal proof. We use the pretrained model provided in (Hurault et al. 2022a) in our experiments.
Results. Theorems establish the convergence of RISP to stationary point with accelerated rate compared with RED. his is illustrated in Figure 2 for the considered linear inverse problems. In the first row, the averaged gradient norm is plotted against the iteration number. It is clearly shown that RISP achieves faster decay of gradient norm than RED iteration. Specifically, in the deblurring task, the gradient norm by RISP has decreased by five orders of magnitude within 200 iterations, whereas RED decreases by only three orders.
RISP achieves accelerated convergence without compromising reconstruction quality. The second row of Figure 2 plots PSNR values against iterations for RISP and the baseline methods. These plots shows that RISP achieve comparable PSNR values RED but in much fewer iterations. For example, RISP reaches the same PSNR roughly five times faster than RED in the MRI experiment. Overall, these results support the theoretical guarantees acceleration and demonstrate the prac- tical effectivness RISP across diverse tasks. We additionally provide visual comparisons of the reconstructed images in Appendix G.2

---

Published as a conference paper at ICLR 2026
GT
(A)
33
(D)
(C)
PSNR
25.25
27.61 JB
PSNR (dB)
TROL
(B)
Noisy
(C)
(D)
(A)
RISP-Prox
RISP-GM
RED-Prox
t= 10
RED-GM
20.73 d6
29.43 dB
31.55
20
0
Runtime (ms)
1 1,600
TROL
Figure 3: Left: Visualization of PSNR curves for RISP and baseline methods on the Rician denoising task with noise level 25.5/255. The x-axis shows runtime in milliseconds. RISP-Pre SSS-PProx reaches 31.55 dB in 160 ms, whereas RED-GM requires roughly ten times longer to achieve comparable performance. Right: Visual comparison of reconstructions produced by each algorithm after 160 milliseconds. Zoomed-in regions highlight residual noise and artifacts. Note how RISP-Prox yields a substantially cleaner, nearly noise-free reconstruction within this time budget.
5.2 NONLINEAR INVERSE PROBLEM
We further investigate the robustness of RISP on the problem of Rician noise removal. Note that the problem is nonlinear, hence leading to nonconvex data-fidelity term f that violates Assumption required for RISP-Prox. On the other hand, we can show that f still has Lipschitz continuous gradient and Hessian, namely, satisfy Assumptions 2 We refer to Appendix G.3 for formal propo- sitions and additional technical details.
Experimental setup. We employ the same score-based prior construction in the linear problems, thereby satisfying Assumptions 3 and validating Theorem [
We evaluate the methods on the
CBSDIO dataset with Rician noise level of 25.5/255.
Results. Figure compares the reconstruction performance for RISP and the baseline methods. The left panel plots the PSNR curves against runtime in milliseconds (ms), while the right panel visualizes the reconstructions obtained at 160 ms. First, the runtime plot demonstrates that RISP-Prox converges even though the data-fidelity term is nonconvex, indicating its robustness be- yond ideal settings. Second, both RISP variants achieve high PSNR values substantially faster than RED-GM and RED-Prox. For example, RISP-Prox reaches 31.55 dB in 160 ms, whereas RED-GM requires roughly ten times longer to achieve comparable performance.
Visual comparisons the 160 ms timestep further corroborate the results. Reconstructions by RED-GM and RED-Prox remain visibly noisy, while RISP-GM produces cleaner images with fewer artifacts, and RISP-Prox yields sharp denoising with weel-preeerved edges. The zoomed-in regions highlight these visual differences. Overall, these results demonstrate the superior reconstruction quality RISP under tight time constraints. In the context of Rician denoising, our method nearly reaches the level of real-time processing (the persistence of human vision is around 100 ms).
5.3 TIME-EFFICIENCY FOR LARGE-SCALE IMAGING
We finally highlight the acceleration benefit enabled by RISP for reconstructing large-scale images. Here, we consider the inverse scattering task that arises in various imaging applications such as tomographic microscopy (Choi et al. 2007). digital holography (Brady et al. 2009 Pellizzari et al. 2020), and radar imaging (Liu et al. 2016 The task aims reconstruct the permittivity contrast distribution an object from measurements of its scattered field captured by an array of receivers. We refer the readers Appendix G.4 for additional technical details on the problem.
8

---

Published as a conference paper at ICLR 2026
PSNR (Runtimet)
26.34 dB (480 minss F3
28:22 da (20 mins] 8
Grounctruth
REDK
RISP-Prox
13:41 d8
25.81 dB (480 mins K
28. 54 d8 (20 mins)
Backprojection
BED-GM
RISP-GM
Figure 4: Visual comparison the reconstructions by RISP and baselines for the inverse scattering task, where the underlying image has a size of 1024 x 1024 pixels. All algorithms are ran until convergence or after reaching the maximum runtime (480 minutes). With only 20 minutes, RISP algorithms restore clear structures and fine details; the other hand, RED algorithms still cannot provide a comparable result after 480 minutes. Note the substantial difference in the PSNR values and visual differences highlighted in the zoomed-in regions.
30
100
Relarive Error
PSNR (dB)
RISP-Prom RISP-GM
RED-Prox
20
RED-GM
10" 10
=z=20
Runtime (minutes)
480
Runtime (minutes)
Figure 5: Visualization the PSNR and relative error curves achieved by RISP and baselines. The relative error is computed by |a+*1 x= |=/[[=]= and is plotted in the log-scale. The æ-axis shows runtime minutes. Note the fast convergence of RISP algorithms to high-quality reconstructions.
Experimental setup. The dataset is generated using the CytoPacq Web Service WWiesner et al. 2019). comprising cell images with a digital resolution of 1024 x 1024 pixels. The score prior is implemented using DRUNet (Zhang al. 2021), trained 500 cell images of size 384 x 384 pixels; we handle the resolution mismatch via patch-based processing. We use 360 receivers and 240 transmitters, and add AWGN with standard deviation 10-4
Results. visually compares the reconstruction quality obtained by RISP and baseline meth- ods. Since the compressing ratio is m/d d 360 240/ 10242 8.2%. the problem is severely ill- posed. This is evidenced by the poor reconstruction obtained by the conventional back-projection method. As shown in the zoomed-in regions, The RED algorithms still reconstruct a blurred nu- clear envelope despite 480 minutes of runtime. In contrast, both RISP-GM and RISP-Prox recover fine cell-wall structures and detailed features near the nuclei only 20 minutes. The visual results clearly show that RISP methods can significantly accelerate the reconstruction while maintaining high imaging quality.
Figure 5 demonstratts the fast convergence of RISP by plotting curves of PSNR values and relative errors. As shown, both RISP variants show rapid, stable convergence as well as steady decrease in relative error. This empirical trend matches the theoretical acceleration established in Theorems 2 Furthermore, we observe that the acceleration becomes more pronounced on this large-scale recon- struction task. In particular, RISP-GM and RISP-Prox converge least twenty-fout times faster than RED-GM and RED-Prox. We attribute this speedup to higher per-iteration costs. When each iteration is more expensive, reducing the number of iterations could produce larger gain in runtime.

---

Published as a conference paper at ICLR 2026
6 CONCLUSION
In this work, we propose RISP as an extension of the popular RED framework for imaging inverse problems. RISP achieves provably faster convergence while remaining compatible with score-based image priors for high-quality reconstruction. The central component of RISP is the restarted iner- tia mechanism, which employs inertial updates for acceleration but uses the restarting strategy to prevent instability and overshooting. We theoretically analyze the convergence of RISP, showing that it achieves an accelerated rate of On 4/7) over RED. We also provide a continuous-tinn inter- pretation that connects RISP with the heavy-ball dynamics and offers complementary insights into the speed-up. Extensive experiments demonstrate that RISP algorithms substantially reduce recon- struction time while preserving competitive image quality, highlighting the theoretical and practical benefits of integrating restarted inertia with score priors
Limitations. Our acceleration guarantees rely on Lipschitz regularity conditions, which excludes some problems such as Poisson denoising. In addition, RISP introduces hyperparametens (e.g., inertial weights 0 and restarting threshold B); while our experiments show robustness across wide ranges, some manual tuning may be needed in practice.
ACKNOWLEDGMENT
This work was supported in part by the ANR project PEPR PDE-AI and the French Direction Générale de I' A'Armmment (DGA). Experiments reported in this paper were carried out using com- putational resources from the PlaFRIM experimental testbed (httss//www.plafrim.. ), supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP, and the Conseil ré- gional d' Aquitaine and from the Advanced Research Computing at Hopkins (ARCH) core facility (rockfish.jhu.edu) supported by the National Science Foundation (NSF) under grant OAC-1920103.
REPRODUCIBILIIY STATEMENT
All theoretical proofs are provided in the appendix. Additional technical details on the experiments are also provided the appendix.
ETHICS
We do not notice any ethical concerns in this work. We used public data in all experiments. Large language models (LLMs) were used for grammar checking and polishing.
REFERENCES
Naman Agarwal, Zeyuan Allen -Zu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedingy of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199, 2017.
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 Process. Mag., 37(1):105 116, 2020.
Teodoro Alamo, Daniel Limon, and Pablo Krupa. Restart fista with global linear convergence. In 2019 18th European Control Conference (ECC), pp. 1969-1974. IEFE, 2019.
Vassilis Apidopoulos, Nicolò Ginatta, and Silvia Villa. Convergence rates for the heavy-ball con- tinuous dynamics for non-convex optimization, under polyak-lojasiewicz condition. Journal of Global Optimization. 84(3):563-589) 2022.
Hedy Attouch, Zaki Chbani, Jalal Fadili, and Hassan Riahi. First-order optimization algorithms via inertial systems with Hessian driven damping. Mathematical Programming, pp. 1-43, 2022.
Sean-Francodd Aujol, Charles Dossal, and Aude Rondepierre. Optimal convergence rates for nes- terov acceleration. SIAM Journal on Optimization, 29(4)3331-33553 2019.
10

---

Published as a conference paper at ICLR 2026
Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Convergence rates of the Heavy- Ball method under the tojasiewicz property. Mathematical Programming, 198(1):195-25) 2023.
Jean-François Aujol, Luca Calatroni, Charles Dossal, Hippolyte Labarrière, and Aude Rondepierre. Parameter-free fista by adaptive restart and backtracking. SIAM Journal on Optimization, 34(4): 3259-3285, 2024a.
Jean-François Aujol, Charles Dossal, Hippolyte Labarrière, and Aude Rondepierre. Heavy Ball momentum for non-strongly convex optimization. arXiv preprint arXiv:2403.06910 2024b.
Jean-François Aujol, Charles Dossal, Hippolyte Labarrière, and Aude Rondepierre Fista restart using an automatic estimation of the growth parameter. Journal of Optimization Theory and Applications, 206(2):51, 2025.
Frank Bowman. Introduction to Bessel functions. Courier Corporation, 2012.
David J Brady, Kerkil Choi, Daniel L Marks, Ryoichi Horisaki, and Schoon Lim. Compressive holography. Optics express, 1701539130,0-11449, 2009.
G. Buzzard, S. H. Chan, S. Srechari, and C. A. Bouman. Plug-and play unplugged: Optimization free reconstruction using consensus equilibrium. SIAM J. Imaging Sci., 11(3):2001-2220, 2018.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "Convex until proven guilty": Dimension-frea acceleration of gradient descent non-convex functions. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learming Research, pp. 654-663, PMLR, 06-11 Aug 2017a.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. "convex until proven guilty": Dimension-fie acceleration of gradient descent on non-convex functions. International con- ference machine learning, pp. 654-663. PMLR, 2017b.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programmingg 184(1-2)) (1-2):7 11122221112222 1-120, 2020.
Stanley H. Chan, Xiran Wang, and Omar A. Elgendy. Plug-and- admm for image restoration: Fixed point convergence and applications, 2016.
/tttpp:://axxiv.orr//bbbb www.:orgg/aabb/l//oo
01710
Wonshik Choi, Christopher Fang- Yen, Kamran Badizadegan, Seungeun Oh, Niyom Lue, Ramachan- dra R Dasari, and Michael S Feld. Tomographic phase microscopy. Nature methods, 4(9):717- 719, 2007.
Tsz Ching Chow, Chaoyan Huang, Zhongming Wu, Tieyong Zeng, and Angelica I Aviles-Rivers Inertial proximal luffereence-o--comeee algorithm with convergent bregman plug-and-pla for non- convex imaging. arXiv preprint vrXiv:240.00326. 2024.
Hyungjin Chung, Jeongsol Kim, Michael T Mccann, Mare I. Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. arXiv preprint arXiv:2209.1448 2022a.
Hyungjin Chung, Bycongsu Sim, Dohoon Ryu, and Jong Chul Ye. Improving diffusion models for inverse problems using manifold constraints. Advances in Neural Information Processing Systems, 35:25683-2565 25696, 2022b.
Regev Cohen, Michael Flad, and Peyman Milanfar. Regularization by denoising via fixed-point projection (red-pro). SIAM J. Imag. Sci., 14(3):137-11466, 2021.
Marina Danilova, Anastasiaa Kulakova, and Boris Polyak. Non-monotone behavior of the Heavy Ball method. In Difference Equations and Discrete Dynamical Systems with Applications: 24th ICDEA, Dresden, Germany, May 21-25, 2018 24, pp. 213-230. Springer, 2020.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780-8794 2021.

---

Published as a conference paper at ICLR 2026
Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse problem solving: A filtering perspective. In The Tweifth International Conference on Learning Representations, 2024.
Bradley Efron. Tweedie's ' formula and selection bias. Journal of the American Statistical Associa- tion, (06(496):1602--) 160--114, 2011.
Michael Elad and Michal Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image processing, (5(12):3736-3745 2006.
Olivier Fercoq and Zheng Qu. Adaptive restart of accelerated gradient methods under local quadratic growth condition. IMA Journal of Numerical Analysis, 39(4):2069-2)) 2019.
Yuan Gao, Wenhan Guo, and Yu Sun. Neural inverse scattering with score- regularization. In 2025 IEEE Conference on Computational Imaging Using Synthetic Apertures (CISA), pp. 1-5, 2025. doi: 10.1109/CISA444433.22222 210.94444..22221111555...... 10015577
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1):267- 305, 2016.
Hákon Gudbjartsson and Samuel Patz. The rician distribution of noisy mri data. Magnetic resonance in medicine, 34(6):9009114, 10-914, 1995.
Antoine Guennec, Jean-Frangee Aujol, and Yann Traonmilin. Joint structure-texture low- dimensional modeling for image decomposition with plug-and-play framework. SIAM Journal on Imaging Sciences, 18(2):1344-1371, 2025.
Sergey Guminov, Alexander Gasnikov, and Ilya Kuruzov. Accelerated methods for weakly-quasi convex optimization problems. Computational Management Science, 20(1):36, 2023.
Huiyuan Guo, Juan José Maulén, and Juan Peypouquet. A speed restart scheme for a dy- namical system with hessian-driven damping and three constant coefficients. arXiv preprint arXiv:2412.0669,, 2024.
Kanan Gupta and Stephan Wojtowytsch. Nesterov acceleration in benignly non-convex landscapes. In International Conference on Learning Representations, 2025.
Tao He, Yasheng Sun, Biao Chen, Jin Qi, Wenhai Liu, and Jie Hu. Plug-and-play inertial forward- backward algorithm for poisson image deconvolution. Journal of Electronic Imaging, 28(4): 043020-043020, 2019.
Julien Hermant, Jean-Franggan Aujol, Charles Dossal, and Aude Rondepierre. Study of the be- haviour nesterov accelerated gradient in a non convex setting: the strongly quasar convex case. arXiv preprint arXiv:2405. 2024.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1894-1938. PMLR, 2020.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-68.5 2020.
Tao Hong, Yaniv Romano, and Michael Elad. Acceleration of red via vector extrapolation. Journal of Visual Communication and Image Representation, 63: 102575, 2019.
Samuel Hurault, Arthur Leclaire, and Nicolas Papadakis. Gradient step denoiser for convergent
plug-and-play In International Conference on Learning Representations (ICLR' 22), 2022a.
Samuel Hurault, Arthur Leclaire, and Nicolas Papadakis. Proximal denoiser for convergent plug-
and-play optimization with nonconvex regularization. In International Conference on Machine Learning, pp. 9483-9505. PMLR, 2022b.
Berk Iskender, Mare L. Klasky, and Yoram Bresler. Red-psm:
Regularization by denoising of partially separable models for dynamic imaging. In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), pp. 10595-10604 October 2023.
12

---

Published as a conference paper at ICLR 2026
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International conference on machine learning, pp. 1724-1732. PMLR, 2017.
Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042 1085. PMLR, 2018.
U Kamilov, H Mansour, and B Wohlberg. Hlug-nnd-play fista for solving nonlinear imaging inverse problems. JEEE Signal Processing Letters, 2018.
Ulugbek S. Kamilov, Charles A. Bouman, Gregery T. Buzzard, and Brendt Wohlberg. Plug-and- play methods for integrating physical and learned models in computational imaging: Theory, algorithms, and applications. IEEE Signal. Proc. Mag., 40(1):85-97, 2023.
Jungbin Kim and Insoon Yang. Unifying nesterov's accelerated gradient methods for convex and strongly convex objective functions. In International Conference on Machine Learning, pp. 16897-16954. PMLR, 2023.
Rémi Laumont, Valentin De Bortoli, Andrés Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. Bayesian imaging using plug & play priors: when langevin meets tweedie. SIAM Journal on Imaging Sciences, 15(2):701-737, 2022.
Rémi Laumont, Valentin De Bortoli, Andrés Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. On maximum a posteriori estimation with plug & play priors and stochastic gradient descent. Journal of Mathematical Imaging and Vision, 65(1):140-163, 2023.. 2023.
Anat Levin, Yair Weiss, Fredo Durand, and William T Freeman. Understanding and evaluating blind deconvolution algorithms. In 2009 IEEE conference on computer vision and pattern recognition, pp. 1964-19899 1971. IEEE, 2009.
Bowen Li, Bin Shi, and Ya-xiang Yuan. Linear convergence of rithms without knowledge of the modulus of strong convexity. SIAM Journal Optimization, 34 (2):2150-211)) 2024.
accelerated algo-
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polyloga- rithmic factor in the in the o (opsilon"(-7444) complexity. Journal of Machine Learning Research, 24(157):1-37, 2023.
Dehong Liu, Ulughek S Kamilov, and Petros T Boufounos. Compressive tomographic radar imaging with total variation regularization. In 2016 4th International Workshop on Compressed Sensing Theory and its Applications Radar, Sonar and Remote Sensing (CoSeRa), pp. 120-123. IEEE, 2016.
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
Morteza Mardani, Jiaming Song, Jan Kautz, and Arash Vahdat. variational perspective on solving inverse problems with diffusion models. arXiv preprint ar X345:23300.043311, 2023.
David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proceedings eighth IEEE international conference on computer vision. ICCV 2001, volume 2. pp. 416-423. IEEE, 2001.
Ségolène Tiffany Martin, Anne Gagneux, Paul Hagemann, and Gabriele Steidl. Pnp-flow: Plug- and-play image restoration with flow matching. In The Thirteenth International Conference on Learning Representations, 2024.
Naoki Marumo and Akiko Takeda. Parameter-free accelerated gradient descent for nonconvex min- imization. SIAM Journal on Optimization, 34(2):2093-2120, June 2024. ISSN 1095-7189, doi: N0.1133722m154099 URL UtI.htt:://dd /wwp:/x/xxddiii///////o//./ org. /00 1.00..115550 1137 1113/22222221 2207/22222543443
Juan José Maulén and Juan Peypouquet. A speed restart scheme for a dynamics with hessian-driven damping. Journal of Optimization Theory and Applications, 199(():831-88) 2023.
13

---

Published as a conference paper at ICLR 2026
Juan Jose Maulén, Huiyuan Guo, and Juan Peypouquet. A continuous- model to interpo- late between speed and function value restart in accelerated first order methods. arXiv preprint arXiv:2506.1 12267, 2025.
C. Metzzle, P. Schniter, A. Veeraraghavan, and R. Baraniuk. prDeep: Robust phase retrieval with flexible deep network. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 3501-3510, 10-15 2018.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical programming, (75(1):9-1077, 2019.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o11/k²). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2013.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal-dual ac- celerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, 36(4):773-810 2021.
Peter Ochs, Alexey Dosovitskiy, Thomas Brox, and Thomas Pock. On iteratively reweighted al- gorithms for nonsmooth nonconvex optimization in computer vision. SIAM Journal on Imaging Sciences, 8(1):331-372, 2015.
Kaito Okamura, Naoki Marumo, and Akiko Takeda. Heavy-ball differential equation achieves o(e-T/4 convergence for nonconvex functions. arXiv preprint arXiv:2406.06//0 2024.
Brendan O' d'onoguue and Emmanuel Candes. Adaptive restart for accelerated gradient schemes. Foundations of computational mathematies, 15(3)7715-732, 2015.
Chicago Y Park, Yuyang Hu, Michael T McCann, Cristina Carcia-Cardona. Brendt Wohlberg, and Ulugbek S Kamilov. Plug-and-play priors as score-based method. In 2025 IEFE International Conference on Image Processing (ICIP), pp. 49-54. IEEE, 2025.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS 2017 Workshop Autodiff. 2017. URL httpt::://// htt.:/aas.ssmmmiscccccccccccocoo org/CorpusID: 40027675
Casey J Pellizzari, Mark F Spencer, and Charles A Bouman. Coherent houg-and-play: digital holo- graphic imaging through atmospheric turbulence using model-based iterative reconstruction and convolutional neural networks. IEEE Transactions on Computational Imaging, 6:1607-1621, 2020.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Compu- fational Mathematics and Mathematical Physics, 4(5):1-17, 1964. ISSN 0041-5553. doi: htips: (hooloog||..ooo00001111555556111
URL https: wtw.wwwwieeeeeieeettttttt.eeeeee com/
E. T. Reehorst and Schniter. Regularization by denoising: Clarifications and new interpretations.
IEEE Trans. Comput. Imag., 5(1):52-67, March 2019.
Marien Renaud, Jean Prost. Arthur Leclaire, and Nicolas Papadakis. Plug-and-play image restora- tion with stochastic denoising regularization, In Forty-first International Conference on Machine Learning, 2024.
Marien Renaud, Valentin De Bortoli, Arthur Leclaire, and Nicolas Papadakis. From stability of langevin diffusion to convergence of proximal meme for non-log-concave sampling. arXiv preprint arXiv:2505. /4177, 2025.
Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regularization by denoising (red). SIAM Journal Imaging Sciences, 10(4): 1808-88444 2017.
14

---

Published as a conference paper at ICLR 2026
Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-2) 268, 1992.
Ernest Ryu, Jialin Liu, Sicheng Wang, Xiaohan Chen, Zhangyang Wang, and Wotao Yin. Plug-and- play methods provably converge with properly trained denoisers. In International Conference Machine Learning, pp. 5546-5557, PMLR, 2019.
Bin Shi, Simon S Du, Michael Jordan, and Weijie J Su. Understanding the acceleration phe- nomenon via high-resolution differential equations. Mathematical Programming, pp. 1-70, 2021.
Jonathan W Siegel. Accelerated first-order methods: Differential equations and Iyapunov functions. 2019.
arXiv preprint
Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse-guided diffusion models for inverse problems. In International Conference Learning Representations, 2023.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, volume 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021.
S. Sreehari, V. Venkatakrishnan, B. Wohlberg, G. T. Buzzard, L. F. Drummy, J. P. Simmons, and
C. A. Bouman. Plug-and-play priors for bright field electron tomography and sparse interpolation. IEEE Trans. Comput. Imag. 2(4):408-44) Dec. 2016.
Weijie Su, Stephen Boyd, and Emmanuel J. Candès, A differential equation for modeling nesterov's accelerated gradient method: theory and insights. Journal of Machine Learning Research, 17 (153):1 13,, 2016. URL http::/ jmlr.
html
Yu Sun, Jiaming Liu, and Ulugbek Kamilov. Block coordinate regularization by denoising. Ad- vances in neural information processing systems, 32, 2019a.
Yu Sun, Brendt Wohlberg, and Ulugbek S Kamilov. An online plug-and-play algorithm for regular- ized image reconstruction. IEEE Transactions on Computational Imaging, 5(3):395-40S 2019b.
Yu Sun, Jiaming Liu, Yiran Sun, Brendt Wohlberg, and Ulugbek Kamilov. Asyne- A prov- ably convergent asynchronous block parallel stochastic method using deep denoising priors. In International Conference on Learning Representations, 2021.
Yu Sun*, Zihui Wu* Xiaojian Xu*, Brendt Wohlberg, and Ulugbek S. Kamilov. Scalable plug-and- 2021.
play ADMM with convergence guarantees. IEEE Trans. Comput. Imag.,
Yu Sun, Zihui Wu, Yifan Chen, Berthy T Feng, and Katherine L Bouman. Provable probabilistic imaging using score-based generative priors. IEEE Transactions on Computational Imaging, 2024.
Hong Ye Tan, Subhadip Mukherjee, Junqi Tang, and Carola-Bibiann Schönlicb. Provably convergent Boug-and-play quasi-newton methods. SIAM Journal on Imaging Sciences, 17(2):785 819, 2024.
Junqi Tang and Mike Davies. A fast stochastic plug-and-play admm for imaging inverse problems. arXiv preprint arXiv:2006. /6630, 2020.
Matthieu Terris, Audrey Repetti, Jean- Christophe Pesquet, and Yves Wiaux. Building firmly non- expansive convolutional neural networks. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 8658 8662. IEEE, 2020.
Singanallur V Venkatakrishhan, Charles A Bouman, and Brendt Wohlberg. Plug and and-play priors for model based reconstruction. In 2013 IEEE global conference on signal and information process- ing, pp. 945-948. IEEE, 2013.
Kun Wang and Andre Wibisono. Continuized acceleration for quasar convex functions in non- convex optimization. In The Eleventh International Conference on Learning Representations, 2023. URI.https. http://:////e/eeeeeeeee www.eviwww.eee... www.:neett.orrmmmameyoooeoeeeeee
15

---

Published as a conference paper at ICLR 2026
Deliang Wei and Fang Li. Flexible parameter selection methods for rician noise removal with con- vergence guarantee. International Journal of Computer Mathematics, 99(11):2250-2217 2022.
Deliang Wei, Shiyang Weng, and Fang Li. Nonconvex rician noise removal via convergent plug-
and-play framework. Applied Mathematical Modelling, 123:197-212, 2023.
Deliang Wei, Peng Chen, and Fang Li. Learning pseudo-contractive denoisers for inverse problems. In Proceedings of the 41st International Conference on Machine Learning, pp. 52500-52524, 2024.
K. Wei, A. Aviles-Rivero, J. Liang, Y. Fu, C.-B. Schnlieb, and H. Huang. Tuning-fre free plug-and-pl proximal algorithm for inverse imaging problems. In Proc. 37th Int. Conf. Machine Learning (ICML), 2020.
Kaixuan Wei, Angelica Rivero Jingwei Liang, Ying Fu, Hua Huang, and Carola-Bibiane Schönlieb. Típnp: Tuning-free plug-and-play proximal algorithms with applications to inverse imaging problems. Journal of Machine Learning Research, 23(16): 2022.
Wiesner, Svoboda, M Maska, and M Kozubek. Cytopacq: web-interface for simulating multi-dimensional cell imaging. Oxford University Press, 2019. ISSN 1367-4803. doi: 10.1093/ bioinformaatccs/rr4417.
Emil Wolf. Three-dimensional structure determination of semi-transparent objects from holographic data. Optics communications, (44):153-156 1969.
Z. Wu, Y. Sun, A. Matlock, J. Liu, L. Tian, and U. S. Kamilov. SIMBA: Scalable inversion in optical tomography using deep denoising priors. IEEE J. Sel. Topics Signal Process., pp. 1-1, 2020.
Zhongming Wu, Chaoyan Huang, and Tieyong Zeng. Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration. SIAM Jour- nal on Imaging Sciences, 17(2):1145-1188 2024.
Pengyun Yue, Cong Fang, and Zhouchen Lin. On the lower bound of minimizing Polyak- Eojasiewiez functions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2948- 2968. PMLR, 2023.
Jure Zbontar, Florian Knoll, Anuroop Sriram, Tullie Murrell, Zhengnan Huang, Matthew J Muckley, Aaron Defazio, Ruben Stern, Patricia Johnson, Mary Bruno, et al. fastmri: An open dataset and benchmarks for accelerated mri. arXiv preprint arXiv:1811.000 1.08899, 2018.
K. Zhang, W. Zuo. S. Gu, and L. Zhang. Learning deep CNN denoiser prior for image restoration. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 3929-3938, 2017a
Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang. Learning deep cnn denoiser prior for image restoration. In Proceedings of the IEEE conference computer vision and pattern recog- nition, pp.
2017b.
Kai Zhang, Yawei Li, Wangmeng Zuo, Lei Zhang, Lue Van Gool, and Radu Timofte. Plug-and and-play image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 (66066666-6 2021.
Kai Zhang, Yawei Li, Wangmeng Zuo, Lei Zhang, Luc Van Gool, and Radu Timofte. Plug-and-pla image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):63006633 6376, 2022. doi: 10. 10.1109/PAMM..201.33000 33089914..
Ningning Zhao, Qi Wei, Adrian Basarab, Nicolas Dobigeon, Denis Kouamé, and Jean- Yves Tourneret. Fast single image super-resolution using a new analytical solution for l - la prob- lems. IEEE Transactions on Image Processing, 25(8)33683-3697 2016. doi: 10. 1..1109/1P..011. 2567075.
Hongkai Zheng, Wenda Chu, Bingliang Zhang, Zihui Wu, Austin Wang, Berthy T Feng, Caifeng Zou, Yu Sun, Nikola Kovachki. Zachary E Ross, al. InverseBench: Benchmarking andg-and- play diffusion priors for inverse problems in physical sciences. The Thirteenth International Conference on Learning Representations, 2025.
16

---

Published as a conference paper at ICLR 2026
Xingyu Zhou. On the fenchel duality between strong convexity and lipschitz continuous gradient. 2018.
arXiv preprint
Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Luc Van Gool. Denoising diffusion models for plug-and-play image restoration. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1219-1229, 2023.
17

---

Appendix: Proofs and Additional Experiments
Contents
Extended Related works
18
Preliminaries
19
Convergence Analysis RED
21
Convergence Analysis of RISP-GM
23
Convergence Analysis of RISP-Prox
24
E.T
Proof sketch
24
E,2
Notations
24
................................
E,3
Large gradient mapping in the last iteration of the epoch
25
E,4
Small gradient mapping for the last iterate of the epoch)
................................
28
E.5
When the restarting is not triggered in the K first iterations
33
E.6
Proof of Theorems and
F
Convergence Analysis of Continuous RISP
36
F1
Continous heavy ball
F2
Restarted heavy ball: continous RISP
................................ ................................
E3
Proof of Theorem 3
38
F.4
Convergence analysis of continuous RED
42
G
A Additional Experiments
43
On the denoiser
43
G.2
Linear inverse problem
44
G.2.1
Deblurring
45
G.2.2
Inpainting
46
G.2.3
Single image super resolution
47
G.2.4
MRI.
47
G.3
Nonlinear inverse problem
48
G.4
Large-scale imaging..
G.5
Hyperparameter robustness studies
53
G.5.1
Influence of the inertial strength 0.
53
G.5.2
Influence of the restarting threshold B
54
G.6
RISP with crffuuiionbbsed. score priors
55
G.7
Comparison between RISP and FISTA
55
G.8
Parameter settings for experiments
56
A
EXTENDED RELATED WORKS
Accelerating gradient descent with inertia. In convex optimization, it is well known that adding an inertial mechanism to gradient descent can accelerate the optimization process (Polyak) 1964]
Nesterov [983; 2013 Fercoq & Qu 2019 Su al. 2016). As many applications involve the min- imization of a non-convex function, the study of inertial acceleration in non-convex optimization
has attracted significant interest (Apidopoulos
al.] [022] Yue et al., 2223 Danilova et al. 2020)
Hinder et al. 2020) Gummiov et al.) 2003; Nesterov et al. 2021 Wang & Wibisono 2023 Hermant
ct 2024 Gupta & Wojtowytsch| 2025). Inertial algorithms are often studied on popular class of non-convex functions, namely functions with Lipschitz continuous gradients. In this case, gradient descent finds a point æ IRd such that [V)( < E in most O iteration. Importantly, only under the gradient Lipschitz assumption, this bound cannot be improved using inertia (Carmon et al. 2020). Going one step further, i.e. assuming the Hessian of the function is Lipschitz, accel- eration using inertia has been established (Carmon et al.) [217b]] Jin et al.) 2018 Li & Lin 2023
Marumo Takeda 2024; Okamura et al, 2024). This opens the door to demonstrating the benefits of momentum in applications involving challenging non-convex landscapes.
18

---

Published as a conference paper at ICLR 2026
Previous works on accelerated RED methods. Since RED methods are known to be slower than end-to-end networks for image reconstruction, a lot of efforts have been made to make RED methods more efficient. (Sun et al. (2019)) have focused on reducing the computational cost of regularization by implementing a block-coorde coordinate gradient descent. Alternatively, (Tang & Davies 2020) apply stochastic gradient descent to the data-fidelity term. (Hong al. 2019) modifies the RED algorithm by incorporating vector extrapolation to accelerate it.
Inertia in RED methods. Previous works have proposed to incorporate inertia into the RED frame- work, not only for acceleration but also for improving restoration quality. (Wu et al. 2024) add inertia to enhance restoration quality in deblurring and super-resolution tasks without analyzing the convergence rate. In similar line of work, (Chow et al. 2024) focus on improving the quality for Rician noise removal and phase retrieval. (He et al., 2019) study Poisson noise removal and observe an empirical acceleration with inertial methods. However, no theoretical justification is provided for this acceleration.
Iterative schemes. Our work proposes to adapt the algorithm in (Li & Lin 2023 into the RED framework, An extensive line of research has adapted various optimization schemes to solve prob- lem (T) This includes alternating direction method of multipliers (ADMM) (Venkatakrishnan et al.)
[013|Ryu et al. 2019), proximal gradient descent (PGD) TTerris et al. 2020 Hurault et al., (2022b),
half-quadratic splitting (HQS) (Zhang et al. 2021 Hurault et al., 2022a). stochastic gradient descent
(SGD) (Renaud et al. 2024) or Langevin al algorithms (Laumont et al. 2022 Sun et al. 2024 Renaud
al. 2025).
Restarting methods. To our knowledge, restarted inertia algorithms are first introduced by O'donnghuee & Candes] 2015) in the convex optimization setting. It considers both fixed restart- ing criterion, namely restarting every N iterations, and adaptive ones. Specifically, denoting the iterations by {x* Jk20, we restart if
F(x ((*=+))= > F(x*)
(Function criterion)
xF x - 00.
(Gradient criterion)
The authors observed that these restarting techniques exhibited clear numerical advantage over vanilla inertial algorithms, but lacked strong theoretical guarantees. Using a continuous version of the Gradient criterion, (Su et al. 2016 Section 5) shows that the restarted ODE associated with the following ODE
G -
VF(xx) 0,
converges linearly when u-strongly convex. Without restart, the best achievable convergence rate in this setting is polynomial (Aujol et al.] 2019 Proposition 7). This gives theoretical guarantee of the benefit of restart in the continuous setting. This result of (Su et al. 2016) is extended to more general dynamical systems, restart criteria and geometric assumptions (Maulén & Peypouquet 2023 Guo et al., 2024 Maulén et al. 2025). In the discrete setting, still for ju-strongly convex functions (or slightly weaker assumptions), provable fast convergence of restarted inertia relies fixed criteria. This criterion involves the knowledge of μ (Necoara et al.) 2019 Fercoq & Qu 2019) which can be estimated by algorithms (Alamo al. 2019: Aujol al. 2024a 2025). To our knowledge, it remains to demonstrate that adaptive criteria, such as function or gradient criterion, allows for such convergence speed of the algorithm. Finally, closer our work, in the context of functions with Lipschitz gradient and Hessian, we note (Li & Lin 2023 Marumo & Takeda 2024]. In particular, (Li & Lin, (023) introduced new restart criterion related to the length of the trajectory, see Section []] This restart mechanism allowed to recover the convergence result of algorithms that mixed the inertial mechanism with an alternative step that exploits the negative curvature of the function, thus showing that this procedure can be discarded. We generalize their algorithm for composite optimization, where the objective function the sum of two non-convex function, with RISP-GM (Algorithm [T) and RISP-Prox (Algorithm{)) (). The latter uses the proximal operator, which provides better experimental results. Finally, note that we focus on the Nesterov inertial mechanism and not the heavy ball because the heavy-ball method requires non-trivial averaging step during restart.
B PRELIMINARIES
The following lemmas classical results. We provide their proof for the sake of completeness.
19

---

Published as a conference paper at ICLR 2026
Lemma 1. Let u R² > R. u has Lu Lu-Lisschizz gradient and has Pu Pu-Lipschitz Hessian, then for
any x. y E Rd we have
Lu (i) u u uxx) + (uu(x), y x) + 2 1 -yll
(ii) u (g)) - ( + (u(( y x) + (Vu (x) x). y
22
Pu
y 3
Proof. (i) We define (tt) = u( + fly - x)) for t E R. By the fundamental theorem of calculus, one has
m(y) u(x) = =1( (0))= S.' (1(s)ds= - L/' (Vu(z + s(y -x)),y y x)) ds.
We subtract on each side (Vu(x), y - x), such that
u(y) u(x) - (Vu(x), y x) 1 L/' (Vu(æ + s(y x)) Vu(xx), y x) ds
1 / VVu( + s x)) - Vu(x)) || 11 - x ds
< L 1/' || s(y x) - -x l1y x ds
= =L. yl? /// sds L x yll
where we used Cauchy Schwarz and the L, -upLiscciitz property of Vu.
(ii) We define (tt) = u(w + (yy - x)) for E The proof is similar to point (i), except that we use the second order Taylor formula.
s(1) = + (00))+((00)) + L'' ("(s)ds,
which also writes
2./' (V + s(y- - -))(u=2),
u(y) u(x) - (Vu(x), - x) = -
- z),
x) ds.
z)ds.
We then subtract (y= x) x) on each side, use Cauchy-Sweharz, the property of the operator norm and the Pu Hessian Lipschitz property to get
u(y) u()) (Vu(x) - x) (2)(( x), x))
2 2/ //' ((V2 f(x + sly - 42 (=)) x) y x) do
1
1
// || f(x + s(y- x)) f()) -x)l lly - x || ds
2 2
1
8 <|| f( + s(y x)) <>)(=) 11 x 21 ds
2
Pu | yl // 2ds Pu | y
Lemma 2. Let u. Rd IR be u-weakly convex and differentiable. Then Vax, y e Rd
V || y
u(v) 2 u(x) + (Vu(=). y x)
2
20

---

Published as a conference paper at ICLR 2026
Proof. have
By definition of the weak convexity, f + 5 11.11 is convex. Then, for all æ. y R
f(z) 2 f(y) + (x - y. Vf(y))
u x)) + 2 | 2 u(y) |yal (a y. Vu(y) + vy)
u(y) 2 u(z) + (Vu(z), z) v | y1
2
C CONVERGENCE ANALYSIS OF RED
In this Section, we give a proof of the convergence of 2 stated in Proposition D
This proof's
technique is rather classical (Nesterov 2013, Section 1.2.3). P Tddatss it to the RED-GM framework.
Proposition. Under Assumptions RED-GM in algorithm outputs point & such that
with n. iterations, with n D.
Ao = -OO
|VF())] S
with Ao (2L(F(z)) min F).
Proof. Recall the iterates of RED-GM
aht x (V T(x (z(x))))
Because the score function is defined as S(x) -r - (x))) by Assumption we can write (ar (x))) Vg(æz), such that RED-GM becomes
**+1 = x - f<*") 17 VV(g())) xt v((''
Writing the algorithm in this form allows apply classical gradient descent result. For com- pleteness, we detail the remainder of the proof.
By Assumption 2 F is L L, + Lg Lipschitz. Hence, Lemma (i) can be applied to F at x and y ++1 yielding
F(**) + (VF( - -x*) + L - -
By definition, x k+1 = x - F thus
F(ah+1) < F(a -1 )| Lni
|VF =F((/))=)))))))) (1(a))-(11-2))
(1-22" (n)) 2 |VF(a=*)]
Note that
(1 (1-
Lg 2 2 as long as S +. Then, rearranging and summing over h: = 0,..., n 1,
we get
VF 1| F(x0) - F(x*)
F(x²) min F
Ln
Lg W such that
17
We use the elementary relation Σ km=l
minnke(1......
1 F F(x")
min F In 2
VF(x*))
min kE(L.....s
n 1)
To conclude, noting a == arg mingk wtt.minniee.......... AE(00...x=11 holds
V F((*>>) and fixing " = +. the following
|VF())|
2L(((xx)) - min F).
vn
21

---

Published as a conference paper at ICLR 2026
Existing works studying gradient descent under Assumptions and does manage improve over this convergence speed (Jin et al. 2017). This indicates that assuming the Hessian of the function is Lipschitz does not help achieve faster convergence when only assuming the gradient Lipschitz, making the inertial mechanism crucial to do so. We next show that a similar result is obtained when using RED-Prox instead of RED-GM.
Proposition. Under Assumptions 17 L. outputs a point such that
12 and
RED-PRO, in algorithm with iterations, with
|VF())]
(2(((())) min P²). < Vn
Proof. Because the score function is defined as S(z) -- 1oc-Den Dz())) by Assumption 1 rewrite RED-Prox as a proximal gradient descent algorithm
we can
k+ prox,s (x* 7f Do (xx)) - xh+1 = prox,s (x" - - vV()(=))
Under Assumption and the iterates of this algorithm verify
F( F(x*) S - (1 Ln (w xx
see Ghadimi et al. 2016 Equation 25). Summinng over O,... - 1, we deduce
( - x 1| F(xx) - F(xx))
F(x²) min F
" 1
Ln 2
Ly 1)
2
We use the elementary relation Σx= | (x++1l z²)l| I|| 2 minnee(
/F(=*)|| and not-
, (2 x²6) | we deduce
ing ky == arg minke
Not1 ko
77
F(x") min F
(8)
11-22 Ln
By the caracterization of the proximal operator, we have
(a Natl x0o = -VVg(z"o) - vi(xott
Then, by the smoothness of f (Assumption 2 and 9
we relate the gradient of F to the residuals
V F(x
(artoo) vf(az
fz fo+t) (ax"oo
< V {z( + Vf
ko
+ f ko+1) v f(
S Ro+t 2
+ b No+1 - x to
(10)
+ +
|| ko
Combining 8 and 100. we get
1 5
F(x0)
min F
17
vn
Ln 2
Fixing 1, and noting ã = ku it becomes
[VF() (L(((()))
min F).
Vn
Assumption 4 is only used for the convexity of the data fidelity
22

---

Published as a conference paper at ICLR 2026
D CONVERGENCE ANALYSIS OF RISP-GM
In this section, prove Theorem which establishes the convergence of RISP-GM (Algorithm The key idea that Assumption alllows RISP-GM be reformulated a way that permits the application of optimization result from (L & Lin 2023).
Theorem. Let Assumptions hold. Let q (4L). B= VEip. p. = 4(spn)) E (0, 1), and K K=0 Then, with at most n iterations, RISP-GM outputs a point such that
[VF - 82: On 4/7),
where & = 24/T A L p 1/7 + 1:20-t04
Proof. By Assumption | the third line of Algorithm ! (RISP-GM) writes
z vV "V(""² =² r/VF((²),
where satisfies Assumptions 2 and 3
Then, we can apply (Li & Lin
2023
Theorem 1) to RISP-
iterations. Moreover, it outputs a point & that verifies | F2)]| 82s. So, considering fixed bugdet of iterations, fix
GM, which ensures that the algorithm stops in most ArLi p²
1
L2
2//7 2
T, MT -
4/7
(11)
We plug (51 in the upper bound of the number of iterations, namely Ar et
12 Ep
We have
AFL
AFL
87
24/7 4/7 1217 1 n 4/7 + 12p-in=" nn-
ArL
(12)
(2//7 1,27 12/7p//3=4477 3
72
2
and
L
1
L
E3
2
4/7 + I? nn p) / 12/T
(13)
L2
2
1.pp-In-44
2
Combining 12 and (13) ensures the algorithm ends at most within the fixed budget of n iterations.
Finally, plugging our choice of in the bound |VF(I]| S 82s, we deduce
|[V((2) < 82 2 A A/7
4/7 + 8212 p' in 2/7 p 17
Remark 1. In (Li & Lin 2023 Theorem 1), it is actually stated that the algorithm stops in at that appears in our proof. We believe this precision has been omitted in their original proof because the main term remains the one of order (1-11A))
most p3 =
iterations, without the supplementary term (22
23

---

Published as a conference paper at ICLR 2026
E CONVERGENCE ANALYSIS OF RISP-PROX
This section is dedicated to the proof of Theorem
Theorem. Let Assumptions 7 hold. Let S 8(Ep) -= 1/(8L).
B = 1/(LL), ve/(4p), 0
( E 1), and K 0-1 Then, with at most iterutions, RISP-Prox oulputs point 2
such that
IVF(2) - 45a 1/7
where ε = (2 1/7 4I2 p
E
PROOF SKETCH
The overall strategy of proof is adapted from (Li & Lin 2023 Theorem 1) analyze algorithm 2 We first prove a reformulation of Theorem
Theorem 4. Under Assumptions with
8(Ep)+ + +g. Algorithm with parameter 2 4(Em)2) (0, 1), and K 0-1 outputs point that 2
choice (.gg B
ppt V261
verify V (2) < 45a at most
iterations.
The main challenge stems from the presence of an additional proximal operator in Algorithm 2
First, prove that if the restarting criterion is reached before the maximum number of iterations K, the objective function has a sufficient decrease. This first part of the proof is splitted into two cases, if the gradient mapping at the last iterate before restarting is large (Section E.3)) and if the gradient mapping at the last iterate before restarting is small (Section E.4). The case of small gradient is more
technical due the proximal operator and needs the use of the Hessian Lipschitz property.
Then, this sufficient decreasing property allows us to conclude that an e-stationary point is attained in O(E 4) iterations.
Moreover, we show that the restarting criterion is not reached before the maximum number of iterations K then the output of the algorithm is an E-stationary point (Section E.5
Finally, we show that Theorem 4
reformulation of Theorem
Remark 2. Assuming 0 = 1/ E (0, in Theorem induces the bound e < 256p7
4
E.2 NOTATIONS
As in (Li & Lin 2023). we consider the restart time
k-
K. = min
l:
P 1
1
x1122 B
(14)
We call an epoch of Algorithm 2 all successive iterates {0.... 1}. Using Assumption such that S = Vy, we have that inside an epoch, the iterates of Algorithm 2 verify the following recursive formula
!
x = x + (1 (2 x-11)
(15)
k+1 prox,, , (z (z()(z))
From the definition of the Proximal operator, the following equation is verified
x+1
V V[(x*+1) Vg(z").
(16)
By definition of IC, have
K-1
K21 1,
K.
x - x²11 B².
(17)
1=
24

---

Published as a conference paper at ICLR 2026
It induces control the distance of the k-th iterate to the starting point of the epoch æ0, Ak [0, (C)
k-1
2 k-1
lar - x: 20 =
Σ
x
+1
x²
1 h:
a
++
- x²11 S B²,
(18)
1=
and we have, AA E (0)
|| 1 I 1| x
x
b-11
S 2BB
(19)
where we used that by the definition of zh, one has
1 =1 S 1 11.
(00)
Gradient mapping. When considering algorithms of the form 15 natural to consider the gradient mapping
prox - - V +1) + [/())=
(21)
It can be thought generalization of the gradient in the composite case, as if it reduced to (z()) Importantly, if the gradient mapping is zero, i.e. z" k++ = 0, then
f( ([(***)> Vg(=") vf(x + Vg(x**1) FF =0
Lee we found a stationary point of F, which justifies this analogy.
In the two following sections, we consider two case regarding on the value of the gradient mapping at the end of the epoch xxx xx x|-
E.3 LARGE GRADIENT MAPPING IN THE LAST ITERATION OF THE EPOCH
The goal of this section is to prove Corollary [ which shows that F decrease sufficiently when the
gradient mapping || ||= x x*1| 2 B is large enough.
The following Lemma is prox version of the classic descent Lemma, see e.g. (1.2.19) in (Nesterov) 2013).
Lemma 3. Let xh, z² be the iterates defined in Equation (55) we have for any 2
F(x s F(z*) (1
(2 (2-3)) 3 1
I. || 2/ 2/1
2
with L = Lgg + Lg-
Proof.
F(a
$ SF(2*) (VF(=*) x 1--1-111 =²)
L
x+1 =1
2
= =((z)) (Vg(2*) vf(**), x 2// + L
|| 2
F((*) (Vg(=*) f(x* ++
1+1 - -z - <V/(2 v5(22) x 2²)
L ||ant| -12 -
z²11
2
= F(**)=+ + (
x
r+++1 z
x k+ z²)
(V Vs(*²), e+1 x++1 2/)
17
+ 1 1
L
=
where we use have
(66] in the last equality. Using Cauchy-Schward and the fact that V is L-Lipschitz,
(f(x+t))) vf(**), x
x²) f((
vf(**)]]
| -
< L x+ - 1
25

---

Published as a conference paper at ICLR 2026
Thus obtain the desired inequality
3 2 || 2/112 ( ( 9
F(x*+1) s F(=*)
The following Lemma indicates that the decrease of F at the last iteration of the current epoch can be quantified using the cumulated norms of gradient mapping along these iterates, and the cumulated distance between iterates along this epoch.
Lemma 4. We huve
) - F(x:))
S 2
1
+
K-
+1
xx
nL
3
K 1
2
k
2n
2
2
k==
k=0
Proof. By Lemma] 3 we have
F(x - F(( - -
_11 ||0 - 201
(22)
As F is I-smooth, we have
F(x") 2
2 F(=*) ((=+)+((F((())) (VF(z*), x² - ) 2 - 1011
(23)
Summing Equations 22 and 23 we get
F(x*-1)- F(x**) < - (vF(2*) at - x² + L || x*|
3 L
2
x
2
2
(24)
From the characterization of Equation
16..
making VF(=*) appear we have
x k+1
FF(=*)
(2x
(25)
n
Combining Equations 24 and 25
we have
z x
kt1
#11+
F(x*)
[)(*** v(( xt **)
1)
L
1 11
(1
) ||2 11
11
1
x x - zt) + (V [f( v v)((=t), x - x/)
77
bb 111
1. ||=* - 2422112
+
(26)
2
17
We have the algebraic identity
k+l 2h t 2²
2 1 211 + ||ak 201 -1110 - -000 2²(1²)) (27)
1
Moreover for some X > 0, the Ly Lipschhit continuity of V gives
(V](x*+)) - v tt - =²²)
$ 1 [[((tt)))- - \)(>1)/1+ + 1 1|
=1112 5
AL2 ||
| - =21112- + 22 110 2 2/112
21
(28)
26

---

Published as a conference paper at ICLR 2026
By injecting Equations 27 and 28 into Equation 26 get
))
F(x")
(|
28 111 112 + |
|| 1+*+1
x* (1²) +
x k+1 2/1
21j
||at -
=²11²=
I.
||
x 11
(1
3
L
||_| xx 1|
21
2
2
1
|
x01
-
1
+
1 A
L
|| x11
21
2
17
1
L
||*
x 1|²
2m
2
By using Equation
20
we get
F(a
1
1
+
x T.)
10 x² 11
2n
1
XL3
3 T. ||_ 2
211
2
1
211 + 1 (1 17
2L)
| - 21-
1
L3
3
L
11 - xx+1
21
2n
2L
2
where we fix x = + in the last equality. Using x =x we sum on k: = O,... -
1 (1
F(x
F(x
I
x
k+1
xx
201
+
21 ||0 - x² 11-
21
2 17
K-1 1
3
| x
x +111
21
2
2
k=1
K-2
1
x
b+1
2²1
+ 2
+ 2L
|
2²1(²)
1/1 1 + 2L )
1000
x x11
2m
17
2 17
k=0
1
1
x-1||
11
n13
3
| x 211
21
2m
2
k=U
<
K-2
x
k-1
2²1
x²
1
TT
L
K-1
k
x 1
2m
2
2
k=
k=
Using Lemma 4 we use the restart criterion (44) to ensure the decrease of in the case suffi- ciently large gradient mapping at the last iterate of the epoch.
Corollary 1. If the gradient mapping is large x=- x
2 B, then
B²
F(a*) F(x") <
8rj
Proof. By Lemma 4 we have
F(x²) - -(xx)) s
K-2
x k+1 x x/11
1
nL3
L
K-1
Σ
x
++1
2n
2
2
km0
k=
< L
X-2
1 k+1
x 111
1
n 2
3
L
||
x12
21)
2
2
k=0
27

---

Published as a conference paper at ICLR 2026
If K E || pott x0112 is empty sum, equal to zero. Otherwise, one has
B²
1
T
3
F(a*) - F(x0) < L
L
B
211
2
2
n
3 I
LB
B²
2n
2
3
1
++
L
B²
2
2m
n
3 L
1
L +
B²
2
27
B
811
where we used 1) S ST.
Remark 3. Note that to obtain Corollary 7 it is not necessary that the large gradient mapping occur in the last iterate. This choice of iterate will however be important in the next section, in order to control the distance between iterates at the beginning and end of the epoch, see 29)
E.4 SMALL GRADIENT MAPPING FOR THE LAST ITERATE OF THE EPOCH
The goal of this section is to prove Corollary which shows that F decrease sufficiently when ||x--1- - I < B. Authors of (Li & Lin 2023 use the Hessian Lipschitz Assumption to approx-
imate the function by a quadratic tunction, and the fact that its Hessian matrix is diagonal up to change of basis
In our case considering a sum of two functions and a proximal operator, the choice of the basis must be made carefully.
Preliminary. If the gradient mapping ||a=* xx11|| S B, then from Equation (9) we have
|| x²1 I K-1 00 + 1| x-11|| $ 3B.
(29)
For each epoch, we denote Hg = V2g("" to be the Hessian matrix at the starting iterate x. and H. = UA U to be its eigenvalue decomposition with U, U, Rdxd U and Ag being diagonal. We denote A the jth eigenvalue and ह - _ U y. and Vf(y) f the different objects in the basis of diagonalization for H,-
By Lemma
(ii), have
g(x**) g(x²) - (Vg(x"), x -
-z") + (x x x0)
1
z x x²)=
H
Pg x 113
2
6
(Vg(z"), ), ,.a =0) (xt z0 Ag (5: - 50) + 1 201 (30)
2
9
<g(3g) ((x:)) + pg B3,
where we used Equation 22). and we denote for I E Rd, xy the j-th component of x and t e
((x) = (Vg(x"), x x0) + A,
- x0)=
Σ (z(5z)
j=1
(31)
(t(t) 7,9(20) - Σタ) + + Nj(t 3992
28

---

Published as a conference paper at ICLR 2026
By following the same change of basis for the function f, get
5(x*) f(x²) - (Vf(x"), xx x²) + (xt (0)"H(((z' - =x") + P$ 11x - =10
6
= (V](x"),
), Txxh x0) 2 a "0 - x0) + Pf 11 - x1011
(32)
6
<f( - f(x0) + 2/
where we used Equation 29 and we denote for Rd
f(z)= = f
) (f=")
2 ("""""""""" x²)
1
(33)
By adding Equation (30) and Equation (32p. we have
F(x*) Fxx") S f( F(*)) + 9 2003.
(34)
where we used Equation 29 and F 9 + f.
Writting *++1 8 as inexact forward backward algorithm on F. We show that the iterates v² ++1 _ in the basis of diagonalization of Hg follow inexact forward backward algorithm
on the quadratic function F و + f. up to error term.
By applying the change of basis in equation I3 we get
T kk+1 2t n
Vg(=") - "U""
(35)
zト - - 77 V f( + +70²
(36)
where
jht = -D(3)) + -
U" Vー(ッ) - U U (TV(xx*)))
Then, Algorithm 15 can be written as
= (1- 0 xk-1) gh+1 = prox , (E**) - n5²t)
(37)
To ensure good properties of the iterates of 37 it is necessary to controll the norm of the error as done in the following.
Upper bound on assumption.
The norm of the error term 8* can be controlled using the Hessian Lipschitz
|
Vg( v f(attt) U V'Vg(="))))) U² f(x < -
- ( + ] UT
for x E Rd and For [0, using the Hessian of g is Pg Lipschitz, the fact that |U xl| = ||0|| equation (99) we have
- U'V9(2 |||
Vg(xz) + AG x0) - U Vg(a(=)]]
Vg(x + H x²) - vo(2*)||
( V² V2g(20 0 + +(( - -x") - -H,) (x - x 2d)t
Pg
| z $12 < 2p,
(38)
2
29

---

Published as a conference paper at ICLR 2026
Similarly on f. using equation 29 get
Vf(att1) U U'Vf(x
ff(=") + U U - =0)- - U2 -U- (
Vf((²)) H x²) - vf(x+tt)|
(/, V2 fx= + +1(x0t1 - x0)) - -H,) ( x dct
-
P
|| +1
S pPr B²
(39)
2
By combining equation 39)
and equation 388 we have
-
2p
201
B² S 2033.
(40)
where p:= Pf + Pg.
In the following Lemma, we use the control on g upper bound the decrease of F between the first and last iterate of the current epoch. We will make use of the fact that ğ is separable, thanks to the change of basis.
Lemma 5. Assume H3 = -1-1- -8(pp) à v II. We have
30
8np² B'K
((* S (xx)
x k+1
81
0
Proof. Since 9j (x), defined in equation (3T) is quadratic, we have
2 - x))
9, ) + (V0,
2
Convexity of f induces convexity of f. such that
f(āh-1) < f(0*) + (v) 3. 5*t)
Then, summing over j. using the separability of و we have
f(**t)) Eog = f(5nt)) + g(aht1)= f(x++1))
and
Σ 0z ()(Tgt + (V (V) x 1 -
((3)(()))))))) (V EtH 1/2 -
Combining the three previous equations, we get
=g(=t) (Vg(z*) I*) +
1 Σ
-2p
2
+ + ( 5 - -zh)
=f(a*) + (V)(=t) Vg( xx
x*)
+ 2
Σ
A 1
2pp
+ +( vf( zht
30

---

Published as a conference paper at ICLR 2026
However, by (36). have
Vカ(2") + V/(a _ xh+1 (x
=² -100*)
from which we deduce
F(aht)) S F(x*) + (Vg(z*) )
きz))
+ +
\3 ,
1 1 オ n10% k
In the expression above, only F is not separable. So we have
F 11) - F(th)
- Σ (V - V3 -5) + 12110 2012
(41)
1 (aft) - - - (=)+1 x
(42)
As (T)
(gg( = 25 2))) ) we consider
1
(1))
2//²
2 - z
2n
Aj
1 1))
+
2
<
1
(17))
2/12
- - 2 - - 1イ)
27
1 2 (1 - 1²
for some positive constant a to be specified later, where we use (66 in the first equality.
As we assumed LI > Hg v 11 for all j E (1,...,d d} L 2 > 2 e If < SL. we get that
11
2 - 2 < (-4L + [ 2512 s 0. By injecting these properties into
2n
equation
(1 we have
f(
<f(Tt)
Σ
Σ
k+1 - 15 - mイ)
SF(T
(10) 3pp 1 1
1
53
2
27
2a
2
2n
<p(**) + Σ
(1+ 0) 0)2
2 1
1
+
1
13913)
21
2/11
2
2a
=((x + Σ
(1 + ()(1 - 0)2
a
k+1
185/(
2n
2n
2
20
31

---

Published as a conference paper at ICLR 2026
We have, using x
x0.
()
0)
12
a
Th+
- 5}pp)
21
21)
2
K-1
a
(1 (1
-
|
3311
2m
2
2nj
0=
38
1
81
where we let
in the last inequality, such that
2n
1
0
(1 + (1 - 0)
30
8²
8
38
21
81
2n
81)
21
211
811
So, summing on k = O.....KK KC
we have
K-1
K Σ
F(x*)
S F(x²) + Σ
30
27
+
81
8
k=
k=0
K-1
$ F F(x")
30
2
811
28
k=0
(40 in S. where we use
Lemma 6. Assuming
|| 1=x-1--20 x1 S B, we have
30
8lmp²
Ba K
9
F(x - F(x0) <
+
5033
81,
20
Proof. By Lemma
5 we have
30
K-1
x 11 + 8lnp² B*K K*
((00)- - ((70)
5-
8/1
20
30
x 2 81np2 B*K.
10 b+1
811
20
Using
34
we get
30 K
81mp² B*X
F(x*) - F(x²)
kk+1
1/11
+
+
pBs
81
20
2
k=0
30B²
8lmp² BAK
9
2 BB3
SnK
20
30
81mp2 BA K
9
+
bB3
8nk
20
where the last inequality uses K. < K.
Corollary 2. If the restart criterion is reached at K. <, K, assuming s S 64pyp we have
F(a F(x=)= S
32

---

Published as a conference paper at ICLR 2026
Proof. Combining Corollary and Lemma 0 = 4(Epn))) E (0, 1), and K 8r
and using parameter choice 17
1. B //26
we have
B²
3 E
B²
S
8n
2 vP
81np² B²K K
81
3 8
1/ B²
20
20
29 vp
3 e3
2 2BB
21 Vp
B²
81
2
Such that
30B
81mp2 B*K
B²
F(x*) - F( S - min
2
2B3
8n/
20
811
$ min
16mp
c3 vp
Assuming & S 64pm
1 we have
S 1690
This condition verified as long as S such that
8 256p1
E.5 WHEN THE RESTARTING IS NOT TRIGGERED IN THE K FIRST ITERATIONS
Lemma 7. If the restart criterion of Algorithm not reached, we have
(VF(E)] S 45c.
Proof. The proof follows three steps. First, we bound the quantity step bound the quantity | 21I. which allows to bound the term
V Vg(2) + VS())] The second (
(i) Bounding || Vg((2) + V (+)]l Denote 2 = U 2
U z Ko+T ビ==0
Ko+t
K==
and ē = U Ko+T Σ k=
UT k+1 Ro-I k==
kk+1
Since, و and f are quadratic and
= ~., get
Ko
Vi(7) VV =
VO(=k) (f(a-11)
Ko + 1
k=
Ko
a k+1
z* + m7obk)
(43)
nnKo +)
k=0
1
1 x² (1 -0)(*** xx-1) 1/5
(Ko 1)
Ka
2 Ko+z =" -
-(1- -01--1111
( Ko - )²) +
34
<7KK +
k=0
1
2 Kot1 ko + - Φ + 1
jh
nnKK +1)
k=
0
K
||0 : + +l|
I + 17
|1855
<K +1)
==
2
20B
| Not1
kuoll
+ 2pB²
(44)
nn
33

---

Published as a conference paper at ICLR 2026
Where used in the last inequality the fact that Ko arg min ( IIsAsK-1 equation (T8) and equation (40).
||
-x*1
= KK--1
Moreover, the fact that Ko = arg min $ISASK-1
x²1| gives
1
|100 112
|
x*11
K [K/2]
K/2]
K-1
1
||
xx11²
(45)
K [K/2]
k=0
1
B
2B²
K K/2]
K
K2
where we use in the last inequality the fact that the restarting criterion is not reached at iteration K.
We can now obtain control on [[)(2) + V f())
(V(3)+
+
Vg + V - Vg(=)
-
v
(46)
Using Hessian Lipschitz properties, we already showed in 399
that we have
Vo(3) - (o($)))((3)) < 0g 8 x
2
(47)
f(()) - v((a)
<
Pf
2 x 0 001
(48)
As the restart criterion did not activate for all <
K,
we
have
a x
Ko k+1 22 < B and || .²1 KotI 2k=0
Kn
z x
2B. By injecting
and
48 into 46). we get
2/2B Vg(2) + V((+) - T₁K² nn
20B
+
+ 2pB2 + 2pB2.
Recalling the parameter choice 1)
1 B
F.. 0 =4(mpp)1/1 E (0, 1), and K = = we have
52.
2
2/2B
2V2VE 0² 16v2=
T2²²
n/P
20B
B = 168
n 1
2pB
2
such that
(V) + Vf(()] - (v216 + 16 + 1)s S 40s.
(49)
(ii) Bounding | 2||. Starting from 45). removing the 3 term insider the norm and multiplying
b 17, the exact same computations can be derived to get
Kg
| 211
Σ
k+l
z*
(1
Ko + 01 =='
Ko
Ko +1
2
20B
| #oo ||
K
K
2/BB
20B
+
K2
K
34

---

Published as a conference paper at ICLR 2026
where we used Ko 2 K 2
Recalling the parameter choice 7)
82 2 2.200 0 =4(Epn)))/4
1.
B
3
//22
(0, 1), and K = -.. we have
2/2B 22/202
16
K
262 B 16ne, 20B
K
such that
| 2 - (16+ 16 S 39ne.
(50)
(iii) Bounding [F Note that we have
[F) V Vg(=)]l (V V Vf(#) V
Using the triangular inequality, we get
|VF < V V Vg(E)
S f 12 =1| Vf + Vg(
where the last inequality used the Smoothh property of f. To conclude,
49
50
and
VF
Ly39ns
40c
39 + 40
45c.
E.6 PROOF OF THEOREMS 2 AND
We prove Theorem first. Theorem 2 is a corollary of Theorem 4
Proof of Theorem For each epoch such that the restart criterion is met, we have by Corollary 2
F(w F(x") S
VP
Using that æ is set to be x of the previous epoch, and that min F S [(x for any epoch, summing over N epochs we get
min F - F(x") < -N 5
where init is the starting point x the first epoch. So. noting AF == F(x") - min F, we deduce that the number of epochs N such that the restart criterion is met is upper bounded
APVP
N
leading to a total number of epoch upper-bounded by Ar Since each epoch requires at most
K Kepp
L2
we then deduce there is at most
ArLipt 22ct 7 ensures that this output
gradient
/2
iterations needed before the algorithm stops and output a point 2, Lemma verifies [2)]| < 45s, which concludes the proof of Theorem 4
Proof of Theorem 2, Assume we fix a budget of n iterations. We fix
(2L) ? pt
4L2
F
(51)
n
pm
35

---

Published as a conference paper at ICLR 2026
Aptt
Theorem 4 ensures the algorithm runs for at most this bound. We have
+
1 v2
iterations. We plug 51
V2e4
A p T.
A pT.ppp
/
A (21) 4 pt
V2
41.2 pri
n
A LrLipt p#
(52)
3
(2L) ( 7p
2
n
72
2
and
12
1
V2
EP
22
A
(22)
f pt
41 pn
n
(53)
L
<
V2
412
pro
Combining (52) and (53) ensures the algorithm end at most within the fixed budget n iterations.
Moreover, know from Theorem 4 that the outputs verifies [|VF(())| of E, see (11) we obtain
I 45c, or with our choice
A p
2
VF I 45 22
180
n
pn
F CONVERGENCE ANALYSIS OF CONTINUOUS RISP
Let F Rd + R. The Nesterov accelerated gradient
z = a + (1 - 0n) 1b x k+1 z² - 1/ ((2*)
(NAG)
can be seen discretization of the following continuous dynamical system,
c. + a (x.)) 0,
(DS)
where á., and E, are respectively the first and second order derivative with respect to f E R4, see (Su et al. 2016) for seminal work, or (Kim & Yang 2023 Section B.2.2) for more general result. Equation DS defines damping system, with damping coefficient att). Intuitively, (æ,) is rolling object on the surface defined by the image of f. subject to some friction. The higher (t),, the higher the friction. We will consider the constant friction version, called the heavy ball equation
(Polyak 1964)
G + at, + VF(x.) =.
(HB)
We can think of (xx) in HB as a continuous version of he20 defined NAG with constant sequence for all There are several reasons to study (æ:))20:
1. Dealing with continuous system offers tools that do not exists in the discrete settings, such as derivation, which may leads to smoother computations. If one's goal is to study {a=* J220, one can start to study (æx)22 in order to gain intuition.
36

---

Published as a conference paper at ICLR 2026
2. The dynamical systems can be thought generalization of the algorithms, there exists several way to discretize a dynamical system. By instance, considering the gradient flow equation
á = Va(a)));
(GF)
consider gradient descent x++1 x² FV((x* as explicit discretization of
GF
while the proximal algorithm x++1 = prox,s (x*) = x -, F ((+ can be thought
implicit discretization of GF
F.1 CONTINOUS HEAVY BALL
In this section, we show how the inertial mechanisms of RISP-Prox (A (Algorithm) 2 can be thought as
discretization of the HB equation. The same derivation for RISP- GPM (Algorithm 2 is deduced in
similar way, and has already been done, see (Su et al. 2016 or Kim & Yang 2023 Section B.2.2).
From RISP-Prox Heavy Ball. Under Assumption there exists g which verifies S -Vg.
such that the inertial mechanism of RISP-Prox (Algorithm writes
z² = x² (1 0(1)) x*-1)
x² k+ = prox,; (= [))g)>=))
where we make explicit the dependancy of 0 in the algorithm step-size Because of the characteri- zation of the proximal operator, and the fact that f is differentiable, we can rewrite the following way
z² x + (1 - ((n)) - x 2t11)
(54)
x k+ x² - - 1/ s(
(55)
Merging Equations 54 and 55 we divide by / and rearrange to obtain
x k+1 x
x kk
(1 - 0(n))
(nVa(=**) - VnV f(**+1)
(56)
Vi
V
We want to identify {x* 1220 with continuous curve (ær)1>0 through the identification Dt, = x where (&& keN is a positive and increasing sequence depending of the algorithm stepsize 17. A good choice for (f&)kew is given by ts Viki see (Su et al. 2016). Then, using Taylor expensions, we have
x x+1
Tist1
Ata
1 Tt + tl(l))
tu
+
(57)
V7
Vi
2
k-1
Tt.
St. 1 du.
-1e + +ll/n)) 2
(58)
v
TT
Also, rewriting 54
we get
x
x x
(1 - (n))
= -1 (1-8(m)) + + o(v)))
Multiplying by / each side, we obtain
= + (1 ((n)) / Tha + o(v7)-
This allows to use the Lipschitz gradient property of g. to write
Vg(2*) Vg(x*) ((v7) Vg(x.,,) + +
(59)
By we also have
57
(s b+1
+ -
(60)
Note that precisely in 660 appears that the proximal operator acts as an implicit discretization. In
the case of RISP instead of RISP-Prox, we can replace the computations of (60) by those in (59
Injecting 57 (77-60
60 in (56). we obtain
1 Virrn )-
de +
2V vT olvT) -(())) t
-
(TV
37

---

Published as a conference paper at ICLR 2026
Rearranging, dividing by nn, and using F = f + we deduce
(()) Etg + (F( O(vT).
We can conclude by taking f - O assuming l /
0in) :- a exists.
Remark In the case of p-strongly convex functions with L-Lipschitz gradient, classical choice of (n) 2yp0 1+v/n"" Then, g
0im)
v 2v and we recover the classical choice of friction a(-) of
this setting, see (Siegel 2019).
F.2 RESTARTED HEAVY BALL: CONTINOUS RISP
Inspired by Algorithm in & Lin 2023). we consider the following continuous restart procedure.
Let x E RRd We define ( bER_ such that it verifies (6)
Lt + a + VF(x..1) =0
(HB)
with initial conditions (To.1, t0,1 x0. We then define the restart time
T Tn S || 11 ds B²}.
We define recursively (æI,)ER verifying 6 with initial conditions ((00.,)..00.)))) (1), and
Th = inf((( | ds B²J. Finally, we define (2)) the concatenation of all the trajectories (etaunn such that one has for 0 SOSS Tk
Lt.k-
For some Tmax 0, denote K == arg min (Tmax Jo | ds B²} the number of restart. Below we repeat Theorem for convenience.
Theorem. Let Assumptions [ and hold. Consider the (xf)12 running for a total execu- tion time T R.. Define the output â as the average & = Ko Jo
1. (Ku x FHEK T. dt, where
Ko arg minte| Ergas Timu] | Set the parameters and Velp. Then, under these conditions, the gradient norm satisfies
(sp) Tmax 114)
[VF(#)] 5e = O(T-0(041)) 4/7),
with 24/7 1/T
4/7 T-7/7 1/7 2 T
The theorem proven in the next section. Note that is does not require the Lipschitz gradient Assumption in its proof. However, local Lipschitz gradient property of F, that is the Lipschitz Hessian property, is needed to ensure that each trajectory {æ,t, k KEER, can be well defined.
Remark 5. similar convergence rate for the vanilla heavy ball (6) without restart is provided in OOkamura et al. 2024 Theorem 1), As these authors do not achieve similar result in the discrete setting, Theorem highlights the crucial role of the restart mechanism for (6)
F.3 PROOF OF THEOREM
In order prove Theorem first prove the following intermediate result, which bounds the number of epoch such that the restart criterion is met.
Theorem. Consider (z)) with 144 Tmax = (14) and B = /e/p for some > 0.
Denote K the total number of restarts. Then, K is finite, and defining & Ro So
Ko
x
T, dt
with Ko = arg min U5[
Taps Tmm.]
T,
we have
38

---

Published as a conference paper at ICLR 2026
1. EE T, + Tmax (F( min F) p0=-1/4--10 1/4 (ep))
2. [VF())I S 5c.
From a high perspective, the proof follows similar steps as in the discrete case. We start to show that the total number of restart is of the order ((()) As one epoch ends at S Tax = ((=)) the total amount of running time of the process is O(e-7/A). Interestingly, the latter can be shown without assuming smoothness properties. Finally, it remains to show that the process allows to find point with small gradient norm. This last part requires the Lipschitz property of the Hessian matrix.
Sufficient decrease in each epoch. Similarily to the discrete case, show that each time the restart criterion is triggered, then we have a sufficient decrease of the function value over the epoch.
Lemma 8. Let (z)) verifies HB with initial condition (æo, 0). Assume T T | 1| dt B², for < max We then have
B
F(xr) F(xx)) S
Tmax
Proof. Set the following Lyapunov function
Fg = F(xx)) + ||,bb|12
We differentiate (Er)20
É.
( Fx::), .t) + (d. i+)
HB
(VF(:;), 2t) (i act + VF(x))) = -a [d:
Integrating for E [0, 77, we get
Er - Eg = a L || dt.
Because T' fo ||:a|] dt = B with T s Tmaxo we have
B² S a
B²
| 2 dt aa
Tmax
Finally, noting that assuming do = 0 implies Es- Eu 2 F(IT) - F F(xo), we have
B²
F(xT) F((x)) S Tmax
Lemma 8 will allow to bounds the total number of epochs. Note that in this continuous setting, compared to the discrete setting many things simplify. By instance, there no need use quadratic approximation and to split the space according to the eigenvalues of the Hessian matrix of f. see for comparison Section
Small gradient in last epoch. In this section, we show that in the last epoch, iee. if the restart criterion not triggered for all S Tmax, we can find point with small gradient norm. This part is bit trickier than the previous one, as we need to use different argument from the discrete case. In the discrete case, the linearity of the quadratic approximation was crucial to get the desired result, Section E.S Since such linearity property holds for the gradient in our setting, proceed differently. We begin with Lemma 9 which provides a suitable bound on the average of the gradients.
Lemma 9. Let (x4)22 verifies HB with initial condition do = O. Assume VT E [0, Tmax] one has T So || dt B², Then, defining Ku arg min, Tinx Fnanl || we have
Ko /
2/2B T2
BaB
VF(w.)
<
Tmax
max
39

---

Published as a conference paper at ICLR 2026
Proof.
Ko //
Ko
v (F
=
Ko
(it + (rdi,)de
| do a(xKo
Ko
2a Tmx
Ko
|
xoll: (61)
Tax
where the first equality by definition of (HB
. and the last inequality is by triangular inequality,
using db = 0 and because Kg E TT max Then,
1 Ko
S Ko / || S B²,
Ko zoll
dy
(62)
where the last incquality is because assumed VT E [0, Tmax T So [ dt B², Also, as
Ko arg min Taues Tem] |dbell, one has
Timx
| Ko 11 S Tmax
| dt
Iau
Immex
Lina
| dt
T max
T mox
0
B
2B2
(63)
Tmax
Taa T Tmax
T
max
where used -
| dl <
Injecting (62 and
63 in
61 we obtain
Tam.
Ko /
2/2B
2xB
VF(x,)ds
Ko
T
T Tmax
To conclude we need to bound the gradient of an average of the trajectory. But the gradient is not
linear so VF( Ko _oko x,ds) * Ko fo (F(x,)ds. This is where the Hessian Lipschitz property steps in, as it allows to bound the gap between these quantities. We use the following result.
Lemma 10. Okamura al.
2024 Lemma 1) For let : [0, - Rd. f a p-Lipschitz Hessian function, w [0,4] [0, oo) a measurable function satisfies fo w(s)ds 1, and z =
Jo w(s) (s)ss Then
VF(Z) S ())))V)(((()))
< L./ [=(()]] (f. (olo))(((rr-oddaee - ds.
As in OKamura et al. 2024 we will apply this result with (ZI)ERR = (xt)ER defined by HB but with different choice of weight function w.
Lemma 11. (xx )120 verifies HB with initial condition (æa,, 0). Assume VT E [0, Tmax], one has T S | dt < B2, Then, defining a has
L Sok w,dt with Ko arg min 1e| Tans Inm]] | one Ro
Ko
DB
VF())
VF(x))dt
<
Ko
16
40

---

Published as a conference paper at ICLR 2026
Proof. Applying Lemma 1 Ko
to (a) (xt)eeja, Kol and w(+)
Ko. get
P Ko
(% w(o)w(T)((T o dddodr ds
VF(#)- Ko
V (F
||
2
2
(mm l|ttal? (f² S.a (T- --)ddddd) ds. (64)
Ko
2K
Then, we have
Jo Jo
Ko
Ko
s2
(r o-dddd
T8
dr
2
Ko
Ko
x2
TsdT
dr
2
82
2 (K3 s²)
(Ku 8) 2
sKo(Ko - 5)
where in the last equality we use the elementary fact that a² - b2 = (a + b) - b) for any a, b E R.
The above quantity is maximized for
Ko such that
2
Ko (T- (o-oddodrs S
K3
(65)
8
By injecting
665 into 64
we obtain
Ko J. VF(x.)ds
S Ko /
Ko
VF(
|| ds.
16
Now, because Ko lo | dl < B², we conclude that
1 Ko
I pB²
VF(#)
No
VF(xx)ds
Now, we can prove Theorem 3 Proof of Theorem 3. If
the k-th epoch is such that
Tk
arg inf (e(,,Tra ensures that the following decrease holds
t $o
ds B exists, then Lemma
8 applied to (x (++ 120
+ m
B² Timxx
f T.) f (of (n) S -
-
where we used our choice of parameters. Summing over < K, we get
min - F(x0) S ( ( n.) F(xx") - - - K.
This concludes that K < (F(x:)) min -)2-3/2 In other words, the restart number is upper bounded by (F(x min F) 1)/23/22'/ 12, such that the epoch number is upper bounded by (F(x*)- min -/2 1/2 + 1. In particular, ensures that K < +00. Since epoch duration is at most Tmax (Ep)-1/1 1/4 this means that the process (xf) stops total amount of time upper bounded by (F(x:) min F)5-7/1 11/1
41

---

Published as a conference paper at ICLR 2026
Small gradient norm of the outputs. Now, applying Lemma and Lemma
to
120"
we deduce that in the last epoch such that the restart criterion is not triggered. This because that di with Kg arg min
for & 1 Ko Ko
"
LE( {
Eage
Tume
++
we have
Ko
VF(+)) <
VF(
Ko o
e VF
+ )dt
+
Ko
/
VF
T. )
pB²
2V2B
2aB
16
The
max
According to choice of parameters, have
pB² =
2/2B
2a
e,
2v
2E,
16
16
T
Tmax
max
such that
|F S 5e.
We ready conclude by expressing the result decrease in term of number of iterations.
Result for fixed budget T > 0. We fix a budget of T > 0 computational time. Let
E : p+ (F(x") min F) + + '
(66)
We showed earlier that the total computational running time of the process is most (F(x") min pD)=-//pp//4 + (ep) 11/4 Plugging our choice of of (66), have
-3
(F(=") - min F)s $ pp = (F(x") - min F) (2+p² (F(x*) min F) + 22 22p-11--1)
p
$ (F(x") - min F) (2 (F(x*) min F) - ps
(67)
T
2'
and
(Ep) (2 p² 1 P) + -00--424--7777 -22--17-1) - p- (2 p IT
-T (T-4) 4) - p
(68)
T
Combining 67 and 68 ensures the process ends in at most T computational time. As the output
verifies [V(())
I 5c, then (66) ensures that
|V < 5- 2f (F((") min + +5 2--2"p-'--
F.4 CONVERGENCE ANALYSIS CONTINUOUS RED
As mentioned in the introduction of Appendix F the gradient descent algorithm
k+1 x F)**
(69)
can be seen discretization of a continous dynamical system, namely the gradient flow equation
á = =
(GF)
Under Assumption T the gradient flow equation can be used to formulate a continuous version of
a V f(x)) + S(xz),
(Cont-RED)
where (ontt RED) is gradient flow for VF Vf Vg. This enables to formulate
vergence rate for this continuous version of RED, in order to confirm that the benefit of the inertial mechanism also holds in the continuous setting.
42

---

Published as a conference paper at ICLR 2026
Algorithm 4 RED-GM
Algorithm 5 RRDD-Prx
Require: x² E R n > 0, and 7
Require: x² RR 0, > 0, and
I: k =
k
while
while & < n do
3:
x *++ = x= (Vf((=") + (o(x)))) 1))
3:
a ++ = prox, (x* - --- Do (x(x))
4:
=
4:
k #=
5: end while
5: end while
Ko arg minosken VF('*)]I
Ko = arg minogken [F(a")]]
return Ko
return ~0
Theorem 5. Let (2t)120 be a gradient flow
GF for VF Vf+ Vg. In at most T execution time,
the process achieves point ī such that |VF( F( min ((T-)/2)
Proof. Let
E = F(xx) - min F.
We derivate E,
E, (VF((t), 2) = -1IVF((=)))1
We integrate between 0 and T
L E,ds
L |VF(z)]] dt ET Eo 2 min F F(xo).
Rearranging, and taking the min, we get
T min [VP(x)))) N L [[VF(*)) di < F(oo) min F.
rE(O,T]
Dividing by T, and considering 7 == arg (i (F;);;) 12
we obtain
F( min F
[f(+>))| S
T
The result of Theorem highlights that without the inertial mechanism, we lose the (T--1/7) con- vergence rate (Theorem 3) for a OTT-1/2 convergence rate. Note also that Theorem 5 is consistent with Theorem ! with respectively a convergence rate of 1/2) for the continuous time, and On-1//2 for the discrete time.
Remark 6. As was the when considering the restarted heavy ball equation, there is no need to assume the gradient Lipschitz. In fact, this gradient Lipschitzness is commonly useful to ensure that the discretization preserves the continuous behavior.
G ADDITIONAL EXPERIMENTS
First, we write explicitly below the algorithms RED-GM (Algorithm and RED-Prox (Algorithm for more clarity.
G.1 ON THE DENOISER
In this part, we discuss in detail how the assumptions on the regularization can be verified in practice and which denoiser weights and architecture are used in our experiments.
On the denoiser assumptions. In our experiments (except for linear inverse scattering), we use regularizer Jo proposed by (Hurault al. 2022a)
go (x)
x - No (x))
202
where E Rd and N. is neural network with DRUNet architecture (Zhang et al. 2021
43

---

Published as a conference paper at ICLR 2026
Proposition 2. The regularization 9o (x)
x (=)=)] induces by gradient-step denoiser,
with SoftPlus activations. verifies Assumption
SrpossitionSsshw. that the gradient step denoiser with SoftPlus activations verifies the assumptions that are necessary to obtain convergence guarantees. However, if the activation function is differ- ent, for instance ReLU of eTJJ, then regularization does not necessarily verify the assumption 2 Therefore, the theoretical assumptions are ensured in experiments on deblurring. inpainting, super- resolution and Rician noise removal but not MRI and ODT.
Proof. We assume that 7 has SoftPl uss activation functions. The SoftPlus function is defined for x E R, by
softPlus(r) log (1 +=)).
We have the following derivatives for the Softplus activation function, for R.
|SoEtPlus (x)
+ - S
[SoEtPlus (x)] cosh 2 (x)1 4
[SoftPlus (x) tanh (x) cosh -2 (x)
Because SoftPlus and SoftPlus are bounded, we deduce that SořtPlus(() and SoftPlus (2) are Lipschitz and bounded. Therefore, by composition and sum, JN,, the Jacobian of No. and dzz the differential of J are Lipschitz and bounded.
Then the gradient of the regularization 9r is computed by
V² (ar) = x N₂ (xx) [JN, (z=) (a- - Na())),
with JN, (x)) the jacobian matrix of N, at the point and the Hessian of the regularization is
V go (x) JN. (x) dsz [x]] (x No [JN, (=)) (x)),
where dzg [x] Rd Rdxd is the differential of JN, at point æc thus dzg [a:] (æ= No(x)) e Rdxd
Finally, Assumptions on the regularization are verified.
On the pre-trained weights. For image deblurring, inpainting, super-resolution and Rician noise removal, we use the pre-trained weights proposed in (Hurault et al.) (022b) for GS-DRUNet with SoftP us activation. For MRI reconstruction, we use the pre-trained weights provided (Hurault al. 2022a) trained on gray-scale natural images with eLU activations functions. We do not find pre-trained weights with Soft? ls activations and MRI images, therefore we use these ones. All links to download the weights are provided in the README file of the code.
G.2 LINEAR INVERSE PROBLEM
Experimental setup. For RISP methods, we set the inertia parameter to 0 = 0.2. We note that the algorithm's 's performance robust this choice, as the restart mechanism enhances stability and reduces the need for extensive parameter tuning; see Figure 16 in Appendix G.2.1 We note that due the non-convex nature of the score-based prior, different methods may converge to distinct local solutions, which can lead to different final PSNR values. Details on the calculation of V
and prox, and more results for each problem are given Appendices G.2. G.2.3 The specific configurations for each linear inverse problem are outlined below.
Deblurring, Following (Zhang et al. 2017b; Hurault et al. 2022a), experiments are conducted
on the CBSD10 dataset (Martin al. 2001) with noise level 12.5/255. We use 8 motion kernels from (Levin et al. 2009). 9 x 9 uniform kernel, and a 25 25 Gaussian kernel with o 1.6.
Inpainting Experiments are performed on CBSD68 with 80% of pixels randomly masked and additive Gaussian noise of 1/255.
44

---

Published as a conference paper at ICLR 2026
SISR. We test RISP and baselines CBSDI0. Each image is processed with an anti anti-aliasing blur kernel followed by 2x downsampling. A total of ten motion and fixed kernels are used.
MRI. An 8x undersampling scheme is applied to 10 images from the fastMRI dataset (Zbontar et al. 2018); 4x results are provided in Appendix G.2.4] The k-space noise level is set to 1/255. Due the absence of publicly available MRI-specific models with SoftPlus the score network uses a GS-DRUNet with eLu activations, pre-trained on natural grayscale images.
G.2.1
DEBLURRING
The image deblurring inverse problem can be formulated as
y Aa + n,,
with (O,, oy!) the additive Gaussian noise and = = FFAF Raxd the observation matrix where F the discrete Fourier transform matrix, F its inverse and A a diagonal matrix. The data-fidelity is then defined by
f(x) (000=21144 =114x -yl
And its gradient and proximal operator can be computed in closed-fore using the following formula, for æ E iRd and rj >
V f(x)) = F*A (AFx Fy)
(70)
prox, (x) F* (1+ (1+ F (x 7Ay)
For linear degradation, Assumption on f are verified. However, it is not possible to test in practice the inequality v < On applies.
2/7 L4/7. Therefore, we can not ensure that Theorem
(A) RED-GM (B) RED-Prox (C) RISP-GM (D) RISP-Prox
29
(D)
IC
PSNR (cB)
(B)
(A)
RISP-Prox
RISP-GM
RED-Prox
26.42 26.70
27.76 dB
28.63 dB
RED-GM
t=200
0
Runtime (ms)
1,000
Figure 6: Convergence of RISP methods compared with baselines for deblurring with a noise level of 12.5/255 averaged on CBSD10, and 10 different blur kernels. Time are given NVIDIA 1100 Tensor Core GPU. On right, qualitative restoration of an image after 200 ms. Note that the inertial mechanism allows to accelerate significantly the convergence.
Experimental set-up. As (Zhang al. 201 Hurault et al. 2022a). blur kernels are tested, including the 8 motion kernels proposed by (Levin et al. 22009). 9 x 9 uniform kernel and the 25 25 Gaussian blur kernel with standard deviation 1.6. The noise level is chosen to be ay = 12.5 255. The tested dataset (CBSD10) is composed of subset of 10 images of the CBSD68 data set (Martin et al. 2001).
Figure shows that RISP-Prox achieves 5x acceleration over RED-GM. Qualitative comparisons further indicate that RISP-GM and RISP-Prox recover sharper structures within short time budget (200 ms).
45

---

Published as a conference paper at ICLR 2026
Clean image
Pseudo-inverse
RED-GM
RED-Prox
RISP-GM
RISP-Prox
24.6
37.7 3000ms
37.8 1000ms
37.7 dB 400ms
38.0 dB 200ms
20.0 dB
26.2 1000ms
26.4 1000ms
26.2 4400s
26.2 dB m00ms
24.6 dB
32.6 de 1000ms
32.7 dB 1000ms
32.5 dB 4400ms
32.5 200ms
24.6 d6
26.1 da, 3000ms
25.2 de 1000ms
26.2 dB 400ms
26.3 dB/ 200ms
Figure 7: Qualitative results for image deblurring with various methods after their convergence. Time are computed on a NVIDIA A100 Tensor Core GPU.
Ground Truth Observation
RED-GM
RED-Prox
RISP-GM
RISP-Prox
PSNR
13.09 dB
: 19.42 dB
19.50 dB /B 10s
19.44 dB 4s
19.44 dB/44///15
Figure 8: Qualitative results for image inpainting with 80% random masked pixels and noise level of 0g 1/255 and various methods after their convergence. Time are computed for a NVIDIA A100 Tensor Core GPU.
G.2.2 INPAINTING
For image inpainting, the forward model can be written as
y Ax n,
with n (O, oyla) and A Rdxd, a diagonal matrix with diagonal coefficients in {0, 1}. Then the data-fidelity f(x) | | y2 have the following formula compute its gradient and proximal operator, for æ Rd and 7 > 0,
Vf(x) A (x y) prox,, (x) = (la + nA) (x + 7,Ay)
Experimental set-up. our experiments, we tackle the inpainting problem with 80% random missing pixels. The noise level is chosen be o, 1/255. The validation set is the entire CBSD68 dataset Martin et 2001).
Results. Figure 8 shows the visual results by different methods after convergence. It can be that, RISP-GM accelerates RED-GM by 7.5x, while RISP-Prox has a 10x acceleration over RED- Prox. This clearly show the efficiency of the proposed RISP methods.
46

---

Published as a conference paper at ICLR 2026
Ground Truth
RED-GM
RISP-GM
PSNR
28.94 dB 5s
28.35 dB 2.5s
Bicubic interpolation
RED-Prov
RISP-Prom Prox
20.01 dB
28.4 48 dB 2.5s
28.03 dB 1.8s
Figure 9:
Qualitative results for super-resolution with various methods. On each images, PSNR values and reconstruction time (in second) are provided.
G.2.3 SINGLE IMAGE SUPER RESOLUTION
For image super-resolution, the forward model can be written as
SH x +n
with H E RRdxd the matrix of the convolution with an anti-aliasing kernel of blur, S E Rmxd the standard s-dowsampling matrix, with d s2m and /N(0, ojlm). Therefore, we have following gradients and proximal operator for the data-fidelity f(x)) = H|SHH - yll, given by (Zhao et al. 2016), for æ E Rd and > 0,
Vf(z) ST (SHx y)
prox (x) = 32 F'A' (Ia (la+ 1u++"AA) AM*) AFz,
with = x x H y, A block-diagonal decomposition of the downsampled matrix in the Fourier domain and F the discrete Fourier transform matrix.
Experimental set-up. We study 2x super-resolution with 10 blur kernels introduced in the de- blurring experiment with a noise level of ay = 1/255. The tested data set (CBSD10) is composed of subset of 10 images of the CBSD68 data set (Martin al. 2001).
G.2.4 MRI
For Magnetic Resonance Imaging (MRI), the data-fidelity term can be expressed in the same form as deblurring, with a matrix A whose diagonal entries belong to (0, 13. Consequently, the formulas in (70) remain valid in this setting.
Experimental set-up.
our experiments, we tackle the MRI reconstruction problem with 4x and 8x acceleration. The noise level in the k space is chosen to be σ, 1/255. For validation, use 10 knee images from the FastMRI dataset (Zbontar et al. 2018), following the same protocol as in (Sun et al. 2019a).
Results. Figure 10 demonstrates that RISP-GM and RISP-Prox yield comparable qualitative recon- structions par with RED-GM and RED-Prox, while exhibiting faster convergence. The quanti- tative results for 4x acceleration are reported in Figure [T] In particular, RISP-Prox is the most efficient among the compared methods.
47

---

Published as a conference paper at ICLR 2026
Clean image Pseudo-inverse
RED-GM
RED-Prox
RISP-GM
RISP-Prox
31.82 dB / 10s
32.04 dB
2.5s
32.17 dB 25
32.05 dB 1.95
30.20 dB 10s
30.29 dB 2.5s
30.09 dB 25
30.22 dB / 1.95
30.99 / 10s
30.78 dB 2.5s
31.02 dB /B/23 2s
dB /
33.14 dB 10s
33.13 dB 2.5s
33.38 dB 25
33.32 dB / 1.9s
Figure 10: Visual results for 8x MRI reconstruction by RISP and baselines. For each image, PSNR values and reconstruction time (in second) are provided. Compared with the baseline methods, RISP can significantly accelerate the MRI reconstruction, while maintaining the reconstruction quality.
36
10
Relative Error
PSNR (dB)
RISP-Prox
RISP-GM
RED-Prox
28
RED-GM
10
0
Runtime
10
0
Runtime (s)
10
Figure 11: PSNR and relative error curves on with 4x MRI reconstruction by RISP methods and baselines. The colored area 25%-75% quantiles for the relative errors 1=*+11 xx |=|[|/
G.3 NONLINEAR INVERSE PROBLEM
In this section, provide additional details for the Rician noise removal task. Let Teraa and Timmg denote two i..d. Gaussian noises with zero mean and standard derivation oy. The Rician noise corrupted observation y is obtained by:
M )
n iimag
According to (Gudbjartsson & Patz
9995
the conditional probability density function (PDF) of
y oz
x
+ y2
x y
ply xr) =
exp
To
20
48

---

Published as a conference paper at ICLR 2026
which is known Rice Rician distribution. Here Ig the modified Bessel function of the first kind with order zero. Consider the modified Bessel's differential equations:
v" + xy (x² + nn)yy 0, n 2 0.
The solutions of the previous equation In (x) y(œ) continuous in zero are called the modified Bessel function of the first kind with order n.
After omitting some constant terms, the data fidelity term f for Rician noise removal is
1, x² log
x o
f(x)
20
Based on the recurrence formulas of the derivative of In (Bowman, 2012), we have that Vo E R,
2 [xr)).
[x()) = [1),, (To(x) + I2(x)), [2(x) To(x) x
Thus we have
(xx) = To(x) (z).
Let B(x) = (log [o())) [z() lo(z)
According the proof of Proposition 2.1 in Then B(x) Ia(=)
f1(x)
Wei & Li. 2022), we know
(3(x) = -- B(x) -1--B(x)) B2 (x).
According to Proposition 2.1 in (Wei & Li with (0) = B(xc) 1. B' (z) is decreasing function with (0(0) 0.5, ('ooo) 0. Based on this, we further have
2022). B(x) is increasing concave function on [0, oc)
(²(x)= =
1 B(x) B(x)) B(x) B'(x)) 2B(x)
I
B(x) - BB(x)) - -B((x) (1-1B(x) B(x)) - B²
B(x)
2²
1 +
2 2
2 B(x) + 3 B2(x)) + (B)
In Figure 12
we plot the functions 1o. B. B'. B". It is clear that (²)x) is bounded by [-0.25, 0). Based on this, we now prove that f has Lipschitz gradient and Hessian.
Lemma 12. Let Io be the modified Bessel function of the first kind with order zero. Let be the observation, f (ax be the data fidelity term for the Rician noise removal task, that is,
(1
x:
ac O D
f(x)
log To
20
0
Then, f has a Lipschitz gradient and Hessian.
6.0581
0.9352
0.5000
-0.0022
log I(((e)
B(x)
(3e))
(*)
0.0084
-0.2245
0
0
Figure 12: Visualizations of function Io, B, B"
B"
49

---

Published as a conference paper at ICLR 2026
Proof. To prove that has Lipschitz gradient and Hessian, only need to prove it in the one dimensional case, because the function is separable. Thus, we only need to consider a = 2 E [0, oo). Clearly, we have that
f((x)
y
zy
y
In order to prove that f' is Lipschitz, we only need to prove that f" is bounded.
(" 1
3²
B
o
Since B' is bounded, we know that f has a Lipschitz gradient.
To prove the Lipschitz property of f", only need to prove the boundedness of f(3) Note that
(x)
B"
Yy
of
and that B" is bounded by [-0.25, 0). we complete the proof.
Based on the above derivations, we have already shown how to compute ff:
1
y
f(())
B
y
Computation of prox,," Based on the technique used by (Wei al. 2023), we are able solve ,rox,, efficiently by the Iterative Reweighted L method (IRLI) given in (Ochs et al. 2015). Con- sider the objective function of prox,,"
prox,,(2) = arg min || 2|12 +
x² log To
x
y
20
According to the Lemma in (Wei et al. 2023). it can be rewritten as the sum of convex function fi and non-decreasing concave function f2:
1 || f1(x)) + f2(()) 2
1 + 1)
1,
x²
log To
y
20
9
where
x²
x + y
1
fi(x)
1,
+
x112,
20
2
1, xy
fz(z)
log Io
02
IRL1 algorithm linearizes the non-convex part fz, and solve the resulted weighted convex subprob- lem. The IRLI algorithm for solving prox,, (z) is given as follows:
y
x
B
o
y
1+1
arg segmin 1
1, x
y
1
x
=112
20 y
0
2
3 z
4+
1 1+
In experiments, we set the maximum inner iteration number for IRL1 to be because it usually solves the proximal sub-problem within iterations.
50

---

Published as a conference paper at ICLR 2026
32
0.9
PSNR (dB)
SSIM
RISP-Prox RISP-GM
RED-Prox
t=160
RED-GM
t=160
20
0.4
0
Runtime (ms)
1600
Runtime (ms)
1600
Figure 13: Averaged PSNR and SSIM curves for Rician noise removal with noise level 25.5/255 on CBSDIO by RISP methods and baselines. The z-axis denotes the running time in milliscconds (ms). RISP-Prox converges within 160 ms time budget.
Experimental set-up. We use the same denoiser as in linear inverse problems, and the same test data set (10 images of CBSD68) in the deblurring experiment. The Rician noise level is set to By = 25.5/255. The average PSNR and SSIM curves are reported in Figure 13 We observe clear gain of restarted inertia for acceleration.
Results. Figure 13 visualizes the PSNR and SSIM curves against running time in milliseconds
for Rician noise removal by RISP and baselines. Note that RISP-Prox takes 160 milliseconds to converge, RISP-GM needs 320 milliseconds, while RED-GM needs 1600 milliseconds. The final PSNR values by RISP aligns closely with RED baselines. This indicates that RISP can accelerate the convergence without compromising the performance.
G.4 SCALE IMAGING
Forward model. The linear inverse scattering task aims to reconstruct the permittivity contrast distribution an object from measurements of its scattered field captured by an array of receivers. In setup, consider the first Born approximation (Wolf 1969) which is commonly adopted
in (Zheng et al., 2025 Gao et al. 2025 Sun et al., 2019b).
Hu x) + n,
(71)
where æ denotes the permittivity contrast distribution, y is the scattered field measured by receivers, H is the discretized Green's function that models the responses of the optical system, u is the light field, @ denotes for the Hadamard product and Gaussian noise.
Fidelity term. The corresponding fidelity term is given by
f(x)
H(u -
(72)
2
For this fidelity term f, Assumptions 2 are satisfied.
Experiment setup. In this problem, noise level is 0.0001, as in (Zheng et al. 2025). The dataset of ODT images was created using the CytoPacq Web Service (Wiesner al. 2019
360 receivers and 240 transmitters. The Gaussian
For the denoiser, we use the standard DRUNet architecture as proposed by (Zhang et al. 202T). The training set is generated by the CytoPacq Web Service, which contains 500 cell images with size 384 384. The denoiser is trained using the Adam optimizer, where we set the learning rate to be x 10 10-4, patch size to be 128, batch size to be 32, denoising strength distributed uniformly in E [0, 30) /255 We train the denoiser 600 epochs, and it takes about 70 minutes complete the training process.
Calculation of Prox,f- For the computation of prox, there is efficient solution. Since the image size is large, the matrix Diag(u H DDag((u) has size 10242 x 1024". Thus, computing the inverse of the matrix ADiag(u) H HDiag(u) + T1024a is not practical. In order to approximate prox,, efficiently, we use the AutoGrad toolbox from Py PoTch (Paszke et al. 2017) to calculate the
hhtps://chi..f..mmii/t mim.miicco
51

---

Published as a conference paper at ICLR 2026
PSNR (Runtimc)
29.55 da mins]
30.47 d8 (b mins)
Groundtruth
RED-CM
19.02 dB
29.86 dB (50 minss)
30.68 dB mins)
Backprejcction
Figure 14: Visual reconstruction comparisons by different methods after convergence or maximum running time reached on linear inverse scattering with 360 receivers, 240 transmitters, and corrupted with 0.0003 Gaussian noises, on the test Cell image of size 512 x 512 by RISP methods and base- lines.
gradient, and apply gradient descent inner loop to solve the proximal sub-problem. The objective to compute prox,, (z), with z as input, is
L(x; X
H()Ox) yll +
x11².
(73)
Algorithm Inner Loop for prox,,,(2)
Require: x0 z, 0.
1: while f < T and V L(x v) 2)
< do
2: x++1 = x' 7 V L y,,
3: t=t+1
4: end while
5: return x²
We the gradient descent update æ, until convergence, see Algorithm for details. In Algorithm 6 x." is initialized as the input. The stepsize 7 is set as 4000/Am) The maximum iteration number 7' 100, and
2 x 10-3
Per-iteration runtime for 1024 x 1024 reconstruction. For RISP-GM and RED-GM, score eval- uation takes approximately 0.43 seconds, while the gradient of the data-fidelity term requires about 1.01 seconds per iteration. For RISP-Prox and RED-Prox, score evaluation again takes roughly 0.43 seconds, whereas the proximal evaluation of the data- fide-fiieitty term takes about 2.45 seconds per it- eration. Overall, the per-iteration cost is dominated by the data-fidelity computation rather than by score evaluation.
Additional results on 512 x 512 reconstruction. In Figure 14 we visualize the scattering recon- struction results by RISP and baselines after convergence or the maximum iteration reached. We can clearly that after 60 minutes, the zoomed-in in parts by RED-GM and RED-Pro still bit blurry. While the proposed RISP methods can better reconstruct the fine details in the cells within minutes.
Figure 15 shows the PSNR and SSIM curves by RISP and baselines on inverse scattering. It can be seen that, in general RISP methods exhibit stable and faster convergence in PSNR and SSIM. Overall, RISP methods have a 10x acceleration against RED-GM and RED-Prox. This verifies the potential of the proposed methods large-scale problems.
52

---

Published as a conference paper at ICLR 2026
PSNR (dB)
SSM
RISP-Prox
RISP-GM
RED-Prox
t=6
RED-GM
t=6
18
0.4
Runtime (minutes)
60
Runtime (minutes)
60
Figure 15: Convergence results on linear inverse scattering with 360 receivers, 240 transmitters, and corrupted with 0.0003 Gaussian noises, on the test Cell image of size 512 x 512 by RISP methods and baselines. r-axis denotes the running time minutes, y-axis denotes the PSNR value in dB, or SSIM value.
RISP-GM without restart
RISP-GM with restart
28
28
Deblurring
PSNR (dB)
PSNR (dB)
0,01
0
0 0.1
0
20
20
0 0.2
RED-GM
Iterations
200
Iterations
200
32
32
PSNR (dB)
PSNR (dB)
MRI
0.01
0.3
24
24
= RED-GM
Iterations
500
Iterations
500
Figure 16: Influence of inertial strength 0 in RISP-GM for deblurring (top row) and MRI (bottom row) tasks. We adopt the same settings and parameters in Appendix G.2) with a restarting thresh- old of B = 5, 000. Note how the restarting mechanism clearly stabilizes the convergence. We also note that the restart criterion may not always triggered; see MRI results in the second row.
G.5 HYPERPARAMETER ROBUSTNESS STUDIES
In this section, we examine the influence of the hyperparameters and B on the performance and stability of RISP.
G.5.1 INFLUENCE OF THE INERTIAL STRENGTH
In RISP. the inertial strength 0 >> 0 controls the strength of inertia. The choice removes inertia and reduces the RISP algorithm to its RED counterpart, whereas smaller values of 0 increase the inertial effect. Figure 16 and respectively visualize the convergence of RISP-GM and RISP-Prox for 0 E (0.01, 011, 0.2 0.3. 0.9 in linear inverse imaging problems. All RISP algorithms are run with the corresponding settings and parameters as in Appendix G.2 with a fixed restarting threshold of B 5, 000. For small values of 0, RISP algorithms without restart may become unstable and exhibits oscillatory behavior, as observed the deblurring or inpainting experiments. In contrast, the restart mechanism effectively stabilizes the convergence. We note that the restart mechanism makes RISP less sensitive to the choice of In particular, values of the range [0.1, 0.3) yield comparable performance, suggesting this interval as practical tuning range.
53

---

Published as a conference paper at ICLR 2026
RISP-Prox without restart
RISP-Prox with restart
28
28
Deblurring
PSNR (dB)
PSNR (dB)
= 0,01
0 0.3 0 0.9 RED-Prox
20
20
Iterations
50
Iterations
50
32
32
PSNR (dB)
PSNR (dB)
MRI
= 0.01
8 0.3
= 0.1
0.9
24
0.2
RED-Prox
Iterations
500
0
Iterations
500
Figure 17: Influence of inertial strength in RISP-Prox for deblurring (first row) and MRI (second
row). We adopt the same settings and parameters as in Appendix G.2 with restarting threshold of B 5, 000. Note how the restarting mechanism stabilizes the convergence. We also note that the restart criterion may not be always triggered; see MRI results in the second row.
Deblurring
MRI
28
31
RISP-GM
PSNR (dB)
PSNR (dB)
B 100
10,000
B 1000
B 100,000
5000
RED-GM
B 7000
21
24
Iterations
200
0
Iterations
500
28
RISP- Prox
PSNR (dB)
PSNR (dB)
B = 100
B= 10,000
1000
B 100,000
B
5000
RED-Prox
B 7000
21
24
Iterations
50
Iterations
200
Figure 18: Influence of restarting threshold B in RISP-GM (top row) and RISP-Prox (bottom row) for deblurring (left column) and MRI (right column) tasks. We adopte the corresponding settings and parameters as in Appendix G.2 with two inertial strengths 0.2. As shown in the deblurring frequently, leading more stable stable convergence.
results, small value of B clears inertia In contrast, the effect of is less pronounced settings such as MRI, where the restart criterion is triggered less often. Note that the behavior of RISP similar on large range of B [10?, 10%].
G.5.2 INFLUENCE OF RESTARTING THRESHOLD B.
In RISP, the restarting threshold determines how frequently inertia is cleared to prevent overshooting. A lower threshold triggers restarts more often, while higher threshold sults in fewer restarts. Figure 18 illustrates the influence of the restarting threshold E {100, 1000, 3000, 5000, 7000, 10000, 100000, +oo} in the tasks of image deblurring and MRI, with a fixed inertia strength 0.1. Here, = +oo means that the restart mechanism never triggered. When B is small, restarts occur frequently, leading more stable behavior. When B is large, the
54

---

Published as a conference paper at ICLR 2026
Table 1: Numerical values obtained by RISP with diffusion-based score prior on image deblurring with o = 5%, using the first blur kernel in Levin's 's blur kernel dataset. Running time in second and iteration number are reported at the peak PSNR for each method. Note the faster convergence enabled by RISP even if the score function is not strictly gradient field.
Methods
PSNR
LPIPS
Running time
Iteration
LISP-MM-Diffusion
27.41 dB
0.2188
58
35
RISP-Prox- Prox-Diffusion
27.30 dB
0.2192
3s
22
27.46 dB
0.2267
27s
200
Dri-frroxDiiftssion
27.46 dB
0.2190
58
35
DPS
26.18 dB
0.1791
70s
1000
28
10-1
Relative Error
PSNR (dB)
COD-Pro--Difusionn DifffuiDii
RISP-Prox Diffusion
RISP-GM-Diffusion
21
10
Runtime (s)
27
Runtime (s)
27
Figure 19: Convergence of RISP with diffusion-based score prior for the deblurring task, with noise level 12.5/255 averaged on CBSDI0, and a blur kernel from Levin's dataset (Levin et al., 2009). We observe a behavior of acceleration using RISP, even if using diffusion-based score priors.
restart mechanism is become less active, producing faster trajectories. Overall, the results show that RISP achieve good balance between stability and acceleration for broad range of B values.
G.6 RISP WITH DIFFUSION-BASEE SCORE PRIORS
We further illustrate the benefit of RISP when incorporating diffusion- score priors. We con- sider the image deblurring task with a = 5%, using the first blur kernel in Levin's 's blur kernel dataset. We use the pre-trained score network from the unconditional 256 x 256 model publicly released by (Dhariwal & Nichol 2021
Table summarizes the numerical results. Running time in second and iteration number are reported the peak PSNR for each method. As shown, RISP algorithms reach their peak PSNR in fewer iterations and less computational time than the corresponding RED variants. Figure further cor- roborates the effectiveness by visually comparing the convergence of RISP and RED. These results clearly show that RISP continues to deliver acceleration even when the score function is not strictly a gradient field.
We additionally compare RISP against DPS (Chung al. 2022a) in terms of performance. To evaluate the perceptual quality, we employ Learned Perceptual Image Patch Similarity (LPIPS). For DPS, we the recommended default settings and finetune the key hyperparameters. As shown in Table T] DPS attains lower PSNR but better LPIPS due to its generative sampling nature, whereas RISP offers a more balanced trade-off between reconstruction and perceptual quality.
G.7 COMPARISON BETWEEN RISP AND FISTA
We compare RISP with another inertia-based method, FISTA-PaP (Kamilov et al. 2018 sum- marized in Algorithm|] 7 The evaluation is conducted on the image deblurring task with noise level 5%. using the first blur kernel from Levin's dataset. Both methods employ the same denoiser, GS-DRUNet with S SoftP Plus lus activations; FISTA-PnP treats the denoiser as a proximal operator on the prior term. Each method is finetuned attain its best PSNR.
55

---

Published as a conference paper at ICLR 2026
Algorithm 7 PIP
Require: yº E IR O, and o
I: k 0, fo =1 while n
3: x x+1 = =D - =Do(y"~~Vill ~VV(ly))
4:
t+t1 (1 /1 V1+ 41 12
5:
n+1 x
k+1 --- (ar + x²"
2k11
6:
= ++1
7: end while
return x²
Table 2: Results by RISP and FISTA-PnP on deblurring with 5% and the first blur kernel in Levin's 's blur kernel dataset. Running time in second and iteration number are reported at the peak PSNR for each method.
Methods
PSNR
Running time
Iteration
Convergence?
FISTA-PnP
27.60 dB
0.5s
30
RISP-GM
27.66 dB
0.5s
29
RISP-Prox
27.55 dB
0.2s
12
RED-GM
28.03 dB
2.5s
143
RED-Rrox
27.68
0.5s
29
28
10-1
Relative Error
PSNR (dB)
FISTA-PnP
RISP-Prox
RISP-GM
RED-Prox
RED-GM
21
10-9
0
Iterations
200
Iterations
200
Figure 20: Convergence comparison between RISP and FISTA-PaP.
Table 2 and Figure 20 summerize the results. As shown, RISP-Prox and RISP-GM attains compa- rable (sometimes even faster) convergence speed with FISTA-PnP. For instance, RISP-Prox takes only 12 iterations to achieve its peak PSNR while FISTA-PuP requires 30 iterations. Note that FISTA-PnP uses the adaptive momentum update and lacks theoretical guarantees.
G.8 PARAMETER SETTINGS FOR EXPERIMENTS
In Table we give the hyperparameters setting for different inverse problems.
56

---

Published as a conference paper at ICLR 2026
Invense problem
A
Method
B
RED GM
0.1
Deblurring
15.0
0.1
RED-Prox
2.0
RISP-GM
RISP- ProP
5.0
0.2
5000
RED-GM
0.1
Inpainting
5.0
0.08
RED-Prox
5.0
RISP-GM
RISP Prox
5.0
0.2
5000
RED-GM
0.7
(x-4)
RED-Prox
1.0
1.0
MRI (X8)
0.02
RISP Prox
1.0
0.2
5000
RED-GM
0.4
SR
10.0
0.03
RED-Prox
10.0
RISP-GM
RISP Prox
10.0
0.2
5000
RED-GM
0.03
Ricion Noise Removal
5 10
0.05
RED-Prox
5 10
RISP-GM
0.03
0.01
100
RISP-Prox
10
RED-GM
1 10
Linear Inverse Scattering 1024
1 x 10
0.03
RED Prox
5 10 -
10
RISP-Prox
5 x 10
0.01
x 10
RED-GM
2 x 10
Linear Inverse Scattering
2 x 10
0.03
RED-Prox
5 x
512 512
RISP-Prox
5 10-3
0.01
5000
Table 3: Hyperparameter settings for the experiments.
57


Reviews:
[{"review_id": "zVR2Aje7av", "reviewer": "Reviewer_wKJo", "summary": "This paper proposes Restarted Inertia with Score-based Priors (RISP), an acceleration framework built upon the RED (Regularization by Denoising) methodology for solving imaging inverse problems. The key contribution  is the integration of a restarted heavy-ball-type inertia mechanism with score-based priors derived from deep denoisers, enabling provably faster convergence to stationary points compared to  RED. The authors provide both discrete algorithmic instantiations (RISP-GM and RISP-Prox) and a continuous-time dynamical systems interpretation linked to the heavy-ball ODE.", "questions": "While restart improves stability, the method introduces tunable hyperparameters (e.g., restart threshold B , inertia weight ε ). Although the authors claim robustness and provide some analysis in the appendix , more guidance or adaptive tuning strategies would make this work more practical.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Rigorous convergence analyses for both gradient-based (RISP-GM) and proximal (RISP-Prox) variants under realistic assumptions (e.g., Lipschitz Hessian).\n* Demonstation of significant empirical speedups compared to RED on large scale inverse problems (debluring, super-resolution, inpainting and MRI) \n* A continuous-time dynamical systems interpretation linked to the heavy-ball ODE is offered, enriching theoretical understanding.\n* The performance of the proposed acceleration strategy is validated across diverse tasks, including linear and nonlinear inverse problems \n  showing consistent acceleration and reconstruction quality", "weaknesses": "* The restart condition used in both algorithms (line 5 in both cases) uses a cumulative sum over all past iterations since last restart. This needs to be clarified as a running window accumulator to avoid confusion about global vs. local accumulation.\n* The core idea, ombining restart + inertia + nonconvex smooth optimization is not new. The novelty mainly lies in the application domain (imaging with learned priors) and the compatibility with RED’s score interpretation.\n* An ablation study on the sensitivity to hyperparameters is missing.  \n* Comparison to other acceleration strategies in PnP/RED is limited. For example Anderson acceleration (Hong et al., 2019) has been applied to RED and shows empirical speedups. Also,  FISTA-style momentum with adaptive restart (Alamo et al., 2019; Fercoq & Qu, 2019) could be a relevant baseline.\n\n--\n\n* References\nOlivier Fercoq and Zheng Qu. \"Adaptive restart of accelerated gradient methods under local quadratic growth condition\". IMA Journal of Numerical Analysis, 39(4):2069–2095, 2019.", "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": "", "extra_scores": {}}, {"review_id": "SMQoDQwIlk", "reviewer": "Reviewer_2V7N", "summary": "This paper proposes a method called Restarted Inertia with Score-based Priors (RISP), which extends the popular RED framework by incorporating momentum and a restart mechanism to accelerate convergence in imaging inverse problems. The authors provide non-convex convergence guarantees for two variants—RISP-GM and RISP-Prox—and connect the discrete algorithms to a continuous-time heavy-ball ODE. Experiments on both linear and nonlinear inverse problems demonstrate improved convergence speed and competitive reconstruction quality compared to RED baselines.", "questions": "See [Weaknesses]", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a rigorous non-convex convergence analysis for RISP, establishing an improved rate under Lipschitz-continuous Hessian assumptions. This is a meaningful theoretical advance in the analysis of accelerated methods for imaging inverse problems.\n- The combination of inertia and restarting is well-motivated and effectively addresses overshooting and instability in non-convex settings. The connection to the heavy-ball ODE offers valuable continuous-time intuition.\n- The authors thoroughly evaluate RISP on a range of imaging tasks, including linear and nonlinear inverse problems. The results consistently show faster convergence without sacrificing reconstruction quality, and the method scales well to large images", "weaknesses": "- The paper does not adequately discuss the recent surge of PnP-like methods that use pre-trained diffusion models as score-based priors, such as [1]–[7]. In particular, [7] (A Variational Perspective on Solving Inverse Problems with Diffusion Models) also combines diffusion models with a RED-like framework. A comparison or discussion of how RISP could integrate such powerful priors is missing.\n\n- Another related work in PnP literature is missing [8], which also shows the extension to the RED framework. \n\n- While the experiments are comprehensive, they are limited to traditional denoisers (DRUNet). It would be valuable to see how RISP performs when combined with state-of-the-art diffusion-based score functions, especially since such models have shown superior performance in many inverse problems.\n\n- The method introduces new hyperparameters (theta and B), and while the authors claim robustness, no systematic ablation study is provided to support this claim across different tasks.\n\n### References\n[1] DIFFUSION POSTERIOR SAMPLING FOR GENERAL NOISY INVERSE PROBLEMS, ICLR 2023  \n[2] Improving Diffusion Models for Inverse Problems using Manifold Constraints, Neurips 2022   \n[3] Denoising diffusion models for plug-and-play image restoration, CVPRW 2023  \n[4] zero-shot image restoration using denoising diffusion null-space model, ICLR 2023  \n[5] Diffusion Posterior Sampling for Linear Inverse Problem Solving: A Filtering Perspective, ICLR 2024  \n[6] Pseudoinverse-Guided Diffusion Models for Inverse Problems, ICLR 2023  \n[7] A Variational Perspective on Solving Inverse Problems with Diffusion Models, ICLR 2024  \n[8] TFPnP: Tuning-free Plug-and-Play Proximal Algorithms with Applications to Inverse Imaging Problems, JMLR 2022", "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": "", "extra_scores": {}}, {"review_id": "zJvtBypw8S", "reviewer": "Reviewer_UnZv", "summary": "This paper proposes to accelerate the convergence of the regularization by denoising (RED) framework with score-based priors by incorporating momentum and restart strategies. The authors provide theoretical convergence rate guarantees and extend the analysis to a continuous-time dynamical system formulation. Both the theoretical convergence analysis and empirical experiments demonstrate faster convergence compared to the original RED framework, despite the nonlinearity of score-based priors.", "questions": "Please refer to the Weaknesses section for the main points of clarification and concerns.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical justification for accelerated convergence is rigorous and carefully presented. In particular, it is valuable that the analysis is conducted under non-convex score-based prior conditions, which are more realistic in modern generative models.\n2. The method builds upon the well-studied RED framework and introduces modifications that are principled and consistent with its formulation.\n3. The proposed changes require only a few additional lines of code, making the method highly practical. This simplicity also suggests that the proposed acceleration could potentially be applied to inverse problem solvers that use diffusion model sampling as a denoiser, not only traditional RED implementations.", "weaknesses": "1. The novelty of the proposed method feels somewhat modest. Momentum and restart strategies are widely used in optimization, so the main contribution here seems to lie in establishing acceleration guarantees under non-convex score-based priors. While the theoretical development is sound, the overall structure of the convergence analysis appears similar to existing frameworks for accelerated non-convex optimization. It is not entirely clear how substantially new the analytical perspective is.\n2. While momentum can accelerate the early stages of optimization, it may also introduce oscillations or instability, particularly in nonlinear or ill-conditioned settings. In the experiments presented, there are cases where the final reconstruction quality is actually worse than the baseline without momentum. This suggests that careful hyperparameter tuning may be necessary, and that the practical benefits of acceleration may not always be realized at convergence.\n3. Given that the original RED framework is rarely used in contemporary practice—having largely been superseded by more general PnP and score-based inverse problem formulations—the practical impact of the contribution may be somewhat limited, even if the analysis itself is well executed.", "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": "", "extra_scores": {}}, {"review_id": "GSRojYKVBi", "reviewer": "Reviewer_pe5V", "summary": "This paper develops an acceleration strategy, namely RISP (Restarted Inertia with Score-based Priors), for the Regularization-by-Denoising (RED) framework in imaging inverse problems. Two variants are proposed: RISP-GM (gradient-style) and RISP-Prox (proximal-style), which incorporate an inertial/momentum step and a restart criterion into RED-like updates, and utilize a pretrained score network as the prior. Under assumptions (score is a gradient field, Lipschitz gradient, and Lipschitz Hessian of data fidelity and score), the authors prove accelerated stationary-point convergence rates of $O(1/n^{\\frac{4}{7}})$ for both variants. They connect the discrete methods to a restarted heavy-ball ODE and validate empirically on linear and nonlinear inverse problems, demonstrating substantial iteration and runtime speedups while improving reconstruction quality.", "questions": "- Can you quantify how violations of Assumptions 1–3 affect the convergence rate empirically? For example, how does RISP perform when the score is not exactly a gradient field?\n- Did you compare the chosen restart rule (accumulated relative change) to other restart schemes (e.g., O’Donoghue–Candes adaptive restart or gradient-based restart)? Can you add a discussion, if not a full-blown comparison with other known heuristics for restart?\n- For large-scale inverse scattering, you use DRUNet and patch processing. How sensitive are results to the patching strategy, and does patch-based score evaluation affect theoretical assumptions (e.g., smoothness)?\n- The paper states code will be released upon acceptance. Please ensure the repo includes (i) exact pretrained models used, (ii) scripts for reproducing key plots (gradient-norm decay, PSNR vs runtime), and (iii) detailed hyperparameter selection modules.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper identifies restarting inertia as a theoretically justifiable mechanism to accelerate RED-style algorithms while controlling instability, and presents concrete algorithmic variants.\n- The derivation of $O(1/n^{\\frac{4}{7}})$ convergence under nonconvex score priors is a meaningful advancement in the analysis of accelerated RED/PnP-style methods.\n- The connection to a restarted heavy-ball ODE gives additional intuition and helps explain algorithmic behavior.\n- The empirical section shows applications to linear and nonlinear inverse problems, showing both acceleration benefits and image quality improvement in reconstruction.\n- The algorithms are simple to implement on top of existing RED/PnP solvers: the inertia and restart rules are lightweight and practical.", "weaknesses": "- The accelerated rates require Lipschitz continuity of Hessians (Assumption 3) and that the score be an exact gradient field (Assumption 1). While the paper discusses how these can be approximated in practice (e.g., gradient-step denoisers, Lipschitz activations), a more explicit discussion and empirical diagnostics showing how violation of these assumptions affects performance would strengthen the contribution.\n- RISP introduces several new hyperparameters (e.g., the inertia parameter and restart threshold). The paper reports robustness in experiments, but lacks a systematic ablation or guidance for selecting these values in practice. An appendix table or a small experiment showing sensitivity would help practitioners.\n- The restart trigger is based on accumulated relative change; it would be useful to compare this choice against other restart heuristics (e.g., function value increase, gradient norm increase, or adaptive restart strategies). A short ablation would clarify whether the theoretical restart choice is critical.\n- The manuscript cites inertia/acceleration prior works, but could provide a more direct empirical and conceptual comparison to stronger recent baselines that incorporate momentum or acceleration (e.g., PnP-FISTA, PnP Quasi-Newton, and extrapolated three-operator splitting) beyond baseline RED-GM/RED-Prox.\n1. PnP-FISTA: Kamilov et al., “Plug-and-Play FISTA for Solving Nonlinear Imaging Inverse Problems”. \n2. PnP-QN: Tan et al., “Provably Convergent Plug-and-Play Quasi-Newton Methods”. \n3. Wu et al., “Extrapolated Plug-and-Play Three-Operator Splitting Methods for Nonconvex Optimization with Applications to Image Restoration”. \n-Some of the dramatic runtime gains in the large-scale experiment are attributed to the high per-iteration cost of RED variants; however, the per-iteration complexity and GPU/CPU implementation details (e.g., whether prox evaluation or score computation dominates) are not clearly reported.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)