apparently i underestimated it.
I timed it on my computer (in a vm): Training with T=5000, then testing accuracy on both the whole validation and training sets takes about 10 minutes.
This makes sense since the non-kernel version takes about 1.4 seconds. (1.4 * 5000 is around 11 minutes)
Since it is stochastic, I do 10 such runs for each eta/C combination - already 1.5 hours
To do anything meaningful, then would take multiple hours or even multiple days…
So either I should do less tests, lower T, or I have some error with the algorithm, although the linear growth with T seems inevitable (as it was with kernel perceptron)
(memoization is possible if we derandomize the tests but it means holding $O(T\cdot(|train-set|+|validation-set|))$ float values which is also infeasible)
from what i've read, sometimes a limit is placed where we throw out old values, since very old values have very small weight (assuming $0<\eta<1$)
perceptron weasley (guest) 23 Dec 2016 22:21
