TY - GEN
T1 - New analysis and algorithm for learning with drifting distributions
AU - Mohri, Mehryar
AU - Muñoz Medina, Andres
PY - 2012
Y1 - 2012
N2 - We present a new analysis of the problem of learning with drifting distributions in the batch setting using the notion of discrepancy. We prove learning bounds based on the Rademacher complexity of the hypothesis set and the discrepancy of distributions both for a drifting PAC scenario and a tracking scenario. Our bounds are always tighter and in some cases substantially improve upon previous ones based on the L 1 distance. We also present a generalization of the standard on-line to batch conversion to the drifting scenario in terms of the discrepancy and arbitrary convex combinations of hypotheses. We introduce a new algorithm exploiting these learning guarantees, which we show can be formulated as a simple QP. Finally, we report the results of preliminary experiments demonstrating the benefits of this algorithm.
AB - We present a new analysis of the problem of learning with drifting distributions in the batch setting using the notion of discrepancy. We prove learning bounds based on the Rademacher complexity of the hypothesis set and the discrepancy of distributions both for a drifting PAC scenario and a tracking scenario. Our bounds are always tighter and in some cases substantially improve upon previous ones based on the L 1 distance. We also present a generalization of the standard on-line to batch conversion to the drifting scenario in terms of the discrepancy and arbitrary convex combinations of hypotheses. We introduce a new algorithm exploiting these learning guarantees, which we show can be formulated as a simple QP. Finally, we report the results of preliminary experiments demonstrating the benefits of this algorithm.
KW - Drifting environment
KW - domain adaptation
KW - generalization bound
UR - http://www.scopus.com/inward/record.url?scp=84867880979&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867880979&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34106-9_13
DO - 10.1007/978-3-642-34106-9_13
M3 - Conference contribution
AN - SCOPUS:84867880979
SN - 9783642341052
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 124
EP - 138
BT - Algorithmic Learning Theory - 23rd International Conference, ALT 2012, Proceedings
T2 - 23rd International Conference on Algorithmic Learning Theory, ALT 2012
Y2 - 29 October 2012 through 31 October 2012
ER -