Stochastic Gradient Descent (v.2)

Learning algorithms based on Stochastic Gradient approximations are known for their poor performance on optimization tasks and their extremely good performance on machine learning tasks (Bottou and Bousquet, 2008). Despite these proven capabilities, there were lingering concerns about the difficulty of setting the adaptation gains and achieving robust performance. Stochastic gradient algorithms have been historically associated with back-propagation algorithms in multilayer neural networks, which can be very challenging non-convex problems. Stochastic gradient algorithms are also notoriously hard to debug because they often appear to somehow work despite the bugs. Experimenters are then led to believe, incorrectly, that the algorithm itself is flawed.

Therefore it is useful to see how Stochastic Gradient Descent performs on simple linear and convex problems such as linear Support Vector Machines (SVMs) or Conditional Random Fields (CRFs). This page proposes simple code examples illustrating the good properties of stochastic gradient descent algorithms. The provided source code values clarity over speed.

• The first release of this code (2007) was written to accompany my 2007 NIPS tutorial on large scale learning.

• The second major release of this code (2011) adds a robust implementation of the averaged stochastic gradient descent algorithm (Ruppert, 1988) which consists of performing stochastic gradient descent iterations and simultaneously averaging the parameter vectors over time. When the stochastic gradient gains decrease with an appropriately slow schedule, Polyak and Juditsky (1992) have shown that the convergence is asymptotically as efficient as second-order stochastic gradient descent with much smaller computational costs. One can therefore hope to match the batch optimization performance after a single pass on the randomly shuffled training set (Fabian, 1978; Bottou and LeCun, 2004). Achieving one-pass learning in practice remains difficult because one often needs more than one pass to simply reach this favorable asymptotic regime. The gain schedule has a deep impact on this convergence. Finer analyses (Xu, 2010; Bach and Moulines, 2011) reveal useful guidelines to set these learning rates. Xu (2010) also describe a wonderful way to efficiently perform the averaging operation when the training data is sparse. On problems with moderate dimension, the resulting algorithm reaches near-optimal test set performance in one or two passes. When the dimension increases, the advantage erodes, but the algorithm remains competitive.

• Create a clone of the git repository with command:

     git clone http://leon.bottou.org/git/sgd.git

• As an alternative, you can still download the tarball sgd-2.1.tar.gz released in September 2012. This is no longer the recommended approach but should still work.
• Make sure to read the files “README.txt” and “data/README.txt”.

• Download the following files from the RCV1-V2 web site and install them in directory “data/rcv1”.
  • lyrl2004_tokens_test_pt0.dat.gz, lyrl2004_tokens_test_pt1.dat.gz
  • lyrl2004_tokens_test_pt2.dat.gz, lyrl2004_tokens_test_pt3.dat.gz
  • lyrl2004_tokens_train.dat.gz, rcv1-v2.topics.qrels.gz

• Download the following files from the Pascal Large-Scale Challenge server and install them in directory “data/pascal”.
  • convert.py, alpha_train.lab.bz2, alpha_train.dat.bz2 (860MB)
  • Optionally, webspam_train.lab.bz2, webspam_train.dat.bz2 (1.5GB)

• Download the following files from the CONLL2000 Chunking web site and install them in directory “data/conll2000”.
  • train.txt.gz, test.txt.gz

• Run the conversion script for the Pascal datasets. This requires Python and takes some time.

   $ cd data/pascal
   $ ./convert.py -o alpha.txt alpha train
   $ ./convert.py -o webspam.txt webspam train    # (optional)

• To compile under Linux, simply type “make” in the toplevel directory. The compilation requires the ZLib library. Most Linux distributions provide this by default. Things should be very similar under other Unix operating systems.
• To compile under Windows, see the file “win/README.txt”.

The SVM programs are located in directory “sgd/svm”. The file “svm/README.txt” provides the full details and describes how to run various experiments.

Program “svmsgd” implements a straightforward stochastic gradient descent algorithm.

1. The learning rate has the form η₀ / (1 + λ η₀ t) where λ is the regularization constant.
2. The constant η₀ is determined by performing preliminary experiments on a data subsample.
3. The learning rate for the bias is multiplied by 0.01 because this frequently improves the condition number.
4. The weights are represented as the product of a scalar and a vector in order to easily implement the weight decay operation that results from the regularization term.

Points (1) and (4) follow (Shalev-Schwartz et al., 2007).

Program “svmasgd” implements the averaged stochastic gradient descent algorithm.

1. The learning rate has the form η₀ / (1 + λ η₀ t) ^0.75 where λ is the regularization constant.
2. The constant η₀ is determined by performing preliminary experiments on a data subsample.
3. Averaging starts only at the second epoch. The first epoch is a simple stochastic gradient descent. This provides more robust convergence at the expense of one additional epoch. You can use option -avgstart to change this.
4. Both the stochastic gradient weights and the averaged weights are represented using a linear transformation that yields efficiency gains for sparse training data.

Points (1) and (4) follow (Xu, 2010).

The benchmark task is the recognition of RCV1 documents belonging to the class CCAT. Program “prep_rcv1” reads the RCV1-V2 token files from directory “data/rcv1” and computes the TF/IDF features on the basis of the our training set. This programs produces the two files “rcv1.train.bin.gz” and “rcv1.test.bin.gz” containing our training and testing sets. This short program also generates files in SvmLight format when compiled with option -DPREP_SVMLIGHT.

¹ Extrapolated from a 23642 seconds run on a 30% slower machine.
² Extrapolated from a 66 seconds run on a 30% slower machine.
^* All timings exclude data loading time.

You must first convert the original Pascal files using the Python script convert.py as explained above. Program “prep_alpha” then reads the converted Pascal file “data/pascal/alpha.txt” and produces the two files “rcv1.train.bin.gz” and “rcv1.test.bin.gz” containing our training and testing sets. The alpha dataset illustrates how ASGD sometimes vastly outperforms plain SGD. The plot below shows how ASGD reaches near-optimal test performance only one pass after the activation of the averaging code (epoch 2.)

The CRF programs “crfsgd” and “crfasgd” respectively use the SGD and ASGD algorithms to train a Conditional Random Field. The algorithms are setup exactly as the SVM variants, but the implementation accounts for the greater structural complexity of conditional random fields. Both programs accept the same input files as the well known CRF++ software by Taku Kudo. They produce the same tagging files which can be analyzed using the CONLL perl script “conlleval”. They use the same template files to specify the features and accept the same data files. For convenience, “crfsgd” and “crfasgd” can also directly read gzipped data files. See the CRF++ documentation for details.

Our CRF benchmark is the CONLL2000 Text Chunking task, which consists of dividing a text in syntactically correlated segments (noun phrases, verb phrases, etc.). We use the feature template that comes with CRF++.

³ Extrapolated from a 4335 seconds run on a 30% slower machine.

Rather than emphasizing performance or generality, this code favors readability. I am therefore glad to see that many authors of machine learning projects have found it useful, sometimes directly, sometimes as a source of inspiration. Here are a few links:

• Implicit SGD uses the SVMSGD code as a starting point.
• SciKit contains a SGD optimizer inspired by SVMSGD.
• Shogun contains a SGD module derived from SVMSGD.
• Vowpal Wabbit goes to great lengths to go faster than SVMSGD
• Stanford's JavaNLP project found inspiration in CRFSGD.
• …