A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs

Yancheng Yuan; Zhangcheng Feng

REVIEW 3 major objections 4 minor 2 references

A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs

T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read Randomly perturbing the linearization point lets a single-subproblem algorithm compute d-stationary points of nonsmooth difference-of-convex programs.

desk verdict Clever perturbation idea and solid numerics, but the main convergence theorem rests on an unproved o(alpha_k) rate condition and the abstract advertises a hybrid variant that the paper never delivers. read the letter →

arxiv 2601.02084 v3 pith:GS2XDNRB submitted 2026-01-05 math.OC

Zhangcheng Feng , Yancheng Yuan This is my paper · ORCID

classification math.OC MSC 90C2690C1565K05

keywords difference-of-convexprogrammingd-stationarypointrandomperturbationnonsmoothoptimizationnonconvexalmostsureconvergenceK-sparseregularizationK-mediansclustering

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

This paper proposes a perturbed difference-of-convex algorithm (pDCA) for nonsmooth DC programs ζ = φ − ψ, where ψ is a pointwise maximum of smooth convex functions. The goal is to compute d-stationary points—the strongest local optimality notion for this problem class—rather than just critical points. The central idea is to linearize ψ at a randomly perturbed point x̂_k = x_k + α_k ξ_k: by Rademacher's theorem the active gradient at x̂_k is a singleton almost surely, so the update requires solving only one strongly convex subproblem per iteration. Under bounded-level-set, smoothness, and exposed-direction assumptions, the paper proves that every cluster point of the iterates is a d-stationary point almost surely. This matters because it offers the sharper d-stationary guarantee at a per-iteration cost comparable to the classical DCA, with numerical evidence on sparse regression and K-medians clustering.

What carries the argument

The key mechanism is the random perturbation e_k = α_k ξ_k with ξ_k uniform on the unit sphere and α_k > 0 such that Σ α_k² < ∞. Linearizing ψ at x̂_k = x_k + e_k yields a unique active gradient g_k almost surely, making the subproblem a single strongly convex minimization. Lemma 2 provides a uniform lower bound on the conditional probability that a given active gradient at a cluster point is selected, using the exposed-direction sets A*_i of Assumption 4; the Borel–Cantelli lemma then guarantees that every active index is selected infinitely often, so the limit of the optimality conditions implies d-stationarity.

What would settle it

Run Algorithm 3 on the one-dimensional example ζ(x) = x²/2 − max{−x,0} with α_k = 1/k and a deterministic perturbation rule that always moves away from the d-stationary point. Record, along the subsequence converging to the cluster point, the ratio ∥x_k − x*∥/α_k. If this ratio stays bounded below by a positive constant on every infinite subsequence, the hypothesis of Lemma 2 is violated; observing whether the algorithm still converges to a d-stationary point would show whether the theorem's condition is a genuine gap or merely a proof artifact.

Watch

Extended reading notes

Core claim

The paper's central claim is that random perturbation of the linearization point makes the nonsmooth maximum structure of ψ harmless: at almost every perturbed point the set of active gradients contains a single element, so the algorithm never has to solve the multiple subproblems required by the earlier revised DCA. Theorem 1 states that, under Assumptions 1–4 plus the additional subsequence condition in Lemma 2, every cluster point of the sequence generated by Algorithm 3 is a d-stationary point of ζ almost surely. The proof works by showing that each active gradient at a cluster point is selected with probability at least p_min > 0 infinitely often, which forces the limiting optimality co

Load-bearing premise

The d-stationarity proof relies on an unproved rate condition: along some infinite subsequence converging to a cluster point, the iterates must approach it much faster than the perturbation radius shrinks (∥x_k − x*∥ = o(α_k)); Assumptions 1–4 do not guarantee this, and without it Lemma 2's uniform selection-probability bound—and hence Theorem 1—does not follow.

Editorial extensions

If this is right

pDCA solves one strongly convex subproblem per iteration, so its per-iteration cost is comparable to the classical DCA while targeting a stronger stationarity concept than critical points.
When ψ is piecewise affine, the d-stationary points it finds are local minimizers of the original DC program, not merely points where subgradients intersect.
The algorithm can escape non-stationary critical points, as shown on the one-dimensional example where DCA is trapped at x=0 while pDCA reaches the d-stationary point x=−1.
On K-sparse regularized regression and K-medians clustering, the numerical results show that pDCA recovers the desired sparsity or clustering structure and drives the d-stationarity residual R(·) to zero, often in far fewer subproblems than Algorithm 2.

