# Iteration complexity analysis of random coordinate descent methods for ℓ0 regularized convex problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2014.

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

- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [Query Efficient Decision Based Sparse Attacks Against Black-Box Deep Learning Models](https://mlsanity.com/paper/2202.00091/) (2022)

## Abstract (arXiv)

In this paper we analyze a family of general random block coordinate descent methods for the minimization of ℓ0 regularized optimization problems, i.e. the objective function is composed of a smooth convex function and the ℓ0 regularization. Our family of methods covers particular cases such as random block coordinate gradient descent and random proximal coordinate descent methods. We analyze necessary optimality conditions for this nonconvex ℓ0 regularized problem and devise a separation of the set of local minima into restricted classes based on approximation versions of the objective function. We provide a unified analysis of the almost sure convergence for this family of block coordinate descent algorithms and prove that, for each approximation version, the limit points are local minima from the corresponding restricted class of local minimizers. Under the strong convexity assumption, we prove linear convergence in probability for our family of methods.