New Analysis and Algorithm for Learning with Drifting Distributions

By Mehryar Mohri, Andrés Muñoz Medina. 2012

140 citations recorded by the source corpus.

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 L1 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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Three Approaches for Personalization with Applications to Federated Learning (2020, methodology): “For two distributions over features and labels, D1 and D2, and a class of hypothesesH, label-discrepancy(Mohri and Medina, 2012) is given by discH(D1,D2) = max h∈H ∣LD1(h) −LD2(h)∣.”
Task-Free Continual Learning via Online Discrepancy Distance Learning (2022, neutral): “In addition, the study from [4], similarly to [30, 33], only provides a theoretical guarantee for a single model.”
Robust Learning from Untrusted Sources (2019, methodology): “Following (Mohri & Medina, 2012), we deﬁne the discrepancy between the distributions D i and D T with respect to the hypothesis class H as: (3) Intuitively, the discrepancy between the two distributions is large, if there exists a predictor that performs well on one of them and badly on the other.”
FedBoost: Communication-Efficient Algorithms for Federated Learning (2020, unknown): “• Adaptation or drifting over time: user data may change over time, but, in the ensemble approach, we can keep the base predictors fixed and retrain the ensemble weights whenever the data changes (Mohri & Medina, 2012).”
Learning with Feature and Distribution Evolvable Streams (2020, methodology): “After that, Mohri & Medina (2012) use the Y -divergence to provide a tighter learning guarantee.”
Bridging Theory and Algorithm for Domain Adaptation (2019, background): “Mohri & Medina (2012); Zhang et al. (2012) proposed Y -disc for domain adaptation with partially labeled target data.”
A No-Free-Lunch Theorem for MultiTask Learning (2020, background): “…discrepancy is typically taken to be total-variation (Ben-David, Benedek and Mansour, 1989; Bartlett, 1992; Barve and Long, 1997) or related notions (Mohri and Medina, 2012; Hanneke and Yang, 2019), both our upper and lower-bounds, specialized to the case n = 1 , provide a new perspective for…”
On the Sample Complexity of Adversarial Multi-Source PAC Learning (2020, background): “…distance between two datasets, S i and S j , is deﬁned as This is the empirical counterpart of the so-called discrepancy distance, which, together with its unsupervised form, is widely adopted within the ﬁeld of domain adaptation (Kifer et al., 2004; Ben-David et al., 2010; Mohri & Medina, 2012).”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, unknown): “By symmetrization [33], we have where (cid:12)(cid:12) (cid:12)(cid:12) Following (18), by Talagrand’s lemma (Lemma 5.7) in [34] together with Cauchy-Schwartz, Jensen’s inequality, we have M - Lipschitz in the scalar argument and zero when the scalar argument is zero.”
Domain adaptation and sample bias correction theory and algorithm for regression (2014, background): “Finally, the notion of discrepancy and its extensions similarly play a critical role in the analysis of learning with drifting distributions [22], a scenario that is closely related to those of domain adaption and sample bias correction.”
Adaptation Based on Generalized Discrepancy (2019, methodology): “The Y-discrepancy was first introduced by Mohri and Muñoz (2012) in the context of learning with drifting distributions.”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “Additionally, our findings can be valuable in non-i.i.d. learning settings, such as drifting (Mohri & Medina, 2012) or time series prediction (Kuznetsov & Mohri, 2018; 2020).”
Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees (2022, unknown): “…for the drifting scenario provide bounds for instantaneous error probabilities with respect to empirical risks (generalization bound) (Long, 1999; Mohri & Medina, 2012), while existing methods based on online learning and regret minimization provide bounds for accumulated mistakes with respect…”
On the Value of Target Data in Transfer Learning (2020, background): “The most common such measures are the so-called dA-divergence [3, 4, 5] and the Y-discrepancy [6, 7, 8].”
On Localized Discrepancy for Domain Adaptation (2020, background): “Mohri and Medina (2012) adapts the discrepancy to domain adaptation problem with available target labeled data.”
Time series prediction and online learning (2016, methodology): “In this section we present the applications of our theory to two problems: model selection and the design of ensemble solutions in time series prediction.”
Adaptation Algorithm and Theory Based on Generalized Discrepancy (2014, methodology): “Tighter bounds than those of Mansour et al. (2009) are given by Mohri and Mu˜noz (2012) via the use of the Y -discrepancy,”