[KDD 2020] From Online to Non-i.i.d. Batch Learning
Aug 13, 20201 views
This paper initializes the study of,online-to-batch conversion,when,the samples in batch learning are,not,i.i.d. Our motivation originated from two facts. First, sample sets in reality are seldom i.i.d.,,thus preventing the application of the existing conversions. Second,,the online model of learning permits an,adversarial,stream of samples that almost for sure violates the i.i.d. assumption, raising the,possibility of adapting an online algorithm effectively to learn from,a non-i.i.d. sample set. We present a set of techniques to utilize an,online algorithm as a,black box,to perform batch learning in the,absence of the i.i.d. assumption. Our techniques are generic, and,are applicable to virtually any online algorithms on classification.,This provides strong evidence that the great variety of known algorithms in the online-learning literature can indeed be harnessed to,learn from sufficiently-representative non-i.i.d. samples.