This directory includes sources used in the following paper:

Guo-Xun Yuan, Kai-Wei Chang, Cho-Jui Hsieh, and Chih-Jen Lin.
A Comparison of Optimization Methods and Software for Large-scale
L1-regularized Linear Classification, Journal of Machine Learning, 2010.

This code has been tested under 64-bit Linux environments with
Python 2.6, MATLAB R2008b and R 2.9.

You will be able to regenerate results in the paper. However, results
may be slightly different due to the randomness, the CPU speed, and
the load of your computer. The running time is long as we run every
solver to accurately solve optimization problems.

Please cite the above article if you find this tool useful.
Please also read the COPYRIGHT before using this tool.

Introduction
============

You can choose solvers/data sets for comparisons. See descriptions
in subsequent sections.

We implement CDN and TRON. Other solvers must be downloaded from
their web sites. To obtain function values, testing accuracy,
and number of w's non-zeros after each iteration, we provide patches
and you need to apply them.

Compare Solvers for Logistic Regression w/o Bias: BBR, CDN, SCD, TRON, BMRM
and OWL-QN
===========================================================================

Edit 'compare_lr.py' to indicate solvers for comparison. Comment the
solver that you are not interested in. For example,

#solvers['SCD'] = './SCD/scd'

In the same way, you can exclude some data sets from comparison. For
example,

#bestC['rcv1_test.binary'] = 4.0

After deciding data sets and solvers, you must prepare the data sets
and install the solvers. Please see Sections 'Prepare Data Sets for
Experiments' and 'Installation for Experiments' for more details.

Type

% python ./compare_lr.py

to compare solvers. The results are stored in the 'logLR' directory.

Compare Solvers for Logistic Regression w/ Bias: CDN, CGD-GS, IPM, GLMNET
and Lassplore
=========================================================================

Edit 'compare_lrb.py' to indicate solvers and data sets for comparison.
See the section for 'compare_lr.py' for details.

Type

% python ./compare_lrb.py

to compare solvers. The results are stored in the 'logLRb' directory.

Compare Solvers for L2-loss SVM w/o Bias: CDN, TRON and BMRM
============================================================

Edit 'compare_svm.py' to indicate solvers and data sets for comparison.
See the section for 'compare_lr.py' for details.

Type

% python ./compare_svm.py

to compare solvers. The results are stored in the 'logSVM' directory.

Prepare Data Sets for Experiments
=================================

Due to different data formats used by solvers, MATLAB scripts in
'tools' directory convert data from libsvm format to others. Edit
'tools/Makefile' to give the proper MATLAB path and edit
'gen_data.py' to indicate data sets for generation.

Type

% python ./gen_data.py

The script will build 'tools/libsvmread.mex*' and download a MATLAB
script 'tools/mmwrite.m' for data format conversion. After, the script
will download three data sets (a9a, real-sim and news20.binary) from
LIBSVM Data page and do a 80/20 split for training and testing. It
then stores *.train and *.test in the 'data' directory and converts
them to different format.

Note that you need bunzip2, which is called by gen_data.py

Install CDN for Experiments
===========================

% cd liblinear
% make clean all

Install TRON for Experiments
============================

TRON for logistic regression
% cd tron/tron-lr
% make clean all

TRON for L2-loss SVM
% cd tron/tron-l2svm
% make clean all

Install BBR for Experiments
===========================

Check out a working copy from SVN server by
% svn checkout http://bbrbmr.googlecode.com/svn/trunk/ BBR

Note that the patch only works for version 4.03 of BBR.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% cd BBR
% patch -p1 < ../patch/BBR.patch
% cd gcc

Modify Lines 2-4 in Makefile with your own paths.

% make

Install SCD for Experiments
===========================

Download the .tar.gz file from
http://ttic.uchicago.edu/~tewari/code/scd/scd.tar.gz

Note that the patch only works for a specific version of SCD.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% tar xvzf scd.tar.gz
% cd SCD
% patch -p1 < ../patch/SCD.patch
% make

Install OWL-QN for Experiments
==============================

Download the .zip file from
http://research.microsoft.com/en-us/um/people/jfgao/

Note that the patch only works for version 1.1.2 of OWL-QN.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% unzip -d OWL-QN OWLQN.zip
% cd OWL-QN
% patch -p1 < ../patch/OWL-QN.patch
% cd source
% make

Install CGD-GS for Experiments
==============================

Download the .zip file from
http://www.math.nus.edu.sg/~matys/cgd_logreg.zip

Note that the patch only works for a specific version of CGD-GS.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% unzip cgd_logreg.zip
% cd cgd_logreg
% patch -p1 < ../patch/CGD.patch

Adjust MATLAB path in Makefile if needed.

% make

Install IPM for Experiments
===========================

Download the .tar.gz file from
http://stanford.edu/~boyd/l1_logreg/download/l1_logreg-0.8.2.tar.gz

Note that the patch only works for version 0.8.2 of IPM.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% tar xvzf l1_logreg-0.8.2.tar.gz
% cd l1_logreg-0.8.2
% patch -p1 < ../patch/IPM.patch
% ./configure
% make

Install GLMNET for Experiments
==============================

Download the .tar.gz file from
http://cran.r-project.org/src/contrib/glmnet_1.5.tar.gz

Note that the patch only works for version 1.5 of GLMNET.
Once GLMNET is upgraded, the link above may be broken.
Please find version 1.5 of GLMNET at the CRAN archive
http://cran.r-project.org/src/contrib/Archive/glmnet

% tar xvzf glmnet_1.5.tar.gz
% cd glmnet
% patch -p1 < ../patch/glmnet.patch
% cd ..
% tar cvzf glmnet_1.5.tar.gz glmnet
% R CMD INSTALL -l lib glmnet_1.5.tar.gz

Note that the following R packages are required: SparseM, Matrix and
e1071. They are available at http://cran.r-project.org/web/packages/.
To install them, the command is similar to the above. For instance,

% R CMD INSTALL -l lib e1071_1.5-20.tar.gz

Install Lassplore for Experiments
=================================

Download the .zip file from
http://www.public.asu.edu/~jye02/Software/lassplore/lassplore.zip

Note that the patch only works for version 1.0 of Lassplore.
If you find the patch does not work, please email cjlin@csie.ntu.edu.tw
% unzip lassplore.zip
% cd lassplore
% patch -p1 < ../patch/Lassplore.patch
% cd lassplore
% make

Generate Figures
================

To generate Figures 1-4, please type

% python figure.py lr

To generate Figures 5-8 and 9-10, type, respectively,

% python figure.py lrb
% python figure.py svm

The output figures are stored in the 'figures' directory.
