{"id":"55cff07f-7787-4b8e-afe1-b9c7932d0927","arxiv_id":"1909.02040","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"An online, minibatch version of Regularization by Denoising, On-RED, has a fixed-point residual bound of O(1/sqrt(t)) in convex settings and closely matches batch RED quality on phase retrieval experiments.","lead":"An imaging-reconstruction algorithm that normally needs all measurements at each step is modified to work on small random batches, with a proof of convergence in convex problems. The method targets very large datasets where batch processing is too slow, and tests on phase retrieval with a neural-network denoiser show quality close to full-batch results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 does not prove fixed-point convergence: for fixed B its bound has a positive noise floor, so 'converges to a fixed point at O(1/√t)' overstates the result; the R0/Assumption 2 machinery is also not verified in the experiments.","rationale":"The concern is not that the proof is algebraically wrong; the descent inequality is plausible and the empirical phase-retrieval results show the algorithm can be useful. The problem is that the theorem's mathematical content is weaker than the paper's language. A reviewer relying on the abstract would take away fixed-point convergence at O(1/√t); the theorem actually offers a finite-time bound on average residual that, for fixed B, has a constant noise floor. This matters because Section 5 advertises B=1 as the scalable regime; for that regime Theorem 1 provides no decay as t grows. The reader singled out Assumption 2 as weakest because it is assumed rather than verified; I partially agree, but the more load-bearing defect is that even with Assumption 2 the stated convergence conclusion is unsupported. The proof could be tightened by using the zero conditional mean of the stochastic perturbation, which would remove the need for full Assumption 2; that is a sign the method may be salvageable. None of this changes the overall conditional verdict: the algorithm and experiments are worth publishing with corrected claims, a stated growing-batch rate, and a verification of boundedness or a derivation of it under stronger assumptions.","tokens_in":24533,"tokens_out":15291,"duration_ms":173626,"concrete_test":"Re-derive the final display of Section 7 by taking conditional expectation on both sides of (15) before applying Cauchy-Schwarz to the cross term. Because E[ˆP(x)-P(x)|x]=0, the cross term drops out; then recompute the t→∞ limit for fixed B and γ. If the limit is positive, Theorem 1 cannot support 'converges to a fixed point,' and if the tightened bound no longer contains 2γνR0/√B, Assumption 2 should be restated as an initial-distance condition rather than an iterate-boundedness condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing issue is the gap between the paper's advertised claim and Theorem 1. For fixed minibatch size B and step size γ, the RHS of Theorem 1 has limit (L+2τ)/γ [ν²γ²/B + 2γνR0/√B] as t→∞, which is positive. Hence the theorem does not assert that the average fixed-point residual goes to zero for the algorithm as actually run in Section 5 (B=1). The O(1/√t) statement is obtained by setting B=t, i.e. a growing minibatch that is not part of the theorem's fixed-B hypothesis, and the bound controls only the Cesàro average (or the minimum over k) of ||G(x_{k-1})||². Such a bound does not imply convergence of the iterates x_k to an element of zer(G), so the Introduction's phrase 'On-RED converges to a fixed point at the worst-case rate of O(1/√t)' is not justified by Theorem 1. A second, smaller issue compounds this: the proof introduces Assumption 2 (uniform boundedness of all iterates by R0) and uses it only to bound the cross term pathwise. Because Proposition 1 gives E[ˆP(x)-P(x)|x]=0, taking conditional expectation before Cauchy-Schwarz makes that cross term vanish; the same telescoping then needs only ||x_0-x*||≤R0. Thus the full Assumption 2 is either superfluous or, in the nonconvex CDP experiments, unverified — in either case it cannot be the support for the empirical convergence claims. The theorem itself is plausibly correct in outline; the overstatement is what needs correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes On-RED, an online (minibatch) variant of the Regularization by Denoising framework for imaging inverse problems. At each iteration the algorithm uses a random subset of measurements to form an unbiased gradient estimate, combined with a nonexpansive denoiser. The main theoretical result, Theorem 1, bounds the expected average squared norm of the fixed-point residual G over t iterations under convexity, bounded variance, uniform boundedness of iterates, and nonexpansiveness assumptions. The paper also presents phase-retrieval experiments on coded diffraction patterns, showing that with B=1 On-RED approaches the SNR of full-batch GM-RED while using the same per-iteration cost as a fixed single-measurement batch method.","tokens_in":24926,"tokens_out":4860,"duration_ms":48182,"significance":"If the advertised convergence claim held as stated, On-RED would be a useful scalable alternative to batch RED for large datasets, and the paper would provide a transparent stochastic-gradient analysis for a denoiser-based regularizer. The paper has genuine strengths: the assumptions are stated explicitly, the proof algebra is straightforward to follow, and the experiments cover multiple denoisers (TV, BM3D, DnCNN*) and clearly demonstrate that online processing of measurements improves over a fixed single-measurement batch baseline. However, the central theoretical claim is stronger than what Theorem 1 actually proves, and the numerical validation metric does not directly match the theorem's bound. These issues are load-bearing because the paper's contribution is precisely the claimed O(1/sqrt(t)) fixed-point convergence, and they need to be addressed before publication.","major_comments":[{"comment":"Theorem 1 bounds only the Cesàro average (and hence the minimum) of ||G(x_{k-1})||² over k=1,...,t. For any fixed minibatch size B and fixed step size γ, the right-hand side has the positive limit (L+2τ)/γ [ν²γ²/B + 2γνR0/√B] as t→∞. Therefore the theorem does not establish convergence of the iterates to an element of zer(G), and the Introduction's statement that 'On-RED converges to a fixed point at the worst-case rate of O(1/√t)' is not supported by the theorem. The O(1/√t) statement is obtained only by taking B=t, a growing minibatch that is not what is run in Section 5 (B=1 or B in {10,20,30}). Please revise the advertised claim to a bound on the average fixed-point residual with a positive noise floor, and clearly separate the fixed-B regime from the growing-B regime.","section":"Theorem 1 and Introduction (contribution bullet 1)"},{"comment":"Assumption 2 postulates that all iterates lie within a fixed R0-ball around every point in zer(G), but this is neither derived from the algorithm nor verified in the nonconvex phase-retrieval experiments. In the proof, the Cauchy-Schwarz step requires ||P(x_{k-1})-P(x*)|| ≤ R0 for every k, so the bound genuinely depends on this unverified condition. However, taking the conditional expectation before applying Cauchy-Schwarz makes the cross term vanish because E[hatP(x)|x]=P(x); the telescoping sum then needs only ||x0-x*|| ≤ R0. This shows that Assumption 2 is either avoidable and should be removed from the theorem, or, if kept, must be justified or numerically checked. As written, it cannot support the empirical convergence claims in the nonconvex setting.","section":"Assumption 2 and the proof of Theorem 1 (Section 7, Eq. (15)-(16))"},{"comment":"The quantity plotted and tabulated as 'Norm. Acc.' is ||G(x_k)||²/||G(x_0)||² at the final iteration (or at each k), whereas Theorem 1 bounds E[(1/t)Σ_{k=1}^t ||G(x_{k-1})||²], the average over iterations. The observed improvement with smaller γ and larger B is therefore not a direct empirical verification of the theorem's quantitative bound. Please either report the running average of the residuals (the quantity actually bounded) or clarify that the plots illustrate a related heuristic rather than a direct validation of Theorem 1.","section":"Section 5.2, definition of Norm. Acc. and Table 2"}],"minor_comments":[{"comment":"The phrase 'We establish the theoretical convergence of On-RED in convex settings' is too strong given the noise-floor issue in Theorem 1; suggest 'we establish a fixed-point residual bound' or similar.","section":"Abstract and Conclusion"},{"comment":"The proof of Proposition 2 is entirely imported from the supplementary material of [39] by setting U=UT=I and Gi=G; since this result is central to the nonexpansiveness of P, please include a self-contained derivation or state the exact result from [39] in enough detail to make the proof readable without consulting another paper's supplement.","section":"Proposition 2 (Section 7)"},{"comment":"The wording 'the distance between the farthest point in zer(G) and the sequence {x_k}' is confusing; it should state clearly that all iterates satisfy ||x_k - x*||₂ ≤ R0 for every x* in zer(G) and every k ≥ 0.","section":"Assumption 2"},{"comment":"The column layout of Table 3 is hard to follow: SGM has no denoiser, and GM-RED (fixed 6) is listed only for DnCNN*, making it unclear which columns are comparable; please restructure the table to make the denoiser and algorithm for each column explicit.","section":"Table 3"},{"comment":"The theorem's first inequality E[min_k ||G(x_{k-1})||²] ≤ E[(1/t)Σ||G(x_{k-1})||²] is correct, but the min form can mislead readers into thinking a particular iterate converges; consider omitting it or adding a remark that the bound is on the average residual, not on the final iterate.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a useful paper with a flawed headline. The algorithmic idea is straightforward and worth having: minibatch processing for RED, with convergence analysis borrowed from BC-RED. The phase-retrieval experiments are decent and show that cycling over measurements beats fixing one measurement. But the abstract says \"converges to a fixed point at O(1/sqrt(t))\" and the theorem does not deliver that. It bounds the Cesaro average of squared operator residual by (L+2tau)/gamma [nu^2 gamma^2/B + 2 gamma nu R0/sqrt(B) + R0^2/t]. For fixed B the first two terms are a positive floor, so there is no convergence to a zero of G as t goes to infinity; the O(1/sqrt(t)) claim requires B=t, a growing batch that is not what the experiments or the fixed-B theorem describe. This kind of overstatement needs a direct correction, not just a footnote.\n\nOn the positive side, the paper is honest about the analysis being convex while the experiment is nonconvex. The proof is transparent and, as the stress-test note observes, Assumption 2 (uniform boundedness of all iterates) is actually superfluous: if you take the conditional expectation before Cauchy-Schwarz, the cross term vanishes and only ||x0 - x*|| <= R0 is needed. So the theorem can be strengthened rather than weakened. The empirical story is fine: with B=1, On-RED gets within about 1 dB of full-batch GM-RED and beats GM-RED on a single fixed measurement by a wide margin. That is a legitimate practical result for phase retrieval, even if the problem size (I=6, 256x256) is modest.\n\nSoft spots: tau is tuned per test image for best SNR, so the numbers are optimistic; code and trained DnCNN* are not released, which hurts reproducibility. The nonconvex experiments are not covered by the theory, but that is normal for this literature. The citation pattern is fine; the reliance on [39] is explicit and appropriate.\n\nBottom line: worth a serious referee slot. The right verdict is major revision: fix the convergence claims, drop or downplay Assumption 2 (or keep it but say why), and make code available. This is not a desk-reject; it is a paper whose central mechanics are sound and whose marketing is a little too enthusiastic.","headline":"On-RED is a real but modest contribution, and its advertised convergence claim outstrips what Theorem 1 actually proves.","tokens_in":25480,"tokens_out":2892,"would_cite":true,"duration_ms":29974,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Replacing the full-batch gradient in regularization by denoising with an unbiased random minibatch of measurements preserves a worst-case O(1/√t) fixed-point convergence rate, and in phase retrieval one random measurement per iteration…","keywords":["online regularization by denoising","RED","stochastic gradient methods","phase retrieval","coded diffraction patterns","nonexpansive operators","fixed-point convergence","image reconstruction"],"falsifier":"Track the quantity max_{x* ∈ zer(G)} ‖x_k − x*‖ during an On-RED run on a convex problem with γ = 1/(L+2τ) and a nonexpansive denoiser. If the iterate distance grows without bound, Assumption 2 fails and Theorem 1 does not apply; if it stays bounded but the empirical average of ‖G(x_{k-1})‖² violates the stated O(1/√t) rate, the theorem's constants or variance bound would be suspect.","tokens_in":24335,"feed_emoji":"🖼️","tokens_out":9354,"duration_ms":89206,"temperature":0.7,"pith_summary":"The paper introduces On-RED, an online version of regularization by denoising that updates using only a small random subset of the measurements at each iteration instead of the entire dataset. Its central theoretical claim is that, when the data-fidelity components are convex and differentiable with bounded gradient variance, the denoiser is nonexpansive, and the iterates remain bounded, the average squared fixed-point residual converges at rate O(1/√t). The paper then tests On-RED on the nonconvex problem of phase retrieval from coded diffraction patterns, where a single randomly selected measurement per iteration nearly matches the reconstruction quality of the batch algorithm that uses all measurements. This matters because it gives the RED framework a path to large datasets that are too big for batch processing, while still carrying a convergence guarantee.","feed_headline":"Online RED converges, and one measurement per step rivals full-batch","feed_subtitle":"O(1/√t) fixed-point convergence; in phase retrieval, one random measurement per step matches full-batch quality.","key_machinery":"The central object is the operator G(x)=∇g(x)+τ(x-D_σ(x)), whose zero set is the set of fixed points that RED seeks, together with the averaged operator P=I-γG. On-RED replaces P with the stochastic operator P̂=I-γĜ, where Ĝ uses a minibatch gradient. The proof works because P̂ is an unbiased perturbation of a nonexpansive P: Proposition 1 bounds the perturbation variance by γ²ν²/B, Proposition 2 gives nonexpansiveness of P under the step-size bound, and a telescoping-sum argument converts the per-iteration descent inequality into the averaged residual bound. The minibatch gradient carries the online processing, while the nonexpansive denoiser and bounded variance keep the stochastic perturbation controlled.","core_discovery":"On-RED iterates as x_k = x_{k-1} - γ(∇̂g(x_{k-1}) + τ(x_{k-1} - D_σ(x_{k-1}))), where ∇̂g is an unbiased minibatch gradient and D_σ is a denoiser. Theorem 1 states that if the component functions are convex and L-Lipschitz differentiable, the minibatch gradient has variance at most ν²/B, the zero set of G(x)=∇g(x)+τ(x-D_σ(x)) is nonempty, the iterates stay within radius R₀ of that set, and D_σ is nonexpansive, then for γ ∈ (0, 1/(L+2τ)] the average satisfies E[(1/t)∑_{k=1}^t ‖G(x_{k-1})‖²] ≤ (L+2τ)/γ [ν²γ²/B + 2γνR₀/√B + R₀²/t]. This yields an O(1/√t) average fixed-point residual, and the analysis does not require the denoiser to correspond to an explicit regularizer. In the nonconvex phase-retrieval experiments, On-RED with B=1 outperforms GM-RED using one fixed measurement by more than 4 dB and approaches the full six-measurement batch SNR.","pith_inferences":["A natural extension would replace the assumed bounded-iterate condition with coercivity or strong convexity of g, yielding a version of Theorem 1 in which R₀ no longer appears as an unexplained constant; the paper does not make this derivation.","The same minibatch-perturbation proof strategy likely transfers to variance-reduced gradient estimators such as SVRG or SAGA, which could replace the ν²/B term by a term that decays with iteration count and improve the rate beyond 1/√t.","The empirical success at B=1 suggests that random measurement diversity itself acts as an implicit regularizer in phase retrieval; quantifying SNR as a function of measurement diversity at fixed computation would be a direct testable extension.","On-RED could also be applied to computed tomography or Fourier ptychography, where large measurement sets are common, but the paper's convergence analysis covers only uniform random sampling and would need adaptation for ordered-subset or data-adaptive sampling strategies."],"forward_implications":["For convex data-fidelity, On-RED provides a worst-case O(1/√t) convergence guarantee for the average fixed-point residual, matching the rate of stochastic gradient methods while retaining the RED regularization operator.","The per-iteration cost of On-RED scales with the minibatch size B rather than the total number of measurements I, so the method can be applied when the full dataset cannot be loaded or processed in one gradient step.","Because the theorem does not require the denoiser D_σ to come from an explicit regularizer, the same guarantee covers learned CNN denoisers such as DnCNN*, provided they are nonexpansive.","The phase-retrieval experiments show that cycling over random measurements with B=1 recovers image details lost when a single fixed measurement is used, and approaches the SNR of the full-batch algorithm, indicating that online measurement diversity is practically valuable even in a nonconvex problem.","The numerical trend that smaller step size and larger minibatch improve convergence accuracy extends the theorem's qualitative predictions to the nonconvex coded-diffraction-pattern setting."],"supporting_citations":[{"why":"Introduces the RED framework and the GM-RED gradient-descent iteration that On-RED extends to online processing.","marker":"[34]"},{"why":"Provides the online plug-and-play algorithm whose stochastic-gradient analysis is adapted here to the RED operator.","marker":"[40]"},{"why":"Supplies the nonexpansiveness and descent bounds used in Proposition 2 and in the proof of Theorem 1.","marker":"[39]"},{"why":"Demonstrates RED with a deep CNN denoiser for phase retrieval, the application and baseline that On-RED targets.","marker":"[27]"},{"why":"Clarifies fixed-point convergence of RED without requiring an explicit regularizer, justifying the analysis route taken by this paper.","marker":"[33]"},{"why":"Defines coded diffraction patterns and the phase-retrieval measurement model used in the numerical experiments.","marker":"[11]"},{"why":"Supplies the DnCNN architecture on which the paper's DnCNN* denoiser is based.","marker":"[48]"},{"why":"Provides the monotone operator theory and averaged-operator framework underlying the fixed-point analysis.","marker":"[2]"}],"fun_headline_variants":["Online RED: one random measurement rivals full batch","Single-measurement online RED beats fixed-measurement baseline","On-RED: O(1/√t) convergence with minibatch gradients","Phase retrieval: online RED, one measurement per step, rivals full batch","Online denoising regularization: one measurement per step, near full-batch quality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every On-RED iterate stays within a fixed Euclidean ball of radius R₀ around the set of fixed points; this is assumed rather than derived, so if the iterates drift outside that ball the convergence bound no longer follows.","fun_headline_variants_meta":{"raw":{"variants":["Online RED: one random measurement rivals full batch","Single-measurement online RED beats fixed-measurement baseline","On-RED: O(1/√t) convergence with minibatch gradients","Phase retrieval: online RED, one measurement per step, rivals full batch","Online denoising regularization: one measurement per step, near full-batch quality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000723,"raw_usage":{"total_tokens":3235,"prompt_tokens":931,"completion_tokens":2304,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":2210}},"tokens_in":547,"tokens_out":2304,"duration_ms":17690,"temperature":1.0,"reasoning_tokens":2210,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:02:25.359019+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Track the quantity max_{x* ∈ zer(G)} ‖x_k − x*‖ during an On-RED run on a convex problem with γ = 1/(L+2τ) and a nonexpansive denoiser. If the iterate distance grows without bound, Assumption 2 fails and Theorem 1 does not apply; if it stays bounded but the empirical average of ‖G(x_{k-1})‖² violates the stated O(1/√t) rate, the theorem's constants or variance bound would be suspect.","supporting_citations":[{"cited_title":"Romano, M","cited_arxiv_id":null,"evidence_quote":"Introduces the RED framework and the GM-RED gradient-descent iteration that On-RED extends to online processing."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the online plug-and-play algorithm whose stochastic-gradient analysis is adapted here to the RED operator."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the nonexpansiveness and descent bounds used in Proposition 2 and in the proof of Theorem 1."},{"cited_title":"Metzler, P","cited_arxiv_id":null,"evidence_quote":"Demonstrates RED with a deep CNN denoiser for phase retrieval, the application and baseline that On-RED targets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Clarifies fixed-point convergence of RED without requiring an explicit regularizer, justifying the analysis route taken by this paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines coded diffraction patterns and the phase-retrieval measurement model used in the numerical experiments."},{"cited_title":"Zhang, W","cited_arxiv_id":null,"evidence_quote":"Supplies the DnCNN architecture on which the paper's DnCNN* denoiser is based."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the monotone operator theory and averaged-operator framework underlying the fixed-point analysis."}],"review_version":1}