REVIEW 4 major objections 5 minor 1 cited by
On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (4)
- [Section 4.1–4.7] 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.
- [Theorem 2.4 / Appendix A.3] 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 4.7] 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.
- [Theorem 4.1, Section 4.3] 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.
minor comments (5)
- [Abstract / Section 4.2] 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 2.3 / Introduction] 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.
- [Appendix A.2] 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 4.2] 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.
- [Throughout] 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.
Circularity Check
No circularity: the central formal results are independently proven, and the numerical bounds are model outputs rather than fitted targets; missing solver certificates is a reproducibility issue, not circularity.
full rationale
The paper's derivation chain is not circular. The functional-class equivalence in Theorem 2.2 is proven constructively in Appendix A.2 via Fenchel conjugation, and Theorem 2.4 explicitly identifies the interpolation conditions (6) as necessary but not sufficient for sets of cardinality at least 3; the text then correctly labels (R-PEP-coord) as a relaxation and states that its optimal value provides an upper bound on the true worst-case. That statement is logically correct for the exact SDP optimum, and it is not a self-referential definition of the claimed bound. The formal results in Section 3 are supported by independent proofs: Theorem 3.1 uses an explicit rescaling construction, Theorem 3.2 builds a function f_hat(x) = f(sum of blocks) to realize the p-fold slowdown, and Lemma 3.1 / Theorem 3.3 are algebraic consequences of the previously established inequalities. Self-citations to the authors' prior work [16] appear only as comparisons (Figures 1, 2, and Sections 4.2, 4.6) and are not load-bearing: the new lower bound in Theorem 3.2 is proved directly, not imported from [16]. The numerical 'PEP upper bounds' are outputs of well-defined SDP relaxation models rather than quantities fitted to the target rates, so they are not circular by construction; the real limitation is that the paper gives no solver certificates, code, or dual-feasibility guarantees, so a reader cannot verify that the plotted primal SDP values equal the relaxation optima. That concern is about computational verifiability and global optimality, not about circularity. Overall, the paper's derivation chain stands independently of its own conclusions, and no circular step can be exhibited.
Assumptions & free parameters
assumptions (5)
- standard math Fenchel duality and Young's inequality for proper closed convex functions
- domain assumption The functional class F_coord_0,L is defined via block-wise Lipschitz partial gradients plus convexity
- standard math Existence and attainability of worst-case functions for gradient descent on smooth convex functions
- ad hoc to paper The adapted proof of Theorem 2.1 from [3] remains valid under the modified initial condition Ra
- ad hoc to paper The linear extrapolation from PEP upper bounds for K up to 50 predicts the asymptotic O(1/K) rate under Setting INIT
Cite this review
Pith. "Pith review of On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms." pith.science (2026). https://pith.science/paper/P5RW2OWM
@misc{pith2026250716675,
author = {Pith},
title = {Pith review of: On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms},
year = {2026},
howpublished = {\url{https://pith.science/paper/P5RW2OWM}},
note = {Machine review of arXiv:2507.16675}
}
read the original abstract
We study the worst-case behavior of Block Coordinate Descent (BCD) type algorithms for unconstrained minimization of coordinate-wise smooth convex functions. This behavior is indeed not completely understood, and the practical success of these algorithms is not fully explained by current convergence analyses. We extend the recently proposed Performance Estimation Problem (PEP) approach to convex coordinate-wise smooth functions by proposing necessary interpolation conditions. We then exploit this to obtain improved numerical upper bounds on the worst-case convergence rate of three different BCD algorithms, namely Cyclic Coordinate Descent (CCD), Alternating Minimization (AM), and a Cyclic version of the Random Accelerated Coordinate Descent introduced in Fercoq and Richt\'arik (2015) (CACD), substantially outperforming the best current bounds in some situations. In addition, we show the convergence of the CCD algorithm with more natural assumptions in the context of convex optimization than those typically made in the literature. Our methodology uncovers a number of phenomena, some of which can be formally established. These include a scale-invariance property of the worst case of CCD with respect to the coordinate-wise smoothness constants and a lower bound on the worst-case performance of CCD which is equal to the number of blocks times the worst-case of full gradient descent over the class of smooth convex functions. We also adapt our framework to the analysis of random BCD algorithms, and present numerical results showing that the standard acceleration scheme in Fercoq and Richt\'arik (2015) appears to be inefficient for deterministic algorithms.
Figures
Figures from the paper (4 more)
Forward citations
Cited by 1 Pith paper
-
A constructive approach to strengthen algebraic descriptions of function and operator classes
A constructive one-point strengthening procedure derives stricter, often semidefinite-representable necessary conditions for extending functions and operators from finite data.
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.