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

Zhangcheng Feng, Yancheng YuanarXiv 2026 · DOI · arXiv

TL;DR

Researchers have developed a "perturbed" version of the popular Difference-of-Convex Algorithm (DCA) that can find high-quality "d-stationary" points in nonsmooth optimization problems. By adding a tiny bit of random noise at each step, the new pDCA algorithm avoids the computational bottleneck of solving multiple subproblems, matching the speed of standard methods while providing much stronger theoretical guarantees.

What Problem Does This Paper Address?

Many real-world problems in machine learning and signal processing—like sparse recovery, feature selection, and clustering—can be framed as Difference-of-Convex (DC) programs. These are optimization problems where the objective function is the difference between two convex functions: $f(x) = \phi(x) - \psi(x)$.

The challenge arises when these functions are nonsmooth (i.e., they have "kinks" or sharp corners). Standard algorithms like the classic DCA are efficient but often get stuck at "critical points," which are weak solutions where the algorithm simply stops making progress. To get better results, researchers aim for directional stationary (d-stationary) points, where the function value doesn't decrease in any feasible direction.

Until now, finding these d-stationary points was computationally expensive. Existing state-of-the-art methods required identifying all "active" pieces of the nonsmooth function at every step and solving a separate subproblem for each one. For large-scale problems, this is often too slow to be practical.

Methods

The authors introduce the Perturbed DCA (pDCA). Its brilliance lies in a simple "perturbation" trick:

  1. The Perturbation: At each iteration $k$, instead of calculating the gradient at the current point $x^k$, the algorithm adds a tiny random vector $e^k$ to create a perturbed point $\hat{x}^k$.
  2. The Singleton Property: Thanks to Rademacher’s theorem, a convex function is differentiable almost everywhere. By shifting slightly away from the current point, the algorithm lands on a spot where the "active gradient" is a singleton (only one direction to choose from) with probability one.
  3. Single Subproblem: Because there is only one gradient to worry about, pDCA only needs to solve one strongly convex subproblem per iteration. This makes its per-step cost identical to the standard (but weaker) DCA.

The authors provide a rigorous proof showing that, under practical assumptions, the sequence of points generated by this random process will converge to a d-stationary point "almost surely."

Datasets

The paper evaluates the algorithm on two main types of problems:

  • Synthetic Sparse Regression: Data generated using standard normal distributions to test $K$-sparse regularized linear regression (up to 10,000 variables).
  • Real-World Clustering: Four datasets from the UCI Machine Learning Repository—Iris, Wine, Yeast, and Glass—were used to test the algorithm's performance on $K$-medians clustering models.

Key Insights and Ideas

  • Randomness as a Simplifier: Usually, randomness is used in optimization to escape local minima (like in Stochastic Gradient Descent). Here, it is used to "smooth out" the search for gradients. By avoiding the "corners" where multiple gradients exist, the algorithm simplifies a complex multi-choice decision into a single, efficient calculation.
  • Theoretical Sharpness vs. Efficiency: The paper successfully bridges the gap between the "sharp" theoretical requirements for d-stationarity and the "efficient" practical requirements of large-scale engineering.
  • Assumption 4 (Exposed Directions): A key insight in the proof is the requirement that for any active index, there must be a direction that "exposes" it relative to others. The authors demonstrate that this geometric property naturally holds for common problems like sparse regression and capped $\ell_1$ penalties.

Key Results

  • Escaping Traps: In a simple 1D example where standard DCA gets trapped at a sub-optimal critical point ($x=0$), pDCA successfully uses its perturbations to find the true d-stationary point ($x=-1$).
  • Massive Speedup: When compared to the previous gold-standard for d-stationarity (Algorithm 2 by Pang et al.), pDCA achieved the same solution quality while solving significantly fewer subproblems. In one test case, pDCA solved 11 subproblems compared to 414 for the older method.
  • Clustering Accuracy: On the UCI datasets, pDCA consistently found lower objective values and zero d-stationarity error compared to MATLAB’s built-in kmedoids function, which often failed to find d-stationary points.

Limitations and Future Work

  • Subsequential Convergence: The current proof guarantees that at least one cluster point of the sequence is d-stationary. Proving "sequential convergence"—that the entire sequence settles on a single d-stationary point—remains an open research question.
  • Parameter Sensitivity: While the algorithm is flexible regarding the proximal parameter $\sigma$, the authors note that the specific choice of the perturbation size $\alpha_k$ and $\sigma$ could impact the rate of convergence, which warrants further study.
  • Complexity of Subproblems: While pDCA only solves one subproblem per step, the complexity of that individual subproblem depends on the structure of $\phi(x)$. For very complex $\phi$, even one subproblem might be heavy.

Summary updated

Abstract

This paper introduces an efficient perturbed difference-of-convex algorithm (pDCA) 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, pDCA only requires solving a single subproblem. Therefore, the computational cost of pDCA for one-step update 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. Importantly, under practical assumptions, we prove that every accumulation point of the sequence generated by pDCA is a d-stationary point almost surely. Numerical experiment results on several important examples of nonsmooth DC programs demonstrate the efficiency of pDCA for computing d-stationary points.
BibTeX
@misc{feng2026perturbed,
  author = {Zhangcheng Feng and Yancheng Yuan},
  title = {{A Perturbed DCA for Computing d-Stationary Points of Nonsmooth DC Programs}},
  year = {2026},
  eprint = {2601.02084},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.02084},
}
Figure