🤖 machine learning

Adaptive Data Admission and Retention for Streaming Federated Learning

This paper proposes an Active-Constraint Drift-Plus-Penalty (ACDPP) framework for streaming federated learning with limited client memory, which jointly optimizes server-side data admission and client-side retention to minimize cumulative excess population risk while satisfying sampling-cost and buffer constraints, achieving sublinear regret guarantees validated by experiments.

Original authors: Zhuoyi Zhao, Ben Liang

Published 2026-07-28✓ Author reviewed ⓘ

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhuoyi Zhao, Ben Liang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where your phone, your smartwatch, and your neighbor's tablet all team up to learn a new skill together, like recognizing different types of clouds or translating slang, without ever showing each other their private photos. This is the magic of Federated Learning. Instead of sending all your data to a giant central computer, the learning happens right on your device. But there's a catch: these devices are like tiny backpacks with limited space. They can't hold every single photo or message they ever see. Plus, grabbing new data isn't free; it might cost battery, data plans, or even require a human to label it, and these costs change depending on the time of day or how busy the network is.

So, we have a tricky puzzle: How do you decide which new pieces of information to let into your backpack, and which old ones to throw out, so you learn the best possible model without running out of space or money? If you keep everything, you run out of room. If you only keep the newest stuff, you might miss out on useful patterns from yesterday. If you only keep the cheapest data, you might end up with a model that's too simple. This paper tackles that exact balancing act, treating data not just as information, but as a resource that needs careful admission and retention management.

The Backpack Problem: A Tale of Too Much Data

Imagine you are the captain of a fleet of 10 tiny, flying scout ships (the clients). Your mission is to build a super-smart map of the galaxy (the global model) by collecting star charts (training data). The problem is, each ship has a very small cargo hold (memory), and every time you pick up a new star chart, it costs fuel (sampling cost). Sometimes the fuel is cheap; other times, it's expensive because of a solar storm (time-varying costs).

If you try to keep every chart you ever see, your cargo hold overflows, and your ship crashes. If you only keep the newest charts, you might forget the old patterns that are actually crucial. And if you only grab charts when fuel is cheap, you might end up with a map that's full of holes.

This is the challenge the authors, Zhuoyi Zhao and Ben Liang, set out to solve. They created a smart system called ACDPP (Active-Constraint Drift-Plus-Penalty) to act as the fleet's traffic controller. Their goal was to figure out exactly how many new charts to admit and which old ones to keep, so the fleet learns the best map possible without running out of fuel or cargo space.

The "K-Step" Rule: A Strict but Fair Librarian

The authors realized that to make the math work, they needed a simple rule for the ships. They invented a "K-step retention policy." Think of this as a strict librarian who says, "Every book you bring in stays on the shelf for exactly K days, and then it must go."

This rule is brilliant because it makes the chaos predictable. If every book stays for exactly 7 days, the librarian knows exactly how many books are on the shelf at any time. It prevents the ships from hoarding the "best" books and throwing away the "bad" ones in a way that creates a messy, unbalanced library. By forcing a uniform lifespan for all data, the system can calculate exactly how much "learning power" it has, even if it's reusing the same old charts.

The Smart Traffic Controller: ACDPP

Now, how does the server (the central command) decide how many new charts to send to each ship? This is where the ACDPP policy shines. It uses a clever trick involving a "debt meter."

Imagine the server has a virtual piggy bank. Every time the fleet spends more fuel than the budget allows, the piggy bank goes into debt (the queue grows). If the fuel is cheap, the debt shrinks. The server looks at this debt meter and the current cost of fuel to make a decision:

If the debt is high (we've been spending too much), the server tightens the rules and admits fewer new charts.
If the debt is low, the server relaxes and lets in more charts to help the ships learn faster.

But here's the twist: the server doesn't just pick a random number. It uses a "time-varying rectangular constraint." Imagine a shrinking box. At the start of the mission, the box is huge, allowing the server to be flexible and adapt to wild changes in fuel costs. But as time goes on, the box slowly shrinks, forcing the server to settle into a steady, optimal rhythm. This ensures that in the long run, the fleet finds the perfect balance between learning speed and cost.

What They Found: Faster, Smarter, and Cheaper

The authors didn't just guess; they proved mathematically that their system works. They showed that their policy gets closer and closer to the performance of a "magic oracle"—a perfect, cost-free system that knows the future and never runs out of space.

In their tests, they ran simulations on three famous image datasets: MNIST (handwritten numbers), CIFAR-10 (tiny color images), and ImageNette (real-world photos).

On the simple MNIST task, their method was about 1.9% to 3.5% more accurate than other methods.
On the harder CIFAR-10 task, the improvement was massive: 26.7% better than a hybrid baseline!
On ImageNette, they saw improvements of 4.1%.

More importantly, their system learned much faster. On MNIST and ImageNette, they reached their target accuracy 2.3 times and 2.2 times faster, respectively, than the next best method. On the difficult CIFAR-10 task, the other methods were so slow they didn't even reach the target accuracy within the time limit, while the ACDPP policy got there easily.

The Verdict: A Balanced Approach

The paper concludes that by combining a strict "keep for K steps" rule with a smart, debt-aware admission controller, you can get the best of both worlds. You get the diversity of fresh data and the efficiency of reusing old data, all while staying within your budget and memory limits.

The authors are very confident in these results, having provided mathematical proofs for their claims. They showed that the "regret" (the difference between their performance and the perfect oracle) grows very slowly, meaning the system gets better and better over time. They also proved that the fuel cost violations stay low and that the memory overflow can be completely controlled by simply choosing the right "K" value before the mission starts.

In short, this paper gives us a blueprint for how to build a fleet of learning robots that are smart enough to know when to grab new data and wise enough to know when to let go, ensuring they learn the most with the least amount of waste.

Technical Summary: Adaptive Data Admission and Retention for Streaming Federated Learning

Problem Statement
This paper addresses the challenge of Streaming Federated Learning (FL) in environments where client devices have limited memory and training data arrives sequentially with time-varying sampling costs. Unlike traditional FL setups with fixed offline datasets, streaming FL involves a continuous flow of new samples that incur acquisition, annotation, or transmission costs. Clients cannot store all historical data indefinitely. Consequently, the system faces a fundamental trade-off: admitting fresh samples improves data diversity and generalization but incurs immediate costs, while retaining and reusing historical samples reduces costs but risks "reuse imbalance" (over-reliance on stale data) and memory overflow.

The core problem is formulated as a constrained stochastic optimization task. The objective is to minimize the cumulative excess population risk (the difference between the learned model's risk and the optimal population risk) subject to two long-term constraints:

Sampling-cost budget: The average cost of admitting samples must not exceed a prescribed limit.
Buffer-occupancy constraint: The average number of samples stored in each client's local buffer must not exceed its memory capacity.

Crucially, the framework decouples control: a central Parameter Server (PS) decides admission quantities (how many new samples to accept), while individual clients independently manage their local buffers (which samples to drop) based on local information, without the PS accessing raw data.

Methodology
The authors propose a unified framework comprising a theoretical learning bound and an online control policy.

Learning-Error Bound Derivation:
The paper first derives an explicit upper bound on the cumulative excess population risk. This bound explicitly characterizes three critical factors:
- Instantaneous training sample size ( $n(t)$ ): The number of samples currently in the buffer used for training.
- Distinct-sample growth ( $N(t)$ ): The cumulative number of unique samples seen.
- Reuse imbalance: The loss of statistical diversity caused by uneven reuse of stored samples.
  To capture this, the authors introduce an effective sample size metric, $\tilde{N}_{eff}(t) = N(t) \cdot \tilde{V}(t)$ , where $\tilde{V}(t)$ is a factor measuring the uniformity of sample reuse. The bound shows that learning performance degrades if sample reuse is highly uneven.
Active-Constraint Drift-Plus-Penalty (ACDPP) Policy:
To optimize the system online, the authors develop the ACDPP policy, which combines:
- Client-Side $K$ -Step Retention: A structured rule where every admitted sample is retained for exactly $K$ rounds before being dropped. This deterministic rule simplifies the reuse pattern, allowing the effective sample size factor $\tilde{V}(t)$ to be expressed in closed form.
- Server-Side Online Admission: A modified Drift-Plus-Penalty (DPP) algorithm. The server maintains a virtual cost-debt queue to track sampling-cost violations. It minimizes a "drift-plus-penalty" expression where the penalty term is a surrogate for the learning-error bound derived earlier.
- Time-Varying Rectangular Constraints: A novel addition to the standard DPP framework. The feasible admission region is constrained within a time-varying interval $[\Lambda_{min}(t), \Lambda_{max}(t)]$ that gradually shrinks toward a target operating point $\bar{\Lambda}$ as time progresses. This design balances early-stage flexibility (to adapt to varying costs) with late-stage stability (to minimize the $1/n(t)$ terms in the error bound).

Key Contributions

Theoretical Characterization: The paper establishes a learning-error bound for memory-based streaming FL that explicitly links performance to instantaneous sample size, distinct sample count, and reuse imbalance via an effective sample size representation.
Algorithm Design: The proposal of the ACDPP policy, which integrates a structured $K$ -step client retention rule with a server-side online admission rule featuring time-varying rectangular constraints.
Performance Guarantees: The authors prove that the proposed policy achieves:
- Sublinear Regret: The cumulative excess risk grows sublinearly relative to a costless oracle benchmark (which has unlimited memory and zero sampling cost).
- Sublinear Cost Violation: The cumulative violation of the sampling-cost budget grows sublinearly.
- Bounded Buffer Violation: By offline selection of the retention horizon $K$ , the cumulative buffer-occupancy violation is shown to be uniformly bounded ( $O(1)$ ).
Comparison Framework: The analysis employs a multi-step comparison chain connecting the ACDPP policy to an auxiliary constant-admission policy and finally to the costless oracle, providing explicit regret bounds.

Experimental Results
The policy was evaluated on three image classification datasets: MNIST, CIFAR-10, and ImageNette, under both non-i.i.d. and i.i.d. data partitions.

Performance: ACDPP consistently outperformed baselines, including a hybrid policy (mixing fresh and stale samples) and a constant-admission policy. On CIFAR-10 (non-i.i.d.), ACDPP improved test accuracy by 26.7 percentage points over the hybrid baseline and 3.5 points over the constant-admission baseline.
Convergence Speed: ACDPP converged significantly faster, reaching target accuracies approximately 2.2x to 2.6x faster than baselines on various datasets.
Constraint Satisfaction: Experiments confirmed that the policy maintained buffer occupancy within prescribed limits and stabilized the cost-debt queue, validating the theoretical guarantees.

Significance and Claims
The paper claims to bridge a gap in existing literature by providing a learning-centric framework that jointly optimizes admission and memory management under dynamic costs, rather than focusing solely on system-level resources (communication/computation) or static sample selection.

It moves beyond "score-based" selection methods (which assume high-gradient samples are valuable) by directly minimizing cumulative excess population risk with theoretical regret guarantees.
It addresses the specific challenge of streaming data where the learner must decide how many samples to admit and how long to retain them, a problem not fully addressed by prior resource-centric or selection-centric works.
The authors emphasize that their approach provides explicit, sublinear regret guarantees and handles the coupled effects of sample admission and retention, offering a principled solution for privacy-aware, large-scale model training in edge systems with evolving data streams.