Reading between the lines

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

The proof of Theorem 1 depends on the o(α_k) condition in Lemma 2, which is not implied by Assumptions 1–4; until a way to guarantee that condition is found, the theorem is conditional on an unverified rate assumption.
The abstract mentions a hybrid variant that would decouple the perturbation radius from the local convergence rate, but the full text contains no such algorithm; if it exists, it is likely intended to remove the o(α_k) dependence identified in Lemma 2.
Because p_min is proportional to the spherical area of the exposed-direction sets, cluster points with nearly parallel active gradients could require many iterations before the right piece is selected; this potential slow convergence is not probed in the experiments.
The same perturbation trick could be transplanted to stochastic or inexact DCA variants, where a singleton active gradient would similarly cut the per-iteration cost of computing d-stationary points.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

The core idea here is genuinely nice. At each iteration, linearize the concave part ψ at x_k plus a tiny random perturbation. By Rademacher's theorem, the active gradient at the perturbed point is almost surely a singleton, so you solve one strongly convex subproblem per iteration—same per-iteration cost as DCA—instead of the multiple subproblems in Pang et al.'s ε-active-set algorithm. The convergence argument then tries to show that, along the subsequence where the perturbation picks each active piece infinitely often, the limit satisfies the d-stationarity conditions. That is a real algorithmic innovation, and the numerical experiments on K-sparse regression and K-medians clustering are encouraging: pDCA matches Algorithm 2's quality while solving far fewer subproblems, and beats kmedoids on the clustering examples.

The problem is that the main theorem is not actually a theorem about the algorithm as stated. Theorem 1 is conditional on Lemma 2, and Lemma 2 requires an infinite subsequence where ||x_k - x*|| = o(α_k). That condition is not implied by Assumptions 1–4. Lemma 1 only gives sum E_k ||x_{k+1} - xhat_k||^2 < ∞, hence ||x_{k+1} - xhat_k|| → 0, with no rate. Meanwhile Assumption 3 makes α_k go to zero fast enough that the squares are summable. So nothing in the algorithm guarantees the perturbation remains much larger than the current error along a subsequence. Without that, the proof of the uniform selection probability in Lemma 2 collapses, because the direction term can be swamped by the error term. This is not a minor technicality; it is the load-bearing step for the d-stationarity claim.

Just as serious: the abstract as presented promises a hybrid variant that independently samples the perturbation radius and direction with a safeguard, and claims a convergence theorem under relaxed assumptions. The body contains no such variant, no safeguard, and no relaxed theorem. Either the authors have a version that was cut, or the abstract oversold the paper. For a reviewer, that mismatch is a red flag.

On the positive side, the analysis is otherwise careful: Lemma 1 is a clean application of Robbins–Siegmund, the convex analysis around Proposition 1 is standard, and the verification of Assumption 4 on the examples is earnest. I don't see circularity or fabricated results. The soft spots are genuine gaps, not deceptions. The central idea may well be salvageable—one could imagine an adaptive α_k schedule or a safeguard that enforces the required relative rate, which is presumably what the missing hybrid variant was meant to do.

Who should read this? Anyone working on d-stationarity for nonsmooth DC programs, and anyone who wants a cheap alternative to Pang et al.'s ε-active-set method. The paper deserves a serious referee, but the authors need to either prove the o(α_k) condition, replace it with a verifiable assumption, or present the hybrid variant they advertised. I'd send it out with a request for major revision.

Referee Report

3 major / 4 minor

Summary. The paper proposes a randomly perturbed difference-of-convex algorithm (pDCA) for minimizing structured nonsmooth DC programs of the form min φ(x) − ψ(x) with ψ = max_i ψ_i. The method linearizes the concave part at a randomly perturbed point, so that the active gradient is a singleton almost surely, and solves one strongly convex subproblem per iteration. The authors claim that every cluster point of the generated sequence is a d-stationary point almost surely under 'practical assumptions', and they compare the method numerically with existing algorithms on K-sparse regression and K-medians clustering. The central theorem, however, is explicitly conditional on an unproved rate condition in Lemma 2, and the abstract's promised hybrid variant does not appear in the body.

