2014/03/26 by Andrei Pătraşcu, Ion Necoara, Patrascu, Andrei +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1403.6622
openalex publication_date 2014/03/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.