npinto/asgd — Issue #15: re-parameterize annealing schedule
Author: jaberg
Created: 2012-01-17 23:42:09+00:00
State: open

Remember the previous discussion we had about whether the l2_regularization parameter should be allowed to be 0? I think that was related to a mis-parameterization of the BaseASGD object.

Background: the schedule implemented takes the form C(t) = C0 (1 + C0 k t)^a, where `C0` is the initial sgd step size, `t` is the number of iterations so far, `a` is the annealing exponent, and `k` is an extra multiplier on the time. This form is recommended in [1].

The current naive_asgd implementation hardcodes k = l2_regularization, as suggested in [2].

This leads to weirdness though because `C0` is typically like 1e-2 or 1e-3, and `l2_regularization` should usually be something like 1e-6. In the most aggressive case we end have a schedule like

`C(t) = C0 (1 + 1e-8 t)^a`

For a normal choice of `a=.5` this is basically un-annealed SGD, since it takes 100 million examples to get the learning rate from C0 down to C0/sqrt(2). I'm not that confident in saying it, but I don't think this was how the annealing was meant to be used.

I think this could be improved in two ways:

1. removing the second appearance of `C0` from the annealing schedule (simplify things... why put it in twice? and It is not used in [3])

2. make `k` default to `C0`, rather than `l2_regularization`

3. make `k` a parameter of BaseASGD because both [2] and [3] say it's problem-dependent.

[1] http://arxiv.org/pdf/1107.2490v2
[2] http://www.dbs.ifi.lmu.de/~yu_k/cvpr11_0694.pdf
[3] http://hal.archives-ouvertes.fr/docs/00/60/80/41/PDF/gradsto_hal.pdf