Pith. sign in

REVIEW 2 major objections 3 minor 35 references

Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that coordinate descent converges to critical points at sublinear rates for a broad class of nonsmooth nonconvex objectives, with only a few accelerated inner steps per subproblem.

desk verdict Three of the four coordinate-descent results are sound and useful; the advertised ACPDC complexity claim fails because the inner-iteration count is too small by a factor ~sqrt(m), but the flaw is localized and fixable. read the letter →

arxiv 1909.00918 v1 pith:4FXDCSXF submitted 2019-09-03 math.OC cs.LGstat.ML

Qi Deng , Chenghao Lan This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C2690C2590C06
keywords coordinatedescentnonconvexoptimizationdifference-of-convexacceleratedproximalDCalgorithmpointmethodweaklyconvexfunctionssparse
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper develops coordinate descent algorithms for objectives of the form F = f + phi - h, where f is smooth, $\varphi$ is a simple convex separable regularizer, and h is convex and possibly nonsmooth. It claims that four proposed methods—randomized coordinate subgradient descent, randomly permuted coordinate descent, and two ACD-based proximal methods—converge asymptotically to critical points with sublinear rates on natural optimality measures. The headline efficiency claim is that the difference-of-convex variant ACPDC needs only a logarithmic number of accelerated coordinate descent steps per subproblem while retaining O(1/epsilon) outer complexity. If true, this would make coordinate descent provably efficient for large-scale sparse and weakly convex problems where gradient-based DC solvers are slow.

What carries the argument

The central object is the block composite subgradient g_i(x, nabla_i f(x)-v_i, gamma_i) = gamma_i (x_i - P_i(...)), whose norm vanishes exactly at critical points; the paper proves this equivalence in Proposition 1. For the accelerated methods, the engine is APCG, the accelerated randomized proximal coordinate gradient method, applied to the strongly convex surrogate F_k(x) = f(x) + $\varphi$(x) - h(x_k) - <v_k, x-x_k> + (mu/2)||x-x_k||^2_[1]. The prox-mapping p(x,v,mu) = mu sum_i L_i U_i (x_i - xbar_i) then converts subproblem accuracy into an optimality measure, and Theorem 8 shows this measure is quantitatively equivalent to the composite subgradient norm. The contraction factor $\lambda$ = (1 - $\sqrt$(mutilde/m))^t of APCG is the quantity the proof needs to keep small per outer iteration.

What would settle it

Evaluate $\lambda$ = (1 - $\sqrt$(mutilde/m))^{t0} with mutilde = mu/(1+mu) and t0 = ceil(ln(4m)/$\sqrt$(mutilde)). For m = $10^{6}$ and mu = 1, $\lambda$ is approximately exp(-ln(4*$10^{6}$)/1000) = 0.985, far above the 1/4 threshold used in the proof of Theorem 9; this directly shows the stated inner-iteration count does not establish the descent inequality E[F_k(x_{k+1})] <= F_k(x_k) - (1-2lambda)[F_k(x_k) - F_k(x_{k+1}^*)] on which the outer O(1/epsilon) rate rests.

Watch

Extended reading notes

Core claim

At the center of the paper is the claim that the structure F = f + phi - h can be exploited coordinate-by-coordinate even when h is convex but nonsmooth and nonseparable. For the first two algorithms, RCSD and RPCD, the paper shows asymptotic convergence to critical points and sublinear convergence of a composite subgradient measure. For ACPDC, each DC subproblem is solved inexactly by APCG, and the paper claims that t0 = ceil(ln(4m)/$\sqrt$(mu/(1+mu))) inner iterations suffice: the outer sequence then converges almost surely to critical points and finds a point with E||p(x_k,v_k,mu)||^2 <= epsilon in O(1/epsilon) outer iterations. For weakly convex objectives, ACPP is claimed to attain complexity improving on ordinary coordinate descent by a factor related to $\sqrt$(L/mu) when the condition ratio L_i/mu is large. The accompanying experiments on logistic loss with largest-k norm penalty and smoothed $\ell^1$ with SCAD penalty show ACPDC and ACPP converging faster in objective value than proximal DC with extrapolation.

Load-bearing premise

The load-bearing assumption is that after t0 = ceil(ln(4m)/sqrt(mu/(1+mu))) accelerated-coordinate iterations the error contraction factor lambda stays at or below 1/4; with that t0, lambda is approximately exp(-ln(4m)/sqrt(m)), which exceeds 1/2 for large m, so the descent inequality feeding the supermartingale argument no longer holds.

Editorial extensions

