# Vowpal wabbit and SGD divergence

I have the following vowpal wabbit log. To me it looks quite counter-intuitive: the objective function (l1-regularized hinge loss) seems to go down then suddenly spiking up. I am aware that gradient descent can diverge if the learning rate is too high. What bugs me is this behavior: it tends to converge, then finally diverges. Is this possible for convex functions (it is convex, right?) If the learning rate is not too high initially, and it's decreasing as well as the gradient must, how can it suddenly become too high? What am I missing? Can the vw learning rate decay have something to do with it?

And btw, what's probably wrong with my settings/trainset according to the log? Thanks for your attention.

using l1 regularization = 7.498e-05
final_regressor = /home/mm/models/52.model
Num weight bits = 28
learning rate = 2
initial_t = 0
power_t = 0.5
decay_learning_rate = 1
creating cache_file = /tmp/trtmp.cache
num sources = 1
average    since         example     example  current  current  current
loss       last          counter      weight    label  predict features
0.504495   0.504495           23         2.0   1.0000  -1.0000       16
0.250552   0.000000           68         4.0  -1.0000  -1.0000       15
0.241113   0.232359          143         8.3   1.0000  -1.0000       14
0.311833   0.380056          250        16.9   1.0000  -1.0000       14
0.340020   0.368193          436        33.8  -1.0000  -1.0000        3
0.346579   0.353136          915        67.6  -1.0000  -1.0000       25
0.301540   0.256500         1830       135.2  -1.0000  -1.0000       11
0.253466   0.205517         3625       270.7   1.0000  -1.0000       17
0.225351   0.197240         7251       541.5  -1.0000  -1.0000        2
0.193044   0.160737        14823      1083.1  -1.0000  -1.0000        4
0.171241   0.149439        30096      2166.2  -1.0000  -1.0000       13
0.156050   0.140859        60235      4332.4  -1.0000  -1.0000        3
0.129873   0.103696       120171      8664.8  -1.0000  -1.0000       14
0.110798   0.091725       240159     17330.0   1.0000   1.0000       16
0.104312   0.097826       479570     34660.0  -1.0000  -1.0000        2
0.116619   0.128926       959076     69320.0  -1.0000  -1.0000       18
0.142526   0.168433      1918859    138640.0  -1.0000  -1.0000       14

finished run
number of examples per pass = 62866
passes used = 50
weighted example sum = 227125
weighted label sum = -45425.1
average loss = 0.164373
best constant = -0.2
total feature number = 39394300

• 'learning rate = 2' <- Looks huge indeed Nov 21, 2014 at 9:12

959,783 examples pass between your last line and your second to last line. That's not a "sudden spike", that's a very gradual spike.

1. Set decay_learning_rate = .99 or .95 or .90. This will lower the learning rate over each of the 50 passes.

2. Make sure you are using the latest version of VW (7.10). In 7.4 or 7.7 they added early stopping based on a holdout set, which will prevent this kind of gradual increase in error.

• Thanks, now I see this isn't sudden. And now I'm interested what is the reason. Could you point to certain books/papers maybe that provide theory behind the algorithm (truncaded gradient, if I'm not mistakeb) and in particular, on what conditions doest it converge? Feb 19, 2015 at 9:27
• @alreadyexists I don't have a great technical understanding of the algorithm, sorry. One point is that the model scans through your data one observation at a time, updating the gradient at each observation. This can cause the reported error to jump around a bit, as the model is changing AND the data are changing. At observation 95,9076 the model hasn't even seen half of your data yet, so it's not super surprising that your error on the second half of the dataset was slightly higher than on the first half.
– Zach
Feb 19, 2015 at 21:21
• Also, update to VW 7.10. There's been a lot of bug fixes.
– Zach
Feb 19, 2015 at 21:23
• Also, randomly ordering the rows in your training data can help a lot.
– Zach
Jul 14, 2016 at 14:59