New analysis and algorithm for learning with drifting distributions

DOI10.1007/978-3-642-34106-9_13MaRDI QIDQ3164815zbMATH OpenOpenAlexFDO

Authors Mehryar Mohri, Andrés Muñoz Medina

Publication date 16 October 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.4343

zbMATH Keywords

domain adaptationdrifting environmentgeneralization bound

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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.

Recommendations

• On the complexity of learning from drifting distributions
• Learning with a drifting target concept
• Advances in Artificial Intelligence – SBIA 2004
• The complexity of learning according to two models of a drifting environment
• Learning changing concepts by exploiting the structure of change

Cited in

(16)

• On the complexity of learning from drifting distributions
• The complexity of learning according to two models of a drifting environment
• Detecting virtual concept drift of regressors without ground truth values
• Marginal singularity and the benefits of labels in covariate-shift
• Adaptive transfer learning
• A no-free-lunch theorem for multitask learning
• Handling concept drift via model reuse
• Discrepancy-based theory and algorithms for forecasting non-stationary time series
• Generalization bounds for non-stationary mixing processes
• Learning with a drifting target concept
• Learning from non-iid data: fast rates for the one-vs-all multiclass plug-in classifiers
• Domain adaptation and sample bias correction theory and algorithm for regression
• Best-effort adaptation
• An adaptive transfer learning perspective on classification in nonstationary environments
• Adaptive smooth nonstationary bandits
• Supervised learning with evolving tasks and performance guarantees

This page was built for publication: New analysis and algorithm for learning with drifting distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3164815)