The Development of Coordinate-Descent Algorithms: A Review

• Activity Number: 294
• Type: Topic Contributed
• Date/Time: Tuesday, August 2, 2011 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Wenjiang Fu*+
• Companies: Michigan State University
• Keywords: Coordinate-descent ; Efficiency ; Lasso penalty ; Least-squares regression ; Regularization

Abstract

Thanks to the Lasso penalty model (Tibshirani 1996), a new series of coordinate-descent algorithms have been developed to fit models for high dimensional data, including the Shooting algorithm, the least squares support vector machine algorithm, the coordinate-descent algorithms and application to high dimensional genome data, high dimensional generalized linear regression models, and the active shooting algorithm. The coordinate-descent algorithm can be traced back to the cyclic coordinate-descent algorithm described in Luenberger's monograph Linear and Nonlinear Programming (1972). These algorithms share the same feature, unlike the classical method of working with high dimensional matrix decomposition, such as the Cholesky's decomposition, they take the coordinate-wise minimization procedure iteratively to achieve efficient computation, particularly for high dimensional data, usually of 10,000 dimension or higher. The computational advantages of these methods have no doubt been appreciated. However, certain issues may still exist, including the convergence rate and the efficiency for data that possess largely different characteristics. I will discuss these issues in this talk.