# Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2018.

## Built on by (most cited first, 16 of 16)

- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Data-driven Piecewise Affine Decision Rules for Stochastic Programming with Covariate Information](https://mlsanity.com/paper/2304.13646/) (2023)
- [Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions](https://mlsanity.com/paper/2405.18577/) (2024)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence](https://mlsanity.com/paper/2109.04228/) (2021)
- [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022)
- [Enforcing Fair Predicted Scores on Intervals of Percentiles by Difference-of-Convex Constraints](https://mlsanity.com/paper/2505.12530/) (2025)
- [Stochastic Difference-of-Convex Optimization with Momentum](https://mlsanity.com/paper/2510.17503/) (2025)
- [Outlier-robust neural network training: variation regularization meets trimmed loss to prevent functional breakdown](https://mlsanity.com/paper/2308.02293/) (2023)
- [Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization](https://mlsanity.com/paper/2406.19475/) (2024)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)
- [MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization](https://mlsanity.com/paper/2605.29635/) (2026)
- [Difference of Convex Programming in the Wasserstein Space with Applications to MMD Optimization](https://mlsanity.com/paper/2606.27767/) (2026)

## Abstract (arXiv)

Difference of convex (DC) functions cover a broad family of non-convex and possibly non-smooth and non-differentiable functions, and have wide applications in machine learning and statistics. Although deterministic algorithms for DC functions have been extensively studied, stochastic optimization that is more suitable for learning with big data remains under-explored. In this paper, we propose new stochastic optimization algorithms and study their first-order convergence theories for solving a broad family of DC functions. We improve the existing algorithms and theories of stochastic optimization for DC functions from both practical and theoretical perspectives. On the practical side, our algorithm is more user-friendly without requiring a large mini-batch size and more efficient by saving unnecessary computations. On the theoretical side, our convergence analysis does not necessarily require the involved functions to be smooth with Lipschitz continuous gradient. Instead, the convergence rate of the proposed stochastic algorithm is automatically adaptive to the H"older continuity of the gradient of one component function. Moreover, we extend the proposed stochastic algorithms for DC functions to solve problems with a general non-convex non-differentiable regularizer, which does not necessarily have a DC decomposition but enjoys an efficient proximal mapping. To the best of our knowledge, this is the first work that gives the first non-asymptotic convergence for solving non-convex optimization whose objective has a general non-convex non-differentiable regularizer.