If this is right

  • RCSD covers nonseparable, nonsmooth concave penalties such as the largest-k norm in Problem (63), which earlier nonconvex coordinate descent methods cannot handle.
  • ACPDC, per the paper, needs only t0 = ceil(ln(4m)/sqrt(mu/(1+mu))) ACD iterations per DC subproblem while keeping O(1/epsilon) outer complexity, so the per-iteration cost is much lower than exact DC solvers.
  • ACPP yields a block-gradient complexity roughly (sum sqrt(L_i)) sqrt(mu) log(L/mu) for ill-conditioned weakly convex problems, improving on the O((sum L_i)/epsilon) rate of ordinary randomized coordinate descent when L_i >> mu.
  • The paper's optimality measures—composite subgradient norm and prox-mapping norm—are shown in Theorem 8 to be equivalent up to constants, so convergence in one measure implies convergence in the other.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit that ||p(x_k,v_k,mu)||_[1],* could serve as a practical stopping rule for coordinate descent on DC problems, since Theorem 8 shows it is within constant factors of the composite subgradient norm.
  • The numerical gap in Theorem 9 is not discussed in the paper: with the stated t0, lambda > 1/4 for large m, so the O(log m) per-subproblem complexity in Remark 10 does not follow; a repaired argument would need a sharper APCG bound or a larger t0.
  • A testable extension is that ACPDC's relative advantage over proximal-gradient DC should widen as delta -> 0 in the Huber-smoothed l1 experiments, because the condition ratio L/mu grows.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper proposes four coordinate descent-type methods for minimizing structured nonconvex objectives of the form F(x)=f(x)+φ(x)-h(x), where f is smooth, φ is convex separable, and h is convex (possibly nonsmooth and inseparable). The methods are RCSD (randomized coordinate subgradient descent), RPCD (randomly permuted coordinate descent), ACPDC (an ACD-based proximal DC algorithm), and ACPP (an ACD-based proximal point method for weakly convex problems). For each method the paper claims asymptotic convergence to critical points and sublinear complexity with respect to a tailored optimality measure, and it reports experiments on sparse learning problems showing favorable performance of the CD methods relative to gradient-based baselines.

Significance. If all results were correct, the paper would make a useful contribution by extending coordinate descent to a broad class of nonsmooth, nonconvex, nonseparable problems and by introducing acceleration into DC subproblems. The equivalence result for optimality measures in Theorem 8 and the careful treatment of block-wise Lipschitz constants are valuable elements. The experimental study is also informative. However, two load-bearing proof issues prevent acceptance in the current form: the ACPDC inner-iteration count is quantitatively inconsistent with the APCG contraction used in the proof, and the RPCD convergence proof relies on a false identity. Both are local and appear fixable, but they affect central claims, so the manuscript needs a major revision.

major comments (2)
  1. [§5, Theorem 9 and Remark 10] The inner-iteration count t0 = ceil( ln(4m) / sqrt( mu/(1+mu) ) ) is too small to supply the contraction used in the proof. In the proof of Theorem 9, λ is defined as (1 - sqrt(μ̃/m))^t, and the argument requires λ ≤ 1/4 to keep 1 - 2λ positive in equations (36)-(38). The proof asserts λ ≤ exp(-t sqrt(μ̃)/m), but the correct bound from (1-x)^t ≤ e^{-xt} with x = sqrt(μ̃/m) is λ ≤ exp(-t sqrt(μ̃/m)) = exp(-t sqrt(μ̃)/sqrt(m)). With the stated t0 this gives λ ≳ exp(-ln(4m)/sqrt(m)), which is about 0.9 for m = 10^4 and approaches 1 as m grows, not ≤ 1/4. Consequently the supermartingale/descent argument and the complexity estimate in Theorem 9 and Remark 10 are not established. A valid choice is t0 = Θ(sqrt(m/μ̃) ln(m)), which changes the total block-gradient complexity in Remark 10 from O(ln(m) · μ/ε) to O(sqrt(m/μ̃) ln(m) · μ/ε) and contradicts the advertised claim that only 'a few' ACD iterations are needed per DC subproblem.
  2. [§4, proof of Theorem 5, after Eq. (21)] The proof defines y^{t+1} as the simultaneous block-proximal point argmin_x { <∇f( x̃^t ) - v^k, x> + φ(x) + Σ_i (γ_i/2) ||x_i - x̃^t_i||^2_i } and then states 'Notice that y^m = x^{k+1}'. This identity is false for m > 1: x^{k+1} is produced by sequential coordinate updates, each block using the gradient at a different x̃^t, whereas y^m is the full coordinate-wise proximal point at the single point x̃^{m-1} with the single gradient ∇f(x̃^{m-1}). The subsequent use of (21) at t = m-1 to conclude limsup_k φ(x^{k+1}) ≤ φ(x̄) is therefore unjustified. This is load-bearing for the asymptotic convergence claim in Theorem 5(1). A repair would require an additional estimate controlling ||y^m - x^{k+1}|| in terms of ||x^{k+1} - x^k|| (for instance via block Lipschitz smoothness and stability of the proximal map), which is not present in the proof.
