A Fast Dual Projected Newton Method for l1-Regularized Least Squares

Gong, Pinghua; Zhang, Changshui

doi:10.5591/978-1-57735-516-8/IJCAI11-216

A Fast Dual Projected Newton Method for l1-Regularized Least Squares

Pinghua Gong, Changshui Zhang

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1275-1279.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-216

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.

Pinghua Gong, and Changshui Zhang. 2011. A Fast Dual Projected Newton Method for l1-Regularized Least Squares. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1275–1279. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-216

@inproceedings{ijcai2011p216,
  title     = {A Fast Dual Projected Newton Method for l1-Regularized Least Squares},
  author    = {Gong, Pinghua and Zhang, Changshui},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1275--1279},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-216},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-216},
}

TY  - CPAPER
TI  - A Fast Dual Projected Newton Method for l1-Regularized Least Squares
AU  - Gong, Pinghua
AU  - Zhang, Changshui
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1275
EP  - 1279
DO  - 10.5591/978-1-57735-516-8/IJCAI11-216
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-216
ER  -