Significance. If the advertised convergence result were established, pDCA would be a genuinely useful algorithmic contribution: it would provide a d-stationary guarantee at a per-iteration cost comparable to standard DCA, avoiding the potentially expensive multi-subproblem updates in Pang et al. The numerical evidence on sparse regression and clustering is suggestive, and the paper is clearly written. The main theoretical claim, however, is not supported as stated. The proof of the key lemma requires an asymptotic condition on the perturbation radius relative to the distance to a cluster point, and no argument is supplied that this condition holds under the stated assumptions. Because the central contribution is precisely this convergence guarantee, the gap is load-bearing rather than cosmetic.

major comments (3)

[§3, Lemma 2 and Theorem 1] Theorem 1 is conditional on Lemma 2's hypothesis that there is an infinite subsequence K_sub ⊆ K with ||x_k − x*|| = o(α_k) at each cluster point. This condition is not implied by Assumptions 1–4. Lemma 1 only yields Σ_k E_k[||x_{k+1} − x̂_k||^2] < ∞, hence ||x_{k+1} − x̂_k|| → 0 without any rate. Assumption 3 forces α_k → 0 with Σ α_k^2 < ∞, but nothing in Algorithm 3 controls the ratio ||x_k − x*||/α_k. Thus Theorem 1 is not a convergence guarantee for Algorithm 3; it is a conditional statement for trajectories that happen to satisfy the unverified rate condition. This is the central load-bearing issue.
[Abstract and §3–§5] The abstract supplied with the paper claims convergence to d-stationarity 'under practical assumptions' and announces a hybrid variant that 'decouples the perturbation radii from the local convergence rate of the iterates' with 'more relaxed and practical assumptions'. No such hybrid algorithm or proof appears in Sections 3–5, and Section 5 only discusses future work on sequential convergence. Moreover, the body's Theorem 1 is not a statement under Assumptions 1–4 alone; it is conditional on the unproved o(α_k) condition. The advertised result is therefore overstated.
[§3, Theorem 1 proof] Even if Lemma 2's condition were granted, the theorem states that 'every cluster point' is d-stationary, but the proof fixes one cluster point x* and one subsequence K. No argument shows that the o(α_k) condition holds simultaneously for all cluster points of the bounded sequence. In addition, the Borel–Cantelli step applies to lower bounds on conditional probabilities along a subsequence K' whose definition depends on the random cluster point and trajectory; the measurability of K' is not discussed. The latter point is likely repairable, but the former is not addressed.

minor comments (4)

[Notation, §1] The definition of the ℓ_p norm is garbled: '∥x∥_p := p p Pn i=1 |xi|p' appears corrupted. Please fix the typesetting.
[Remark 1] Typo: 'Algoirthm' should be 'Algorithm'.
[§4, Tables 1–4] The numerical section does not report the α_k schedule used, the number of random trials, or any measure of variability. Table 4 reports R(µ*) = 0.00e+00 for all datasets, which is likely only display precision; please state the termination tolerance and report R(µ*) in scientific notation with the actual values.
[§3, Theorem 1] The phrase 'Under the conditions of Lemma 2' should be made an explicit, numbered assumption in the theorem statement so that the reader can see exactly what is being assumed. As written, it is ambiguous whether the theorem is meant to be a result about the algorithm or about specially selected subsequences.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Theorem 1 is conditional on an unproved rate condition, but the derivation is self-contained; the gap is a correctness issue, not circular reasoning.

full rationale

