Optimization Methods for L1-Regularization

This webpage has been set-up as an on-line appendix to the following works:

Mark Schmidt, Glenn Fung, Romer Rosales. Fast Optimization Methods for L1 Regularization: A Comparative Study and Two New Approaches. European Conference on Machine Learning (ECML), 2007 (pdf).

Mark Schmidt, Glenn Fung, Romer Rosales. Optimization Methods for L1-Regularization. UBC Technical Report TR-2009-19, 2009 (pdf).

Code

The Matlab code for the optimization algorithms used to produce the results presented in the conference paper can be downloaded here.

The Matlab code for the optimization algorithms used to produce the results presented in the extended paper submission can be downloaded here.

The code related to the extended submission has several minor improvements on the methods present in the conference paper, but also contains 2 additional methods and first-order variants of all methods that do not require explicit Hessian calculation (in most cases these are Quasi-Newton methods, and they are accessible in most methods by setting the 'order' parameter to 1). We have also included an L-BFGS version of the ProjectionL1 method that we have used to solve problems with a very large number of variables.

Examples

In both papers, we have included a simple example of using the optimization algorithms. The following steps are identical for the conference and extended papers, and give a demonstration of running the different methods to optimize the logistic regression negative log-likelihood on the UCI Ionosphere data subject to L1-regularization (with the regularization scale fixed at 50).

To run the demo, unzip the downloaded file (either L1General.zip or L1General2.zip). Then start Matlab and type the following: 
>> cd L1General % go to the newly created directory
>> addpath(genpath(pwd)) % adds the needed functions to the Matlab path
>> L1General_example % load the data, set up the loss, and run the optimizers
We have also prepared a more extensive set of examples of using the code on the webpage Examples of using L1General.

Supplemental Material

To the following documents are appendices to the conference paper:
  • Proof of the SmoothL1 Bounds
  • Expanded Experimental Results