{"id":"3aba1774-789f-4ed5-a672-c2d27a9e72e0","arxiv_id":"1908.11835","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A decentralized primal-dual method and its time-varying variant achieve O(1/k^2) ergodic convergence for strongly convex consensus optimization with agent-specific conic constraints.","lead":"Two decentralized primal-dual algorithms let agents minimize the sum of private strongly convex costs while agreeing on one decision that respects each agent's private nonlinear constraints, using only neighbor communication. The paper proves O(1/k^2) convergence for static and time-varying networks, matching the optimal rate of centralized first-order methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DPDA-TV's O(1/k^2) guarantee is proven only under a compact-domain assumption absent from the advertised problem class; Section 6's C-LASSO experiments run outside it.","rationale":"I read the paper as proving a precise but conditional statement: under compact domains and a known approximate-averaging operator satisfying (23), DPDA-TV achieves O(1/K^2) ergodic suboptimality/infeasibility and O(1/K^2) last-iterate distance. The proof of Theorem 3.1 is substantial and the telescoping argument in Lemma 5.3 is coherent; I did not find a clear algebraic error that invalidates the theorem under its stated hypotheses. The most load-bearing soft spot is scope: the abstract and introduction advertise O(1/k^2) for strongly convex conic-constrained consensus without mentioning compactness, while Theorem 3.1 requires Delta < infinity and the proof uses Delta essentially. The Section 6 C-LASSO experiments run in unbounded R^n, so they are outside the theorem and cannot be cited as evidence for the unbounded case. A secondary gap is that the static Theorem 2.2 proof is only sketched and its initialization depends on a dual bound B that requires a Slater point; even if the bound is correct via the same induction as Theorem 3.1, the paper does not fully verify it in the static setting. These concerns align with the reader's conditional verdict: the advertised first O(1/k^2) result is plausible but not established for the full problem class claimed, and the unbounded-domain experiments do not validate the theorem where it is weakest. I therefore recommend leaving the verdict CONDITIONAL, i.e., no change from the reader's assessment.","tokens_in":35521,"tokens_out":18058,"duration_ms":163965,"concrete_test":"Re-run the Section 6 C-LASSO experiment under the theorem's assumptions by adding uniform box constraints ||x_i|| <= D for D in {10^2, 10^4, 10^6} and also the unconstrained D = infinity case, using the theorem's q_k = (5+c) log_{1/zeta}(k+1). Plot the empirical exponent of max_i ||x_i^k - x*|| / ||x*|| and of infeasibility versus k, and record sup_k max_i ||x_i^k|| and ||nu^k||. If the exponent stays approximately 2 with constants independent of D as D grows, the compact-domain condition is likely technical; if the exponent degrades or ||x^k||/||nu^k|| grow with k, then the compact-domain assumption is load-bearing for the advertised O(1/K^2) rate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim -- first O(1/k^2) decentralized rates for nonlinearly conic-constrained consensus -- is not false as stated, but for the time-varying case it is narrower than the abstract and introduction suggest. Theorem 3.1 explicitly assumes Delta = max_i sup_{x in dom phi_i} ||x|| < infinity, introduced in Section 3 just before Definition 5. This is not a removable technicality within the proof as written: the error analysis controls the averaging error e^{k+1} via ||omega^k|| <= ||nu^k||/gamma_k + ||x^{k+1}||, and compactness supplies both ||x^{k+1}|| <= sqrt(N) Delta and, through (39), ||nu^k|| <= 3 sqrt(N) Delta sum_{t<k} gamma_t. These bounds convert the geometric averaging error (23) into the k^4 beta^{q_k} term in Lambda(K) at (57)-(58). If dom phi_i is unbounded, neither ||x^k|| nor ||nu^k|| is a priori controlled, the summability condition sum beta^{q_k} k^4 < infinity no longer bounds Lambda(K), and the O(1/K^2) conclusion of Theorem 3.1 is unsupported. The Section 6 supplement runs C-LASSO with affine constraints but dom phi_i = R^n, i.e., Delta = infinity, so those plots do not exercise the theorem's hypotheses. Static DPDA avoids Delta, but Theorem 2.2 is only sketched ('the result follows from (7)'), and its step-size requires the dual bound B from (16)/(17), computable only with a Slater point and knowledge of ||theta*||; without such data the static O(1/K^2) guarantee is also conditional. The paper itself flags the compactness assumption, and Remark 3.2 admits that a tighter analysis is possible; Lemma 3.2 is stated without proof. These are real limitations on the advertised scope, though not a demonstrated internal contradiction inside Theorem 3.1.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two decentralized primal-dual algorithms for consensus optimization with agent-specific nonlinear conic constraints: DPDA for static networks and DPDA-TV for time-varying networks. For strongly convex objectives it claims O(1/k^2) ergodic rates on suboptimality, infeasibility, and consensus violation, plus O(1/k^2) convergence of the iterates, in terms of communication rounds. The analysis is based on an accelerated primal-dual inequality from the authors' prior work [11], with new bounds for the dual iterates and for the error caused by approximating the averaging operator via finite communication rounds.","tokens_in":35944,"tokens_out":4948,"duration_ms":48091,"significance":"If the results are correct, this is a meaningful advance: it provides the first O(1/k^2) decentralized rates for nonlinearly conic-constrained consensus problems, matching the centralized lower bound up to communication overhead. The paper gives explicit step-size rules and a detailed time-varying analysis via push-sum and Metropolis averaging, with quantified error accumulation. The authors also provide numerical evidence on static and time-varying networks for ellipsoid intersection and C-LASSO problems. The central parameter-free APD inequality and the telescoping structure of the appendix are substantial strengths. However, the time-varying guarantee is conditional on a compact-domain assumption and on knowledge of the averaging contraction parameters, and the static guarantee requires a Slater point and a computable dual bound; these restrictions are not reflected in the abstract.","major_comments":[{"comment":"The compact-domain assumption Δ = max_i sup_{x∈dom φ_i} ||x|| < ∞, introduced just before Definition 5, is load-bearing. The bound (57) on Λ(K) relies on ||x^{k+1}|| ≤ √N Δ and on the estimate (39) for ||ν^k||; without compactness neither is available, and the summability condition on β^{q_k}k^4 no longer controls the error term. Since the abstract and introduction advertise problem (2) without compactness, the time-varying O(1/k^2) claim is narrower than stated. Please either extend the proof to unbounded domains with an alternative boundedness argument, or prominently restrict the claims in the abstract and introduction to the compact-domain setting.","section":"Section 3, Theorem 3.1"},{"comment":"The supplementary C-LASSO experiments solve (70) with local variables x_i ∈ R^n and no bound on the domain, so Δ = ∞. These experiments therefore lie outside the hypotheses of Theorem 3.1. The experimental section should explicitly state this limitation, or the experiments should be modified to use a bounded feasible set that satisfies the theorem's assumptions.","section":"Section 6, C-LASSO experiments"},{"comment":"The proof of the uniform dual bound required for the static case is only sketched (the text says 'Due to the limited space we briefly give the proof sketch'), and Theorem 2.2 states that the rate 'follows from (7)' without a full derivation. Because the step-size selection of DPDA depends on the bound B, which is computable only when a Slater point is available, the static O(1/k^2) guarantee is not fully justified as written. Please provide a complete proof of the dual bound and of Theorem 2.2 in an appendix.","section":"Section 2, Lemma 2.1 and Theorem 2.2"},{"comment":"Lemma 3.2 is stated without proof, and its statement only covers exponents of the form p√k. Remark 3.4 uses q_k = (k+1)^{1/p}, which is not of that form for general p ≥ 1. Since this lemma is used to justify the summability of the error terms and the alternative communication schedule, either the lemma should be proved and generalized to match the claimed use, or the remark should be reworded to rely on a direct super-polynomial decay argument.","section":"Lemma 3.2 and Remark 3.4"}],"minor_comments":[{"comment":"The description of the 'slightly extended version of APD' would benefit from an explicit statement of which assumptions in [11] are relaxed and how the step-size conditions in (6) relate to the original APD conditions.","section":"Section 1.1"},{"comment":"The proof refers to 'the same arguments to obtain (37)', but (37) appears later in the proof of Lemma 3.3; please reorder or add a cross-reference to Equation (37) within the current proof.","section":"Section 5.1 (Proof of Lemma 2.3)"},{"comment":"The notation Λ(K) appears in the theorem statement but is only defined later in the proof (after (67)); please define it in the statement or right after the display, and check that it is compatible with Λ0 in Theorem 2.2.","section":"Theorem 3.1, statement"},{"comment":"The plots in Figures 10-12 would be easier to read if the legend entries were consistent across panels and the y-axis labels matched the statistics described in the text.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript heavily relies on the authors' own prior work [11], [30], [36]; this is natural given the lineage, but the referee reports should ask that the missing proofs of Lemma 2.1 and Lemma 3.2 be included rather than deferred to previous papers. The compactness gap between the advertised problem class and the time-varying theorem is the main correctness-risk area; it is fixable by either extending the analysis or adjusting the claims. The paper fits the scope of the journal and the numerical study is useful, though the C-LASSO part should be brought under the theorem's assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's the quick take on 1908.11835. The paper's real contribution is an O(1/k^2) ergodic rate for decentralized consensus optimization with agent-specific nonlinear conic constraints, over static and time-varying directed graphs. If the main theorems hold, that is a genuine improvement over the O(1/k) rates in the authors' earlier work [30] and over the no-rate results in [26]-[29]. The APD-based derivation is sound in outline: the paper extends the authors' published SIOPT result [11] to a conic-constrained consensus reformulation, and the time-varying analysis handles the approximate averaging error via an explicit induction on the dual iterates. The appendix is substantial, and the proof of Theorem 3.1 is mostly there.\n\nThe soft spots are real but not fatal. The time-varying result in Theorem 3.1 assumes compact domains (Delta < infinity) and this assumption is load-bearing: it controls ||x^k|| and ||nu^k||, which in turn bound the averaging error. The abstract and introduction do not mention it, so the advertised scope is wider than the proven theorem. The Section 6 C-LASSO experiments use unbounded polyhedral domains, so they do not exercise the theorem's hypotheses. A referee should ask the authors to either relax the compactness condition or state the theorem with it upfront. The static result, Theorem 2.2, is only sketched—the dual-bound proof is deferred with 'due to limited space'—and Lemma 3.2 is stated without proof, though that lemma looks standard. None of this is a demonstrated contradiction, but the static theorem as written is more promise than proof.\n\nThe self-citation pattern is heavy, but not circular: the key inequality (7) comes from the published [11], and the target rates are not fitted constants. I take the novelty claim seriously.\n\nWho this is for: people working on primal-dual methods for decentralized constrained optimization. It deserves a serious referee. I would accept it for review and push for a complete static proof and a clearer treatment of the compactness assumption, but I would not desk-reject it.","headline":"A genuinely useful O(1/k^2) result for decentralized conic consensus, but the time-varying theorem is narrower than advertised and the static proof is mostly a sketch.","tokens_in":36492,"tokens_out":4170,"would_cite":true,"duration_ms":36661,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C46","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"A decentralized primal-dual method achieves optimal $O(1/k^2)$ rates for constrained consensus over static and time-varying networks.","keywords":["decentralized optimization","consensus optimization","primal-dual method","conic constraints","strong convexity","accelerated methods","time-varying networks","convergence rate"],"falsifier":"Run DPDA on a two-agent static network for problem (2) with $n=2$, $f_i(x)=\\tfrac12\\|x-a_i\\|^2$ for distinct $a_i$, and constraint sets $\\{x : \\|x\\|^2 \\le 1\\}$ for both agents (a Slater point exists), measuring $\\phi(\\bar{x}^K)-\\phi(x^*)$ and the infeasibility of $\\bar{x}^K$. Theorem 2.2 predicts both decay as $O(1/K^2)$ with $W_K=\\Theta(K^2)$; if the experimental decay is provably slower (e.g., $O(1/K)$) for a correctly tuned implementation, the theorem's claim would be contradicted.","tokens_in":35352,"feed_emoji":"⚡","tokens_out":8733,"duration_ms":73502,"temperature":0.7,"pith_summary":"The paper aims to establish that a group of agents, each minimizing its own strongly convex cost function and each imposing its own nonlinear conic constraint, can reach a common optimal decision at a $O(1/k^2)$ rate using only neighbor-to-neighbor message passing. This rate matches the optimal centralized rate for first-order primal-dual methods, making decentralization costless in convergence order. Prior decentralized methods for such conic constraints either required impractical projections onto the constraint sets or converged only at $O(1/k)$. The paper proves the rate for both static networks and time-varying directed networks, with total communication rounds growing as $O(k)$ and $O(k \\log k)$, respectively. If the theorems are correct, these are the first $O(1/k^2)$ guarantees for nonlinearly conic-constrained consensus optimization.","feed_headline":"First O(1/k^2) rate for distributed conic-constrained consensus","feed_subtitle":"A primal-dual method matches centralized convergence speed using only neighbor-to-neighbor message passing.","key_machinery":"The central object is a convex-concave saddle-point reformulation of (2), where dual variables $\\theta_i$ enforce each conic constraint $g_i(x) \\in -K_i$ via projection onto the polar cone $K_i^*$, and a consensus dual variable ($\\lambda$ for static, $\\nu$ for time-varying) enforces agreement. The paper's APD-based recursion alternates primal and dual updates with step sizes $\\tau_k = \\Theta(1/k)$ and $\\gamma_k = \\Theta(k)$, which yields the weight factor $W_K = \\Theta(K^2)$. Two detailed mechanisms carry the argument: an x-update-before-y-update ordering that produces an inductive bound on the dual iterates (breaking the circular dependence between the coupling Lipschitz constant and the dual bound), and for DPDA-TV an approximate averaging operator $R^k$ (the push-sum protocol) whose error $\\|R^k(\\omega) - P_{\\Xi}(\\omega)\\| \\le N \\Gamma \\beta^{q_k} \\|\\omega\\|$ is controlled by choosing $q_k = (5+c)\\log_{1/\\varsigma}(k+1)$ communication rounds per iteration.","core_discovery":"On the paper's own terms, the central discovery is that strong convexity can be fully exploited in a decentralized primal-dual framework: DPDA (static networks) and DPDA-TV (time-varying networks) generate ergodic averages $\\bar{x}^K$ that satisfy $\\max\\{|\\phi(\\bar{x}^K)-\\phi(x^*)|,\\ d_{\\Xi}(\\bar{x}^K)+\\sum_i \\|\\theta_i^*\\|\\, d_{-K_i}(g_i(\\bar{x}^K_i))\\}=O(1/K^2)$, and last iterates with $\\|\\bar{x}^K - x^*\\|^2 = O(1/K^2)$, provided the dual sequences stay bounded and, for DPDA-TV, the approximate averaging errors decay fast enough. The key is a step-size scheduling that grows the consensus weights as $W_K = \\Theta(K^2)$ while damping primal step sizes as $\\Theta(1/k)$. When the constraint functions are affine, no dual bound is needed; when they are nonlinear, a Slater point yields the bound $B$ in (17). The paper also shows the $O(1/k^2)$ rate persists under time-varying directed topologies, where the consensus projection is replaced by an inexact push-sum average.","pith_inferences":["The compact-domain assumption in Theorem 3.1 is not a proof artifact only: the numerical tests on C-LASSO in Section 6 use unbounded $\\mathbb{R}^n$ domains, so the stated $O(1/k^2)$ guarantee does not formally cover those experiments. A localization argument (e.g., a projected step that keeps iterates in a bounded set) would be a natural extension.","The dual bound $B$ in (17) requires a Slater point; the framework leaves open the case where the duality gap is zero but no Slater point exists, which would need a different mechanism to control dual iterates.","If the averaging contraction parameters $\\Gamma$ and $\\beta$ are unknown, the paper's own Remark 3.4 shows that choosing $q_k = (k+1)^{1/p}$ keeps convergence but inflates the communication count to $O(K^{1+1/p})$; one could test whether the asymptotic rate still holds with such a choice in practice.","The summability condition $\\sum_k \\beta^{q_k} k^4 < \\infty$ quantifies how much inexactness an accelerated primal-dual method can tolerate; it suggests that any consensus subroutine with geometrically decreasing error can be plugged into the framework without destroying the $O(1/k^2)$ rate."],"forward_implications":["For strongly convex agents with nonlinear conic constraints, achieving $\\epsilon$-suboptimality and $\\epsilon$-infeasibility requires $O(1/\\sqrt{\\epsilon})$ iterations on static networks and $\\tilde{O}(N^4/\\sqrt{\\epsilon})$ total communication rounds on time-varying networks.","When the constraint functions are affine, the primal step size no longer depends on the dual bound, and the communication complexity improves to $\\tilde{O}(N^{3.5}/\\sqrt{\\epsilon})$.","The $O(1/k^2)$ rate matches the centralized lower bound $\\Omega(1/k^2)$ for first-order primal-dual methods, so decentralization does not slow down convergence in this setting.","A corollary of the analysis gives an $O(1/k)$ rate when strong convexity is relaxed, extending the authors' earlier result from affine to nonlinearly conic-constrained problems."],"supporting_citations":[{"why":"supplies the accelerated primal-dual template and step-size conditions from which DPDA and DPDA-TV are derived.","marker":"[11]"},{"why":"the authors' earlier distributed primal-dual method with O(1/k) rate that this paper extends from affine to nonlinear conic constraints.","marker":"[30]"},{"why":"provides the Omega(1/k^2) lower bound that the O(1/k^2) rate matches for first-order primal-dual methods.","marker":"[32]"},{"why":"source of the restricted-strong-convexity regularization lemma adapted to handle the merely convex case.","marker":"[15]"},{"why":"the original accelerated primal-dual recursion that APD generalizes for the saddle-point formulation.","marker":"[34]"},{"why":"provides the accelerated step-size recursion (gamma_k = Theta(k), tau_tilde_k = Theta(1/k)) that Lemma 2.1 derives its rate from.","marker":"[35]"},{"why":"lemma that converts a Slater point into a finite bound on the dual variables, needed to initialize B in the static method.","marker":"[36]"},{"why":"establishes geometric convergence of push-sum averaging over M-strongly connected directed time-varying graphs, providing the contraction beta.","marker":"[41]"},{"why":"bounds the averaging error for time-varying undirected graphs, giving the parameters Gamma and beta used in Assumption 3.2.","marker":"[42]"}],"fun_headline_variants":["O(1/k^2) decentralized conic-constrained consensus","Strong convexity unlocks O(1/k^2) decentralized rates","Conic-constrained consensus at O(1/k^2) speed","Decentralized primal-dual achieves O(1/k^2) rate","O(1/k^2) rate for distributed conic-constrained optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantees rest on strong convexity of the aggregate objective and, for time-varying networks, on bounded search domains and known contraction parameters for the approximate consensus averaging; if any of these fail, the stated $O(1/k^2)$ rate is not proven.","fun_headline_variants_meta":{"raw":{"variants":["O(1/k^2) decentralized conic-constrained consensus","Strong convexity unlocks O(1/k^2) decentralized rates","Conic-constrained consensus at O(1/k^2) speed","Decentralized primal-dual achieves O(1/k^2) rate","O(1/k^2) rate for distributed conic-constrained optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001939,"raw_usage":{"total_tokens":7558,"prompt_tokens":893,"completion_tokens":6665,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":509,"completion_tokens_details":{"reasoning_tokens":6569}},"tokens_in":509,"tokens_out":6665,"duration_ms":42759,"temperature":1.0,"reasoning_tokens":6569,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:06:36.499970+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DPDA on a two-agent static network for problem (2) with $n=2$, $f_i(x)=\\tfrac12\\|x-a_i\\|^2$ for distinct $a_i$, and constraint sets $\\{x : \\|x\\|^2 \\le 1\\}$ for both agents (a Slater point exists), measuring $\\phi(\\bar{x}^K)-\\phi(x^*)$ and the infeasibility of $\\bar{x}^K$. Theorem 2.2 predicts both decay as $O(1/K^2)$ with $W_K=\\Theta(K^2)$; if the experimental decay is provably slower (e.g., $O(1/K)$) for a correctly tuned implementation, the theorem's claim would be contradicted.","supporting_citations":[{"cited_title":"A primal-dual method for conic constrained distributed optimization problems,","cited_arxiv_id":null,"evidence_quote":"the authors' earlier distributed primal-dual method with O(1/k) rate that this paper extends from affine to nonlinear conic constraints."},{"cited_title":"Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems,","cited_arxiv_id":null,"evidence_quote":"provides the Omega(1/k^2) lower bound that the O(1/k^2) rate matches for first-order primal-dual methods."},{"cited_title":"Extra: An exact first-order algorithm for decentralized consensus optimization,","cited_arxiv_id":null,"evidence_quote":"source of the restricted-strong-convexity regularization lemma adapted to handle the merely convex case."},{"cited_title":"On the ergodic convergence rates of a first-order primal–dual algorithm,","cited_arxiv_id":null,"evidence_quote":"the original accelerated primal-dual recursion that APD generalizes for the saddle-point formulation."},{"cited_title":"A first-order primal-dual algorithm for convex problems with applications to imaging,","cited_arxiv_id":null,"evidence_quote":"provides the accelerated step-size recursion (gamma_k = Theta(k), tau_tilde_k = Theta(1/k)) that Lemma 2.1 derives its rate from."},{"cited_title":"A distributed ADMM-like method for resource sharing over time-varying networks,","cited_arxiv_id":null,"evidence_quote":"lemma that converts a Slater point into a finite bound on the dual variables, needed to initialize B in the static method."},{"cited_title":"Distributed optimization over time-varying directed graphs,","cited_arxiv_id":null,"evidence_quote":"establishes geometric convergence of push-sum averaging over M-strongly connected directed time-varying graphs, providing the contraction beta."},{"cited_title":"On distributed averaging algorithms and quantization effects,","cited_arxiv_id":null,"evidence_quote":"bounds the averaging error for time-varying undirected graphs, giving the parameters Gamma and beta used in Assumption 3.2."}],"review_version":1}