{"id":"0459709a-e9fa-41c4-945e-1d78a06543a5","arxiv_id":"2507.16675","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A performance estimation framework for coordinate-wise smooth convex functions yields improved worst-case bounds for cyclic coordinate descent and proves a p-fold lower bound versus full gradient descent.","lead":"This paper builds a mathematical tool that computes worst-case performance bounds for cyclic block coordinate descent, an algorithm that updates one part of the variables at a time. The tool gives tighter bounds than older analyses and shows that the worst-case slowdown is at least the number of blocks times full gradient descent.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Numerical worst-case 'upper bounds' are not verifiably upper bounds: no code, no solver certificates, and primal SDP values alone are lower bounds on the relaxation optimum.","rationale":"I read the paper in good faith. The formal extension of PEP to coordinate-wise smooth convex functions appears sound: Lemma 2.2 and Theorem 2.2 correctly characterize the class via per-block quadratic lower bounds, Theorem 2.3 states necessary interpolation conditions (reading (6) as holding for each block, consistent with Lemma 2.2), and Theorem 2.4 provides a valid non-sufficiency counterexample. The scale-invariance (Theorem 3.1), the p-fold lower bound (Theorem 3.2), and the 2-block descent lemma (Lemma 3.1, Theorem 3.3) are internally consistent. The load-bearing weakness is the numerical section: the headline 'improved numerical upper bounds' cannot be checked without code, and the way SDP values are reported may not guarantee they are upper bounds. The paper itself flags Setting INIT convergence as 'numerical evidence' (Section 4.2), yet the abstract claims 'we show the convergence'—an overstatement that should be corrected. The strongest formal claim (Theorem 3.2) is unaffected, but the quantitative contributions and the CACD slowdown conclusion rest on unverified computation. This matches the reader's weakest assumption, so I do not propose changing the CONDITIONAL verdict; rather, the condition should explicitly require code and solver certificates, plus a consistency check against Theorem 3.2.","tokens_in":29811,"tokens_out":34861,"duration_ms":330981,"concrete_test":"Request the authors' SDP code and solver logs; re-run the 2-block CCD Setting INIT SDP at K=10 and K=50 with a certified solver (e.g., SDPA-GMP or MOSEK with dual certificate) and compare the certified upper bound to (i) the plotted value in Figure 2(a) and (ii) the lower bound p times the worst-case of gradient descent after 2K steps from Theorem 3.2. If the certified upper bound exceeds the plotted value by more than solver tolerance, or lies below the lower bound, the improved-bound and O(1/K) claims are not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The quantitative claims (Figures 1, 2, 6, 7, Table 2) are presented as improved worst-case upper bounds obtained by solving the SDP relaxation (R-PEP-coord) of Section 4.1. For a maximization SDP, a feasible primal solution provides a lower bound on the SDP optimum; an upper bound on the true worst-case requires the SDP optimum or a dual certificate. The paper reports no solver certificates, tolerances, or code, so a reader cannot verify that the plotted values are not merely feasible primal objectives below the true SDP optimum. Moreover, since the interpolation conditions (6) are only necessary (Theorem 2.4), the SDP is a relaxation: the true worst-case is at most the SDP optimum, so only the certified SDP optimum is a valid upper bound. An inaccurate solver solution could also violate the paper's own lower bound (Theorem 3.2): for 2-block CCD in Setting INIT, the reported upper bound times K at large K should exceed p times the GD worst-case, approximately 1/2; if the plotted curve lies below this, the numerical upper bound is invalid. The CACD slowdown conclusion (Section 4.7) is similarly based on unverified upper bounds, not lower bounds, so the claim 'slower than O(1/K^2)' is an extrapolation from loose numerical values. These issues are addressable by releasing code and certificates, hence CONDITIONAL.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a Performance Estimation Problem (PEP) framework for unconstrained minimization over coordinate-wise smooth convex functions. It derives necessary interpolation conditions (6), observes that they are sufficient only for two-point sets, and relaxes the resulting PEP to an SDP. It then uses this SDP to compute numerical worst-case bounds for cyclic coordinate descent, alternating minimization, and a cyclic variant of the Fercoq--Richtárik accelerated coordinate descent. Formal results include a scale-invariance theorem for CCD, a lower bound showing that p-block CCD is at least p times worse than full gradient descent after pK steps, and a descent lemma for 2-block CCD with a gradient-norm bound. Numerical sections report improved bounds under two initial-condition settings and argue that the deterministic accelerated scheme appears to converge slower than O(1/K^2).","tokens_in":30131,"tokens_out":20582,"duration_ms":207969,"significance":"If the numerical bounds are backed by certified SDP solutions, the paper provides a substantial toolkit for BCD worst-case analysis and a first PEP treatment of coordinate-wise smooth function classes. The formal results—Theorem 3.1's scaling reduction, Theorem 3.2's lower-bound construction, and Lemma 3.1's descent inequality—are elegant and appear correct, and the p-times-GD lower bound gives a clean benchmark for future upper bounds. The paper is also honest in several places about the heuristic status of the numerical evidence, though the abstract and conclusion occasionally overstate it. The main obstacles are the lack of reproducible and certified SDP computations and an invalid counterexample in Theorem 2.4.","major_comments":[{"comment":"The numerical 'upper bounds' in Figures 1–7 and Tables 1–2 are not verifiable upper bounds as reported. For a maximization SDP, a feasible primal solution is only a lower bound on the SDP optimum; an upper bound on the true worst case requires the certified SDP optimum or a dual certificate, because (R-PEP-coord) is only a relaxation of the true PEP. The paper gives no solver, tolerances, or certificates, so a reader cannot check that the plotted values are not below the true relaxation optimum. This directly affects the central quantitative claims of Sections 4.2, 4.4, and 4.7. Please release reproducible code and certificates, or explicitly relabel the plotted values as heuristic estimates.","section":"Section 4.1–4.7"},{"comment":"The counterexample claimed to show non-sufficiency of (6) for |I|=3 does not satisfy (6) for L=(1,1) as stated. For the pair (x1,g1,f1) and (x2,g2,f2) in Table 3, f2 + <g2, x1−x2> + (1/2)||g1−g2||^2 = 0 + 0 + 1 = 1 > 1/2 = f1, violating the first interpolation inequality. Thus the insufficiency for N≥3 is not established. Please provide a valid counterexample or revise the statement of Theorem 2.4 and the related discussion in Section 2.3 that relies on it.","section":"Theorem 2.4 / Appendix A.3"},{"comment":"The conclusion that CACD converges slower than O(1/K^2) is not supported by the displayed evidence. Figure 7 plots an upper bound multiplied by K^2; the fact that this computed surrogate is increasing in K does not exclude a true O(1/K^2) rate whose constant is small, nor does it provide the required lower bound on the worst-case performance. Please rephrase the conclusion as 'the PEP upper bound does not capture an O(1/K^2) rate' or supply lower-bound certificates, and adjust the abstract and conclusion accordingly.","section":"Section 4.7"},{"comment":"The statement of Theorem 4.1 is under-specified: the quantity R in (16) is printed as min_{x*∈X*} max_{k∈{1,...,K}}{||x−x*|| : f(x)≤f(x0)}, which does not depend on k and does not match the Setting ALL definition in (13). In addition, the proof is only a citation to [3, Corollary 3.7] with the descent lemma swapped. Since the semi-analytical bound in Figure 3 is a stated contribution, please give a complete derivation and a precise definition of R.","section":"Theorem 4.1, Section 4.3"}],"minor_comments":[{"comment":"The abstract states that 'we show the convergence of CCD with more natural assumptions', but Section 4.2 only provides numerical evidence (a linear fit of reciprocal bounds) under Setting INIT; please soften the wording.","section":"Abstract / Section 4.2"},{"comment":"Contribution (i) says that the necessary conditions characterizing Fcoord are also sufficient, while Theorem 2.4 says the interpolation conditions (6) are sufficient only for |I|=2; please disambiguate between the function-class characterization and the finite-set interpolation conditions.","section":"Section 2.3 / Introduction"},{"comment":"In the proof of (3)⇒(1), after adding the two inequalities, the Cauchy-Schwarz bound should be applied to <∇ℓ f(x+Uℓh)−∇ℓ f(x), h>, giving ||Δℓ|| ||h||; the printed version with the full gradient norm and ||Uℓh|| does not imply the stated Lipschitz bound.","section":"Appendix A.2"},{"comment":"The linear fits in Figure 2(c,d) should be described as heuristic; they do not constitute a proof of an O(1/K) rate under Setting INIT.","section":"Section 4.2"},{"comment":"There are numerous typos and unclear phrases, e.g., 'Introdution' in the Section 2 heading, 'Plunging this into (9)' in Lemma 3.1, and 'we use the inequalities of 2 in Theorem 2.2' in Section 4.2; a careful proofread is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The numerical reproducibility issue is the main blocker: the paper should not present unverified SDP outputs as rigorous upper bounds. The invalid counterexample in Theorem 2.4 is also concerning and should be fixed before acceptance. I would also ask the authors to substantiate their strong criticism of [24, Theorem 3.1] with a concrete demonstration, since the current text only refers to the lower bound of Theorem 3.2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real step forward for PEP-based analysis of coordinate descent, and the formal parts look sound to me. The genuinely new pieces are (i) necessary interpolation conditions for coordinate-wise smooth convex functions, with Theorem 2.4 correctly stating that they are sufficient only for two-point sets and giving a concrete three-point counterexample; (ii) the scale invariance theorem; and (iii) the lower bound in Theorem 3.2, which is proved constructively and is easy to verify. The 2-block descent lemma and the gradient-norm bound are clean and useful.\n\nThe soft spots are mostly in the numerical sections. The paper presents PEP upper bounds as improved, but gives no code, no solver model files, no dual certificates, and no tolerances. For a maximization SDP relaxation of the true PEP, a feasible primal objective is only a lower bound on the relaxation optimum; only a certified optimal value or a dual certificate gives a genuine upper bound on the worst case. That means the quantitative claims in Figures 1, 2, 6, 7 and Table 2 are not independently checkable as published. This is fixable by releasing the model and certificates, but it has to be fixed before the \"improved bound\" claims are credible.\n\nTwo smaller issues. The abstract says \"we show the convergence of CCD under more natural assumptions,\" but Section 4.2 only provides numerical evidence and a linear fit; that should be labeled as evidence, not proof. And Remark 3.3 asserts that the bound in [24] is false because it violates the new lower bound. That may well be right, but the paper does not demonstrate the contradiction step by step; it deserves a precise derivation or at least a reproducible SDP for the bound being challenged.\n\nI do not think the central argument is broken. The lower bound and scale invariance hold independently of the numerics, and the interpolation conditions are worth having even if the SDP relaxation is not tight. The paper should get a serious referee. The revision gate should be: code and certificates, plus wording changes for the abstract and Remark 3.3.","headline":"A genuinely useful PEP extension with solid formal results, but the headline numerical upper bounds need code and solver certificates before they can be checked.","tokens_in":30649,"tokens_out":2727,"would_cite":true,"duration_ms":29215,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C22","90C60","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that p-block cyclic coordinate descent has worst-case performance at least p times that of full gradient descent, and uses a performance-estimation framework to obtain improved upper bounds for block-coordinate algorithms.","keywords":["coordinate-wise smooth convex functions","performance estimation problem","cyclic coordinate descent","alternating minimization","accelerated coordinate descent","worst-case analysis","semidefinite programming","interpolation conditions"],"falsifier":"Run the paper's SDP relaxation for, say, two-block CCD with $L=(1,1)$ and $R_i=1$ in an independent solver and compare the objective with the reported bound; a smaller optimum would mean the published curve is not actually an upper bound, while a larger one would mean the reported comparisons used a non-optimal certificate. Separately, computing the worst-case smooth function for full gradient descent, lifting it to $p$ blocks via $\\hat f(x)=f(x^{(1)}+\\cdots+x^{(p)})$, and measuring CCD's normalized performance would directly test Theorem 3.2: any value below $p$ times the full-gradient worst case after $pK$ steps would contradict it.","tokens_in":29592,"feed_emoji":"📉","tokens_out":9467,"duration_ms":95513,"temperature":0.7,"pith_summary":"This paper addresses a well-known mismatch: cyclic and alternating block-coordinate descent algorithms work well in practice, yet the best theoretical worst-case guarantees are much more pessimistic. It extends the performance estimation problem (PEP) approach—computing an algorithm's worst-case behavior by solving an optimization problem over the function class—to convex functions with coordinate-wise Lipschitz gradients, via necessary interpolation conditions that combine convexity and block smoothness in one inequality per block. With this machinery the paper reports numerical worst-case upper bounds for cyclic coordinate descent (CCD), alternating minimization, and a cyclic accelerated coordinate descent that are substantially tighter than the best analytical bounds in many regimes, improving the known cubic dependence on the number of blocks to a linear one. It also proves formal results: the normalized worst-case performance of CCD is scale-invariant in the block smoothness constants, and after $K$ cycles a $p$-block CCD is at least $p$ times worse than $pK$ steps of full gradient descent on smooth convex functions. The upshot is that the practical efficiency of block-coordinate updates is compatible with, and in key respects predicted by, a worst-case theory that treats each coordinate block as a separate smooth direction.","feed_headline":"Cyclic block descent's worst case: p times full gradient's","feed_subtitle":"New performance-estimation bounds tighten the gap and show acceleration needs randomness.","key_machinery":"The load-bearing object is the pairwise interpolation condition (6) for the class $F_{0,L}^{\\mathrm{coord}}$, equivalently characterized in Theorem 2.2 by the lower bound $$f(x_2) \\ge f(x_1) + \\langle \\nabla f(x_1), x_2 - x_1\\rangle + \\frac{1}{2L_\\ell}\\|\\$nabla^{{(\\ell)}}$f(x_1) - \\$nabla^{{(\\ell)}}$f(x_2)\\|^2$$ for each block $\\ell$. These inequalities fold convexity and block-coordinate smoothness into one quadratic constraint per block, and when imposed on all pairs of triples $(x_i,g_i,f_i)$ they are necessary for a convex coordinate-wise smooth function to interpolate the data. They are sufficient for two-point sets but not for larger sets, so the PEP built on them is intentionally a relaxation; the paper converts it into an SDP by a Gram-matrix lifting, with $p$ block Gram matrices instead of one. The other key mechanism is the scale-invariance reduction (Theorem 3.1), which rewrites any CCD run with anisotropic constants $L_\\ell$ as an isotropic one on a rescaled function, and the lifting construction $\\hat f(x)=f(x^{(1)}+\\cdots+x^{(p)})$ used in Theorem 3.2 to transfer the worst-case function of full gradient descent into a coordinate-wise function that makes CCD reproduce gradient descent $p$ times per cycle.","core_discovery":"The central claim is that the necessary interpolation conditions (6)—for every pair of points and every coordinate block $\\ell$, $$f_i \\ge f_j + \\sum_{\\ell=1}^p \\langle $g_j^{{(\\ell)}}$, $x_i^{{(\\ell)}}$ - $x_j^{{(\\ell)}}$\\rangle + \\frac{1}{2L_\\ell}\\|$g_i^{{(\\ell)}}$ - $g_j^{{(\\ell)}}$\\|^2$$—give a tractable relaxation of the exact worst-case problem for coordinate-wise smooth convex functions. Because the conditions are necessary but not sufficient for three or more interpolation points, the resulting semidefinite program is a relaxation and hence yields valid upper bounds on the worst-case performance. Using this relaxation, the paper computes bounds for cyclic coordinate descent under the standard 'all iterates bounded' assumption and under a milder 'initial distance only' assumption, obtaining rates consistent with $O(1/K)$ and beating the best previous analytical bound by an order of magnitude. Two formal results anchor the numerics: scaling all block smoothness constants to one leaves the normalized worst case unchanged, and there is a worst-case function on which $p$-block CCD is exactly $p$ times slower than full gradient descent, making the worst case of CCD at least $p$ times that of full gradient descent after the same number of partial-gradient steps.","pith_inferences":["The necessary-but-not-sufficient interpolation conditions point to triple-point constraints as the natural route to an exact PEP for coordinate-wise smooth functions; adding them might convert the reported upper bounds into exact worst-case rates or expose where the relaxation is loose.","The scale-invariance theorem makes the isotropic case $L=(1,\\dots,1)$ the only one that matters, so the paper's numerical observation of linear-in-$p$, $O(1/K)$ behavior becomes a concrete conjecture that an analytical proof for equal smoothness constants would settle.","The CACD slowdown suggests that momentum-based acceleration for coordinate descent is structurally tied to random block selection; a deterministic accelerated method with $O(1/K^2)$ would likely need a different mechanism, such as cyclic step sizes or memory of past partial gradients.","The numerically optimized descent-lemma constants and step sizes could be turned into a practical tuning rule: choose constants from a small SDP once and use them as a fixed step-size schedule, which the reported numbers suggest should be shorter than the full-gradient step $1/L_\\ell$."],"forward_implications":["Worst-case analyses of CCD can be normalized to unit smoothness constants, so any future upper bound proved for $L=(1,\\dots,1)$ automatically holds for arbitrary block smoothness constants, with the same normalized rate.","The lower bound of Theorem 3.2 implies every valid upper bound on CCD's worst-case function-value accuracy must grow at least linearly in the number of blocks $p$; the paper's numerical bounds match this linear growth, so the old cubic-in-$p$ bound cannot be optimal.","Under the milder Setting INIT—only an initial-distance bound to some minimizer—the PEP computations give the first evidence of $O(1/K)$ convergence for CCD, a regime where no analytical bound was previously available.","For two-block CCD, the new descent lemma gives an $O(1/K)$ upper bound on the minimal squared gradient norm along the iterates, a residual measure that full-gradient analyses also control.","The cyclic accelerated coordinate descent (CACD) bound grows with $K^2(f(x_N)-f_*)$, so the acceleration scheme inherited from randomized coordinate descent does not deliver its $O(1/K^2)$ rate when forced into deterministic cyclic order."],"supporting_citations":[{"why":"Supplies the best-known analytical baseline bound for CCD under Setting ALL, which the new numerical bounds are compared against.","marker":"[3]"},{"why":"Introduced the performance estimation problem concept that the paper extends to coordinate-wise smooth functions.","marker":"[8]"},{"why":"Provides the convex interpolation and Gram-matrix lifting technique used to reformulate the PEP relaxation as an SDP.","marker":"[28]"},{"why":"Contains a prior PEP-derived CCD upper bound that the paper argues contradicts Theorem 3.2 and is therefore incorrect.","marker":"[24]"},{"why":"Supplies previous worst-case lower bounds for BCD algorithms over globally smooth convex functions, used to gauge tightness of the new bounds.","marker":"[16]"},{"why":"Provides an earlier SDP-based analysis of randomized and cyclic coordinate descent whose interpolation conditions are looser than the new ones.","marker":"[1]"},{"why":"Defines the randomized accelerated coordinate descent algorithm whose cyclic variant (CACD) is analyzed and compared against.","marker":"[9]"},{"why":"Provides a related SDP/Lyapunov approach for random coordinate descent, used as a point of comparison for the PEP-based analysis.","marker":"[26]"}],"fun_headline_variants":["Worst-case CCD: p times slower than full gradient","New bounds cut cyclic descent worst-case gap by 10x","Standard acceleration fails for deterministic cyclic descent","Scale-invariance: CCD worst-case ignores block smoothness ratios","Acceleration in cyclic descent needs randomness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The quantitative comparisons and the CACD slowdown claim rest on the numerical semidefinite programs being solved to their true global optimum, and the paper supplies no code, model files, or solver certificates to verify those optima; the formal theorems about scale invariance, the lower bound, and the descent lemma do not depend on these numerics.","fun_headline_variants_meta":{"raw":{"variants":["Worst-case CCD: p times slower than full gradient","New bounds cut cyclic descent worst-case gap by 10x","Standard acceleration fails for deterministic cyclic descent","Scale-invariance: CCD worst-case ignores block smoothness ratios","Acceleration in cyclic descent needs randomness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000947,"raw_usage":{"total_tokens":4114,"prompt_tokens":1089,"completion_tokens":3025,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":2949}},"tokens_in":705,"tokens_out":3025,"duration_ms":23794,"temperature":1.0,"reasoning_tokens":2949,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:05:43.575562+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's SDP relaxation for, say, two-block CCD with $L=(1,1)$ and $R_i=1$ in an independent solver and compare the objective with the reported bound; a smaller optimum would mean the published curve is not actually an upper bound, while a larger one would mean the reported comparisons used a non-optimal certificate. Separately, computing the worst-case smooth function for full gradient descent, lifting it to $p$ blocks via $\\hat f(x)=f(x^{(1)}+\\cdots+x^{(p)})$, and measuring CCD's normalized performance would directly test Theorem 3.2: any value below $p$ times the full-gradient worst case after $pK$ steps would contradict it.","supporting_citations":[{"cited_title":"On the convergence of block coordinate descent type methods","cited_arxiv_id":null,"evidence_quote":"Supplies the best-known analytical baseline bound for CCD under Setting ALL, which the new numerical bounds are compared against."},{"cited_title":"Shi and R","cited_arxiv_id":null,"evidence_quote":"Contains a prior PEP-derived CCD upper bound that the paper argues contradicts Theorem 3.2 and is therefore incorrect."},{"cited_title":"Hendrickx, and Fran¸ cois Glineur","cited_arxiv_id":null,"evidence_quote":"Supplies previous worst-case lower bounds for BCD algorithms over globally smooth convex functions, used to gauge tightness of the new bounds."},{"cited_title":"Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming","cited_arxiv_id":null,"evidence_quote":"Provides an earlier SDP-based analysis of randomized and cyclic coordinate descent whose interpolation conditions are looser than the new ones."},{"cited_title":"Accelerated, parallel and proximal coordinate de- scent","cited_arxiv_id":null,"evidence_quote":"Defines the randomized accelerated coordinate descent algorithm whose cyclic variant (CACD) is analyzed and compared against."},{"cited_title":"Stochastic first-order methods: Non-asymptotic and computer-aided analyses via potential functions","cited_arxiv_id":null,"evidence_quote":"Provides a related SDP/Lyapunov approach for random coordinate descent, used as a point of comparison for the PEP-based analysis."}],"review_version":1}