SGDClassifier: Online Learning/partial_fit with a previously unknown label My training set contains about 50k entries with which I do an initial learning. On a weekly basis, ~ 5k entries are added; but the same amount "disappears" (as it is user data which has to be deleted after some time).

Therefore I use online learning because I do not have access to the full dataset at a later time. Currently I'm using an SGDClassifier which works, but my big problem: new categories are appearing and now I can't use my model any more as they were not in the initial fit.

Is there a way with SGDClassifier or some other model? Deep learning?

It doesn't matter if I have to start from scratch NOW (i.e. use something other than SGDClassifier), but I need something which enables online learning with new labels.
It sounds like you don't want to start retraining the model every time a new label category appears. The easiest way to retain maximal information of past data would be train one classifier per category. 

This way you can continue to train each classifier incrementally ("online") with something like SGDClassifier without having to retrain them. 
Whenever a new category appears you add a new binary classifier for just that category. You then select the class with the highest probability/score among the set of classifiers.

This is also not much different from what you are doing today, because scikit's SDGClassifier already handles the multiclass-scenario by fitting multiple "One vs All" classifiers under the hood. 

If a lot of new categories keep coming up, of course, this approach might become a little tricky to manage.