minor comments (3)
  1. [§2 and §4-§6] The global constant L is used in Theorem 5(2), Theorem 8, and Theorem 13, but it is never defined in Section 2. Please state explicitly that L is the global Lipschitz constant of ∇f, e.g., L = sqrt( Σ_i L_i^2 ), and use a different symbol or define L clearly to avoid confusion with the block constants L_i.
  2. [§4, proof of Theorem 5] The sentence 'Due to the convexity of F̃(x)' is not the correct justification for F̃(x) ≥ F(x); the inequality follows from convexity of h via -h(x^k) - <v^k, x - x^k> ≥ -h(x). The wording should be corrected so the proof does not appear to assume convexity of f.
  3. [§7.2, parameter setting] The sentence 'For both ACPDC and ACPP, we choose t from the range [m, t0]' is inconsistent with the stated theoretical values of t0, since for the datasets used (e.g., m = 10000) the theoretical t0 is far smaller than m. Please clarify the intended search range and how t0 is defined in the experiments.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the paper's convergence results are derived from stated assumptions and externally cited APCG/RCD results, not from its own conclusions.

full rationale

No circular step is present in the manuscript. The algorithms RCSD, RPCD, ACPDC, and ACPP are analyzed from explicit assumptions on f, phi, and h, with convergence inherited from independent external results such as the APCG contraction bound (Theorem 7, cited from [21]) and the RCD framework (cited from [25]). The optimality measures g and p are defined in-paper as structural quantities, not fitted parameters renamed as predictions. The inner-iteration count t0 in Theorem 9 and Remark 10 is proposed as a theoretical choice, not calibrated to the target convergence measures. There is also no load-bearing self-citation chain: the authors do not rely on their own prior results to force the conclusions. The main concern raised about Theorem 9 is a possible algebraic error in the bound on lambda, but that is a correctness or rigor issue, not circularity, because the offending inequality is a mis-evaluation of an external contraction estimate rather than a definitional equivalence between an input and an output.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The theoretical results contain no free parameters fitted to data; the listed parameters are the problem-class assumptions and standard algorithmic inputs. The experimental mu and t are manual tuning choices. The ACPDC analysis leans on the quoted APCG rate, which is external but appears misapplied.

free parameters (2)
  • mu in ACPDC experiments = 0.01
    Section 7.2 sets mu=0.01 for ACPDC because it consistently yields good performance; the weak convexity constant of the objective is not derived.
  • t in ACPDC/ACPP experiments = range [m, t0]
    The number of inner ACD iterations is tuned in Section 7.2 rather than set by the theorem.
assumptions (7)
  • domain assumption f is block-wise Lipschitz smooth (Assumption 1)
    Used in the descent lemmas for RCSD, RPCD, ACPDC, and ACPP.
  • domain assumption phi is convex, block-separable, with simple proximal mappings (Assumption 2)
    Required for the block proximal updates in Algorithms 1, 2, and 5.
  • domain assumption h is convex continuous (Assumption 3)
    Used to linearize the concave part and to bound subgradients.
  • domain assumption F is level-bounded and attains a finite minimum (Assumptions 4-5)
    Used to guarantee boundedness of iterates and a finite function gap.
  • domain assumption For ACPDC, f is convex and sup_{v in dh(x)} ||v|| <= M (Theorem 9)
    The convexity of f is assumed for simplicity before Algorithm 3; the bounded subgradient condition is explicit in Theorem 9 and used in the finite complexity bound.
  • domain assumption For ACPP, f is mu-weakly convex and h is void (Section 6)
    The proximal point analysis relies on the weak convexity inequality (42) and the strong convexity of the subproblem F_k.
  • standard math APCG convergence rate from [21] as restated in Theorem 7
    Used to bound the inner subproblem error; the restated rate (1 - sqrt(mut/m))^K is the source of the t0 inconsistency.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization." pith.science (2026). https://pith.science/paper/4FXDCSXF

@misc{pith2026190900918,
  author       = {Pith},
  title        = {Pith review of: Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4FXDCSXF}},
  note         = {Machine review of arXiv:1909.00918}
}
read the original abstract

