Regularization and feature scaling in online learning? Let's say I have a logistic regression classifier. In normal batch learning, I'd have a regularizer term to prevent overfitting and keep my weights small. I'd also normalize and scale my features.
In an online learning setting, I'm getting a continuous stream of data. I do a gradient descent update with each example and then discard it. Am I supposed to use feature scaling and regularization term in online learning? If yes, how can I do that? For example, I don't have a set of training data to scale against. I also don't have validation set to tune my regularization parameter. If no, why not?
In my online learning, I get a stream of examples continuously. For each new example, I do a prediction. Then in the next time step, I get the actual target and do the gradient descent update.
 A: The open-source project vowpal wabbit includes an implementation of online SGD which is enhanced by on the fly (online) computation of 3 additional factors affecting the weight updates. These factors can be enabled/disabled by their respective command line options (by default all three are turned on, the --sgd option, turns them all off, i.e: falls-back on "classic" SGD).
The 3 SGD enhancing options are:


*

*--normalized updates adjusted for scale of each feature

*--adaptive uses adaptive gradient (AdaGrad) (Duchi, Hazan, Singer)

*--invariant importance aware updates (Karampatziakis, Langford)


Together, they ensure that the online learning process does a 3-way automatic compensation/adjustment for:


*

*per-feature scaling (large vs small values)

*per-feature learning rate decay based on feature importance

*per feature adaptive learning rate adjustment for feature prevalence/rarity in examples


The upshot is that there's no need to pre-normalize or scale different features to make the learner less biased and more effective.
In addition, vowpal wabbit also implements online regularization via truncated gradient descent with the regularization options:


*

*--l1 (L1-norm)

*--l2 (L2-norm)


My experience with these enhancements on multiple data-sets, was that they significantly improved model accuracy and smoother convergence when each of them was introduced into the code.
Here are some academic papers for more detail related to these enhancements:


*

*Online Importance Weight Aware Updates by Nikos Karampatziakis and John Langford + Slides of talk about this paper

*Sparse online learning via truncated gradient by John Langford, Lihong Li, and Tong Zhang

*Adaptive Subgradient Methods for Online Learning and Stochastic Optimization by John Duchi, Elad Hazan, Yoram Singer

A: This paper describes a technique for online regularization which they apply to various algorithms, including logistic regression: http://ai.stanford.edu/~chuongdo/papers/proximal.pdf
A: yes you certainly need regularisation... it also helps the gradient descent ( and initialise learning rate to 1/C)
see eg SGD-QN paper http://leon.bottou.org/papers bottou's papers
you haven't really explained what you mean by online learning: eg for each point do you get target value? 
I don't know how you would incorporate... searching for C ... I guess you would have multiple classifiers with different regularisation terms and track the prediction error ( before you update weights)
