How do I normalize data in online learning? In offline machine learning, the data normalization of features with different units seem to be simple, we can apply this formula.

But, when using incremental learning (weighted kNN in my case) new instances will be added to the initial training set, so do we use the same formula? if yes which max and min should I use (those of the original training set or the new one)?
 A: In an ideal world, our training data should be representative of the production data, which means that the descriptive statistics (such as the mean, max, or min) should not change too much. Thus, in an "online-learning" environment, we should be able to use the max and min value from the historical training data to do the normalization.
If the training data is not representative of the production data, or we do not know how production data is distributed, the answer is 1. collect data; 2. do "training off line;" and then put into production.
A: One possibility is to update statistics (mean, variance, min, max, etc.) using all historical data in an online manner and use them to normalize your data. Welford's online algorithm is such an example. 
However, this kind of “online” normalization is not injective (if used in a strict online manner). In the sense that two distinct inputs that arrived at different time may be mapped / normalized to the same output value. Furthermore, this mapping / filtering / normalization is not guaranteed to be monotonic (especially in the beginning when very few data have been observed). 
So depending on the scarcity of the data, different strategies can be used. If the data is scarce or the sample efficiency is a crucial criterion, for example in some real life applications, we just use the strict online strategy. Otherwise, for example in cases where there is a simulator to generate data, we may refer to "cold start", we begin with gathering data to have statistics (mean, variance, etc.) that are stable enough before using them to normalize training data. At the training time, training data can be used or not to further adjust / update those statistics depending on the scarcity of the data. At test time, test data will not be used to adjust / update statistics. 
A: I encountered this issue when I put a classifier into production. The two alternatives we considered were:
1. To use historical data's (as has been proposed in other questions) metrics (min, max, sdv) to normalize new coming data.
2. To renormalize all data with the new coming data and recalculate the model.    
Even if option number two is in theory more correct (all data is taken into account for normalization), it brings new issues (recalculation of the model, big delay in classification time). Thus, if a sufficiently big sample has been used in the first normalization, I would NOT look for new normalization parameters each time data is added but use the old ones.
