Convergence of Common Proximal Methods for L1-Regularized Least Squares

Tao, Shaozhe; Boley, Daniel; Zhang, Shuzhong

Convergence of Common Proximal Methods for L1-Regularized Least Squares

Shaozhe Tao, Daniel Boley, Shuzhong Zhang

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Machine Learning. Pages 3849-3854.

Abstract

We compare the convergence behavior of ADMM (alternating direction method of multipliers), [F]ISTA ([fast] iterative shrinkage and thresholding algorithm) and CD (coordinate descent) methods on the model L1-regularized least squares problem (aka LASSO). We use an eigen analysis of the operators to compare their local convergence rates when close to the solution. We find that, when applicable, CD is often much faster than the other iterations, when close enough to the solution. When far from the solution, the spectral analysis implies that one can often get a sequence of iterates that appears to stagnate, but is actually taking small constant steps toward the solution. We also illustrate how the unaccelerated ISTA algorithm can sometimes be faster compared to FISTA when close enough to the solution.

Shaozhe Tao, Daniel Boley, and Shuzhong Zhang. 2015. Convergence of Common Proximal Methods for L1-Regularized Least Squares. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3849–3854. https://ijcai.org/proceedings/2015/541

@inproceedings{ijcai2015p541,
  title     = {Convergence of Common Proximal Methods for L1-Regularized Least Squares},
  author    = {Tao, Shaozhe and Boley, Daniel and Zhang, Shuzhong},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {3849--3854},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Machine Learning},
  url       = {https://ijcai.org/proceedings/2015/541},
}

TY  - CPAPER
TI  - Convergence of Common Proximal Methods for L1-Regularized Least Squares
AU  - Tao, Shaozhe
AU  - Boley, Daniel
AU  - Zhang, Shuzhong
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 3849
EP  - 3854
UR  - https://ijcai.org/proceedings/2015/541
ER  -