Online (and Offline) on an Even Tighter Budget

Jason Weston, Antoine Bordes and Leon Bottou

AISTATS 2005

Timing comparison

USPS digit 0 vs rest

Here are timings on USPS digit 0 vs rest, comparing SVM, Perceptron, Budget Perceptron and Tighter Budget Perceptron. The Tighter Budget Perceptron does not have a secondary cache (it uses all points to evaluate the error) so could be faster.


Algorithm
Time
SVs
Error
SVM (*)
17 secs
241
0.51%
Perceptron (1 epoch)
27 secs
128
0.76%
Perceptron (10 epochs)
103 secs
225
0.71%
Budget Perceptron (cache size 85) 69 secs
85
9.4%
Budget Perceptron (cache size 60)
64 secs
60
3.15%
Tighter Budget Perceptron (cache size 85) 40 sec
85
0.71%
Tighter Budget Perceptron (cache size 60) 47 secs
60
1.07%

(*) Note that SVM is the time given by SVM-Light, optimized C code, the other algorithms are unoptimized (Matlab) code.

These are timings of only a single run, so the error rates should be viewed with caution (see the paper for results averaged over 10 splits.) This explains why the Budget Perceptron results fluctuate so much in the tabes (they have very high variance.)

Banana

Here are timings on banana dataset (a much noisier problem), comparing SVM, Perceptron, Budget Perceptron and Tighter Budget Perceptron. The Tighter Budget Perceptron again does not have a secondary cache.

Algorithm
Time
SVs
Error
SVM (*)
322 secs
862
10.15%
Perceptron (1 epoch)
5.62 secs
583
11.54%
Perceptron (10 epochs)
61 secs
962
13.77%
Budget Perceptron (cache size 300) 29 secs
300
34.62%
Budget Perceptron (cache size 100)
20 secs
100
47.46%
Tighter Budget Perceptron (cache size 300) 105 secs
300
10.08%
Tighter Budget Perceptron (cache size 100) 52 secs
100
11.54%

Conclusions

These timing experiments show that the Tighter Budget is not necessarily slower than the Budget Perceptron, despite having much more accurate performance (faster on the clean problem, slower on the noisy problem, but on the noisy problem the Budget Perceptron simply does not work). On noisy problems, it also improves over the accuracy of the Perceptron, while remaining competitive with an SVM, even with optimized SVM code, and unoptimized (Matlab) code for the Tighter Budget algorithm itself.

There are many ways to improve the timings reported here, apart from optimizing the code itself, including: (i) adding the secondary cache or (ii) removing more than one point at a time, etc..


Click here to go back to the main page.