[KDD 2020] A Block Decomposition Algorithm for Sparse Optimization
Aug 13, 20207 views
Sparse optimization is a central problem in machine learning,and computer vision. However, this problem is inherently,NP-hard and thus difficult to solve in general. Combinatorial search methods find the global optimal solution but are,confined to small-sized problems, while coordinate descent,methods are efficient but often suffer from poor local minima.,This paper considers a new block decomposition algorithm that combines the effectiveness of combinatorial search,methods and the efficiency of coordinate descent methods.,Specifically, we consider a random strategy or/and a greedy,strategy to select a subset of coordinates as the working set,,and then perform a global combinatorial search over the working set based on the original objective function. We show that,our method finds stronger stationary points than Amir Beck,et al.’s coordinate-wise optimization method. In addition, we,establish the convergence rate of our algorithm. Our experiments on solving sparse regularized and sparsity constrained,least squares optimization problems demonstrate that our,method achieves state-of-the-art performance in terms of,accuracy. For example, our method generally outperforms,the well-known greedy pursuit method.