{"id":"8b1a5f46-9d1d-49b2-9f5a-dd1221514b4c","arxiv_id":"2501.04165","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A restarted accelerated gradient method and the proximal bundle method are both shown to be instances of accelerating and non-accelerating inexact proximal point frameworks, with optimal iteration complexity.","lead":"This paper shows that a restarted version of Nesterov's accelerated gradient method fits an existing mathematical framework and keeps the same optimal worst-case speed. It also shows that the proximal bundle method fits a related framework, so two seemingly different optimization techniques turn out to share one underlying principle.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The optimal-complexity claim rests on an unproved import: Theorem 2.5 cites [28, Thm 3.8] with a one-sentence 'minor modification' assertion and never maps Algorithm 2's w_k to the A-HPE sequence that theorem bounds.","rationale":"The reader's weakest assumption is exactly the unproved applicability of [28, Thm 3.8], and my reading confirms that this is the load-bearing point. Proposition 2.8 is self-contained: the derivation of the relative-error condition from Lemmas 2.6 and 2.7 is coherent, and the constants in (23) are consistent with Lemma 2.4. Lemma 3.1 is also a clean verification that the MPB stopping criterion implies the HPE condition. Neither of these is the problem. The problem is that Theorem 2.5, which supplies the outer-loop rate, is merely stated. The text says the results of [28, Section 3] apply 'with minor modification, such as generalizing f to phi,' but no modification is described and no proof is given. Moreover, the mapping between Algorithm 2 and the A-HPE sequence is not explicit: step 3 updates w_k by taking the better of w_{k-1} and tilde w_k, and z_k by the momentum formula, but the paper never says whether the bound in [28, Thm 3.8] is for the y_k sequence (here tilde w_k), the x_k extragradient sequence, or some other sequence. If it is for y_k, the step-3 min is harmless; if it is for x_k, the min update is not the A-HPE update and the bound does not transfer. Because Theorem 2.9 multiplies this outer rate by the inner complexity, the main optimality claim is unsupported until this is settled. I am not asserting the theorem is false; I am asserting the paper does not prove it, and the reader's conditional verdict is therefore appropriate. I also note the novelty overlap with [19] as a separate concern, but it does not affect correctness and is not load-bearing for the main theorem.","tokens_in":11773,"tokens_out":24512,"duration_ms":204961,"concrete_test":"Derive Theorem 2.5 from [28, Thm 3.8] line by line for phi = f + h, writing out the A-HPE invariant (e.g., B_k phi(w_k) + (1/2)||z_0 - x^*||^2 <= (1/2)||z_0 - x^*||^2) and checking whether the paper's updates z_k = z_{k-1} - b_k u_k and w_k = argmin{w_{k-1}, tilde w_k} satisfy it. If the invariant requires x_k = tilde z_k - lambda u_k but Algorithm 2 replaces it by w_k, the proof fails; if it only requires tilde w_k, the transfer via step 3 works. This single re-derivation settles whether Theorem 2.9 is proved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central result, Theorem 2.9, is a product of two factors: the outer-loop rate in Theorem 2.5 and the inner ACG complexity in Proposition 2.8. Proposition 2.8 is proved in the text, and its arithmetic checks out modulo Lemma 2.4. The load-bearing gap is Theorem 2.5. It is not proved; the justification in Section 2.2 is the sentence 'With minor modification, such as generalizing f to phi, the results in Section 3 of [28] are applicable... Consequently, Theorem 3.8 of [28] also holds.' That assertion is doing all the work. Two concrete things must be true for it to land: (i) the A-HPE oracle conditions in [28, Section 3] are satisfied by (13)-(14) with phi in place of f and tilde z_k in place of bar x_{k-1}; (ii) the error bound in [28, Thm 3.8] attaches to the sequence that Algorithm 2 actually outputs, namely w_k. The paper does not identify which A-HPE sequence the theorem bounds. Algorithm 2 step 3 sets w_k = argmin{w_{k-1}, tilde w_k}, so if [28, Thm 3.8] bounds f(y_k) = phi(tilde w_k), the transfer is immediate; if it bounds the extragradient point bar x_{k-1} - lambda_k v_k, no transfer is proved. Because the theorem is only stated, not derived, the reader cannot verify either point. If the extension fails even in constant or sequence mapping, the O(sqrt(L) d0 / sqrt(eps)) claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a restarted accelerated composite gradient (restart ACG) method for convex smooth composite optimization (CSCO) and claims it achieves the optimal iteration complexity O(√L d0/√ε). The method is a double-loop algorithm: the outer loop follows the accelerated hybrid proximal extragradient (A-HPE) framework of Monteiro and Svaiter [28] with a constant proximal step λ, and the inner loop invokes an ACG subroutine to approximately solve the proximal subproblem until the relative-error conditions (13)–(14) are met. Section 2.3 proves that the inner ACG loop produces such a triple in O(min{√(λL), ln(λL)}) iterations, and Theorem 2.9 combines this with an imported rate bound from [28] to obtain the stated optimal complexity. Section 3 shows that the modern proximal bundle (MPB) method is an instance of the HPE framework, giving explicit expressions for the triple satisfying (25)–(26). The paper's stated contribution is a conceptual unification of restart ACG and MPB as multi-step implementations of proximal-point-based acceleration frameworks.","tokens_in":12051,"tokens_out":7264,"duration_ms":66587,"significance":"If the main claim holds, the paper offers a clean unifying perspective: restart ACG is a multi-step implementation of A-HPE and MPB is a multi-step implementation of HPE, which would help explain their practical advantage over single-step counterparts. The inner-loop verification in Proposition 2.8 is concrete and the arithmetic checks out, and Lemma 3.1 is a clean verification that MPB fits the HPE framework. However, the optimal-complexity theorem rests on an unproved import from [28], so the central claim is not yet fully supported in the manuscript. The conceptual contribution is real but conditional on closing that gap.","major_comments":[{"comment":"The paper's central optimal-complexity claim, Theorem 2.9, rests entirely on Theorem 2.5, which is not proved. The paragraph before Theorem 2.5 asserts that 'with minor modification, such as generalizing f to φ, the results in Section 3 of [28] are applicable' and that 'Theorem 3.8 of [28] also holds,' but it does not verify the hypotheses of [28, Thm. 3.8] for Algorithm 2, nor does it identify which of the sequences generated by Algorithm 2 (w_k, \\tilde w_k, or z_k) the theorem's bound attaches to. Since [28, Thm. 3.8] is proved for a specific A-HPE sequence and under specific step-size/error-tolerance conditions, the one-sentence 'minor modification' assertion is insufficient. Please provide a proof of Theorem 2.5 or a detailed mapping of Algorithm 2's iterates to the framework of [28, Section 3], and verify explicitly that all assumptions of [28, Thm. 3.8] hold for constant λ and the 0.9-relative-error criterion (14).","section":"Section 2.2, Theorem 2.5"},{"comment":"The bound φ(w_k) − φ* ≤ 2 d0^2/(λ k^2) in Theorem 2.5 is stated 'for completeness' but no proof or derivation is given, and the text explicitly says 'without providing a proof.' This is a load-bearing missing element, not a mere presentation issue. Even if the transfer from [28] is straightforward, the authors should either include the adaptation proof in the paper or state precisely which theorem in [28] applies to which sequence and why the sequence w_k produced by the min-selection in step 3 of Algorithm 2 inherits the bound.","section":"Section 2.2, Algorithm 2 and Theorem 2.5"}],"minor_comments":[{"comment":"The quantity d0 appears in Theorem 2.5, Theorem 2.9, and the abstract but is never defined. Please define it explicitly (presumably d0 = ||w0 − z*|| for some minimizer z* of φ).","section":"Sections 2.2 and 2.3 (d0)"},{"comment":"Lemma 2.4 is imported from [27, Prop. 1(c)] without proof and is used to guarantee A_j ≥ 6λ in Proposition 2.8. Since this lemma is load-bearing for the inner-loop complexity, please either include a proof in the appendix or state explicitly which result in [27] is being used and confirm that its hypotheses match the ACG variant in Section 2.1, including the strong-convexity and smoothness constants.","section":"Section 2.3, Lemma 2.4"},{"comment":"The statement that 'MPB and the subgradient method both have optimal complexity bound O(M^2 d0^2/ε^2)' is made without a proof or citation. If this is intended as context, a reference would be helpful; if it is a new claim, it needs support.","section":"Section 3.2, complexity claim"},{"comment":"There are minor typographical issues, e.g., 'acc elerated' and 'smoo th' in the abstract, and 'fconcludes' in the introduction. These should be corrected during revision.","section":"Abstract and Introduction"},{"comment":"Since Theorem 2.5 is imported rather than proved, consider relabeling it as a quoted result or a lemma with a clear citation, so that the reader can distinguish the paper's original contributions from the imported rate bound.","section":"Section 2.2, Theorem 2.5 labeling"}],"recommendation":"major_revision","confidential_remarks":"The manuscript fits the journal's scope and the unification idea is attractive. The main issue is that the optimal-complexity theorem depends on an unproved import from [28] with no detailed verification of the hypotheses. If the author can supply a proper proof or a complete mapping to the A-HPE framework, the contribution would be acceptable. The MPB-as-HPE result is a nice contribution on its own and is well supported by Lemma 3.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on Liang's paper. The cleanest part is the internal math: Proposition 2.8, which shows the inner ACG loop produces an A-HPE triple in O(min{sqrt(lambda*L), ...}) iterations, is verifiable and correct. I checked Lemmas 2.6 and 2.7; the arguments go through, and the constant 9/16 is consistent. The MPB-as-HPE lemma (Lemma 3.1) is a nice, short observation and genuinely clarifies the connection between bundle methods and proximal point schemes.\n\nThe weak spot is exactly what the stress-test note says: Theorem 2.5 is the load-bearing complexity estimate, and it is imported from [28] with one sentence about a 'minor modification.' The paper doesn't prove it, and it doesn't identify which sequence in [28] maps to w_k here. That said, I think the concern is more about presentation than substance: Algorithm 2 is literally A-HPE with constant stepsize, and the standard A-HPE theorem does give phi(w_k) for this update rule. Still, a referee should ask the author to prove the theorem in this context or cite a precise statement in [28] that covers composite phi.\n\nMy bigger hesitation is novelty. The paper calls Algorithm 2 a 'novel restarted version,' but it is a doubly accelerated inexact proximal point method, which is the title of the author's earlier paper [19]. The paper never clarifies how the restart version differs from [19] in construction or result. That is a real positioning problem.\n\nOverall, the mathematical core is sound, the MPB connection is new, and the complexity bound is likely correct. It deserves a serious referee. I'd send it out with a request: prove or precisely localize Theorem 2.5, and explain the relationship to [19] and [23]. If those are resolved, it is a solid contribution for the proximal point and bundle method community.","headline":"Liang's paper is mostly right: the inner-loop verification is solid, but the main complexity bound is imported without proof and the novelty vs. his earlier work is under-specified.","tokens_in":12671,"tokens_out":4722,"would_cite":true,"duration_ms":43819,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49M37","65K05","68Q25","90C25","90C30","90C60"],"pacs":[],"model":"deepseek-v4-flash","headline":"A restarted accelerated gradient method and the proximal bundle method are shown to be instances of (accelerated) inexact proximal point frameworks, giving restart ACG optimal complexity.","keywords":["convex composite optimization","restart accelerated gradient","proximal bundle method","accelerated hybrid proximal extragradient","inexact proximal point","iteration complexity","cutting-plane method","smooth composite optimization"],"falsifier":"Run Algorithm 2 on a one-dimensional convex composite instance such as $f(x)=x^2$ and $h(x)=|x|$, with $\\lambda$ set at both endpoints $1/L$ and $d_0^2/\\bar\\varepsilon$, and count all inner ACG iterations required to reach objective gap $\\bar\\varepsilon$ from $x_0=d_0$; if the count grows faster than a constant times $\\sqrt{L}d_0/\\sqrt{\\bar\\varepsilon}$, the claimed bound is false.","tokens_in":11465,"feed_emoji":"🧩","tokens_out":8239,"duration_ms":75114,"temperature":0.7,"pith_summary":"This paper tries to show that two apparently unrelated optimization methods—the restart accelerated composite gradient (ACG) method and the modern proximal bundle method—are in fact two faces of the same proximal-point principle. For restart ACG, the paper constructs a specific algorithm and proves that each outer loop is precisely an instance of the accelerated hybrid proximal extragradient (A-HPE) framework, which yields the optimal iteration complexity $O(\\sqrt{L}d_0/\\sqrt{\\bar\\varepsilon})$ for convex smooth composite problems. For the proximal bundle method, it proves the analogous membership in the non-accelerated HPE framework, showing the bundle method is a restarted cutting-plane method. The value of the claim is explanatory: if true, the practical edge of restarted and bundle schemes over their single-step counterparts is inherited from a common multi-step versus single-step implementation distinction.","feed_headline":"Two optimal optimization methods share one proximal-point core","feed_subtitle":"Restart accelerated gradient and proximal bundle both turn out to be multi-step proximal point instances.","key_machinery":"The load-bearing object is the A-HPE framework, an accelerated hybrid proximal extragradient scheme: an outer loop that approximately solves a proximal subproblem, with relative-error conditions relating a subgradient $u_k\\in\\partial_{\\eta_k}\\varphi(\\tilde{w}_k)$ to the displacement $\\tilde{w}_k-\\tilde{z}_k$, and then updates along $u_k$. The inner ACG variant is the engine that produces those triples; its key identity converts the algorithm's defining inequalities into exactly the A-HPE conditions. For the bundle method, the corresponding machinery is the HPE framework (the non-accelerated version) and a bundle model $\\Gamma_j\\le f$; the paper shows the bundle stopping criterion is equivalent to HPE's relative-error inequality. The constant $0.9$ in the restart ACG stopping criterion is arbitrary in $(0,1)$, showing the result is insensitive to that tolerance.","core_discovery":"The paper's central claim is that restart ACG is a concrete realization of the A-HPE framework: each call to the inner ACG subroutine produces a triple $(\\tilde{w}_k,u_k,\\eta_k)$ satisfying the framework's relative-error conditions, and the outer acceleration schedule is exactly A-HPE with constant step size. Relying on the existing A-HPE convergence theorem, the paper concludes that restart ACG solves any convex smooth composite problem in $O(\\sqrt{L}d_0/\\sqrt{\\bar\\varepsilon})$ iterations—the same optimal rate as the classical accelerated gradient method. It further proves that the modern proximal bundle method, when its bundle subproblems are solved to a declared tolerance, satisfies the HPE framework's conditions with the assignment $w_k=x_j$, $\\tilde{w}_k=\\tilde{x}_j$, $u_k=(x_0-x_j)/\\lambda$, and $\\eta_k=\\varphi(\\tilde{x}_j)-(\\Gamma_j+h)(x_j)+\\langle x_0-x_j,x_j-\\tilde{x}_j\\rangle/\\lambda$, making it an HPE instance and hence a restarted cutting-plane method. The paper's stated aim is the unification: both methods are multi-step implementations of (accelerated) inexact proximal point schemes.","pith_inferences":["The paper leaves implicit that any restart schedule for ACG can be read as a choice of how many inner iterations to run before the next prox step; tuning that schedule is equivalent to tuning the HPE relative-error tolerance.","The same lens suggests a testable design: replace the inner ACG subroutine with a different fast proximal subroutine, such as a second-order or randomized method, and the optimal outer rate should survive as long as the relative-error conditions hold.","For strongly convex objectives with unknown strong-convexity parameter, the framework points toward a universal restart ACG whose step size $\\lambda$ is adapted online; whether that achieves optimal complexity without knowing the parameter is open.","Editorial: the unification is structural rather than black-box—it identifies matching stopping criteria and update rules, so it may extend to non-Euclidean or stochastic settings where both A-HPE and HPE have analogues."],"forward_implications":["If the main theorem holds, restart ACG is optimal for convex smooth composite problems, matching the classical accelerated gradient rate $O(\\sqrt{L}d_0/\\sqrt{\\bar\\varepsilon})$ while suppressing oscillatory behavior.","Every outer iteration needs only a subroutine satisfying the A-HPE relative-error conditions, so any other inner method with the same guarantee can substitute for ACG without changing the outer rate.","The proximal bundle result implies the bundle method is a restarted cutting-plane method, so its optimal $O(M^2d_0^2/\\bar\\varepsilon^2)$ bound for nonsmooth composite problems follows from HPE theory rather than a separate bundle analysis.","The multi-step versus single-step comparison gives a structural reason why restart ACG and the proximal bundle method outperform their single-step counterparts in practice: both allow larger prox steps and pay for them with inner loops.","If the imported convergence theorem extends exactly as assumed, the proof route is unified: analyze the outer proximal scheme once, then supply any subroutine satisfying the error conditions."],"supporting_citations":[{"why":"Supplies the A-HPE framework and the convergence theorem that yields the outer-loop rate used in the paper's main complexity result.","marker":"[28]"},{"why":"Supplies the ACG variant and the growth bound on the coefficients $A_j$ used to control inner-loop iteration complexity.","marker":"[27]"},{"why":"Supplies the HPE framework that the proximal bundle method is shown to instantiate.","marker":"[11]"},{"why":"Introduces the proximal bundle method whose optimal-complexity analysis the HPE interpretation recovers.","marker":"[21]"},{"why":"Provides the unified bundle-model framework underlying $\\Gamma_j$ in the HPE-instance proof.","marker":"[23]"},{"why":"Identifies the single-step accelerated method that serves as the one-step A-HPE counterpart in the paper's comparison.","marker":"[5]"}],"fun_headline_variants":["Proximal point unites two optimal optimizers","Restart ACG and bundle: same proximal-point root","Two algorithms, one proximal-point framework","Unified: two optimizers, one proximal core","Acceleration and bundling: both proximal-point instances"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The optimal-complexity bound rests entirely on an existing A-HPE theorem that is invoked without proof and assumed to survive the generalization from a smooth function to the composite objective $\\varphi$.","fun_headline_variants_meta":{"raw":{"variants":["Proximal point unites two optimal optimizers","Restart ACG and bundle: same proximal-point root","Two algorithms, one proximal-point framework","Unified: two optimizers, one proximal core","Acceleration and bundling: both proximal-point instances"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000776,"raw_usage":{"total_tokens":3417,"prompt_tokens":913,"completion_tokens":2504,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":2430}},"tokens_in":529,"tokens_out":2504,"duration_ms":18999,"temperature":1.0,"reasoning_tokens":2430,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:41:05.302217+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a one-dimensional convex composite instance such as $f(x)=x^2$ and $h(x)=|x|$, with $\\lambda$ set at both endpoints $1/L$ and $d_0^2/\\bar\\varepsilon$, and count all inner ACG iterations required to reach objective gap $\\bar\\varepsilon$ from $x_0=d_0$; if the count grows faster than a constant times $\\sqrt{L}d_0/\\sqrt{\\bar\\varepsilon}$, the claimed bound is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the A-HPE framework and the convergence theorem that yields the outer-loop rate used in the paper's main complexity result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the ACG variant and the growth bound on the coefficients $A_j$ used to control inner-loop iteration complexity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the HPE framework that the proximal bundle method is shown to instantiate."},{"cited_title":"Liang and R","cited_arxiv_id":null,"evidence_quote":"Introduces the proximal bundle method whose optimal-complexity analysis the HPE interpretation recovers."},{"cited_title":"Liang and R","cited_arxiv_id":null,"evidence_quote":"Provides the unified bundle-model framework underlying $\\Gamma_j$ in the HPE-instance proof."},{"cited_title":"Beck and M","cited_arxiv_id":null,"evidence_quote":"Identifies the single-step accelerated method that serves as the one-step A-HPE counterpart in the paper's comparison."}],"review_version":1}