Novel coordinate descent (CD) methods are proposed for minimizing nonconvex functions consisting of three terms: (i) a continuously differentiable term, (ii) a simple convex term, and (iii) a concave and continuous term. First, by extending randomized CD to nonsmooth nonconvex settings, we develop a coordinate subgradient method that randomly updates block-coordinate variables by using block composite subgradient mapping. This method converges asymptotically to critical points with proven sublinear convergence rate for certain optimality measures. Second, we develop a randomly permuted CD method with two alternating steps: linearizing the concave part and cycling through variables. We prove asymptotic convergence to critical points and sublinear complexity rate for objectives with both smooth and concave parts. Third, we extend accelerated coordinate descent (ACD) to nonsmooth and nonconvex optimization to develop a novel randomized proximal DC algorithm whereby we solve the subproblem inexactly by ACD. Convergence is guaranteed with at most a few number of ACD iterations for each DC subproblem, and convergence complexity is established for identification of some approximate critical points. Fourth, we further develop the third method to minimize certain ill-conditioned nonconvex functions: weakly convex functions with high Lipschitz constant to negative curvature ratios. We show that, under specific criteria, the ACD-based randomized method has superior complexity compared to conventional gradient methods. Finally, an empirical study on sparsity-inducing learning models demonstrates that CD methods are superior to gradient-based methods for certain large-scale problems.

Figures

Figures reproduced from arXiv: 1909.00918 by the authors.

