TY - JOUR
T1 - Proximal average approximated incremental gradient descent for composite penalty regularized empirical risk minimization
AU - CHEUNG, Yiu Ming
AU - Lou, Jian
N1 - Publisher Copyright:
© 2016, The Author(s).
PY - 2017/4/1
Y1 - 2017/4/1
N2 - Composite penalties have been widely used for inducing structured properties in the empirical risk minimization (ERM) framework in machine learning. Such composite regularizers, despite their superior performance in grasping structural sparsity properties, are often nonsmooth and even nonconvex, which makes the problem difficult to optimize. Proximal average (PA) is a recently proposed approximation technique targeting these regularizers, which features the tractability of implementation and theoretical analysis. However, current PA-based methods, notwithstanding the promising performance of handling composite penalties against traditional techniques, are either slow in convergence or do not scale well to large datasets. To make PA an ideal technique for optimizing ERM with composite penalties, this paper proposes a new PA-based algorithm called IncrePA by incorporating PA approximation into an incremental gradient framework. The proposed method is a more optimal PA-based method that features lower per-iteration cost, a faster convergence rate for convex composite penalties, and guaranteed convergence for even nonconvex composite penalties. Experiments on both synthetic and real datasets demonstrate the efficacy of the proposed method in optimizing convex and nonconvex ERM with composite penalties.
AB - Composite penalties have been widely used for inducing structured properties in the empirical risk minimization (ERM) framework in machine learning. Such composite regularizers, despite their superior performance in grasping structural sparsity properties, are often nonsmooth and even nonconvex, which makes the problem difficult to optimize. Proximal average (PA) is a recently proposed approximation technique targeting these regularizers, which features the tractability of implementation and theoretical analysis. However, current PA-based methods, notwithstanding the promising performance of handling composite penalties against traditional techniques, are either slow in convergence or do not scale well to large datasets. To make PA an ideal technique for optimizing ERM with composite penalties, this paper proposes a new PA-based algorithm called IncrePA by incorporating PA approximation into an incremental gradient framework. The proposed method is a more optimal PA-based method that features lower per-iteration cost, a faster convergence rate for convex composite penalties, and guaranteed convergence for even nonconvex composite penalties. Experiments on both synthetic and real datasets demonstrate the efficacy of the proposed method in optimizing convex and nonconvex ERM with composite penalties.
KW - Composite regularizer
KW - Empirical risk minimization
KW - Incremental gradient descent
KW - Proximal average
UR - http://www.scopus.com/inward/record.url?scp=84995766801&partnerID=8YFLogxK
U2 - 10.1007/s10994-016-5609-1
DO - 10.1007/s10994-016-5609-1
M3 - Journal article
AN - SCOPUS:84995766801
SN - 0885-6125
VL - 106
SP - 595
EP - 622
JO - Machine Learning
JF - Machine Learning
IS - 4
ER -