# RA-DCA: A Randomized Active-Set DCA for Directional Stationarity in Max-Structured DC Programs

arXiv: https://arxiv.org/abs/2605.23550 · HTML: https://mlsanity.com/paper/2605.23550/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 9 of 9)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Computing B-Stationary Points of Nonsmooth DC Programs](https://mlsanity.com/paper/1511.01796/) (2015)
- [A proximal difference-of-convex algorithm with extrapolation](https://mlsanity.com/paper/1612.06265/) (2016)
- [Composite Difference-Max Programs for Modern Statistical Estimation Problems](https://mlsanity.com/paper/1803.00205/) (2018)
- [DC Decomposition of Nonconvex Polynomials with Algebraic Techniques](https://mlsanity.com/paper/1510.01518/) (2015)
- [On the Convergence Analysis of DCA](https://mlsanity.com/paper/2211.10942/) (2022)
- [Discrete Dynamical System Approaches for Boolean Polynomial Optimization](https://mlsanity.com/paper/1912.10221/) (2019)

## Abstract (arXiv)

We study nonsmooth difference-of-convex programs whose subtracted convex term is a finite maximum of smooth convex functions. In this setting, standard DCA iterations may converge to critical points that are not directionally stationary, whereas exact active-vertex screening can be expensive when active sets are large or combinatorial. We propose RA-DCA, a vertex-first randomized active-set DCA that projects active gradients onto sampled directions, checks a sampled vertex residual, and uses a small linear program only as a low-residual convex-combination fallback. The method preserves the descent structure of DCA and reduces the randomized screening layer to matrix multiplications. Under the stated regularity, numerical active-set consistency, and random-embedding assumptions, every accumulation point generated by the safeguarded method is directionally stationary with probability one. MATLAB experiments first test the theorem on degenerate max-affine, max-quadratic, and sparse support-function models, where the safeguard avoids nonstationary critical points and closely tracks a full active-vertex scan. Block top-k tests then show that the same screening idea remains useful when exact aggregate enumeration is combinatorial. Trimmed-regression, complementarity, and QUBO diagnostics separate cases where active-set selection helps from cases dominated by multistart search, the DC split, or other problem-specific features.