{"id":"b1857752-e8f8-400d-af6c-327c6a4d2bc2","arxiv_id":"2508.01353","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Adaptive, linesearch-free Bregman proximal gradient algorithms are proven convergent under only local relative smoothness, via a new Bregman-Young inequality.","lead":"This paper develops two linesearch-free adaptive Bregman proximal gradient algorithms that choose stepsizes from local curvature estimates and prove convergence without global relative smoothness or strong convexity. A Bregman version of Young's inequality is the key tool, and numerical tests show faster progress than several existing Bregman methods on Poisson regression, simplex barrier problems, and unconstrained quartic problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.2 asserts without proof that gamma_k -> 0 forces x_k to converge; this is false in general and the proof needs a weaker consecutive-difference argument to justify Lambda -> 1.","rationale":"The reader identified the same weak point as the most load-bearing concern, and I agree: Lemma 4.2's proof contains an unsupported and, taken literally, false assertion that gamma_k -> 0 forces convergence of the entire iterate sequence in a compact set. The proof of the main convergence result (Theorem 4.4, and consequently Eq. (2.8)) relies on Lemma 4.2 to rule out vanishing stepsizes; without a valid argument the central claim is not established. The concern is real but likely patchable, because the proof only needs the consecutive gradients to coalesce, not full sequence convergence. I also checked the later part of Theorem 4.4: the definition of v_k in Section 4.1 has an indexing error (it should be H_k(x_{k-1}) - H_k(x_k), which lies in gamma_k times the subdifferential), but this is a minor typo that does not change the conclusion. The unproved rate claim in Remark 2.6(i) is not load-bearing for the main theorem. Overall, the paper's methodology is sound in outline, and the flagged gap justifies a conditional verdict rather than rejection.","tokens_in":29140,"tokens_out":42102,"duration_ms":457080,"concrete_test":"Independently prove Lemma 4.2 using only the weaker fact that gamma_k -> 0 implies D_phi(x_{k+1}, x_k) -> 0 (by continuity of the Bregman prox at gamma = 0), hence xi_k - eta_k -> 0 on the compact set K. Then re-derive the bound |Lambda_{k,delta} - 1| -> 0 without assuming convergence of x_k. If the weaker fact fails under Assumption 2.1, the concern lands; if it holds, the lemma is valid and the central proof stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 4.2, to show Lambda_{k,delta} -> 1 under gamma_k -> 0, the proof states 'standard results ensure that (x_k) converges to some point x in K'. This assertion is not established and is false in general: a sequence in a compact set with ||x_{k+1}-x_k|| -> 0 need not converge. The paper only needs xi_k - eta_k -> 0, which would follow from ||nabla phi(x_k) - nabla phi(x_{k-1})|| -> 0; this in turn follows from gamma_k -> 0 via the limit prox_{gamma g}(y) -> y, but that argument is not given. Since Claim 2 uses Lemma 4.2 to ensure that the second term in the min (2.6)/(2.7) eventually exceeds rho-hat, forcing gamma_{k+1} = rho-hat_{k+1} gamma_k and contradicting gamma_k -> 0, the proof of Theorem 4.4 (and hence Eq. (2.8)) collapses if the assertion cannot be replaced by a valid weaker claim. A secondary indexing error in Section 4.1 (v_k should be H_k(x_{k-1}) - H_k(x_k) in gamma_k times partial phi(x_k)) is also present but fixable by rescaling.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the composite convex minimization problem (P) in which the differentiable term f is only locally smooth relative to a Legendre kernel phi (Assumption 2.1). It proposes two adaptive Bregman proximal gradient algorithms, B-adaPG and B-adaPG-alpha, whose stepsizes are updated from local quantities l_k, Lambda_{k,delta}, and the local symmetry coefficient alpha_k, with no backtracking linesearch. The main result, Theorem 2.5, states that inf_k phi(x_k) = inf_C phi; under an interior-minimizer condition the iterates converge to a solution, and under Assumption 2.3 they are bounded with a unique optimal limit point. The analysis rests on a Bregman generalization of Young's inequality (Lemma 3.2) and a merit-function identity (Lemma 3.1). Numerical experiments cover polynomial-growth Hessians, KL regression, simplex barrier problems, and Euclidean problems, with comparisons to linesearch methods, BaGRAAL, ABPG-g, and Euclidean adaPG variants.","tokens_in":29402,"tokens_out":23204,"duration_ms":225094,"significance":"If the main results hold, this is a substantial advance in adaptive Bregman methods: it removes global relative smoothness, global strong convexity of the kernel, and backtracking linesearch while keeping a self-contained convergence proof from explicit assumptions. The Bregman-Young inequality is a clean and potentially reusable tool, and the local moduli are defined from iterates rather than fitted to the conclusion, so the analysis does not appear circular. The numerical study is broad and the paper is honest about its remaining open questions. However, the contribution is conditional: one load-bearing lemma is proved by an unjustified convergence assertion, and the displayed stepsize updates appear to have a missing reciprocal. These issues must be resolved before the central claims are fully supported.","major_comments":[{"comment":"The proof asserts that if gamma_k -> 0, then 'standard results ensure that (x_k) converges to some point x in K'. This is not a standard consequence of the assumptions: gamma_k -> 0 does not by itself imply ||x_k - x_{k-1}|| -> 0, and even that weaker condition would not force convergence of a sequence in a compact set. The assertion is load-bearing, because Claim 2 of Theorem 4.4 uses Lemma 4.2 to conclude that the second term in (2.6)/(2.7) eventually forces gamma_{k+1} = rho-hat_{k+1} gamma_k, contradicting gamma_k -> 0. Without a valid proof of Lambda_{k,delta} -> 1, the argument for Theorem 4.4 and hence Eq. (2.8) collapses. The proof should be repaired by a direct argument that does not require convergence of (x_k), for example by showing that the Bregman proximal step with vanishing stepsize satisfies Delta_phi(x_k, x_{k-1}) -> 0 and then estimating the ratio defining Lambda_{k,delta} via the mean-value theorem and continuity of nabla^2 phi* on the compact set nabla phi(K).","section":"Lemma 4.2 (Section 4.2)"},{"comment":"As displayed, the second argument of the minimum is proportional to [Lambda_{k,delta} - (1 - gamma_k l_k)]_+ and not to its reciprocal. Consequently, whenever Lambda_{k,delta} <= 1 - gamma_k l_k, the update would give rho_{k+1} = 0, contradicting Remark 2.4 (which states that in this case all updates reduce to rho_{k+1} = rho-hat_{k+1}), contradicting Claim 2 in Section 4.1, and contradicting the requirement that all stepsizes remain positive. The derivation in Section 3.3 leading to (3.16), together with the logic of Claim 2, indicates that the bracket should appear in the denominator, i.e. rho_{k+1} = min(rho-hat_{k+1}, alpha_k/(1+alpha_k) * 1/(2 rho-hat_{k+1} [Lambda_{k,delta} - (1 - gamma_k l_k)]_+)), with the analogous correction in (2.7). The displayed formulas must be corrected and all subsequent uses checked against the corrected update.","section":"Section 2.2, Eqs. (2.6)-(2.7)"},{"comment":"The definition v_k := H_{k-1}(x_{k-1}) - H_{k-1}(x_k) is not an element of gamma_k partial phi(x_k). From (3.4b) the correct relation is gamma_k tilde{nabla}phi(x_k) = H_k(x_{k-1}) - H_k(x_k). With the printed definition, the inequality gamma_k P_{k-1}(x_star) <= rho_k <x_star - x_{k-1}, -v_{k-1}> and the subsequent Bregman-Young bound do not follow. This indexing error is local and fixable by setting v_k := H_k(x_{k-1}) - H_k(x_k) (equivalently, v_{k-1} = H_{k-1}(x_{k-2}) - H_{k-1}(x_{k-1})), after which the displayed chain of inequalities becomes consistent with the definition of Lambda_{k-1,2 rho-hat_k}.","section":"Section 4.1, paragraph following Eq. (4.8)"}],"minor_comments":[{"comment":"The claimed O(1/(K+1)) rate is asserted without proof. Lemma 4.1(ii) alone yields P_min^K(x) <= U_0(x) / sum_{k=1}^{K+1} gamma_k, and a rate requires a lower bound gamma_k >= gamma_min > 0; the remark says such a bound can be derived but provides no details. Either supply the argument or explicitly label the rate as a conjecture/open problem.","section":"Remark 2.6(i)"},{"comment":"The displayed equality B_{k+1} = Delta_phi(x_{k+1}, x_k) + gamma_{k+1} tilde D_g(x_{k+1}, x_k) appears to omit a second nonnegative term. The correct identity is Delta_phi(x_{k+1}, x_k) + gamma_{k+1}(tilde D_g(x_{k+1}, x_k) + tilde D_g(x_k, x_{k+1})), or alternatively one can invoke monotonicity of partial g directly. The inequality conclusion remains valid, so this is a typographical issue rather than a mathematical one.","section":"Lemma 3.5"},{"comment":"The numerical comparisons are reported as single trajectories, without multiple runs or error bars. Given the claim of robustness across problem classes, reporting averaged behavior over several seeds, or at least a small number of repeated trials, would substantially strengthen the empirical conclusions.","section":"Section 5"},{"comment":"There are several minor typos, including 'B-adaPGand is compared' and 'the linear variant'. The paper would also benefit from a sentence noting explicitly that B-adaPG-alpha is tested only in settings where alpha(phi) > 0, consistent with Table 1.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The missing reciprocal in (2.6)-(2.7) is likely a typesetting artifact, but it affects the central algorithm statement and must be confirmed by the authors. The gap in Lemma 4.2 is genuine and requires a new proof technique; the suggested direct estimate should be feasible within the paper's current scope. I do not see circularity in the main convergence analysis, and the Bregman-Young inequality is a valuable contribution in its own right. I recommend major revision rather than rejection, since the identified issues appear fixable without changing the overall framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new piece is the Bregman-Young inequality (Lemma 3.2) and the two adaptive stepsize rules built on it. They yield the first Bregman proximal gradient method that provably attains the infimum under local relative smoothness, without global strong convexity of the kernel and without backtracking linesearch. That is a real extension of the Euclidean adaPG line, and the conservatism relative to [12, 11] is openly acknowledged and shown to be minor in practice.\n\nThe analysis is mostly rigorous: Lemma 3.1 checks out, Theorem 2.5 follows from explicit assumptions, and the numerical experiments cover a sensible range of problems with an honest comparison against linesearch and BaGRAAL. The authors also mark their own open questions (e.g., stepsizes staying bounded away from zero on the boundary, Section 5.4) instead of overclaiming.\n\nThe soft spots are fixable rather than structural. Lemma 4.2 invokes 'standard results ensure that (x_k) converges' to get Lambda_{k,delta}->1 from gamma_k->0. That assertion is not standard and is false in general. Since Claim 2 uses it to rule out gamma_k->0, the proof of Theorem 4.4 needs the repair: show consecutive differences vanish directly from gamma_k->0 via the limit prox_{gamma g}(y)->y, which the authors did not include. I expect that argument to work, so I would call this a gap, not a collapse. Minor issues: Remark 2.6(i) states an O(1/(K+1)) rate without proof (either prove it or delete it), there is a small indexing typo in Section 4.1 (v_k should involve H_k, not H_{k-1}), and the figures are single trajectories without error bars or code release. None of these change my recommendation.\n\nThis paper deserves a serious referee. I would send it out, with an explicit request to fix Lemma 4.2 and either justify or cut the rate claim in Remark 2.6. It will be of value to researchers working on adaptive Bregman methods and relative-smooth optimization.","headline":"A genuinely new adaptive Bregman proximal gradient method with a mostly sound analysis, one fixable gap in Lemma 4.2, and honest numerics.","tokens_in":29950,"tokens_out":5165,"would_cite":true,"duration_ms":54635,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65K05","90C06","90C25","90C30","49M29"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes two linesearch-free adaptive stepsize rules for the Bregman proximal gradient method and proves that, under only local relative smoothness, the objective values converge to the infimum and, under mild extra…","keywords":["convex composite optimization","Bregman proximal gradient","relative smoothness","adaptive stepsizes","linesearch-free optimization","Bregman distance","Bregman-Young inequality","Legendre functions"],"falsifier":"Run B-adaPG on the polynomial-Hessian problem (5.1) with the quartic kernel (5.2) and on the KL nonnegative regression problem (5.3), recording the stepsizes γ_k and iterates x_k. If any run shows γ_k → 0 while (x_k) stays inside a compact subset of int dom φ yet fails to converge, for example oscillating between two cluster points, then Lemma 4.2's assertion is false and the proof of Claim 2 would need replacement.","tokens_in":1714,"feed_emoji":"📉","tokens_out":2918,"duration_ms":105286,"temperature":0.7,"pith_summary":"This paper presents two adaptive, linesearch-free variants of the Bregman proximal gradient method for convex composite minimization. The central claim is that the iterates reach the optimal value in the limit, inf_k φ(x_k) = inf_C φ, assuming only that the smooth term is locally relatively smooth with respect to a Legendre kernel, with no global relative smoothness modulus, no global strong convexity of the kernel, and no backtracking linesearch. If a minimizer lies inside the kernel's domain, the whole sequence converges to a solution, and under a mild zone condition the sequence is bounded with a unique optimal limit point. The proof rests on a Bregman generalization of Young's inequality that controls the inner-product term which had blocked such extensions. This matters because the usual global assumptions are hard to verify and force conservative stepsizes, while the new rules generate stepsizes from local data only.","feed_headline":"Adaptive Bregman stepsizes converge without linesearch","feed_subtitle":"A Bregman-Young inequality lets adaptive Bregman proximal gradient converge under only local relative smoothness.","key_machinery":"The central object is the Bregman-Young inequality of Lemma 3.2, ⟨x−y, v⟩ ≤ (1/δ)D_φ(x,y) + (1/δ)D_{φ*}(∇φ(y)+δv, ∇φ(y)), derived from the three-point identity and Legendre duality; it replaces Euclidean Young and Cauchy-Schwarz bounds that are unavailable in Bregman geometry. Around it the paper builds three data-driven estimates: the local relative smoothness ℓ_k between consecutive iterates, the curvature Λ_{k,δ} of the forward operator H_k = ∇φ − γ_k∇f measured in conjugate Bregman distance, and the local symmetry ratio α_k. These feed multiplicative stepsize updates ρ_{k+1} = γ_{k+1}/γ_k, given in (2.6) and (2.7), which keep a merit function U_k decreasing. The descent of this merit function, combined with Lemma 4.1 and the no-vanishing-stepsizes argument of Claim 2, yields the convergence statements.","core_discovery":"In the paper's own formulation, the discovery is Theorem 2.5: for B-adaPG, and for B-adaPGα when the kernel has a positive symmetry coefficient, under local relative smoothness one always has inf_k φ(x_k) = inf_C φ. If the solution set meets the interior of the kernel's domain, the sequence converges to a minimizer; under Assumption 2.3 the iterates are bounded and admit exactly one optimal limit point. The stepsizes come from three local quantities—the relative smoothness estimate ℓ_k, the forward-operator curvature estimate Λ_{k,δ}, and the local symmetry ratio α_k—so no trial-and-error inner loop is needed. The engine is a Bregman version of Young's inequality, which bounds the troublesome inner product B_{k+1} directly in Bregman distances and lets the analysis proceed with only local moduli.","pith_inferences":["If the unproved convergence assertion in Lemma 4.2 turns out to require extra conditions, the proof that stepsizes stay bounded away from zero would need a different argument; Theorem 2.5 might still be true, just not proven by the current route.","The Bregman-Young inequality likely applies beyond proximal gradient, for example to Bregman proximal point, Douglas-Rachford, or accelerated Bregman variants where inner products appear; testing it there is a natural next step.","The numerical observation that stepsizes stay bounded away from zero even near boundary points suggests a stronger theorem under Assumption 2.3 might hold, a question the paper explicitly leaves open.","One direct test would be to run B-adaPG on a problem with no global relative smoothness modulus at all, such as f(x) = 1/x relative to the Boltzmann-Shannon entropy, and check that the convergence behavior and stepsize trajectories match the theory."],"forward_implications":["Bregman proximal gradient can be run with no backtracking linesearch and no knowledge of any global smoothness constant, as long as the smooth term is locally relatively smooth.","Stepsizes are computed from the current and previous iterates, so the per-iteration cost stays comparable to plain BPG while stepsizes can grow orders of magnitude beyond the conservative 1/L constant.","Even when all minimizers lie on the boundary of the kernel's domain, such as with relative-entropy barriers, the objective values still satisfy inf_k φ(x_k) = inf_C φ; under Assumption 2.3 the sequence has a unique optimal limit point.","When the kernel is the Euclidean quadratic, the rules reduce to slightly conservative versions of the existing Euclidean adaptive proximal gradient updates, recovering that theory as a special case.","The Bregman-Young inequality is stated as a standalone tool and can be reused wherever inner products need to be controlled by Bregman distances."],"supporting_citations":[{"why":"Supplies the Euclidean adaptive proximal-gradient framework and the main identity that Lemma 3.1 extends to Bregman geometry.","marker":"[12]"},{"why":"Establishes relative smoothness, the symmetry coefficient, and the BPG update that this paper relaxes to local versions.","marker":"[3]"},{"why":"Introduces relative smoothness with respect to a kernel and gives the polynomial-Hessian example used in Section 5.2.","marker":"[14]"},{"why":"Origin of the adaptive-gradient-without-descent stepsize rationale and the local Lipschitz estimate idea.","marker":"[16]"},{"why":"Provides the Euclidean adaptive update that B-adaPGα specializes to when the kernel is the Euclidean quadratic.","marker":"[11]"},{"why":"The Bregman golden-ratio algorithm used as the main adaptive Bregman baseline in the numerical experiments.","marker":"[25]"},{"why":"Defines Bregman functions with zone, the basis of Assumption 2.3 used for boundary-case convergence.","marker":"[23]"},{"why":"Accelerated Bregman proximal gradient with gain adaptation, a principal numerical competitor and source of the triangle-scaling comparison.","marker":"[10]"}],"fun_headline_variants":["Bregman-Young inequality enables linesearch-free adaptive stepsizes","Adaptive Bregman stepsizes converge without backtracking","Local relative smoothness is enough for adaptive Bregman method","No linesearch: adaptive Bregman proximal gradient converges locally"],"cache_read_input_tokens":32128,"weakest_assumption_plain":"The proof rests on the unproved assertion in Lemma 4.2 that if stepsizes tend to zero while iterates remain in a compact region inside the kernel's domain, the iterates converge; if that assertion fails, the argument that stepsizes stay bounded away from zero collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bregman-Young inequality enables linesearch-free adaptive stepsizes","Adaptive Bregman stepsizes converge without backtracking","Local relative smoothness is enough for adaptive Bregman method","No linesearch: adaptive Bregman proximal gradient converges locally"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000652,"raw_usage":{"total_tokens":2947,"prompt_tokens":857,"completion_tokens":2090,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":2019}},"tokens_in":473,"tokens_out":2090,"duration_ms":18849,"temperature":1.0,"reasoning_tokens":2019,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T05:40:31.796464+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run B-adaPG on the polynomial-Hessian problem (5.1) with the quartic kernel (5.2) and on the KL nonnegative regression problem (5.3), recording the stepsizes γ_k and iterates x_k. If any run shows γ_k → 0 while (x_k) stays inside a compact subset of int dom φ yet fails to converge, for example oscillating between two cluster points, then Lemma 4.2's assertion is false and the proof of Claim 2 would need replacement.","supporting_citations":[{"cited_title":"Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient.Mathematical Programming, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the Euclidean adaptive proximal-gradient framework and the main identity that Lemma 3.1 extends to Bregman geometry."},{"cited_title":"Bauschke, Jérôme Bolte, and Marc Teboulle","cited_arxiv_id":null,"evidence_quote":"Establishes relative smoothness, the symmetry coefficient, and the BPG update that this paper relaxes to local versions."},{"cited_title":"Adaptive gradient descent without descent","cited_arxiv_id":null,"evidence_quote":"Origin of the adaptive-gradient-without-descent stepsize rationale and the local Lipschitz estimate idea."},{"cited_title":"On the conver- gence of adaptive first order methods: Proximal gradient and alternating minimization algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the Euclidean adaptive update that B-adaPGα specializes to when the kernel is the Euclidean quadratic."},{"cited_title":"Bregman-goldenratioalgorithmsfor variational inequalities.Journal of Optimization Theory and Applications, 199(3):993–1021, 2023","cited_arxiv_id":null,"evidence_quote":"The Bregman golden-ratio algorithm used as the main adaptive Bregman baseline in the numerical experiments."},{"cited_title":"Solodov and Benar F","cited_arxiv_id":null,"evidence_quote":"Defines Bregman functions with zone, the basis of Assumption 2.3 used for boundary-case convergence."},{"cited_title":"Accelerated Bregman proxi- mal gradient methods for relatively smooth convex optimization.Compu- tational Optimization and Applications, 79(2):405–440, 2021","cited_arxiv_id":null,"evidence_quote":"Accelerated Bregman proximal gradient with gain adaptation, a principal numerical competitor and source of the triangle-scaling comparison."}],"review_version":1}