[ogrisel]

Thanks for the reply. I was told by twitter that this is similar to the kernel perceptron which I don't know well either. There is a good introduction with python code snippet here:

http://www.mblondel.org/journal/2010/10/31/kernel-perceptron...

However it seems that you need to compute the kernel expansion on the full set of samples (or maybe just the accumulated past samples?): this does not sound very online to me...

[sparsevector]

It's true you need to compute the kernel dot product between every example you see and every example in the support set (every example that ever previously evaluated to signed margin < 1). Whether it's online depends on your definition of "online" . It's definitely not online in the sense of using memory independent of the number of examples, since you have to keep around the support set. I think there are results showing the support set grows linearly with the size of the training set under reasonable assumptions. However, it is online in the sense that it operates on a stream of data, computing predictions and updates for each example one-by-one. It's also online in the sense that its analysis is based on online learning theory (e.g. mistake / regret bounds). A lot of learning theory papers use "online" in the latter two senses, which is confusing if you expect the former.