A Fast Dual Projected Newton Method for L1-Regularized Least Squares
Abstract
L1-regularized least squares, with the ability of discovering sparse representations, is quite prevalent in the field of machine learning, statistics and signal processing. In this paper, we propose a novel algorithm called Dual Projected Newton Method (DPNM) to solve the L1-regularized least squares problem. In DPNM, we first derive a new dual problem as a box constrained quadratic programming. Then, a projected Newton method is utilized to solve the dual problem, achieving a quadratic convergence rate. Moreover, we propose to utilize some practical techniques, thus it greatly reduces the computational cost and makes DPNM more efficient. Experimental results on six real-world data sets indicate that DPNM is very efficient for solving the L1-regularized least squares problem, by comparing it with state of the art methods.
Cite
Text
Gong and Zhang. "A Fast Dual Projected Newton Method for L1-Regularized Least Squares." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-216Markdown
[Gong and Zhang. "A Fast Dual Projected Newton Method for L1-Regularized Least Squares." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/gong2011ijcai-fast/) doi:10.5591/978-1-57735-516-8/IJCAI11-216BibTeX
@inproceedings{gong2011ijcai-fast,
title = {{A Fast Dual Projected Newton Method for L1-Regularized Least Squares}},
author = {Gong, Pinghua and Zhang, Changshui},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {1275-1280},
doi = {10.5591/978-1-57735-516-8/IJCAI11-216},
url = {https://mlanthology.org/ijcai/2011/gong2011ijcai-fast/}
}