{"id":"6edc1fcb-4da9-40df-9620-3378c72c0371","arxiv_id":"2607.16003","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Averaged, noise-weighted Bregman–Kaczmarz recovers the exact solution under fresh independent noise, with convergence that provably improves as the batch size grows.","lead":"Averaging several corrupted measurements per step and down-weighting the noisier ones makes the adaptive Bregman–Kaczmarz algorithm provably faster as the batch grows, with exact recovery of the true solution still guaranteed. The result is useful for tomographic and signal-recovery problems where every measurement is noisy but batches can be processed in parallel.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1 omits the condition x*_0 ∈ R(A^T); without it the proof of Lemma 4.2 cannot apply Assumption 3.2 and the theorem is false as stated.","rationale":"The reader identified the independent-noise model and the σ_i = 0 edge case as the weakest assumptions. Those are real limitations, but the most load-bearing gap is more specific and more central: Theorem 2.1 as stated is false because it omits the requirement x*_0 ∈ R(A^T). The proof's use of Assumption 3.2 at every iterate requires the dual iterates to remain in R(A^T); this is not guaranteed by the algorithm unless the initial dual point lies there. The counterexample A = [1,0], x*_0 = (0,1) is a minimal instance where the theorem's conclusion fails while all stated hypotheses hold. This is a missing hypothesis rather than a broken proof idea, so the appropriate outcome is conditional acceptance pending an explicit initialization condition and a corrected statement. I also noted a secondary, non-central issue: Appendix E's closed-form solution of the step-size ODE has a sign error — the proposed u(t) = K·W₀(c₀e^{at}) has du/dt > 0 while the ODE has du/dt < 0, so Corollary 2.4's displayed formula is wrong even though its stated 1/k tail is correct. This further supports a CONDITIONAL verdict rather than ACCEPT.","tokens_in":26899,"tokens_out":43192,"duration_ms":370044,"concrete_test":"Analytic counterexample check: run Algorithm 1 with A = [1, 0], b = 0, f(x) = 0.5‖x‖², x*_0 = (0,1), σ₁ > 0, τ = 1, and any (p₁,w₁) satisfying (3). The residual is identically zero, so d_k = 0, η_k is irrelevant, and x_k = (0,1) for all k; (8) would require convergence to 0, a contradiction. Re-run with x*_0 = 0 to confirm the theorem holds once the missing hypothesis is added.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 2.1 claims exact recovery for iterates generated by (4)–(5) under only the coupling (3) and Assumption 3.2. But Lemma 4.2 applies Assumption 3.2 with x = x_k and x* = x*_k, which requires x*_k ∈ ∂f(x_k) ∩ R(A^T). Since d_k ∈ R(A^T), the iterate update x*_{k+1} = x*_k − η_k d_k preserves membership in R(A^T) only if x*_0 ∈ R(A^T). The theorem never states this. If x*_0 has a component in null(A), that component is never updated, and x_k converges to ∇f*(x*_hat + z), not to xhat. Concrete counterexample: A = [1, 0], b = 0, f(x) = 0.5‖x‖², x*_0 = (0,1), any σ₁ > 0. Then the single row has residual zero at every iterate, so d_k = 0 for all k and x_k = (0,1) forever, while (8) predicts E‖x_k − 0‖² ≤ (2C/τ)β_k → 0. The fix is to add the standard initialization condition x*_0 ∈ R(A^T) (e.g., x*_0 = 0), which also makes the induction in the proof valid. As printed, the main theorem has a missing hypothesis that is load-bearing for the central exact-recovery claim.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Adaptive Averaged Bregman-Kaczmarz (AABK) method for linear inverse problems in which every queried measurement is corrupted by fresh, independent, zero-mean noise. The method averages a batch of weighted Bregman-Kaczmarz updates and uses an adaptive step size. The main result (Theorem 2.1) gives a bound on the expected squared error, E||x_k - x_hat||^2 <= (2 Tr(PW^2 Sigma D^{-2})/tau) beta_k, with beta_k -> 0, implying exact recovery of the minimum-f solution. The authors prove that the guaranteed contraction improves monotonically with batch size tau, propose noise-aware weights that minimize the noise prefactor, and analyze the step-size asymptotics. Numerical experiments on synthetic data and CT reconstruction support the qualitative claims.","tokens_in":27365,"tokens_out":13300,"duration_ms":134667,"significance":"If the main theorem is correct, the paper resolves a genuine open question: whether block/batch versions of adaptive Bregman-Kaczmarz can be proven to accelerate with batch size. The key reduction to a single positive-semidefinite matrix T is elegant, and the combination of averaging, adaptive stepping, and noise-aware weighting is a meaningful advance over the authors' earlier ABK and RSKA methods. The paper is also carefully written, with detailed appendices for the one-step bound, spectral estimates, the step-size recursion, and the optimal-weight derivation. The numerical experiments are relevant and support the main qualitative predictions. However, the central theorem as stated has a missing initialization hypothesis that makes it false, and the superiority claim for the noise-aware weights is only established for the prefactor, not for the full convergence bound. These issues are fixable but currently compromise the paper's main claims.","major_comments":[{"comment":"The main theorem is false as stated because it omits the initialization condition x*_0 in R(A^T). Lemma 4.2 applies Assumption 3.2 at x = x_k, x* = x*_k, which requires x*_k in ∂f(x_k) ∩ R(A^T). Since d_k in R(A^T), this membership is preserved only if x*_0 in R(A^T). Without it, the null(A) component of x*_0 is never updated. Concrete counterexample: A = [1,0], b = 0, f(x) = 0.5||x||^2, x*_0 = (0,1), any σ_1>0. The single row has zero residual at every iterate, so d_k = 0 and x_k = (0,1) for all k, while (8) predicts convergence to 0. Add the explicit hypothesis x*_0 in R(A^T) (e.g., x*_0 = 0) to Theorem 2.1 and Algorithm 1.","section":"Theorem 2.1, Lemma 4.2, Assumption 3.2"},{"comment":"The optimal noise-aware weighting p_i ∝ σ_i||a_i||, w_i ∝ ||a_i||/σ_i is derived by minimizing Σ σ_i^2||a_i||^2/p_i over p_i ≥ 0. If σ_i = 0 for a noiseless row, the formal minimizer sets p_i = 0, which violates the standing coupling (3) because the right-hand side α/||A||_F^2 is positive for every i. The elimination step w_i = α||a_i||^2/(p_i||A||_F^2) then also becomes undefined. Moreover, Theorem 2.1 divides by Tr(PW^2ΣD^{-2}), so this quantity must be positive. Please state explicitly that σ_i > 0 for all i, or introduce an epsilon-floor in the sampling distribution and adjust the optimality claim.","section":"Corollary 2.3, §4.5, Eq. (3)"},{"comment":"The claimed strict superiority of the noise-aware weights over uniform weighting is established only for the prefactor C_noise = Tr(PW^2ΣD^{-2}), not for the full expected-error bound (8). The weights W also enter the matrix T in (6) and hence the step sequence and the decay factor β_k. The optimal weights can make σ_max(T) (or the certified bound U(τ)) much larger than in the uniform case W = αI, slowing the decay of β_k. For example, with A = [1;1], τ = 1 and σ = (1, ε), the optimal weights give σ_max(W) ≈ 1/(2ε), whereas uniform gives σ_max(W) = α. Thus a smaller prefactor can be offset by a slower rate; the paper's abstract and contribution list state that the weighting is 'strictly better' without qualifying this. Please either prove a comparison for the full bound or explicitly restrict the claim to the noise prefactor and asymptotic tail.","section":"Corollary 2.3 / Abstract, Eq. (8)"}],"minor_comments":[{"comment":"The SSIM/PSNR row contains missing separators: '0.86120.9409' and '24.547931.6334' should be separate values with proper column separation.","section":"Table 2"},{"comment":"The vertical axis label 'xK' should be 'x_k' (or |x_k - x_hat|/|x_hat|).","section":"Figure 3"},{"comment":"The main text says 'The detailed proof of this lemma can be found in [24]', but Appendix C contains a full proof. Cite the appendix instead, or remove the reference to [24].","section":"Lemma 4.3"},{"comment":"The heuristic estimators replace x_hat by x_N without stating the approximation clearly. Please clarify that the formulas are computed with Bregman distances to x_N and are therefore only valid when x_N is sufficiently close to x_hat.","section":"§2.6, Eqs. (9)-(10)"},{"comment":"The algorithm input should include the initialization condition x*_0 ∈ R(A^T) (or x*_0 = 0) in view of the missing hypothesis in Theorem 2.1.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one. The core idea — averaging the block updates and combining with the adaptive Bregman–Kaczmarz step — is genuinely new, and the reduction to a single PSD matrix T is elegant. But the main theorem is false as stated: it omits the standard initialization condition x*_0 ∈ R(A^T). Concrete counterexample: A = [1, 0], b = 0, f(x) = ½‖x‖², x*_0 = (0,1). The single row has zero residual for every iterate, so d_k = 0 forever, x_k stays at (0,1), while (8) predicts convergence to 0. The induction in Lemma 4.2 applies Assumption 3.2 at x_k with x*_k, which requires x*_k ∈ R(A^T); the update preserves that only if x*_0 is in R(A^T). So the theorem needs one extra hypothesis. That is a small fix — x*_0 = 0 works and is what the experiments actually use — but it is load-bearing and must be stated.\n\nWhat is genuinely good: the monotone-in-τ guarantee with stable-rank gain via the averaged T matrix, the noise-aware weights p_i ∝ σ_i‖a_i‖ with the Cauchy–Schwarz optimality argument, and the clean step-size asymptotics (Lambert-W, 1/k tail). The related-work table correctly identifies this cell as empty; [27] explicitly left block-size acceleration open. Lemma 4.3 is deferred to [24], which is acceptable if that reference is solid. The self-citations are legitimate here: the new content is derived from first-principles bounds, not fitted.\n\nOther soft spots, in decreasing order. (1) The optimal weights give p_i = 0 for a noiseless row (σ_i = 0), so that row is never sampled; the paper neither assumes σ_i > 0 nor discusses the edge case. (2) The synthetic headline comparisons use oracle β_0 (ground truth) for ABK and AABK, which flatters them; the CT heuristic runs are more honest. (3) No error bars or released code.\n\nVerdict: this deserves a serious referee. Fix the missing hypothesis, clean up the experimental protocol, and separate the exact-β_0 theorem from the heuristic estimators, and it becomes a solid contribution. I'd take it to reading group as-is — the flaw is instructive.","headline":"The averaging-plus-adaptive-step idea is real and the T-matrix analysis is clean, but Theorem 2.1 is false as stated because it omits the standard initialization x*_0 in R(A^T).","tokens_in":792,"tokens_out":1560,"would_cite":false,"duration_ms":37872,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F10","15A29","65F20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that an averaged, noise-weighted, adaptively stepped Bregman-Kaczmarz method recovers the exact noise-free solution of a consistent linear system even when every query carries fresh zero-mean noise, and that its guaranteed","keywords":["randomized Bregman-Kaczmarz","adaptive stepsize","averaging","inverse problems","block methods","heteroscedastic noise","exact recovery","stable rank"],"falsifier":"Run AABK on a fixed random Gaussian system (m=2000, n=100) with known per-row variances, compare the expected error at a fixed iteration for τ=1 and τ=20, and check that the τ=20 curve continues to decrease to zero at the rate predicted by the stable rank factor; a plateau above the noise floor, or a slowdown inconsistent with the predicted factor, would contradict the bound (8).","tokens_in":26787,"feed_emoji":"🎯","tokens_out":8834,"duration_ms":74689,"temperature":0.7,"pith_summary":"The paper claims that a block version of the adaptive Bregman-Kaczmarz method can both provably accelerate with batch size and still recover the exact noise-free solution of a consistent linear system, even though every measurement it queries carries freshly drawn zero-mean noise. The key move is to average the block updates rather than sum them; this collapses the analysis onto a single positive semidefinite matrix T whose largest eigenvalue decreases monotonically with the batch size. The paper further introduces a noise-aware weighting and sampling rule that provably lowers the rate constant below uniform weighting whenever row noise is not proportional to row norms—a condition the authors argue is 'essentially never' met in practice. If true, this would be the first averaged adaptive Bregman-Kaczmarz method with proven exact recovery and batch-size acceleration, offering a practical way to exploit parallel hardware and heterogeneous noise information simultaneously.","feed_headline":"Larger batches provably speed exact recovery under fresh noise","feed_subtitle":"Averaging, not summing, row updates makes bigger batches provably faster—and still hits exactly zero.","key_machinery":"The central object is the positive semidefinite matrix T = (1/(2τ))W + (α/(2||A||_F^2))(1 − 1/τ)AA^T, which combines the weight matrix W, the Gram matrix AA^T, the batch size τ, and the relaxation α. Its spectral radius σ_max(T) sets the per-step contraction, and because the update is an average rather than a sum, σ_max(T) decreases with τ, making larger batches provably faster. The adaptive step η_k = αγβ_k / (1 + 2αγσ_max(T)β_k) with β_{k+1} = β_k(1 − αγη_k/2) is the second load-bearing mechanism: the shrinking tail of β_k (and hence η_k ~ 1/k) averages out the fresh noise and drives the error exactly to zero. The coupling (3), p_i w_i / ||a_i||^2 = α/||A||_F^2, ties sampling probabilities","core_discovery":"Under the independent-noise model (each query of row j returns b_j plus a fresh zero-mean error of known variance σ_j^2), with the coupling p_i w_i / ||a_i||^2 = α/||A||_F^2 and the error-bound Assumption 3.2, Theorem 2.1 states that the iterates of Algorithm 1 satisfy E||x_k − x̂||^2 ≤ (2 Tr(PW^2ΣD^{-2})/τ) β_k, where β_k is deterministic and decreases to zero; hence the iterates converge in expectation to the exact noise-free solution. The proof reduces to the PSD matrix T = (1/2τ)W + (α/(2||A||_F^2))(1 − 1/τ)AA^T: its largest eigenvalue controls the contraction factor, and the 1/τ factor from averaging is what makes σ_max(T) shrink with τ. Proposition 2.2 shows the guaranteed rate improve","pith_inferences":["Because the variance reduction enters through the 1/τ factor in T, the averaging trick is not specific to Bregman-Kaczmarz; any row-action or stochastic-gradient method whose update is a sum could likely be averaged to obtain a similar batch-size monotonicity, as long as fresh noise is available.","The optimal weighting requires knowing each σ_i; an untested but natural extension is to estimate variances online by querying each row repeatedly at startup, then feed the estimates into the weighting rule.","The paper proves expectation bounds; the natural next step (which the authors note) is high-probability concentration, which would be needed for single-run guarantees in real-time imaging or control.","The observation that the averaged step permits η_k > 1 suggests an over-relaxation principle for noisy stochastic iterations generally; early over-relaxation plus tail decay might accelerate other adaptive stochastic algorithms."],"forward_implications":["If Theorem 2.1 holds, exact recovery from fresh noisy measurements requires no regularization beyond the strongly convex penalty f; the noise is averaged away by the adaptive step, not suppressed by a noise ball.","The monotonicity result means doubling the batch size strictly improves the guaranteed contraction (for uniform weights), so parallel hardware that can evaluate more rows per step is directly converted into a provably faster method.","The noise-aware weighting gives a principled way to prioritize measurements: sample rows in proportion to σ_i ||a_i|| and weight them inversely to their noise—a concrete recipe for heteroskedastic sensor noise.","The step-size analysis (Corollary 2.4) shows the method is self-tuning between regimes: a constant over-relaxed step early (even >1, unlike standard ABK) and a 1/k Robbins-Monro tail later; users do not need to switch step rules.","The heuristic estimation of γ and β_0 from one auxiliary run means the method can be deployed without access to the true solution, needing only the two phase-window indices N_0 and N_1."],"fun_headline_variants":["Averaging instead of summing makes bigger batches provably faster","Noise-aware weights improve exact recovery: averaging wins","Batch averaging yields provable speedup for exact recovery","Averaging, not summing, accelerates exact recovery","Bigger batches faster? Only if you average the rows"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire exact-recovery guarantee rests on the independent-noise model: every query of a row returns a fresh, zero-mean error with known strictly positive variance, because it is the shrinking step size averaging over these fresh errors that drives the iterates to the exact solution.","fun_headline_variants_meta":{"raw":{"variants":["Averaging instead of summing makes bigger batches provably faster","Noise-aware weights improve exact recovery: averaging wins","Batch averaging yields provable speedup for exact recovery","Averaging, not summing, accelerates exact recovery","Bigger batches faster? Only if you average the rows"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000401,"raw_usage":{"total_tokens":1970,"prompt_tokens":828,"completion_tokens":1142,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":1063}},"tokens_in":572,"tokens_out":1142,"duration_ms":9039,"temperature":1.0,"reasoning_tokens":1063,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T21:38:04.716782+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run AABK on a fixed random Gaussian system (m=2000, n=100) with known per-row variances, compare the expected error at a fixed iteration for τ=1 and τ=20, and check that the τ=20 curve continues to decrease to zero at the rate predicted by the stable rank factor; a plateau above the noise floor, or a slowdown inconsistent with the predicted factor, would contradict the bound (8).","supporting_citations":[],"review_version":1}