An Efficient Algorithm for Minimizing Multi Non-Smooth Component Functions

Abstract

Many problems in statistics and machine learning can be formulated as an optimization problem of a finite sum of nonsmooth convex functions. We propose an algorithm to minimize this type of objective functions based on the idea of alternating linearization. Our algorithm retains the simplicity of contemporary methods without any restrictive assumptions on the smoothness of the loss function. We apply our proposed method to solve two challenging problems: overlapping group lasso and convex regression with sharp partitions. Numerical experiments show that our method is superior to the state-of-the-art algorithms, many of which are based on the accelerated proximal gradient method. Supplementary materials for this article are available online.