# Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 9 Sep 2021.

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

- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Positive-Unlabeled Learning with Non-Negative Risk Estimator](https://mlsanity.com/paper/1703.00593/) (2017)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Learning One-hidden-layer ReLU Networks via Gradient Descent](https://mlsanity.com/paper/1806.07808/) (2018)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017)
- [An Asynchronous Parallel Stochastic Coordinate Descent Algorithm](https://mlsanity.com/paper/1311.1873/) (2013)
- [A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems](https://mlsanity.com/paper/1303.4434/) (2013)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [Computing B-Stationary Points of Nonsmooth DC Programs](https://mlsanity.com/paper/1511.01796/) (2015)
- [Variable Smoothing for Weakly Convex Composite Functions](https://mlsanity.com/paper/2003.07612/) (2020)
- [A Family of Inexact SQA Methods for Non-Smooth Convex Minimization with Provable Convergence Guarantees Based on the Luo-Tseng Error Bound Property](https://mlsanity.com/paper/1605.07522/) (2016)
- [DC Decomposition of Nonconvex Polynomials with Algebraic Techniques](https://mlsanity.com/paper/1510.01518/) (2015)
- [A Block Decomposition Algorithm for Sparse Optimization](https://mlsanity.com/paper/1905.11031/) (2019)
- [Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization](https://mlsanity.com/paper/1305.4027/) (2013)
- [Exact penalty decomposition method for zero-norm minimization based on MPEC formulation](https://mlsanity.com/paper/1412.4452/) (2014)
- [Efficiency of Coordinate Descent Methods For Structured Nonconvex Optimization](https://mlsanity.com/paper/1909.00918/) (2019)
- [Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints](https://mlsanity.com/paper/1608.04430/) (2016)

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

- [Coordinate Descent Methods for Fractional Minimization](https://mlsanity.com/paper/2201.12691/) (2022)
- [A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints](https://mlsanity.com/paper/2304.03641/) (2023)

## Abstract (arXiv)

Difference-of-Convex (DC) minimization, referring to the problem of minimizing the difference of two convex functions, has been found rich applications in statistical learning and studied extensively for decades. However, existing methods are primarily based on multi-stage convex relaxation, only leading to weak optimality of critical points. This paper proposes a coordinate descent method for minimizing a class of DC functions based on sequential nonconvex approximation. Our approach iteratively solves a nonconvex one-dimensional subproblem globally, and it is guaranteed to converge to a coordinate-wise stationary point. We prove that this new optimality condition is always stronger than the standard critical point condition and directional point condition under a mild textitlocally bounded nonconvexity assumption. For comparisons, we also include a naive variant of coordinate descent methods based on sequential convex approximation in our study. When the objective function satisfies a textitglobally bounded nonconvexity assumption and textitLuo-Tseng error bound assumption, coordinate descent methods achieve textitQ-linear convergence rate. Also, for many applications of interest, we show that the nonconvex one-dimensional subproblem can be computed exactly and efficiently using a breakpoint searching method. Finally, we have conducted extensive experiments on several statistical learning tasks to show the superiority of our approach. Keywords: Coordinate Descent, DC Minimization, DC Programming, Difference-of-Convex Programs, Nonconvex Optimization, Sparse Optimization, Binary Optimization.