An Efficient Algorithm for Minimizing Multi Non-Smooth Component Functions

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.统计学与机器学习领域的诸多问题，均可建模为有限个非光滑凸函数之和的优化问题。本文基于交替线性化的思想，提出了一种针对该类目标函数的最小化算法。该算法保留了当代方法的简洁性，且无需对损失函数的光滑性施加任何限制性假设。我们将所提算法应用于两类极具挑战性的问题：重叠分组套索（overlapping group lasso）以及带尖锐划分的凸回归。数值实验结果表明，我们的算法性能优于当前顶尖算法，其中诸多算法均基于加速近端梯度法（accelerated proximal gradient method）。本文的补充材料可在线获取。