The derivation chain is self-contained rather than circular. Algorithm 3's update (11) is a standard proximal linearization; Lemma 1 obtains boundedness and summability of proximal gaps from Assumptions 1–3 and the Robbins–Siegmund lemma. Lemma 2's uniform selection bound is a genuine geometric/probabilistic statement: under Assumption 4, the exposed-direction set has positive spherical measure, so the conditional probability of selecting a given active gradient is bounded below. Theorem 1 then passes to the limit in the optimality condition (16) on a subsequence where each active gradient is selected, using Proposition 1 (an external characterization from Pang et al. [18]); d-stationarity is not assumed in the subproblem or in the definitions. The main weakness — the unproved o(alpha_k) condition in Lemma 2 (and the abstract's promised hybrid variant, which is absent from the body) — is an unverified hypothesis or manuscript inconsistency, not a reduction of the conclusion to the inputs. No parameter is fitted to data and renamed a prediction; the numerical experiments are separate demonstrations. Self-citations [15, 26, 29, 30] appear only for solvers (semismooth Newton, adaptive sieving) used in the numerical subproblems, while the convergence proof relies on external standard results (Rademacher, Rockafellar, Durrett, Pang et al., Le Thi/Pham). Hence no circular step is present.

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

No new physical or mathematical entities are introduced. The theoretical load is carried by the problem assumptions plus the unproved rate condition in Lemma 2; the two algorithm hyperparameters σ and α_k are not specified in the experiments.

free parameters (2)

σ
Proximal parameter in Algorithm 3; any σ > 0 works in theory, but the numerical sections never report the value actually used.
α_k schedule
Perturbation radii. Assumption 3 only requires ∑ α_k^2 < ∞; the manuscript does not specify the schedule used in the experiments, so the reported behavior cannot be exactly reproduced.

assumptions (6)

domain assumption Assumption 1: level sets of ζ are bounded.
Used in Lemma 1 to conclude the iterates are bounded almost surely.
domain assumption Assumption 2: each ψ_i is L-smooth.
Controls function and gradient perturbations in Lemma 1 and Lemma 2.
ad hoc to paper Assumption 3: ∑ α_k^2 < ∞.
Algorithmic design choice to apply the Robbins–Siegmund lemma; not a property of the optimization problem.
domain assumption Assumption 4: exposed direction sets A*_i are nonempty for each active index at every cluster point.
Ensures a positive probability of selecting each active gradient; verified for the examples but not established for general DC programs.
ad hoc to paper Existence of an infinite subsequence with ∥x_k − x*∥ = o(α_k) at each cluster point.
Load-bearing condition in Lemma 2 and Theorem 1; not implied by Assumptions 1–4 and not enforced by the algorithm.
standard math Rademacher's theorem and standard convex-analysis subdifferential facts.
Used to argue the active gradient at a random perturbed point is a singleton almost surely.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs." pith.science (2026). https://pith.science/paper/GS2XDNRB

@misc{pith2026260102084,
  author       = {Pith},
  title        = {Pith review of: A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GS2XDNRB}},
  note         = {Machine review of arXiv:2601.02084}
}

read the original abstract

This paper introduces an efficient perturbed difference-of-convex algorithm (perturbed DCA) for computing d-stationary points of an important class of structured nonsmooth difference-of-convex problems. Compared to the principal algorithms introduced in [J.-S. Pang, M. Razaviyayn, and A. Alvarado, Math. Oper. Res. 42(1):95--118 (2017)], which may require solving several subproblems for a one-step update, perturbed DCA only requires solving a single subproblem. Therefore, the per-iteration computational cost of perturbed DCA is comparable to the widely used difference-of-convex algorithm (DCA) introduced in [D. T. Pham and H. A. Le Thi, Acta Math. Vietnam. 22(1):289--355 (1997)] for computing a critical point. We establish the subsequential and almost sure convergence of the perturbed DCA to d-stationary points under certain conditions. To decouple the perturbation radii from the local convergence rate of the iterates, we further propose a hybrid variant of the perturbed DCA that independently samples the perturbation radius and direction with a safeguard using a proximal DCA step. Importantly, under more relaxed and practical assumptions, we prove that every accumulation point of the sequence generated by the hybrid perturbed DCA is a d-stationary point almost surely. Numerical results on several important examples demonstrate the efficiency of the proposed methods for computing d-stationary points.

Figures

Figures reproduced from arXiv: 2601.02084 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 1 linked inside Pith

[12]

,DC programming and DCA: Thirty years of developments, Mathematical Programming, 169 (2018), pp. 5–68

2018
[13]

,Open issues and recent advances in DC programming and DCA, Journal of Global Op- timization, 88 (2024), pp. 533–590. [14]X. Li, D. F. Sun, and K.-C. Toh,A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems, SIAM Journal on Optimization, 28 (2018), pp. 433–458. 21 [15]M. Lin, Y. Yuan, D. F. Sun, and K.-C. Toh,A highl...

arXiv 2024

Pith tools

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

[1] [12]

,DC programming and DCA: Thirty years of developments, Mathematical Programming, 169 (2018), pp. 5–68

2018

[2] [13]

,Open issues and recent advances in DC programming and DCA, Journal of Global Op- timization, 88 (2024), pp. 533–590. [14]X. Li, D. F. Sun, and K.-C. Toh,A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems, SIAM Journal on Optimization, 28 (2018), pp. 433–458. 21 [15]M. Lin, Y. Yuan, D. F. Sun, and K.-C. Toh,A highl...

arXiv 2024