{"id":"68c123ad-7ef1-4724-b004-a3cde5c66546","arxiv_id":"2607.08174","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"An adaptive golden-ratio primal-dual algorithm is shown to need no step-size cap or linesearch, with O(1/N) rates, plus two strongly-convex-focused variants with O(1/N²) rates.","lead":"This paper shows a golden-ratio primal-dual algorithm can automatically keep its step sizes safe, so no user-set cap, linesearch, or global Lipschitz constant is needed. It also adds two accelerated variants that reach faster O(1/N²) error rates when strong convexity is available, tested on Poisson image deblurring.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6.2 (the accelerated O(1/N^2) rate for Algorithm 4) is stated without proof, and the gamma-threshold (63) requires a known strong-convexity constant mu_h; without the omitted proof or released code, the second accelerated-rate claim is unverified.","rationale":"The reader's conditional verdict is well-founded. The no-cap result and Algorithm 3's O(1/N^2) proof appear technically sound: Lemma 6.3 telescopes correctly, Lemma 6.4 provides the key lower bound, and the weighted ergodic averages give the stated rate. For Algorithm 4, however, the central rate theorem is not proved; the paper explicitly omits the details. This is a load-bearing concern because the abstract and the table of contributions claim both accelerated variants, and the numerical experiments in Setting 3 rely on Algorithm 4. The reader's weakest assumption focused on the threshold (63) and the need for mu_h, which is part of the same issue: without the omitted proof one cannot even check whether the threshold is used correctly. We do not see an internal inconsistency in the written proofs that would force rejection; the gap is one of completeness and verifiability. Releasing the code and supplying the proof of Theorem 6.2 would address the concern. Since the reader already set CONDITIONAL, our assessment does not change the verdict.","tokens_in":31890,"tokens_out":12714,"duration_ms":104950,"concrete_test":"Independently fill in the proof of Theorem 6.2 following the stated analogy: replace zeta_n in Lemma 6.4 with the fixed gamma in Algorithm 4, and verify that the induction for tau_n >= Mbar / sqrt(L^2 + C beta_n) still holds when beta_{n+1} <= (1 + gamma U) beta_n. Then check that beta_{n+1} >= beta_n(1 + gamma Mbar / sqrt(L^2 + C beta_n)) yields beta_n >= c0 n^2 and beta_n tau_n >= c1 n. If any step fails, or if gamma_bar in (63) is not sufficient to bound the extra term in (71), then the O(1/N^2) rate for Algorithm 4 is unsupported. A complementary check: run Algorithm 4 on Setting 3 with mu_h perturbed by +/-10% and examine whether the log-log slope of |Phi - Phi*| vs N changes from -2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract claims two accelerated variants with ergodic O(1/N^2) rates, but only Algorithm 3 has a full proof (Lemmas 6.3-6.5, Theorem 6.1). Algorithm 4's Theorem 6.2 is dismissed with 'the proof follows an analogous argument ... we omit the details' (end of Section 6.1). The omitted part is not a formality: it must establish (i) a lower bound tau_n >= Mbar / sqrt(L^2 + C beta_n) with Mbar independent of n under the fixed-gamma update beta_n = beta_{n-1}(1 + gamma tau_{n-1}); (ii) quadratic growth beta_n >= c0 n^2; and (iii) beta_n tau_n >= c1 n, which together give Q_N ~ N^2. The threshold gamma_bar in (63) also requires the global strong-convexity constant mu_h; in Section 7.1.3 gamma = 0.99 gamma_bar is chosen after trial and error for beta0. If mu_h is overestimated or the unproved lower-bound argument fails for Algorithm 4, inequality (69) does not telescope and rate (56) is not established. This is an explicit limitation: the second accelerated-rate result is stated but not demonstrated in the manuscript.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a class of adaptive golden-ratio primal–dual methods for composite convex optimization (1), where the differentiable term h is only locally smooth. It first revisits the aEGRPDA algorithm of Soe et al. [26] and removes the artificial step-size cap τ_max. The key structural argument is Remark 4.2, which uses Lemma 2.5 (min{a,b} ≤ √(ab)) to show that the adaptive rule (13) itself yields a uniform upper bound on τ_n, so no linesearch, no global Lipschitz constant, and no cap are needed. Algorithms 2, 3, and 4 are then analyzed: Algorithm 2 is shown to have ergodic O(1/N) objective and feasibility rates (Theorem 4.2), and linear convergence under strong convexity of f and g* (Theorem 5.1). Algorithm 3, which exploits strong convexity of f, is proved to have ergodic O(1/N²) rates (Theorem 6.1). Algorithm 4, which exploits global strong convexity of h, is claimed to have the same O(1/N²) rate (Theorem 6.2), but the proof is omitted. Numerical experiments on Poisson imaging problems illustrate the methods in three settings.","tokens_in":32317,"tokens_out":2271,"duration_ms":22253,"significance":"If the results are correct, the paper makes a useful contribution: it provides a principled way to run a golden-ratio primal–dual method without a step-size cap or linesearch under only local smoothness, and it extends accelerated O(1/N²) guarantees to a locally smooth setting, which is uncommon in the literature. The proof that the adaptive rule self-bounds τ_n (Remark 4.2) is simple and elegant, and the resulting O(1/N) estimates that are independent of τ_max genuinely improve on prior work [26]. The linear-convergence section (Section 5) is carefully written, with explicit constants and a clear contraction argument. The main weakness is that the second accelerated result (Theorem 6.2 for Algorithm 4) is stated without proof, and the numerical experiments choose γ via trial and error after computing γ̄ from (63), which depends on the global strong-convexity constant μ_h. This leaves the paper's second central accelerated-rate claim under-supported.","major_comments":[{"comment":"Theorem 6.2, the O(1/N²) rate for Algorithm 4, is stated without proof: 'The proof follows an analogous argument as in Remark 6.3, Lemma 6.4, Lemma 6.5 and Theorem 6.1. Because of its simplicity, we omit the details.' This is a load-bearing omission. The analogous argument must establish the lower step-size bound τ_n ≥ M̄/√(L²+Cβ_n) with M̄ independent of n, the quadratic growth β_n ≥ c₀n², and β_nτ_n ≥ c₁n for the fixed-γ update (64). None of these steps appears in the text for Algorithm 4, and the presence of γ in (64) changes the recursion substantially from the μ-driven update of Algorithm 3. The rate (56) therefore is not demonstrated for Algorithm 4 as stated.","section":"Section 6.1, Theorem 6.2"},{"comment":"The threshold γ̄ in (63) depends on μ_h, the global strong-convexity constant of h. In the experiments, γ = 0.99 γ̄ is selected only after trial and error (Section 7.1.3: 'after a few trial and error, we are satisfied with β₀ = 5, and after computing γ̄ from (63), select γ = 0.99 ¯γ'). If μ_h is unknown or overestimated, Lemma 6.8's telescoping argument (the inequalities following (72)) may fail: the γτ_n terms would not be absorbed by μ_hτ_n and θ_n terms, so (69) would not telescope and (56) would not follow. The paper does not provide a strategy for estimating μ_h or a robustness analysis for misspecified μ_h. This is connected to the omission of the proof of Theorem 6.2 and should be addressed explicitly.","section":"Section 6.1, Eq. (63) and Section 7.1.3"},{"comment":"Lemma 4.2's lower bound on τ_n and θ_n relies on [37, Lemma 4.2] without reproducing the statement or verifying its hypotheses for Algorithm 2. Since this lower bound is used in Theorem 4.1 and Theorem 4.2 to obtain nonzero Δ and the O(1/N) rate, the dependence should be made transparent: state the lemma or at least explicitly verify the required conditions. The reader should not have to consult a separate paper to see whether the assumptions (e.g., the specific form of the step-size update) match.","section":"Section 4, Lemma 4.2"}],"minor_comments":[{"comment":"The text refers to 'Algorithm 6' in 'the accelerated method (Algorithm 6) yields a lower overall objective residual'. The algorithm is Algorithm 4. Please correct the numbering.","section":"Section 7.1.3, paragraph after Fig. 13"},{"comment":"The phrase 'parameter-free' is used for Algorithm 2, but the method still depends on β, ψ, α_n, and τ₀. What the paper actually shows is that the rate estimates do not depend on an artificial cap τ_max. Please qualify the term, e.g., 'cap-free' or 'parameter-free in the convergence-rate bound'.","section":"Abstract and Introduction"},{"comment":"The convention '0/0 = +∞' is stated, but the update (13) when x_n = x_{n-1} and L_n = 0 gives a denominator of zero. The convention makes the fraction equal to +∞, so τ_n = min{ρτ_{n-1}, +∞} = ρτ_{n-1}, which is consistent with the remark, but this should be stated more explicitly because the usual computer arithmetic would produce NaN.","section":"Section 4, Remark 4.1"},{"comment":"The definition of M̄ in Lemma 6.4 contains τ₁ and τ₂, which are defined by the algorithm. The induction proof then claims the bound for n=1,2 by definition. This is fine, but the notation M̄ is used before τ₁ and τ₂ are introduced as deterministic functions of the input. Suggest moving the induction start to n=3 or clarifying that τ₁,τ₂ are fixed by the initial data.","section":"Section 6, Algorithm 3 and Lemma 6.4"},{"comment":"Figure captions and text frequently write 'PFGRPDA' instead of 'PF-GRPDA'. Also, the caption of Figure 3 says 'Several heuristic adaptive-β n for PFGRPDA' and 'Thin faded curves show individual heuristic choices' – this is a bit confusing because the figure seems to show only one method with several β-update variants. Please clarify.","section":"Section 7, general"},{"comment":"Lemma 2.5 is stated as 'min{a,b} ≤ √(ab)' for a,b>0. This is true but unnecessarily weak: the sharpest bound is min{a,b} ≤ √(ab), which is exactly the geometric mean. The proof is fine, but the lemma could be stated as an equality-like bound without overclaiming.","section":"Section 2, Lemma 2.5"}],"recommendation":"major_revision","confidential_remarks":"The paper's main algorithmic idea is attractive and the proof for Algorithm 2 is self-contained modulo the cited [37, Lemma 4.2]. The O(1/N²) rate for Algorithm 4 is a central advertised contribution, so the omission of its proof is a serious gap. I am not asking for full verbatim proof of every lemma, but Theorem 6.2 must be accompanied by at least a complete proof sketch of the three claimed steps (lower bound on τ_n, quadratic growth of β_n, and β_nτ_n ≥ c₁n) for the γ-recursion. The numerical section's trial-and-error selection of γ also undermines the practical message: if μ_h must be known exactly, the 'parameter-free' selling point is weakened. These are fixable within the manuscript's scope, hence major_revision rather than reject."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news here is that the tau_max cap in their earlier aEGRPDA is redundant. The argument is simple (Lemma 2.5 plus the observation that the adaptive rule bounds tau_n above), and it removes a hyperparameter that was both practically and theoretically annoying. The O(1/N) rate in Theorem 4.2 then no longer depends on tau_max. That part is solid and worth knowing.\n\nThe second piece is acceleration. Algorithm 3, which accelerates when f is strongly convex, has a complete proof: the energy argument in Lemmas 6.2-6.5 is detailed and the quadratic growth of beta_n is shown. That gives an honest O(1/N^2) rate without linesearch, under local smoothness. Good.\n\nThe soft spot is Algorithm 4, for the case where h is strongly convex and locally smooth. Theorem 6.2 states the O(1/N^2) rate but the proof is \"analogous ... we omit the details\". This is not a small omission. The telescoping inequality (69) depends on a threshold gamma_bar in (63) that requires the global strong convexity constant mu_h. Three separate inequalities have to be balanced; the omitted lower-bound argument for tau_n is exactly the kind of step that can fail. The numerical section then picks gamma = 0.99 gamma_bar by trial and error. So the second accelerated-rate claim is under-supported as it stands. If the authors fill the gap and release code, the paper is in much better shape; a referee should ask for that.\n\nAlso note: the lower bound for tau_n in Lemma 4.2 invokes [37, Lemma 4.2]; that's fine externally, but it means the no-cap result leans on a prior lemma. The experiments include a heuristic adaptive beta_n rule that is not covered by the theory, and code is only 'available upon request'. Both are minor but worth mentioning if you referee.\n\nWho is this for: people working on primal-dual methods for imaging where h is only locally smooth. The no-cap result and Algorithm 3 will likely be cited. The paper deserves a serious referee, but Theorem 6.2 must be fixed before the abstract's claim of two accelerated variants is justified.","headline":"The no-cap step-size result is a genuinely useful fix, and Algorithm 3's acceleration is well proved, but the second accelerated-rate theorem (Algorithm 4) is stated without its proof and relies on a trial-and-error threshold, so the paper needs revision before the abstract's two-variant claim is credible.","tokens_in":32742,"tokens_out":2292,"would_cite":true,"duration_ms":20811,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","65K10","49M27","65J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the adaptive golden-ratio primal–dual algorithm needs no step-size cap—its own adaptive rule keeps step-sizes bounded—and provides two accelerated variants with ergodic 1/N² rates under strong convexity.","keywords":["primal–dual algorithms","golden ratio","adaptive step-size","local smoothness","strong convexity","accelerated convergence","Poisson imaging","ergodic rate"],"falsifier":"Run Algorithm 2 on the quadratic test in Section 3 with no τ_max and record the primal step-sizes: for every n the bound τ_n ≤ √(ρ c_max) from Remark 4.2 must hold, and the iterates must converge; any τ_n exceeding that bound, or any divergence, refutes the parameter-free claim.","tokens_in":31824,"feed_emoji":"⚡","tokens_out":7705,"duration_ms":64169,"temperature":0.7,"pith_summary":"Structured convex problems in imaging often involve a differentiable term that is only locally smooth, making global Lipschitz constants unavailable. The paper shows that the adaptive golden-ratio primal–dual algorithm does not need an artificial cap on primal step-sizes: its step-size rule has a growth branch and a local-smoothness branch, and the elementary inequality min{a,b} ≤ √(ab) forces a uniform bound automatically. With the cap removed, the method retains a parameter-free ergodic O(1/N) rate and, when both nonsmooth primal and dual functions are strongly convex, converges linearly. Two accelerated variants—one using strong convexity of the nonsmooth component, one using strong convexity of the differentiable component—achieve ergodic O(1/N²) rates without a linesearch. Experiments on Poisson image reconstruction show faster residual decay for the accelerated methods.","feed_headline":"Adaptive golden-ratio method proves its step cap redundant","feed_subtitle":"Two accelerated variants reach 1/N² convergence without a linesearch or global Lipschitz constant.","key_machinery":"The machinery is the adaptive primal step-size update τ_n = min{ρτ_{n-1}, α_n α_{n-1} ψ θ_{n-1} / ((L_n² + βψ‖K‖²)τ_{n-1})}, where L_n is the local estimate of the Lipschitz constant of ∇h, combined with the golden-ratio convex averaging z_n = (ψ−1)/ψ x_{n-1} + 1/ψ z_{n-1} with ψ∈(1,φ]. The critical handle is Lemma 2.5: min{a,b} ≤ √(ab), applied to the two branches of the update, which yields the uniform bound τ_n ≤ U independent of all iterates. For the accelerated variants, the dual-primal ratio β_n is made to grow (β_n = β_{n-1}(1+μζ_n τ_{n-1}) for strong convexity of f, β_n = β_{n-1}(1+γτ_{n-1}) for strong convexity of h); the proofs show β_n grows quadratically, so the weighted ergodic","core_discovery":"At the center of the paper is a single observation: the artificial upper bound τ_max placed on primal step-sizes in the earlier aEGRPDA is redundant. Writing the update as τ_n = min{ρτ_{n-1}, c_n/τ_{n-1}} with c_n bounded above, the inequality min{a,b} ≤ √(ab) yields τ_n ≤ √(ρ c_n) ≤ U, so the adaptive rule is self-bounding. This leads to Algorithm 2 (PF-GRPDA), a parameter-free method for locally smooth h, with ergodic O(1/N) guarantees for objective residual and feasibility violation and linear convergence when f and g* are strongly convex. The paper then derives two accelerated variants: Algorithm 3, which grows the dual scaling β_n via β_n = β_{n-1}(1 + μζ_n τ_{n-1}) when f is strongly c","pith_inferences":["The min-of-two-branches bounding trick likely extends to other adaptive first-order methods: any step-size update that combines a multiplicative growth branch with a reciprocal local-curvature branch is automatically bounded without a cap.","The two acceleration mechanisms are complementary and depend on how the problem is split: placing strong convexity in f or in h determines which accelerated variant applies, so the splitting choice itself becomes an algorithmic lever.","The threshold γ̄ for Algorithm 4 depends on the global strong-convexity constant µ_h; estimating µ_h adaptively along the iterates would complete the parameter-free story, and the paper explicitly lists this as an open direction.","The heuristic adaptive-β rule used in the experiments is outside the proved theory; a convergence proof for it would extend the parameter-free guarantee to the primal–dual scaling ratio."],"forward_implications":["Users can drop the τ_max hyperparameter: the ergodic O(1/N) rates for objective residual and feasibility violation hold with no step-size cap.","When f and g* are both strongly convex, Algorithm 2 converges linearly, giving a linearly convergent, locally-smooth primal–dual method with no external tuning except β, ψ, α.","With f strongly convex, Algorithm 3 obtains an ergodic O(1/N²) rate while keeping h only locally smooth and needing no linesearch or global Lipschitz constant.","With h globally strongly convex, Algorithm 4 obtains the same O(1/N²) ergodic rate under a step-size rule that remains adaptive.","On Poisson imaging problems, the accelerated variants reduce feasibility violation and objective residual faster than the base method in the reported runs."],"fun_headline_variants":["Golden-ratio method drops step cap, accelerates to 1/N²","Adaptive primal-dual: no cap, no linesearch, faster","Parameter-free golden-ratio solver beats Poisson imaging","Step cap redundancy proof in golden-ratio primal-dual","Two accelerated variants hit 1/N² without Lipschitz"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The accelerated 1/N² rate for the h-strongly-convex variant (Algorithm 4) is only proved if the acceleration parameter γ stays below a threshold built from the global strong-convexity constant µ_h of h; if µ_h is unknown or misestimated, or γ is chosen above the threshold, the telescoping inequality that yields the rate does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Golden-ratio method drops step cap, accelerates to 1/N²","Adaptive primal-dual: no cap, no linesearch, faster","Parameter-free golden-ratio solver beats Poisson imaging","Step cap redundancy proof in golden-ratio primal-dual","Two accelerated variants hit 1/N² without Lipschitz"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000174,"raw_usage":{"total_tokens":1155,"prompt_tokens":814,"completion_tokens":341,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":269}},"tokens_in":558,"tokens_out":341,"duration_ms":3353,"temperature":1.0,"reasoning_tokens":269,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T04:23:02.153777+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on the quadratic test in Section 3 with no τ_max and record the primal step-sizes: for every n the bound τ_n ≤ √(ρ c_max) from Remark 4.2 must hold, and the iterates must converge; any τ_n exceeding that bound, or any divergence, refutes the parameter-free claim.","supporting_citations":[],"review_version":2}