An Adaptive Algorithm for Learning with Unknown Distribution Drift
This work addresses the challenge of distribution drift in machine learning for scenarios where drift magnitude is unknown, offering an incremental improvement over existing methods by adapting to data without explicit drift estimation.
The paper tackles the problem of learning with unknown distribution drift by introducing an adaptive algorithm that does not require prior knowledge of drift magnitude, achieving error rates comparable to algorithms that know the drift in advance, with applications in binary classification and linear regression.
We develop and analyze a general technique for learning with an unknown distribution drift. Given a sequence of independent observations from the last $T$ steps of a drifting distribution, our algorithm agnostically learns a family of functions with respect to the current distribution at time $T$. Unlike previous work, our technique does not require prior knowledge about the magnitude of the drift. Instead, the algorithm adapts to the sample data. Without explicitly estimating the drift, the algorithm learns a family of functions with almost the same error as a learning algorithm that knows the magnitude of the drift in advance. Furthermore, since our algorithm adapts to the data, it can guarantee a better learning error than an algorithm that relies on loose bounds on the drift. We demonstrate the application of our technique in two fundamental learning scenarios: binary classification and linear regression.