{"id":"2a8bca03-2e0d-42f4-b416-00a299c5929f","arxiv_id":"2611.17026","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A projection-free primal-dual method with a transformed flow attains the optimal first-order oracle complexity for strongly convex affine-constrained problems, and an O(1/N^2) Lyapunov decay for convex problems under a boundedness condition.","lead":"This paper proposes accelerated transformed primal-dual algorithms for smooth convex optimization with affine equality constraints, and proves an accelerated linear rate for strongly convex problems and a homotopy-based sublinear rate for convex problems. It matters because the method is projection-free and its stated oracle complexity matches known lower bounds for this problem class.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"The O(1/N^2) convex rate in Theorem 5.1 depends on a uniform all-stage boundedness assumption that the paper acknowledges is unproven; the strongly convex results are not affected.","rationale":"The reader's weakest_assumption correctly identifies the uniform boundedness condition in Theorem 5.1 as the key unresolved issue. The paper's own Remark 5.1 acknowledges that the fixed-parameter result does not establish this bound. My stress-test confirms that this is the single most load-bearing concern: the O(1/N²) convex rate is conditional on an unverified assumption. The strongly convex results are not affected. The reader's verdict of CONDITIONAL is appropriate; no change is needed. The concrete test I propose would settle whether the assumption can be violated or whether a proof is missing.","tokens_in":28165,"tokens_out":540,"duration_ms":5035,"concrete_test":"Construct a convex L-smooth f (e.g., f(x)=0 on a bounded set and quadratic outside) and a constraint Bx=b such that the homotopy ATPD (Algorithm 3) generates a primal iterate with ∥x−x⋆∥² exceeding the initial bound R². If such an example exists, the uniform boundedness assumption fails and the O(1/N²) claim is unsupported. Alternatively, prove that the homotopy dynamics enforce the bound automatically; the paper currently does not provide such a proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim for general convex objectives—accelerated O(1/N^2) decay of the modified Lyapunov energy—rests on the uniform boundedness condition ∥x−x⋆∥² ≤ R² for all primal iterates at every homotopy stage (Theorem 5.1, line [b224]). The paper itself states in Remark 5.1 (line [b216]) that the fixed-parameter result (Proposition 5.1) does not establish this bound, and that the homotopy theorem separately assumes it. No argument is given that the homotopy halving of ε preserves the bound; the induction in the proof of Theorem 5.1 simply assumes it holds. Without this condition, the perturbed decay estimate (Lemma 5.3) cannot be applied, and the O(1/N²) rate has no proof. The strongly convex results (Theorem 4.2, Corollary 4.1) do not require this assumption and are unaffected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper proposes Accelerated Transformed Primal-Dual (ATPD) methods for smooth convex optimization problems with affine equality constraints. For strongly convex objectives, the method achieves an accelerated linear convergence rate that matches known lower bounds on first-order oracle complexity, using one gradient evaluation and two matrix-vector products per iteration. For general convex objectives, a homotopy perturbation strategy is introduced, and an O(1/N^2) rate for the modified Lyapunov energy is claimed under a uniform boundedness condition on the primal iterates at all homotopy stages. Numerical experiments on Stokes equations, policy evaluation, and compressed sensing support the theory.","tokens_in":33253,"tokens_out":857,"duration_ms":35085,"significance":"If the strongly convex results are correct, ATPD provides an optimal first-order method for constrained smooth strongly convex problems with separate complexity bounds for gradient evaluations and matrix-vector products, which is a significant contribution. The continuous-time Lyapunov analysis is elegant and guides the discrete algorithm. The convex extension is potentially important but currently conditional on an unproven boundedness assumption.","major_comments":[{"comment":"The O(1/N^2) rate for general convex objectives in Theorem 5.1 depends on the uniform boundedness assumption that all primal iterates at every homotopy stage satisfy ||x - x*||^2 <= R^2. The paper acknowledges in Remark 5.1 that the fixed-parameter result (Proposition 5.1) does not establish this bound, and the homotopy theorem separately assumes it. No argument is given that the homotopy halving of epsilon preserves the bound. Without this condition, the perturbed decay estimate (Lemma 5.3) cannot be applied, and the claimed accelerated sublinear rate has no proof. This is a load-bearing gap for the convex part of the paper and should be addressed, either by proving the boundedness condition under reasonable assumptions or by restating the convex claim as conditional.","section":"Theorem 5.1 and Remark 5.1","authors_acknowledge":"The homotopy theorem below separately assumes a uniform bound over all stages; the fixed-parameter result does not by itself estab- lish that bound.","authors_acknowledge_p":0.86}],"minor_comments":[{"comment":"The step-size bound is written as '1-delta 1+delta', which is ambiguous; it should be written as (1-delta)/(1+delta) for clarity.","section":"Algorithm 2, line 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"Figure 1 is referenced but has no caption or detailed description in the text; a brief description of what is plotted should be included.","section":"Section 6.2, Figure 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The comparison includes OptAlg, ALALM, and APAPC, but the parameters used for these methods are not specified; this should be clarified for reproducibility.","section":"Section 6.3.2, Figure 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper states that residual-based stopping does not imply the spectral bound (30); it would be helpful to clarify whether the numerical experiments use a fixed linear solver or a residual-based stopping criterion, and whether the theoretical guarantees apply in the latter case.","section":"Remark 4.1","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"The strongly convex part of this paper is well done. The ATPD algorithm is a genuine new construction—adding an auxiliary variable y to the transformed primal-dual flow, using AOR-based implicit-explicit discretization, and proving decay of a modified Lyapunov function with separate gradient and matrix-vector complexity counts. The analysis is careful, the Lyapunov identities check out, and the step-size conditions in Theorem 4.2 and Corollary 4.1 are explicit. The strongly convex results match the lower bounds from Salim et al. [45], which is the right benchmark. Credit where due: this is a clean piece of work for the µ>0 case.\n\nThe soft spot is the general convex homotopy result (Theorem 5.1). The paper states the uniform boundedness assumption ∥x−x⋆∥² ≤ R² for all primal iterates at every homotopy stage, and Remark 5.1 explicitly says the fixed-parameter result (Proposition 5.1) does not establish this bound. The induction in the proof of Theorem 5.1 simply assumes it holds. No argument is given that the homotopy halving of ε preserves the bound. So the O(1/N²) rate for general convex objectives is conditional on an unverified assumption. The authors are honest about this—they flag it themselves—but it means the central claim for the convex case is not yet a theorem. The strongly convex results are unaffected.\n\nMinor issues: the numerical experiments run with parameters outside the theoretical guarantees (e.g., ATPD-0 with θ=1, which violates the strict inequality in Lemma 5.2). The authors disclose this, but it weakens the experimental support for the theory. No code is shipped, so the numerical claims cannot be independently reproduced from the preprint.\n\nWho this is for: researchers working on first-order methods for constrained convex optimization, especially those interested in oracle complexity separation. The strongly convex part is a solid contribution. The convex part is a conditional result that needs further work.\n\nRecommendation: I would send this to peer review. The strongly convex analysis is worth refereeing, and the convex part can be addressed in revision. The paper is serious and the authors are transparent about limitations.","headline":"Strongly convex ATPD results are solid and match lower bounds; the general convex O(1/N^2) rate is conditional on an unproven uniform boundedness assumption that the authors acknowledge but do not resolve.","tokens_in":29018,"tokens_out":566,"duration_ms":5992},"pith_extraction":{"msc":["37N40","47H05","47J25","65B99","65J15","65L20"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"Optimal first-order complexity for affine-constrained smooth convex problems","keywords":["accelerated primal-dual methods","affine equality constraints","first-order oracle complexity","Lyapunov analysis","convex optimization","saddle-point problems","homotopy perturbation"],"falsifier":"If for a simple convex quadratic with affine constraint, the homotopy ATPD method (Algorithm 3) fails to achieve O(1/$N^{2}$) decay of the Lyapunov energy when the primal iterates leave a bounded region, then the uniform boundedness assumption is violated and the convex-case theory would not apply to that problem.","tokens_in":29786,"feed_emoji":"⚡","tokens_out":1160,"duration_ms":16126,"temperature":0.7,"pith_summary":"This paper introduces Accelerated Transformed Primal–Dual (ATPD) methods that achieve the known lower bounds on first-order oracle complexity for smooth convex optimization with affine equality constraints. For strongly convex objectives, ATPD converges linearly with a contraction factor depending on the square root of the condition number, using one gradient evaluation and two matrix–vector products per iteration. For general convex objectives, a homotopy strategy yields an accelerated sublinear rate under a uniform boundedness condition. The method avoids projections and exact subproblem solves, making it practical for large-scale problems where the cost of matrix–vector products dominates.","feed_headline":"Optimal oracle complexity for affine-constrained optimization","feed_subtitle":"ATPD achieves accelerated linear convergence without projections or exact subproblem solves.","key_machinery":"The accelerated transformed primal–dual flow (ATPD flow) combines an auxiliary variable splitting with a linear transformation that restores strong monotonicity of the saddle operator. The flow is discretized using accelerated overrelaxation, leading to Algorithm 2. The modified discrete Lyapunov function E_α^M incorporates a cross-term that enables the accelerated convergence analysis via a strong Lyapunov property.","core_discovery":"ATPD methods achieve optimal first-order oracle complexity for smooth convex optimization with affine equality constraints. For strongly convex objectives, the method attains a linear convergence rate matching the lower bounds derived by Salim et al. (2022). The acceleration mechanism is based on an exponentially stable continuous-time flow and a modified discrete Lyapunov function. The analysis separates the costs of gradient evaluations and matrix–vector products, showing that ATPD uses O(√κ(f) log(1/ε)) gradient evaluations and O(√κ(f)κ(BBᵀ) log(1/ε)) matrix–vector products to reach ε-accuracy.","pith_inferences":["The uniform boundedness assumption in Theorem 5.1 is not verified by the paper for the homotopy method; a proof that the bound holds under the algorithm's dynamics would complete the convex case theory.","The method's reliance on a fixed linear inner solver satisfying (30) may be restrictive; practical implementations using CG or other nonlinear solvers are not covered by the convergence theory.","The extension to nonsmooth objectives, mentioned as future work, would significantly broaden applicability to problems like Lasso or total variation denoising, but would require new techniques to handle nondifferentiability."],"forward_implications":["If ATPD is correct, it provides the first method achieving the separate oracle complexity bounds for gradient evaluations and matrix–vector products without projections or exact subproblem solves.","The method directly applies to problems in PDE-constrained optimization, image processing, distributed optimization, and machine learning where affine constraints appear.","The homotopy extension offers a practical way to handle unknown strong convexity parameters while maintaining accelerated rates under a boundedness condition.","The analysis framework connecting continuous-time flows to discrete algorithms may guide the design of accelerated methods for other structured optimization problems."],"supporting_citations":[{"why":"Establishes the lower complexity bounds for first-order oracle complexity that ATPD matches.","marker":"[45]"},{"why":"Provides the non-accelerated transformed primal–dual method and its convergence analysis, which ATPD extends.","marker":"[14]"},{"why":"Supplies the standard accelerated gradient method for unconstrained problems and the smooth-convex gradient inequality used in Lemma 4.2.","marker":"[40]"},{"why":"Discusses acceleration techniques for saddle-point problems, which ATPD adapts to the affine-constrained setting.","marker":"[34]"},{"why":"Provides an accelerated linearized augmented Lagrangian method used as a baseline in numerical comparisons.","marker":"[26]"},{"why":"Studies near-optimal complexity separation for composite saddle-point problems and provides the OptAlg baseline.","marker":"[6]"}],"fun_headline_variants":["Accelerated primal-dual hits optimal oracle bounds","No projections needed for affine-constrained speed","ATPD matches lower complexity limits in convex optimization","Faster affine-constrained solving with optimal gradient counts","Continuous-time flow yields accelerated linear convergence"],"cache_read_input_tokens":0,"weakest_assumption_plain":"For general convex objectives, the homotopy method's accelerated sublinear rate depends on the assumption that all primal iterates at every homotopy stage stay within a fixed ball of known radius around the solution.","fun_headline_variants_meta":{"raw":{"variants":["Accelerated primal-dual hits optimal oracle bounds","No projections needed for affine-constrained speed","ATPD matches lower complexity limits in convex optimization","Faster affine-constrained solving with optimal gradient counts","Continuous-time flow yields accelerated linear convergence"]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000122,"raw_usage":{"cost":0.000122248,"is_byok":false,"cost_details":{"upstream_inference_cost":0.000122248,"upstream_inference_prompt_cost":8.8368e-05,"upstream_inference_completions_cost":3.388e-05},"total_tokens":957,"prompt_tokens":836,"completion_tokens":121,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":50}},"tokens_in":836,"tokens_out":121,"cost_source":"openrouter_usage","duration_ms":2072,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":50,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T07:29:53.762264+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"If for a simple convex quadratic with affine constraint, the homotopy ATPD method (Algorithm 3) fails to achieve O(1/$N^{2}$) decay of the Lyapunov energy when the primal iterates leave a bounded region, then the uniform boundedness assumption is violated and the convex-case theory would not apply to that problem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the lower complexity bounds for first-order oracle complexity that ATPD matches."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the non-accelerated transformed primal–dual method and its convergence analysis, which ATPD extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard accelerated gradient method for unconstrained problems and the smooth-convex gradient inequality used in Lemma 4.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Discusses acceleration techniques for saddle-point problems, which ATPD adapts to the affine-constrained setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides an accelerated linearized augmented Lagrangian method used as a baseline in numerical comparisons."},{"cited_title":"Opti- mization Methods and Software, pp","cited_arxiv_id":null,"evidence_quote":"Studies near-optimal complexity separation for composite saddle-point problems and provides the OptAlg baseline."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}