{"id":"1e76042b-4cdc-4a2c-a454-d93a1677fc26","arxiv_id":"2411.16743","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"New accelerated Bregman proximal gradient algorithms with inexact oracles achieve O(1/N^2)-type rates for relatively smooth problems, with an adaptive intermediate variant interpolating between fast and robust rates.","lead":"This paper proposes accelerated optimization methods for minimizing functions that are smooth relative to a reference function, when gradients are noisy or inexact. It provides convergence rates and shows numerical gains on a Poisson inverse problem, though several technical assumptions need repair.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Accelerated rates require γ∈(1,2] but the Poisson inverse problem's IS divergence has γ<1; numerical experiments treat γ as a tunable parameter, so the central application is not covered by the theory.","rationale":"The reader's weakest assumption points exactly to the triangular scaling exponent restriction. This is the most load-bearing concern because it affects the paper's central advertised application: the Poisson inverse problem, whose natural prox-function yields an IS divergence with γ<1, is excluded from the accelerated rate guarantees. The numerical experiments sidestep the issue by treating γ as a free parameter, which is not legitimate because γ is a property of the divergence, not a hyperparameter. If the true γ is ≤1, then the O(1/N^γ) acceleration claimed in Theorem 4.5 does not hold for these experiments, and the comparison with non-accelerated BPG is not a valid test of the theory. The reader's verdict of CONDITIONAL is appropriate: the mathematical results may be correct under their assumptions, but the paper's scope and experimental validation need substantial revision. I would keep the verdict unchanged rather than escalate, because the concern is a scope/applicability gap rather than an internal contradiction of the theorem under its stated assumptions.","tokens_in":22987,"tokens_out":12508,"duration_ms":96130,"concrete_test":"Compute the actual triangular scaling exponent of the Itakura–Saito divergence VIS used in the Poisson experiments of Section 6 by evaluating, for random x,z,ẑ in the positive orthant and θ∈(0,1), the ratio V((1−θ)x+θz,(1−θ)x+θẑ)/V(z,ẑ) and taking the tightest uniform bound over many triples and θ values. If the observed exponent is at most 1, as Example 2.9 asserts, then rerun the Section 6 comparisons with the algorithm's γ set to that true value, keeping the prox-function fixed, and compare against the non-accelerated BPG baseline. If the reported acceleration disappears when γ is fixed to the divergence's actual value, the experimental claim in Section 6 is not supported by Theorem 4.5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 4.1, 4.5, and 5.4 depend on the Bregman divergence satisfying the triangular scaling property (Definition 2.6) with an exponent γ strictly in (1,2]. This exponent is a structural property of the divergence, not an algorithmic input that can be chosen freely. The paper's own Examples 2.8 and 2.9 state that the KL divergence has γ=1 and the Itakura–Saito divergence has γ<1. The motivating Poisson inverse problem (Example 2.3) uses the log-barrier prox-function d(x)=−Σ ln x_i, whose Bregman divergence is VIS, hence γ<1 by Example 2.9. Consequently the accelerated O(1/N^γ) guarantees of Theorems 4.1, 4.5, and 5.4 do not apply to the problem the paper advertises. The numerical experiments in Section 6 run the same Poisson problem with γ=2, 1.4, and 1.1, but replacing the algorithm's γ does not change the actual triangular scaling exponent of the IS divergence; no prox-function with γ∈(1,2] is specified for those runs. The proof of Theorem 4.5 also relies on the line-search condition L_{k+1} ≥ (θ_{k+1}/θ_k)^γ in Algorithm 3, a restriction not justified in the text, but the primary concern is that the central claim of accelerated rates for relatively smooth problems is not established for the non-Euclidean examples that motivate the paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes accelerated Bregman gradient methods with an inexact oracle for minimizing convex functions that are relatively smooth or relatively Lipschitz continuous with respect to a reference prox-function. It presents four algorithms: an adaptive fast gradient method based on similar triangles (Algorithm 1), a non-adaptive accelerated Bregman proximal gradient method (Algorithm 2), an adaptive version of it (Algorithm 3), and an adaptive intermediate Bregman method (Algorithm 4) that interpolates between accelerated and non-accelerated behavior. Convergence-rate theorems are stated for the relatively smooth case (Theorems 3.1, 4.1, 4.5, and 5.4) in the presence of an inexact oracle, and the universality of the methods for relatively Lipschitz continuous problems is argued informally. The paper concludes with numerical experiments on a Poisson inverse problem comparing the proposed algorithms with an adaptive Bregman proximal gradient method.","tokens_in":23371,"tokens_out":10427,"duration_ms":83947,"significance":"If the results are correct, they would constitute a useful extension of accelerated Bregman proximal methods to the inexact-oracle setting and introduce an interesting noise-robust intermediate method. The proofs are self-contained, and the non-adaptive Theorem 4.1 appears coherent. However, the actual scope is considerably narrower than advertised: the accelerated guarantees require the triangular scaling property with exponent γ strictly in (1,2], while the motivating Poisson inverse problem uses a divergence with γ<1, and numerical experiments treat γ as a freely tunable parameter. In addition, the adaptive line-search condition in Algorithm 3 is scale-inconsistent and breaks the proof of Theorem 4.5. These are load-bearing issues that prevent acceptance in the present form.","major_comments":[{"comment":"The line-search condition L_{k+1} ≥ (θ_{k+1}/θ_k)^γ in Algorithm 3 is scale-inconsistent: the right-hand side is dimensionless, while L_{k+1} scales with the relative smoothness parameter. If the true parameter L is less than 1, then for large k this condition forces L_{k+1} to be at least about 1, and the assumption L_1 < 2L need not imply L_N < 2L. The proof of Theorem 4.5 explicitly uses this condition in the chain following Eq. (47) to replace θ_k^γ L_{k+1} by θ_{k+1}^γ, so the final bound (46) is not justified. The condition should be replaced by a scale-corrected version, for example L_{k+1} ≥ (θ_{k+1}/θ_k)^γ L_k or another form that respects the scaling of L.","section":"§4.2, Algorithm 3, line 8"},{"comment":"The accelerated convergence results in Theorems 3.1, 4.1, and 4.5 assume the triangular scaling property with γ ∈ (1,2]. The paper's own Examples 2.8 and 2.9 state that the KL divergence has γ=1 and the Itakura–Saito divergence has γ<1, while Example 2.3, which motivates the paper, uses the log-barrier prox-function d(x)=−Σ ln x_i, whose Bregman divergence is VIS. Hence γ<1 for the Poisson inverse problem, and the convergence theorems do not apply to the problem advertised in the abstract. The numerical experiments in Section 6 run the same Poisson problem with γ=2, 1.4, and 1.1, but γ is a structural property of the divergence rather than an algorithmic input; no prox-function satisfying triangular scaling with those exponent values is specified for the experiments. The claims and experiments should be restricted to divergences with γ∈(1,2], or the experimental setup must be justified by explicit prox-functions for each γ.","section":"§6 and Examples 2.8–2.9"}],"minor_comments":[{"comment":"The name 'Itakuro–Saito divergence' is a typo; it should be 'Itakura–Saito divergence'.","section":"Example 2.9"},{"comment":"The update L_{k+1}=2^{i_k−1}L_k gives L_{k+1}=L_k/2 when i_k=0; clarify whether the exponent is intended to be i_k or explain why halving is allowed, and state that the line search terminates in finite time.","section":"Algorithm 1, line 4"},{"comment":"The while condition at line 3 refers to y0 before y0 is computed in line 5; the pseudocode should be reordered so that y0 is initialized before the condition is evaluated, or a repeat-until form should be used.","section":"Algorithm 4, lines 3–5"},{"comment":"The statement uses V(x0,x*)=d(x*)≤R0, but this equality holds only when x0 minimizes d and d(x0)=0; the assumption should be stated as V(x0,x*)≤R0 or d(x*)≤R0.","section":"Theorem 5.4 and Corollary 5.3"},{"comment":"The assumption 0<α_k≤B_k≤A_k is stated for all k but is not verified in the paper; please add a short proof or a reference showing that the updates of Algorithm 4 maintain these inequalities.","section":"Eq. (52) and Theorem 5.4 proof"},{"comment":"The manuscript contains numerous typographical and grammatical errors (e.g., 'we concluded its convergence rate', 'Itakuro–Saito', 'with constant γ >0'); a thorough language revision is recommended.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper's references [12], [13], and [28] have substantial author overlap with the present authors, but the new proofs appear self-contained rather than circular. The main obstacle is the combination of the scale-inconsistent adaptive line search and the mismatch between the γ∈(1,2] assumption and the Poisson inverse problem's divergence; these are fixable in principle but require substantial rewriting of Sections 4.2 and 6. The numerical experiments would also benefit from reproducible code and a precise description of the prox-structure used for each reported γ value."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has real new material: accelerated Bregman proximal gradient methods with inexact oracles, both non-adaptive and adaptive, plus an adaptive intermediate method. The convergence proofs are mostly coherent and self-contained, and the nonlinear acceleration rate for the non-adaptive case is a legitimate extension of known APBG results. No fitted constants, no circularity. I'd credit the authors for that.\n\nThe soft spot is the one the stress-test flagged, and it's real. Definition 2.6 and Examples 2.8–2.9 state that KL has γ=1 and the Itakura–Saito divergence has γ<1. The Poisson inverse problem (Example 2.3) uses the log-barrier prox-function, whose Bregman divergence is IS. Yet Theorems 4.1, 4.5, and 5.4 all require γ∈(1,2]. The experiments in Section 6 vary γ as if it were a tunable parameter (2, 1.4, 1.1) without changing the prox-function. That is a load-bearing mismatch: the accelerated rates simply do not apply to the IS divergence, so the paper's central numerical demonstration is not backed by its theory. The authors need to either switch to a prox-function with γ>1 or explicitly limit the accelerated claims to such divergences.\n\nA smaller issue: Algorithm 3's line search asks for L_{k+1} ≥ (θ_{k+1}/θ_k)^γ, a dimensionless bound. When the true L is small (less than 1), this can push L above 2L, breaking the assumption L_N<2L used in Theorem 4.5. That proof needs a scaling fix.\n\nThe \"universality\" claims for relatively Lipschitz functions only show that the line search terminates; no convergence rates are given. Fine, but the wording overstates what is proven.\n\nOverall, the core theoretical contributions are worth having and the paper should go to peer review. The numerical section must be reconciled with the γ requirement, and the adaptive proof needs attention. I'd send it out with expectation of major revision.","headline":"Useful new accelerated Bregman methods with inexact oracles, but the advertised Poisson inverse problem application is not covered by the theory because its divergence has the wrong scaling exponent.","tokens_in":23887,"tokens_out":4214,"would_cite":true,"duration_ms":36659,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Accelerated Bregman proximal gradient methods keep their convergence rate when the oracle is inexact, up to an additive noise term, provided the Bregman divergence obeys a triangular scaling inequality with exponent between 1 and 2.","keywords":["convex optimization","accelerated Bregman proximal gradient","inexact oracle","relative smoothness","relatively Lipschitz continuity","triangular scaling property","adaptive fast gradient method","intermediate Bregman method"],"falsifier":"Evaluate the triangular scaling inequality numerically for the prox-function used in an application: draw random triples $(x,z,\\tilde z)$ and compare $V((1-\\theta)x+\\theta z,(1-\\theta)x+\\theta\\tilde z)$ with $\\theta^\\gamma V(z,\\tilde z)$. If the smallest exponent that fits is $\\le1$, then the proof step behind Theorem 4.5 is invalid for that problem and the accelerated guarantee cannot be certified; for the Poisson experiments with the log-barrier prox, the paper's own Example 2.9 indicates exactly this situation.","tokens_in":22785,"feed_emoji":"⚡","tokens_out":10305,"duration_ms":89964,"temperature":0.7,"pith_summary":"This paper tries to establish that accelerated Bregman proximal gradient methods still converge at their fast rates when the optimization oracle is inexact, meaning that only approximate function values and gradients are available. For a convex function that is relatively smooth with respect to a reference prox-function, it proposes an adaptive fast gradient method and two accelerated Bregman proximal gradient methods, and proves rates of the form $O(L(\\gamma/(\\gamma+N))^\\gamma V(x_*,x_0))$ plus an additive term proportional to the noise level $\\delta$. The same algorithms are shown to apply to relatively Lipschitz continuous objectives, and an adaptive intermediate method interpolates between slower, noise-tolerant and faster, noise-sensitive regimes. A sympathetic reader would care because noisy gradients are the norm in large-scale machine learning and inverse problems, and the paper's message is that acceleration need not be sacrificed in that setting.","feed_headline":"Inexact gradients still accelerate relatively smooth minimization","feed_subtitle":"Accelerated Bregman proximal methods retain their rate under inexact oracles, with an adaptive middle path between speed and stability.","key_machinery":"The load-bearing object is the triangular scaling property of the Bregman divergence $V(x,y)=d(x)-d(y)-\\langle\\nabla d(y),x-y\\rangle$: the inequality $V((1-\\theta)x+\\theta z,(1-\\theta)x+\\theta \\tilde z)\\le \\theta^\\gamma V(z,\\tilde z)$ for every $\\theta\\in[0,1]$. This inequality is what lets the proofs bound the Bregman distance between the convex combination points $y_k=(1-\\theta_k)x_k+\\theta_k z_k$ and $x_{k+1}=(1-\\theta_k)x_k+\\theta_k z_{k+1}$ by $\\theta_k^\\gamma V(z_{k+1},z_k)$, converting the algorithm's updates into a telescoping Lyapunov inequality. The second ingredient is the $(\\delta,L)$-oracle model $0\\le f(x)-\\left(f_\\delta(y)+\\langle\\nabla f_\\delta(y),x-y\\rangle\\right)\\le LV(x,y)+\\delta$, and the third is relative smoothness, $f(y)\\le f(x)+\\langle\\nabla f(x),y-x\\rangle+LV(y,x)$, which replaces the usual Lipschitz-gradient upper model.","core_discovery":"The central claim is that the inexact-oracle accelerated Bregman proximal gradient method, under the triangular scaling property with exponent $\\gamma\\in(1,2]$, satisfies $f(x_N)-f(x_*) \\le 2L\\left(\\frac{\\gamma}{\\gamma+N-1}\\right)^\\gamma V(x_*,x_0)+(2(N-1)L+1)\\delta$ after $N$ iterations; in the noiseless limit $\\delta=0$ this recovers the $O(1/N^\\gamma)$ rate of the exact-oracle method. The paper also proves a similar-triangles fast gradient method with rate $8LR^2/(N+1)^2 + \\frac{2}{A_N}\\sum_{k=0}^{N-1}A_{k+1}\\delta_k$, and an adaptive intermediate Bregman method whose rate $(k+2)^{-(p-1)(\\gamma-1)-1}$ interpolates between non-accelerated ($p=1$) and accelerated ($p=2$) behaviour. The universality statements extend both accelerated families to relatively Lipschitz continuous objectives, at the cost of a slightly degraded oracle in the line-search test.","pith_inferences":["A design lesson the paper leaves implicit is that the triangular scaling exponent should be treated as a selection criterion for the prox-function, since the Kullback-Leibler and Itakura-Saito divergences lie outside the accelerated regime.","One testable extension would be to estimate $\\gamma$ numerically for a candidate divergence and use it as a pre-screening test before committing to an accelerated Bregman method.","The growth of the noise term in Theorem 4.5 suggests that when $\\delta$ is fixed and not small, a user should switch to the intermediate method; this is a practical reading of the interpolation the authors construct."],"forward_implications":["For any relatively smooth problem whose prox-function has a triangular scaling factor $\\gamma\\in(1,2]$, inexact oracles preserve the accelerated rate; noise only adds a term proportional to $\\delta$.","The same iterations solve relatively Lipschitz continuous problems, so the methods are universal in the sense the paper states.","The adaptive intermediate method gives a user a dial $p\\in[1,2]$ between non-accelerated and accelerated convergence, without switching algorithms.","In the Euclidean case $\\gamma=2$, the intermediate method's rate is $(k+2)^{-p}$ plus $(k+2p)^{p-1}\\delta$, making the interpolation explicit.","With fixed noise $\\delta$, the bound in Theorem 4.5 grows linearly in $N$, so the method is best viewed as achieving accuracy of order $\\delta$ rather than converging to zero."],"supporting_citations":[{"why":"Supplies the accelerated Bregman proximal gradient prototype and the triangular scaling property definition reused throughout the proofs.","marker":"[6]"},{"why":"Provides the $(\\delta,L)$-oracle definition and the similar-triangles fast gradient template that Algorithm 1 adapts.","marker":"[12]"},{"why":"Establishes the relative smoothness condition and shows the Poisson and D-optimal design problems fit it.","marker":"[5]"},{"why":"Introduced relative smoothness and the descent lemma that motivates Bregman proximal steps.","marker":"[4]"},{"why":"Supplies the relative Lipschitz continuity inequality used to prove universality of Algorithms 1 and 3.","marker":"[28]"},{"why":"Provides the universal intermediate gradient method whose Bregman version Algorithm 4 is designed to match.","marker":"[13]"},{"why":"Is the non-accelerated adaptive Bregman proximal gradient baseline used in the numerical comparisons.","marker":"[31]"}],"fun_headline_variants":["Boost Bregman methods: noisy oracles don't slow them down","Accelerated Bregman stays fast even with inexact gradients","Adaptive Bregman: speed and robustness combined","Universal acceleration for smooth and Lipschitz problems","New Bregman methods: fast, noisy-tolerant, adaptive"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire argument rests on the chosen Bregman divergence satisfying the triangular scaling inequality with an exponent strictly between 1 and 2; the paper's own examples show the Kullback-Leibler divergence has exponent 1 and the Itakura-Saito divergence has exponent below 1, so the accelerated guarantees do not cover those natural measures.","fun_headline_variants_meta":{"raw":{"variants":["Boost Bregman methods: noisy oracles don't slow them down","Accelerated Bregman stays fast even with inexact gradients","Adaptive Bregman: speed and robustness combined","Universal acceleration for smooth and Lipschitz problems","New Bregman methods: fast, noisy-tolerant, adaptive"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000397,"raw_usage":{"total_tokens":2088,"prompt_tokens":965,"completion_tokens":1123,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":1039}},"tokens_in":581,"tokens_out":1123,"duration_ms":10596,"temperature":1.0,"reasoning_tokens":1039,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:05:33.624640+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the triangular scaling inequality numerically for the prox-function used in an application: draw random triples $(x,z,\\tilde z)$ and compare $V((1-\\theta)x+\\theta z,(1-\\theta)x+\\theta\\tilde z)$ with $\\theta^\\gamma V(z,\\tilde z)$. If the smallest exponent that fits is $\\le1$, then the proof step behind Theorem 4.5 is invalid for that problem and the accelerated guarantee cannot be certified; for the Poisson experiments with the log-barrier prox, the paper's own Example 2.9 indicates exactly this situation.","supporting_citations":[{"cited_title":"Adaptive Algorithms for Relatively Lips- chitz Continuous Convex Optimization Problems","cited_arxiv_id":null,"evidence_quote":"Supplies the relative Lipschitz continuity inequality used to prove universality of Algorithms 1 and 3."}],"review_version":1}