Performance of First- and Second-Order Methods for L1-Regularized Least Squares Problems

Technical Report ERGO-15-005

K. Fountoulakis and J. Gondzio

We study the performance of first- and second-order optimization methods for l1-regularized sparse least-squares problems as the conditioning and the dimensions of the problem increase up to one trillion. A rigorously defined generator is presented which allows control of the dimensions, the conditioning and the sparsity of the problem. The generator has very low memory requirements and scales well with the dimensions of the problem.

Key words: L1-regularized least-squares, First-order methods, Second-order methods, Sparse least-squares instance generator, Ill-conditioned problems.

PDF ERGO-15-005.pdf.

Written: March 30, 2015, revised December 11, 2015.
Computational Optimization and Applications 65 (2016) 605--635.
Published online: June 14, 2016.

Related Software:
trillion Instance generators for l1-regularized over- and underdetermined least squares.