************************************************************************                                                         
                               README                                   

        C++ code for Stochastic Variance Reduced Gradient (SVRG)
                            November 2013                                                                   
************************************************************************

Contents:
---------

1. Introduction
2. Creating the Executable
3. Usage
4. Data format
4.1. Data points
4.2. Target values
5. Origin of sample data
6. Contact
7. Copyright
8. References

---------------
1. Introduction
This software package provides implementation of the convex case (linear predictors) of stochastic variance reduced gradient (SVRG) described in [1].  Implementation of the non-convex case (neural network) is not included in this package.  

--------------------------
2. Creating the Executable 

You need to build your executable from the source code.  A make file "makefile" is provided at the top directory.  It is configured to use "g++".  You may need to customize "makefile" for your environment.  

To build the executable, change the current directory to the top directory and enter in the command line "make". Check the "bin" directory to make sure that your new executable "linsvrg" is there.  

----------------
3. Usage

Usage:  linsvrg  parameters
               or 
        linsvrg  @parameter_filename
               or 
        linsvrg
    
parameters: keyword-value pairs (e.g., "num_iterations=50") and options (e.g., "ShowLoss") delimited by ",".  Sample shell scripts can be found at sample/.  

parameter_filename: If the argument begins with '@', the rest is regarded as the pathname to a parameter file; e.g., if the argument is "@test.param", the file "test.param" will be scanned for parameters.  In the parameter file: parameters should be delimited by newline characters; anything that begins with "#" is regarded as comments.  Sample parameter files can be found at sample/param/.  

To get help on parameters, call linsvrg without any argument.  

----------------
4. Data format 
 
Sample data files are provided at sample/data/.  A sample perl script "convert_libsvmdata.pl" to convert LIBSVM format to the linsvrg format described below is provided at sample/.   

4.1 Data points
[Dense format]
The data points (or feature vectors) should be given in a plain text file of the following format. Each line represents one data point. In each line, values should be separated by one or more white space characters.  All the lines should have exactly the same number of values. The values should be in the format that is recognized as valid floating-point number expressions by atof of C libraries. The following example represents three data points of five 
dimensions.

  0.3   -0.5  1  0   2
  1.555 0     0  2.8 0
  0     0     0  3   0

[Alternative data format for sparse data points]
For sparse data which has many zero components (e.g., bag-of-word data), the following format can be used instead. The first line should be “sparse d” where d is the feature dimensionality. Starting from the second line, each line represents one data point. In each line, non-zero components should be specified as feature#:value where feature# begins from 0 and goes up to d-1.  For example, the three data points above can be expressed as:
 
  sparse 5
  0:0.3  1:-0:5  2:1   4:2
  0:1.555  3:2.8
  3:3
  
4.2 Target values
[Classification]
For classification tasks, each line of the target file should contain a class label of one data point.  The order must be in sync with the data point file.  The class labels must be integers starting from 0; e.g., if the task is 3-way classification, the class labels should be 0, 1, and 2.  

[Regression]  
For regression tasks, each line of the target file should contain one target value of one data point.  The order must be in sync with the data point file. 

----------------
5. Origin of sample data 
The covtype dataset provided at sample/data/ is originally from the UCI repository [2].  
These files were generated by converting the LIBSVM scaled version downloadable at 

  http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary.html#covtype.binary  

to the format described above and randomly dividing into training data and test data.  These files were used in [1].  

----------
6. Contact 
riejohnson@gmail.com

------------
7. Copyright
SVRG C++ code is distributed under the GNU public license. Please read the file COPYING.

-------------
8. References

[1] Rie Johnson and Tong Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  NIPS 2013. 
[2] UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml/