{"id":"489a93d8-a8f3-475e-a17e-caf086597b26","arxiv_id":"1909.00918","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper proves sublinear rates for coordinate subgradient descent, randomly permuted coordinate descent, and accelerated proximal point methods on structured nonconvex problems, but the accelerated DC method's inner-iteration complexity is not supported by the paper's own equations.","lead":"This paper designs coordinate descent algorithms for nonconvex optimization problems that combine a smooth term, a convex term, and a concave term, and proves convergence rates. The results matter for large-scale sparse learning, but one headline efficiency claim for the accelerated method is internally inconsistent.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ACPDC inner-iteration count t0 in Theorem 9 is too small by a factor ~sqrt(m); with the stated t0 the contraction λ is ~0.9, so the O(log m) complexity claim fails.","rationale":"The reader identified exactly the load-bearing weakness: Theorem 9 states t0 = ceil(ln(4m)/sqrt(~µ)), but the proof needs λ ≤ 1/4 and the displayed exponential bound is algebraically wrong. One small correction: using the correct APCG rate, the required t0 is Θ(sqrt(m/~µ) ln(1/λ)), not Θ(m/sqrt(~µ)); either way it is polynomial in m, so the advertised O(ln m) inner complexity and 'few ACD iterations' claim fail. This is a genuine correctness gap in the headline ACPDC contribution, and it is specific and fixable: replacing t0 with the correct expression restores the descent argument, at the price of a worse complexity bound. Because the paper also contains the sound RCSD, RPCD, and ACPP results, the overall verdict of CONDITIONAL remains appropriate: acceptance should require the authors to correct Theorem 9 and Remark 10 and restate the complexity honestly. No verdict change from the reader is needed.","tokens_in":29387,"tokens_out":8112,"duration_ms":70258,"concrete_test":"Set m = 10^4 and µ = 0.01, so ~µ = µ/(1+µ) ≈ 0.0099 and t0 = ceil(ln(4·10^4)/sqrt(~µ)) ≈ 107. Compute λ = (1 − sqrt(~µ/m))^{t0} = (1 − 0.000995)^{107} ≈ 0.899, which violates the λ ≤ 1/4 requirement used in equations (36)–(38) of Theorem 9. Then compute the smallest t with λ ≤ 1/4, approximately t ≥ (ln 4)/sqrt(~µ/m) ≈ 1394, and verify that with λ = 0.899 the factor (1 − 2λ) is negative, so the proof's descent inequality and the final K^{-1} bound fail. Updating Remark 10 with this corrected t removes the claimed O(log m) inner complexity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing flaw is in Theorem 9/Remark 10 of Section 5. The proof requires λ = (1 − sqrt(~µ/m))^{t0} ≤ 1/4 to keep (1 − 2λ) positive in equations (36)–(38) and to make the supermartingale/descent argument valid. With the stated t0 = ceil(ln(4m)/sqrt(~µ)) and ~µ = µ/(1+µ), λ is at most exp(−ln(4m)/sqrt(m)) = (4m)^{-1/sqrt(m)}, which is approximately 0.9 for m = 10^4 and approaches 1 as m grows; it is far above 1/4. The proof's line 'λ ≤ exp(−(t sqrt(~µ))/m) ≤ 1/4' uses the wrong exponent: the correct APCG contraction from Theorem 7 gives exp(−t sqrt(~µ/m)) = exp(−t sqrt(~µ)/sqrt(m)). Therefore the condition λ ≤ 1/4 requires t0 ≥ sqrt(m/~µ) ln 4 (and the paper's own incorrect inequality would require the even larger t0 ≥ (m ln 4)/sqrt(~µ)). Either way, the claimed 'at most a few ACD iterations' and the O(ln m) inner complexity in Remark 10 are unsupported: the corrected t0 grows polynomially in m, changing the total block-gradient complexity from O(ln m · µ/ε) to at least O(sqrt(m/µ) · µ/ε) or worse. The RCSD, RPCD, and ACPP results are not affected by this flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":29681,"tokens_out":20788,"duration_ms":199939,"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":[{"comment":"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.","section":"§5, Theorem 9 and Remark 10"},{"comment":"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.","section":"§4, proof of Theorem 5, after Eq. (21)"}],"minor_comments":[{"comment":"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.","section":"§2 and §4-§6"},{"comment":"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.","section":"§4, proof of Theorem 5"},{"comment":"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.","section":"§7.2, parameter setting"}],"recommendation":"major_revision","confidential_remarks":"The two major issues appear local and fixable rather than fatal: the ACPDC theorem can be repaired by enlarging t0 at the price of a worse (polynomial in m) inner-iteration bound, and the RPCD proof can likely be repaired with a perturbation estimate. However, the corrected ACPDC complexity is substantially weaker than the headline 'few ACD iterations' claim, so the authors should be asked to restate the contribution precisely. The manuscript does not show circular reasoning or reliance on its own conclusions; the problems are internal to the proofs of Sections 4 and 5."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has three solid, genuinely useful results—RCSD, RPCD, and ACPP—and one headline result, ACPDC, whose stated complexity does not follow from the proof. The flaw is specific and fixable, but it is load-bearing for the abstract's central promise.\n\nWhat's new: first complexity guarantees for coordinate descent on min f + phi - h with h convex continuous but nonsmooth and inseparable, extending Patrascu-Necoara and the DC literature. RCSD handles nonuniform sampling and gives sublinear rates; RPCD gives a deterministic sublinear rate for the smooth phi=0 case; ACPP gives a cleaner complexity for ill-conditioned weakly convex problems. The proofs for these three appear coherent, the optimality measures are natural, and the literature gaps versus [16] and [25] are real.\n\nWhere it breaks: Theorem 9 and Remark 10. The APCG contraction is (1 - sqrt(tilde_mu/m))^t; the proof bounds it by exp(-(t sqrt(tilde_mu))/m), which is wrong by a factor sqrt(m). With the stated t0 = ln(4m)/sqrt(tilde_mu), lambda is about (4m)^(-1/sqrt(m)), which approaches 1 for large m and is nowhere near 1/4. The descent argument and supermartingale step require lambda <= 1/4. Correcting the contraction gives t0 = Theta(sqrt(m/mu) ln 4) (or worse), so the \"few ACD iterations\" claim and the O(ln m) inner complexity are unsupported. The algorithm with a larger t may work—the structure of the proof is plausible—but the theorem as written does not go through.\n\nMinor: experiments are illustrative rather than conclusive; no code, no error bars, and mu and t are tuned. That is okay for a theory paper, but the empirical claims should be read as suggestive.\n\nBottom line: a serious referee should engage. Keep RCSD, RPCD, ACPP; ask for a corrected ACPDC iteration count, a revised complexity (likely Theta(sqrt(m/mu)) inner iterations), and a clear statement about what remains of Remark 10.","headline":"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.","tokens_in":30261,"tokens_out":3719,"would_cite":true,"duration_ms":37211,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C25","90C06"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["coordinate descent","nonconvex optimization","difference-of-convex optimization","accelerated coordinate descent","proximal DC algorithm","proximal point method","weakly convex functions","sparse optimization"],"falsifier":"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.","tokens_in":29115,"feed_emoji":"📉","tokens_out":10658,"duration_ms":101084,"temperature":0.7,"pith_summary":"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.","feed_headline":"Nonconvex DC subproblems solved with only a few accelerated steps","feed_subtitle":"New coordinate descent variants converge to critical points and beat gradient-based DC solvers on large sparse problems.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the APCG method whose contraction rate (Theorem 7) is the inner-loop engine of ACPDC and ACPP.","marker":"[21]"},{"why":"Defines 1-RCD, the nonconvex randomized coordinate descent that RCSD generalizes and whose sublinear rate is recovered as a special case.","marker":"[25]"},{"why":"Supplies DC formulations for sparse optimization, including the largest-k norm penalty used as the paper's main application.","marker":"[33]"},{"why":"Gives the proximal DC algorithm with extrapolation that serves as a state-of-the-art gradient-based baseline in the experiments.","marker":"[30]"},{"why":"Introduces the proximal DC algorithm and the synthetic data generation procedure used in the empirical study.","marker":"[18]"},{"why":"Provides the (epsilon, delta)-approximate stationarity criterion adopted in the ACPP analysis.","marker":"[20]"}],"fun_headline_variants":["Coordinate descent outperforms gradients on large nonconvex sparse learning","Few accelerated steps per DC subproblem speed up nonconvex CD","Randomized CD converges to critical points on nonsmooth nonconvex sums","New CD methods outperform gradient-based solvers on nonconvex DC"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Coordinate descent outperforms gradients on large nonconvex sparse learning","Few accelerated steps per DC subproblem speed up nonconvex CD","Randomized CD converges to critical points on nonsmooth nonconvex sums","New CD methods outperform gradient-based solvers on nonconvex DC"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001875,"raw_usage":{"total_tokens":7410,"prompt_tokens":1050,"completion_tokens":6360,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":6285}},"tokens_in":666,"tokens_out":6360,"duration_ms":165205,"temperature":1.0,"reasoning_tokens":6285,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:33:55.716935+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the APCG method whose contraction rate (Theorem 7) is the inner-loop engine of ACPDC and ACPP."},{"cited_title":"Patrascu and I","cited_arxiv_id":null,"evidence_quote":"Defines 1-RCD, the nonconvex randomized coordinate descent that RCSD generalizes and whose sublinear rate is recovered as a special case."},{"cited_title":"ya Gotoh, A","cited_arxiv_id":null,"evidence_quote":"Supplies DC formulations for sparse optimization, including the largest-k norm penalty used as the paper's main application."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the proximal DC algorithm with extrapolation that serves as a state-of-the-art gradient-based baseline in the experiments."},{"cited_title":"Khamaru and M","cited_arxiv_id":null,"evidence_quote":"Introduces the proximal DC algorithm and the synthetic data generation procedure used in the empirical study."},{"cited_title":"Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization","cited_arxiv_id":"1805.05411","evidence_quote":"Provides the (epsilon, delta)-approximate stationarity criterion adopted in the ACPP analysis."}],"review_version":1}