Are there any online learning algorithm that do not depend on the order of arrival of the data ?

I am looking for algorithms that, given a sequence of data $(x_i,y_i)_{i\in[1,n]}$ :

  • Will produce the same result as they would after the last step of training on a permutation of the training set $(x_{\sigma(i)},y_{\sigma(j)})_{i\in[1,n]}$

  • Admit a training via update step when they receive a new point

It is easy to verify, that linear regressions, per example, have the first property, and the online learning algorithms (FTRL, perceptron...) have the second one.

Naive Bayes algorithms, per example, can be implemented in an streaming manner and the models produced will be indentical (since the estimation of probabilities will not depend on the order of the observations), and they will have the two properties.

Nearest centroid classifier (wikipedia article) can enjoy such a representation as well.

Are there other methods satisfying these two requirements ?

  • $\begingroup$ This question would benefit from being narrowed or focused. Consider any static method that applies to all $n$, is independent of the order of the data, and updates its results from $n-1$ values to $n$ values by applying the method to those $n$ values. It will trivially have all properties you ask of it. This includes almost every method ever invented for making predictions or estimates about a population based on a random sample of it. $\endgroup$ – whuber May 22 '17 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.