# An Improved Algorithm for Learning Drifting Discrete Distributions

arXiv: https://arxiv.org/abs/2403.05446 · HTML: https://mlsanity.com/paper/2403.05446/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 8 Mar 2024.

## Builds on (most cited first, 5 of 5)

- [Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods](https://mlsanity.com/paper/2002.11955/) (2020)
- [An Adaptive Algorithm for Learning with Unknown Distribution Drift](https://mlsanity.com/paper/2305.02252/) (2023)
- [Statistical Learning under Nonstationary Mixing Processes](https://mlsanity.com/paper/1512.08064/) (2015)
- [Learning with a Drifting Target Concept](https://mlsanity.com/paper/1505.05215/) (2015)
- [Nonparametric Density Estimation under Distribution Drift](https://mlsanity.com/paper/2302.02460/) (2023)

## Built on by (most cited first, 2 of 2)

- [Momentum LMS Theory beyond Stationarity: Stability, Tracking, and Regret](https://mlsanity.com/paper/2602.11995/) (2026)
- [Dynamic estimation of slowly varying sequences](https://mlsanity.com/paper/2606.23655/) (2026)

## Abstract (arXiv)

We present a new adaptive algorithm for learning discrete distributions under distribution drift. In this setting, we observe a sequence of independent samples from a discrete distribution that is changing over time, and the goal is to estimate the current distribution. Since we have access to only a single sample for each time step, a good estimation requires a careful choice of the number of past samples to use. To use more samples, we must resort to samples further in the past, and we incur a drift error due to the bias introduced by the change in distribution. On the other hand, if we use a small number of past samples, we incur a large statistical error as the estimation has a high variance. We present a novel adaptive algorithm that can solve this trade-off without any prior knowledge of the drift. Unlike previous adaptive results, our algorithm characterizes the statistical error using data-dependent bounds. This technicality enables us to overcome the limitations of the previous work that require a fixed finite support whose size is known in advance and that cannot change over time. Additionally, we can obtain tighter bounds depending on the complexity of the drifting distribution, and also consider distributions with infinite support.