Figure 1
Figure 1. Experimental results on logistic loss classification with largest- [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Experimental results on smoothed l1 regression with SCAD penalty. y-axis: objective value (log scaled). x-axis: number of passes to the dataset. Test datasets (from top to bottom): synthetic, E2006-tfidf and UJIndoorLoc and E2006-log1p. Meanwhile, we observe that, CD methods still perform consistently better than gradient-based methods, and pDCAe performs consistently better than pDCA. Moreover, we find that both AC… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages

  1. [16]

    L. T. K. Hien, N. Gillis, and P. Patrinos , Inertial block mirror descent method for non-convex non- smooth optimization, arXiv preprint arXiv:1903.01818, (2019)

    work page Pith review arXiv 2019

  2. [25]

    Patrascu and I

    A. Patrascu and I. Necoara , Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization, J. Glob. Optim., 61 (2015), pp. 19–46

    work page 2015

  3. [1]

    Allen-Zhu, Z

    Z. Allen-Zhu, Z. Qu, P. Richtárik, and Y. Yuan , Even faster accelerated coordinate descent using non-uniform sampling, Int. Conf. on Mach. Learn., (2016), pp. 1110–1119

    work page 2016

  4. [2]

    N. T. An and N. M. Nam , Convergence analysis of a proximal point algorithm for minimizing differences of functions, Optimization, 66 (2017), pp. 129–147

    work page 2017

  5. [3]

    Beck and N

    A. Beck and N. Hallak , Optimization problems involving group sparsity terms, Math. Program., (2018), pp. 1–29

    work page 2018

  6. [4]

    Beck and L

    A. Beck and L. Tetruashvili , On the convergence of block coordinate descent type methods, SIAM J. on Optim., 23 (2013), pp. 2037–2060

    work page 2013

  7. [5]

    Accelerated Methods for Non-Convex Optimization

    Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford , Accelerated methods for non-convex optimization, arXiv preprint arXiv:1611.00756, (2016). 24

    work page Pith review arXiv 2016

  8. [6]

    Chang and C.-J

    C.-C. Chang and C.-J. Lin , LIBSVM: A library for support vector machines, ACM Trans. on Intell. Syst. Technol., 2 (2011), pp. 27:1–27:27. Software available athttp://www.csie.ntu.edu.tw/~cjlin/libsvm

    work page 2011

Show all 35 references
  1. [7]

    C. D. Dang and G. Lan , Stochastic block mirror descent methods for nonsmooth and stochastic optimiza- tion, SIAM J. on Optim., 25 (2015), pp. 856–881

    2015

  2. [8]

    Da vis and B

    D. Da vis and B. Grimmer , Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems, SIAM J. on Optim., 29 (2019), pp. 1908–1930

    2019

  3. [9]

    Drusvyatskiy and C

    D. Drusvyatskiy and C. Paquette , Efficiency of minimizing compositions of convex functions and smooth maps, Math. Program., (2018), pp. 1–56

    2018

  4. [10]

    Dua and C

    D. Dua and C. Graff , UCI machine learning repository, 2017

    2017

  5. [11]

    J. C. Duchi and F. Ruan , Stochastic methods for composite and weakly convex optimization problems, SIAM J. on Optim., 28 (2018), pp. 3229–3259

    2018

  6. [12]

    F an and R

    J. F an and R. Li , Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96 (2001), pp. 1348–1360

    2001

  7. [13]

    Ghadimi and G

    S. Ghadimi and G. Lan , Stochastic first-and zeroth-order methods for nonconvex stochastic programming, SIAM J. on Optim., 23 (2013), pp. 2341–2368

    2013

  8. [14]

    Program., 156 (2016), pp

    , Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156 (2016), pp. 59–99

    2016

  9. [15]

    P. Gong, C. Zhang, Z. Lu, J. Z. Huang, and J. Ye , A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems, Int. Conf. on Mach. Learn., 28 (2013), pp. 37–45

    2013

  10. [17]

    M. Hong, M. Raza viyayn, Z. Q. Luo, and J. S. Pang , A unified algorithmic framework for block- structured optimization involving big data: With applications in machine learning and signal processing, IEEE Signal Process. Mag., 33 (2016), pp. 57–77

    2016

  11. [18]

    Khamaru and M

    K. Khamaru and M. J. W ainwright , Convergence guarantees for a class of non-convex and non-smooth optimization problems, Int. Conf. on Mach. Learn., (2018), pp. 2606–2615

    2018

  12. [19]

    W. Kong, J. G. Melo, and R. D. Monteiro , Complexity of a quadratic penalty accelerated inex- act proximal point method for solving linearly constrained nonconvex composite programs, arXiv preprint arXiv:1802.03504, (2018)

    2018 arXiv

  13. [20]

    Lan and Y

    G. Lan and Y. Yang , Accelerated stochastic algorithms for nonconvex finite-sum and multi-block optimiza- tion, arXiv preprint arXiv:1805.05411, (2018)

    2018 arXiv

  14. [21]

    Q. Lin, Z. Lu, and L. Xiao , An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization, SIAM J. on Optim., 25 (2015), pp. 2244–2273

    2015

  15. [22]

    Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J

    Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. on Optim., 22 (2012), pp. 341–362

    2012

  16. [23]

    Nesterov and S

    Y. Nesterov and S. U. Stich , Efficiency of accelerated coordinate descent method on structured opti- mization problems, SIAM J. on Optim., 27 (2017), pp. 110–123

    2017

  17. [24]

    Nouiehed, J.-S

    M. Nouiehed, J.-S. Pang, and M. Raza viyayn , On the pervasiveness of difference-convexity in opti- mization and statistics, Math. Program., (2018), pp. 1–28

    2018

  18. [26]

    Richtarik and M

    P. Richtarik and M. Takac , Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144 (2014), pp. 1–38. 25

    2014

  19. [27]

    Richtarik and M

    P. Richtarik and M. Takac , Parallel coordinate descent methods for big data optimization, Math. Pro- gram., 156 (2016), pp. 433–484

    2016

  20. [28]

    H. A. L. Thi and T. P. Dinh , Dc programming and dca: thirty years of developments, Math. Program., 169 (2018), pp. 5–68

    2018

  21. [29]

    H. L. Thi, T. P. Dinh, H. Le, and X. Vo , DC approximation approaches for sparse optimization, Eur. J. Oper. Res., 244 (2015), pp. 26–46

    2015

  22. [30]

    B. Wen, X. Chen, and T. K. Pong , A proximal difference-of-convex algorithm with extrapolation, Com- put. Optim. Appl., 69 (2018), pp. 297–324

    2018

  23. [31]

    Y. Xu, Q. Qi, Q. Lin, R. Jin, and T. Yang , Stochastic optimization for dc functions and non-smooth non-convex regularizers with non-asymptotic convergence, arXiv preprint arXiv:1811.11829, (2018)

    2018 arXiv

  24. [32]

    Xu and W

    Y. Xu and W. Yin , A globally convergent algorithm for nonconvex optimization based on block coordinate update, J. Sci. Comput., 72 (2017), pp. 700–734

    2017

  25. [33]

    ya Gotoh, A

    J. ya Gotoh, A. Takeda, and K. Tono , DC formulations and algorithms for sparse optimization prob- lems, Math. Program., 169 (2018), pp. 141–176

    2018

  26. [34]

    A. L. Yuille and A. Rangarajan , The concave-convex procedure (CCCP), in Advances in Neural Infor- mation Processing Systems 14, 2002, pp. 1033–1040

    2002

  27. [35]

    Zhang and T

    C.-H. Zhang and T. Zhang , A general theory of concave regularization for high-dimensional sparse esti- mation problems, Stat. Sci., 27 (2012), pp. 576–593. 26

    2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.