Paper deep dive
Adaptive Data Admission and Retention for Streaming Federated Learning
Zhuoyi Zhao, Ben Liang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study streaming federated learning with limited client memory, where newly generated training data incur time-varying sampling costs and must be selectively admitted and retained over time. We consider a joint server-side admission and client-side memory-management framework with the objective of minimizing the cumulative excess population risk under a sampling-cost budget and buffer constraints. We first derive a learning-error bound that explicitly captures the effects of instantaneous training sample size, distinct-sample growth, and reuse imbalance through a characterization of the effective sample size. Through a surrogate penalty obtained from this bound, we develop an Active-Constraint Drift-Plus-Penalty (ACDPP) policy that combines a structured client-side $K$-step retention rule with a server-side online admission rule and a time-varying rectangular admission region. We further present a sequence of comparison arguments, via an auxiliary constant-admission policy, that connects the ACDPP learning bound to a costless oracle benchmark. This yields explicit guarantees in terms of sublinear regret and sampling-cost violation, while the buffer-occupancy violation is controlled through offline selection of the retention horizon. Experiments on multiple datasets demonstrate that the proposed policy remains close to the oracle benchmark while satisfying the sampling-cost and buffer constraints.
Tags
Links
- Source: https://arxiv.org/abs/2607.23987v1
- Canonical: https://arxiv.org/abs/2607.23987v1
Trouble viewing inline? Open PDF directly →
Full Text
92,073 characters extracted from source content.
Expand or collapse full text
Adaptive Data Admission and Retention for Streaming Federated Learning Zhuoyi Zhao University of TorontoToronto, ONCanada zhuoyijoeyzhao@gmail.com and Ben Liang University of TorontoToronto, ONCanada liang@ece.utoronto.ca (2026) Abstract. We study streaming federated learning with limited client memory, where newly generated training data incur time-varying sampling costs and must be selectively admitted and retained over time. We consider a joint server-side admission and client-side memory-management framework with the objective of minimizing the cumulative excess population risk under a sampling-cost budget and buffer constraints. We first derive a learning-error bound that explicitly captures the effects of instantaneous training sample size, distinct-sample growth, and reuse imbalance through a characterization of the effective sample size. Through a surrogate penalty obtained from this bound, we develop an Active-Constraint Drift-Plus-Penalty (ACDPP) policy that combines a structured client-side K-step retention rule with a server-side online admission rule and a time-varying rectangular admission region. We further present a sequence of comparison arguments, via an auxiliary constant-admission policy, that connects the ACDPP learning bound to a costless oracle benchmark. This yields explicit guarantees in terms of sublinear regret and sampling-cost violation, while the buffer-occupancy violation is controlled through offline selection of the retention horizon. Experiments on multiple datasets demonstrate that the proposed policy remains close to the oracle benchmark while satisfying the sampling-cost and buffer constraints. streaming federated learning, online sampling, stochastic optimization †copyright: none†journalyear: 2026†ccs: Computing methodologies Machine learning†ccs: Computing methodologies Distributed computing methodologies†ccs: Networks Network dynamics 1. Introduction Federated learning (FL) enables multiple devices to collaboratively train a shared model without directly transferring their raw data to a central server (McMahan and others, 2017; Kairouz and McMahan, 2021). By keeping data local, FL has emerged as a promising paradigm for privacy-aware and large-scale model training in mobile and edge systems (Bonawitz and others, 2019; Wang and others, 2019). The performance of FL, however, depends fundamentally on the quality, quantity, and diversity of the data available across participating clients. In practice, client data are often highly heterogeneous due to differences in user behavior, sensing environments, and local data-generation processes and generalization (Karimireddy and others, 2020; Tan and others, 2022; Wang and others, 2020). Moreover, in many real-world applications, local datasets evolve over time as new samples are continuously generated, collected, or labeled (Gong and others, 2024; Shi and others, 2023; Sun and others, 2025; Zhang and others, 2024; Huynh and others, 2025). As a result, beyond model aggregation itself, an important question in FL is how to manage the training data pipeline under statistical heterogeneity and temporal data evolution. In particular, client data may be generated and collected in an online fashion rather than provided as a fixed offline dataset. Examples include edge sensing, mobile crowdsourcing, and human-in-the-loop labeling systems, where new samples arrive sequentially and may incur non-negligible acquisition, annotation, or transmission costs before they can be used for training (Zhou and others, 2020; Hu and others, 2024). Such costs are often time-varying due to changes in sensing conditions, network status, device availability, or labeling effort. At the same time, client devices are typically memory-limited and cannot retain all previously observed samples indefinitely. As a result, the learner must continuously decide whether to admit newly arrived samples and which historical samples to retain for future reuse. This creates a fundamental trade-off: admitting more fresh samples may improve data diversity and generalization, while reusing retained samples can reduce immediate acquisition cost and increase the effective training set size. Therefore, beyond classical federated optimization, streaming FL calls for a principled framework that manages sample admission and buffer occupancy under dynamic cost and memory constraints. While prior works have studied resource management (Zhou and others, 2020; Hu and others, 2024), and sample selection (Gong and others, 2024; Shi and others, 2023; Sun and others, 2025; Marfoq and others, 2023) in streaming FL, they do not provide a unified framework that directly optimizes learning performance under joint admission and memory constraints. In particular, existing resource-centric approaches mainly focus on communication, computation, or energy efficiency (Zhou and others, 2020; Hu and others, 2024), whereas learning-centric sample selection methods typically do not explicitly account for long-term sampling cost, buffer occupancy, or the coupled effect of sample admission and retention (Gong and others, 2024; Shi and others, 2023; Sun and others, 2025). Our work bridges this gap by proposing a learning-centric modeling framework for streaming FL with limited client memory, which jointly captures server-side sample admission and client-side buffer management. Specifically, we formulate the problem as a constrained stochastic optimization problem whose objective is to minimize the cumulative excess population risk under long-term sampling-cost and buffer-occupancy constraints. This formulation enables a principled treatment of the trade-off among sample freshness, sample reuse, memory limitation, and admission cost, and lays the foundation for both the benchmark design and the online policy developed in this paper. The main contributions of this paper are summarized as follows. • We establish a learning-error bound for streaming FL with memory-based training, which explicitly characterizes the roles of the instantaneous training sample size, the cumulative number of distinct samples, and the reuse imbalance caused by repeated use of stored samples. In particular, we introduce an effective sample size representation that makes these effects transparent and amenable to control design. • We propose an ACDPP policy that combines a structured client-side K-step retention rule with a server-side online admission rule based on a modified form of Lyapunov drift-plus-penalty optimization. In particular, to strengthen the control design, we impose a time-varying rectangular constraint on the feasible admission region, which gradually drives the admission process toward a target operating point. • We prove explicit guarantees for the proposed policy, including a sublinear regret bound relative to a costless oracle benchmark and a sublinear sampling-cost violation bound derived via Lyapunov analysis. Our analysis proceeds through a sequence of finite-horizon comparisons that connect the ACDPP-induced learning bound to the oracle through its surrogate penalty and an auxiliary constant-admission policy. In addition, we provide an offline method for choosing the time-invariant retention horizon K to ensure uniformly bounded cumulative buffer-occupancy violation. • We conduct experiments on multiple canonical datasets to validate the proposed policy and demonstrate its effectiveness under streaming sample admission, buffer constraints, and time-varying sampling costs. 2. Related Work 2.1. Centralized Learning with Streaming Data In centralized streaming learning, samples arrive sequentially rather than as a fixed dataset. As a result, the learner typically trains on only a partially observed dataset at any point in time (Gomes and others, 2019; Gama and others, 2013). This is often due to limited storage or the use of memory-efficient stream summaries in high-volume data streams (Cormode and Muthukrishnan, 2005; Wang and others, 2024; De Lange and others, 2021). Despite these connections, centralized streaming learning does not capture the network-edge setting considered here. It overlooks the distributed nature of data generation and storage across edge devices, along with the resulting heterogeneity in local data distributions, memory capacities, and resource constraints. It also generally does not account for the time-varying operating conditions that are common in edge environments. 2.2. Streaming Federated Learning Several works have studied online resource management for streaming FL using Lyapunov optimization. CEFL (Zhou and others, 2020) jointly optimizes admission control, load balancing, and accuracy tuning to minimize operational costs. Hu et al. (Hu and others, 2024) further incorporate device scheduling and bandwidth allocation under long-term energy constraints. While these approaches enable online decision-making with constraint guarantees, they primarily focus on system-level costs rather than learning performance, and assume unlimited on-device storage. Another line of research develops data valuation metrics for sample selection under limited on-device storage. Gong et al. (Gong and others, 2024) propose gradient-norm based selection to accelerate convergence, Shi et al. (Shi and others, 2023) employ contrastive learning for importance scoring in unlabeled settings, and Sun et al. (Sun and others, 2025) learn query policies via multi-agent reinforcement learning. Notably, while these score-based methods implicitly assume that high-gradient-norm or high-loss samples are more valuable for learning, they do not explicitly optimize for the underlying population risk. In contrast, our framework directly minimizes the cumulative excess risk with respect to the target distribution, providing theoretical regret guarantees. Furthermore, these scoring mechanisms focus on which sample to select while our admission control determines how many samples to retain under cost constraints. Marfoq et al. (Marfoq and others, 2023) provide a foundational analysis for streaming FL, characterizing the bias-optimization tradeoff when mixing historical and fresh clients. They establish that the optimal strategy depends on the ratio between gradient variability and effective sample size, with the extreme cases being uniform weighting when gradient variability dominates and historical-only weighting when sample size effects dominate. However, their analysis does not address online admission decisions, storage management, or explicit optimization of the mixing strategy under resource constraints. Recent studies also address non-stationary data streams where distributions evolve over time. Zhang et al. (Zhang and others, 2024) propose Fed-HIST to leverage historical model knowledge. Huynh et al. (Huynh and others, 2025) analyze convergence under Markovian data streams. These works focus on adapting to distribution drift, whereas our work targets stationary environments where the optimal model remains fixed and the challenge lies in optimal sample management under resource constraints. 3. Preliminaries 3.1. Network Model We consider a streaming FL system consisting of a parameter server (PS) and M clients, operating over discrete communication rounds indexed by t∈1,2,…,Tt∈\1,2,…,T\. Each client is indexed by m∈1,2,…,Mm∈\1,2,…,M\. Training samples are generated in a streaming manner: at the beginning of each round t, the PS determines the admission decisions, and the admitted samples are stored locally at the clients for future training.111An alternative is for the clients to locally determine admission. In that case, due to the positive sampling costs, it is necessary to consider fairness and incentives among the clients. Such game theoretic analysis is outside the scope of this work. Instead, here we focus on overall system cost and performance, so it suffices to consider server-side admission control. We assume that client m is associated with a local data distribution mP_m, and that each sample admitted at client m is drawn independently and identically distributed (i.i.d.) from mP_m. Due to privacy and security constraints, sample admission and local memory management are decoupled across the server and the clients. In particular, the PS never accesses raw samples; instead, it only determines the admission amount at each client in each round. Once admitted, a sample is stored locally in the buffer of the corresponding client. Buffer management is then carried out independently by each client through local dropping actions based solely on client-side information. The admitted and retained samples constitute the local training memory used for subsequent local model updates. Server-side admission actions and sampling cost. At each round t, the PS decides how many new samples to admit at each client. For each client m, samples are indexed by their generation order, and (m,i)(m,i) denotes the i-th sample generated at client m. To represent the sample-level admission status for subsequent buffer and age evolution, we define the binary admission indicator (1) am,i(t)∈0,1,a_m,i(t)∈\0,1\, where am,i(t)=1a_m,i(t)=1 means that sample (m,i)(m,i) is admitted to the local buffer of client m in round t. Accordingly, we define the admission amount at client m in round t as (2) λm(t)≜∑iam,i(t),∀m, _m(t) _ia_m,i(t), ∀ m, which is the number of samples admitted at client m in round t. Admitting one new sample in round t incurs a time-varying per-sample sampling cost c(t)≥0c(t)≥ 0, revealed to the PS at the beginning of round t. Let c¯T≜1T∑t=1T[c(t)] c_T 1T _t=1^TE[c(t)] denote the average per-sample sampling cost over the horizon T. We impose the average sampling-cost constraint (3) 1T∑t=1T[c(t)∑m=1Mλm(t)]≤C, 1T _t=1^TE\! [c(t) _m=1^M _m(t) ]≤ C, where C>0C>0 is the prescribed per-round sampling-cost budget. Client memory state and buffer dropping. Each client maintains a local buffer that stores admitted samples for future training. Let qm,it∈0,1q_m,i^t∈\0,1\ indicate whether sample (m,i)(m,i) is present in the local buffer of client m at the beginning of the local training phase of round t, i.e., after the admission and dropping actions in round t have been executed. The resulting buffer occupancy is defined as (4) nm(t)≜∑iqm,it,n_m(t) _iq_m,i^t, which is the number of samples stored in the local buffer of client m in round t. Accordingly, let m(t)Q_m(t) denote the set of samples stored in the local buffer of client m in round t, so that nm(t)=|m(t)|n_m(t)=|Q_m(t)|. To capture limited memory, we impose an average buffer-occupancy constraint on each client: (5) 1T∑t=1T[nm(t)]≤Bm,m=1,…,M, 1T _t=1^TE[n_m(t)]≤ B_m, m=1,…,M, where Bm>0B_m>0 is the prescribed average memory budget of client m. Client m independently manages its local buffer through a binary drop action dm,i(t)∈0,1d_m,i(t)∈\0,1\, where dm,i(t)=1d_m,i(t)=1 means that sample (m,i)(m,i) is removed from the local buffer of client m in round t. Dropping actions are determined locally based solely on client-side information. Sample age and its evolution. For each sample (m,i)(m,i), let Am,it∈ℕA_m,i^t denote its age at the beginning of the local training phase of round t. The age serves as a residence-time counter and is updated only when the sample is present in the local buffer at the beginning of the next local training phase. Specifically, (6) Am,it+1=Am,it+1,if qm,it=1 and qm,it+1=1,1,if qm,it=0 and qm,it+1=1,Am,it,if qm,it+1=0,A_m,i^t+1= casesA_m,i^t+1,&if q_m,i^t=1 and q_m,i^t+1=1,\\ 1,&if q_m,i^t=0 and q_m,i^t+1=1,\\ A_m,i^t,&if q_m,i^t+1=0, cases with initialization Am,i0=0A_m,i^0=0 for all m,im,i. Thus, the age of a sample is incremented while it remains in the buffer, initialized to 11 when it newly enters the buffer, and frozen once it is no longer stored. 3.2. Distributed Learning Model Let θ(t)∈Θθ^(t)∈ denote the global model at the beginning of the local training phase of round t. We assume that all clients participate in every communication round. Moreover, due to the limited buffer size at each client, we consider a full-batch local update regime, in which each client directly uses all samples currently stored in its local buffer to perform local training. Let ℓ(θ;z) (θ;z) denote the sample-wise loss of model parameter θ on data sample z. The empirical risk over the local buffer of client m in round t is defined as (7) F^m,t(θ)≜1nm(t)∑z∈m(t)ℓ(θ;z). F_m,t(θ) 1n_m(t) _z _m(t) (θ;z). Accordingly, the corresponding local gradient is (8) ∇F^m,t(θ)=1nm(t)∑z∈m(t)∇θℓ(θ;z).∇ F_m,t(θ)= 1n_m(t) _z _m(t) _θ (θ;z). Starting from θm(t,0)=θ(t) _m^(t,0)=θ^(t), each client performs E≥1E≥ 1 steps of gradient descent with stepsize η>0η>0 on the empirical risk F^m,t F_m,t: (9) θm(t,e+1)=θm(t,e)−η∇F^m,t(θm(t,e)),e=0,…,E−1. _m^(t,e+1)= _m^(t,e)-η\,∇ F_m,t\! ( _m^(t,e) ), e=0,…,E-1. After the local updates, client m uploads the model difference (10) Δm(t)≜θm(t,E)−θ(t). _m^(t) _m^(t,E)-θ^(t). Let αm≥0 _m≥ 0 denote the prescribed importance weight of client m, with ∑m=1Mαm=1 _m=1^M _m=1. The server then aggregates the client updates according to a FedAvg-style rule: (11) θ(t+1)=θ(t)+∑m=1Mwm,tΔm(t),wm,t≥0,∑m=1Mwm,t=1,θ^(t+1)=θ^(t)+ _m=1^Mw_m,t\, _m^(t), w_m,t≥ 0, _m=1^Mw_m,t=1, where a natural choice of wm,tw_m,t, for example, is memory-proportional weighting, i.e. (12) wm,t=αmnm(t)∑j=1Mαjnj(t).w_m,t= _mn_m(t) _j=1^M _jn_j(t). 3.3. Problem Formulation Learning objective. We define the target population distribution as the weighted mixture (13) ≜∑m=1Mαmm.P _m=1^M _mP_m. Our goal is to learn a model that minimizes the population risk (14) F(θ)≜z∼[ℓ(θ;z)],θ∈Θ,F_P(θ) _z [ (θ;z)], θ∈ , and let θ⋆∈argminθ∈ΘF(θ)θ ∈ _θ∈ F_P(θ). Server and client control variables. The system is controlled through a decomposed architecture. On the server side, the PS determines the admission amounts λm(t)m=1M\ _m(t)\_m=1^M at each round t, which can be equivalently represented by the sample-level admission indicators am,i(t)m,i\a_m,i(t)\_m,i via (2). On the client side, each client m independently determines the sample-level dropping actions dm,i(t)i\d_m,i(t)\_i to manage its local buffer. Together, the admission and dropping actions govern the evolution of the client buffers and must jointly satisfy the sampling-cost constraint (3) and the average buffer-occupancy constraint (5). Let πSπ^S denote the server-side policy that maps server-observable information (e.g., the history of communicated updates and the current cost c(t)c(t)) to admission actions. For each client m, let πmC _m^C denote the client-side policy that maps local buffer states (including sample ages) to dropping actions. We denote the resulting joint policy by (15) π≜(πS,πmCm=1M).π (π^S,\ _m^C\_m=1^M ). Optimization objective and constraint violation. Under the learning dynamics in Section 3.2, the global model sequence θ(t)t=1T\θ^(t)\_t=1^T is induced by the joint policy π through its effect on sample admissions, buffer evolution, and the resulting local updates. Although performance is evaluated with respect to the target population distribution P, the model at each round is trained only on the samples currently stored in the client buffers. These stored samples are time-varying and are jointly determined by the admission and dropping actions over time. Hence, policy design in our setting amounts to controlling the evolving buffer contents so that training on the stored samples leads to low expected loss under the target population distribution P. To evaluate the learning performance induced by a given joint policy π, we define the cumulative excess population risk up to horizon T as (16) ℰT(π)≜∑t=1T[F(θ(t))−F(θ⋆)].E_T(π) _t=1^TE\! [F_P(θ^(t))-F_P(θ ) ]. This quantity measures the cumulative suboptimality of the model sequence induced by policy π relative to the population-risk minimizer θ⋆θ . Our goal is to develop joint policies π that minimize the cumulative excess population risk ℰT(π)E_T(π) subject to the sampling-cost constraint (3) and the average buffer-occupancy constraint (5). 4. Streaming FL Convergence Analysis In this section, we analyze the learning performance of the streaming FL under server-side sample admission and client-side memory management. The key challenge is that the model is trained on time-varying buffer contents induced by the joint policy, rather than on direct samples from the target population distribution. Our focus is therefore on understanding how the evolving stored samples and their repeated reuse affect the convergence behavior of the learning process. In particular, we derive a bound on the cumulative excess population risk in (16). 4.1. Assumptions We impose the following standard regularity assumptions. Assumption 1 (Bounded domain). The parameter set Θ has diameter D, i.e., ‖θ−θ′‖2≤D,∀θ,θ′∈Θ.\|θ-θ \|_2≤ D, ∀θ,θ ∈ . Assumption 2 (Smoothness and bounded gradients). The population risk F_P is L-smooth on Θ , i.e., ‖∇F(θ)−∇F(θ′)‖2≤L‖θ−θ′‖2,∀θ,θ′∈Θ.\|∇ F_P(θ)-∇ F_P(θ )\|_2≤ L\|θ-θ \|_2, ∀θ,θ ∈ . Moreover, the loss ℓ(θ;z) (θ;z) is differentiable in θ, and its per-sample gradients are uniformly bounded: ‖∇θℓ(θ;z)‖2≤G,∀θ∈Θ,z.\| _θ (θ;z)\|_2≤ G, ∀θ∈ ,\;z. Hence, any empirical gradient formed as an average over stored samples is also bounded in norm by G. Assumption 3 (Bounded loss and finite pseudo-dimension). The loss is bounded as ℓ(θ;z)∈[0,B] (θ;z)∈[0,B] for all θ∈Θθ∈ and z. In addition, the loss-composed hypothesis class ℓ∘ℋ has finite pseudo-dimension, denoted by Pdim(ℓ∘ℋ)Pdim( ). For sharper control of the stochastic-gradient term, we further impose the following assumption. Assumption 4 (Bounded gradient variance). The per-sample gradient has uniformly bounded population variance: (17) z∼[‖∇θℓ(θ;z)−∇F(θ)‖22]≤σ2,∀θ∈Θ.E_z [ \| _θ (θ;z)-∇ F_P(θ) \|_2^2 ]≤σ^2, ∀θ∈ . 4.2. Learning Error Bound We next derive an upper bound on the cumulative excess population risk ℰT(π)E_T(π) under a given joint policy π. The bound depends on the policy-induced evolution of the training samples, in particular on the instantaneous training sample size, the cumulative number of distinct samples, and the loss of diversity caused by repeated reuse of stored samples. Under the full-batch local training regime, let nπ(t)n^π(t) denote the total number of stored samples used for training at round t under policy π. Further, let Nπ(t)N^π(t) denote the number of distinct samples that have been used in local training up to round t. Since retained samples may be reused multiple times across rounds, the quantity Nπ(t)N^π(t) alone does not fully reflect the amount of statistical information available for learning. To capture the loss of diversity caused by uneven sample reuse, we introduce an effective sample size. Specifically, for each distinct sample i∈1,…,Nπ(t)i∈\1,…,N^π(t)\, let Aiπ(t)A_i^π(t) denote the cumulative number of times that sample i has been used in local training up to round t. We define (18) ~π(t)≜A¯π(t)2A¯π(t)2+Var(Aπ(t)), V^π(t) A^π(t)^2 A^π(t)^2+Var(A^π(t)), and (19) Neffπ(t)≜Nπ(t)~π(t),N_eff^π(t) N^π(t)\, V^π(t), where A¯π(t) A^π(t) and Var(Aπ(t))Var(A^π(t)) are the empirical mean and variance of Aiπ(t)i=1Nπ(t)\A_i^π(t)\_i=1^N^π(t), respectively. The factor ~π(t)∈(0,1] V^π(t)∈(0,1] measures the uniformity of sample reuse: it is close to 11 when the reuse counts are nearly uniform, and becomes smaller when the reuse pattern is highly uneven. Accordingly, Neffπ(t)=Nπ(t)~π(t)N_eff^π(t)=N^π(t) V^π(t) quantifies the effective amount of statistical diversity retained in the stored samples. We now state the main excess-risk bound. The proof combines (i) a smoothness-based optimization recursion, (i) variance control for stochastic gradients under sample reuse, and (i) a uniform generalization bound controlled by the pseudo-dimension; detailed arguments are deferred to the appendix. The bound is closely related in spirit to the general streaming-learning analysis of Theorem 4.4 in (Marfoq and others, 2023), but is specialized here to the present full-batch memory-based federated setting. Rather than giving an abstract order-level characterization as in (Marfoq and others, 2023), we express the bound explicitly in terms of the policy-induced quantities nπ(t)n^π(t), Nπ(t)N^π(t), and ~π(t) V^π(t) through Neffπ(t)=Nπ(t)~π(t)N_eff^π(t)=N^π(t) V^π(t). This explicit decomposition makes the separate effects of training sample size, distinct-sample growth, and reuse imbalance transparent, and will be instrumental for the subsequent online control design. Theorem 1. Under Assumptions 1–4, let θπ(t)t=1T\ _π^(t)\_t=1^T be the model sequence generated by the learning dynamics under a given joint policy π. Then the cumulative excess population risk satisfies (20) ℰT(π)≤ℰ¯T(π),E_T(π)≤ E_T(π), where (21) ℰ¯T(π) E_T(π) =∑t=1T[Dσ1nπ(t)−1Nπ(t)~π(t)+ησ2(1nπ(t)−1Nπ(t)~π(t)) \!=\! _t=1^T\! [Dσ\!\! 1n^π(t)\!-\! 1N^π\!(t) V^π(t)\!+\!ησ^2\! (\!\! 1n^π(t)\!-\! 1N^π\!(t) V^π(t)\! ) +10BPdim(ℓ∘ℋ)Nπ(t)~π(t)1+log(Nπ(t)Pdim(ℓ∘ℋ))+C2]. +0B Pdim( )N^π\!(t) V^π(t) 1+ \! ( N^π\!(t)Pdim( ) )+C_2 ]. Here, C2C_2 collects initialization and lower-order constant terms, including D22η D^22η and other algorithm-dependent constants. Proof. See Appendix A in (Zhao and Liang, 2026). ∎ 5. Active-Constraint DPP Policy Utilizing the excess-risk bound in (20), we develop a joint admission-retention design for the streaming FL system. Our goal is to construct a structured online control policy that satisfies the long-term sampling-cost constraint and minimizes a tractable surrogate of the cumulative excess population risk. While Theorem 1 provides an explicit policy-dependent upper bound, it remains difficult to optimize directly under a general buffer-management policy, because the reuse-uniformity factor ~π(t) V^π(t) depends on the entire sample-retention pattern. To address this difficulty, we first impose a structured client-side retention rule, namely the K-step retention policy, which regularizes sample reuse and yields a tractable surrogate for online control. Based on this client-side structure, we then construct a DPP-based server-side admission policy using a cost-debt virtual queue together with a learning-oriented penalty term. To further strengthen the control design, we impose a time-varying rectangular constraint on the admission action space. This construction extends the classical DPP framework in (Neely, 2022) by allowing the feasible admission interval to shrink gradually over time toward the target operating point. Algorithm 1 summarizes the overall Active-Constraint DPP policy, including the client-side K-step retention rule, the server-side online admission update, and the resulting distributed learning procedure. We next formalize each component of this policy. 1 Inputs: θ(1)θ^(1), Z(1)=0Z(1)=0, qm,i0\q_m,i^0\, Am,i0\A_m,i^0\, N(0)N(0), n(0)n(0), C, Bmm=1M\B_m\_m=1^M, K, V, Λ¯ , ρ Output: θ(t)t=1T+1\θ^(t)\_t=1^T+1 2 3for t=1,2,…,Tt=1,2,…,T do 4 5 The server does: 6 Observe (t)O(t) and c(t)c(t) 7 8 Solve (34) to obtain ⋆(t) λ (t) 9 10 Update Z(t+1)Z(t+1) and Am,it+1\A_m,i^t+1\ using (26) and (6) 11 12 Update Nπ(t)N^π(t) and nπ(t)n^π(t) 13 14 15 Each client m in parallel does: 16 Admit λm(t) _m(t) new samples using ⋆(t) λ (t) 17 18 Perform local training and compute Δm(t) _m^(t) using (8), (9), and (10) 19 20 Update qm,it+1\q_m,i^t+1\ using (22) 21 22 23 The server does: 24 Aggregate and update θ(t+1)θ^(t+1) using (11) 25 26 Algorithm 1 Active-Constraint DPP Algorithm 5.1. K-Step Retention Policy We first introduce the K-step retention policy, which imposes a simple deterministic client-side retention rule and makes the reuse pattern of stored samples explicitly characterizable. The key idea is that, under K-step retention, every admitted sample remains in the local buffer for a fixed number of rounds, so that the reuse-uniformity factor ~π(t) V^π(t) can be expressed in closed form. Definition 0 (K-step retention policy). Fix an integer retention horizon K≥1K≥ 1. A client-side policy is called a K-step retention policy if, for every client m∈1,…,Mm∈\1,…,M\, every admitted sample (m,i)(m,i), and every round t∈1,…,Tt∈\1,…,T\, the dropping action satisfies (22) dm,i(t)=Am,it=K,∀m,i,t.d_m,i(t)=1\A_m,i^t=K\, ∀ m,i,t. That is, each sample is retained in the local buffer for exactly K rounds after admission and is removed when its age reaches K. We next characterize the reuse-uniformity factor under the K-step retention policy. Under this policy, every sample admitted no later than round t−K+1t-K+1 has already contributed exactly K training uses by round t, while only the samples admitted in the most recent K−1K-1 rounds incur a reuse deficit. Define (23) D∂(1)(t)≜∑j=t−K+2t(K−(t−j+1))∑m=1Mλm(j),D_∂^(1)(t) _j=t-K+2^t (K-(t-j+1) ) _m=1^M _m(j), and (24) D∂(2)(t)≜∑j=t−K+2t(K2−(t−j+1)2)∑m=1Mλm(j).D_∂^(2)(t) _j=t-K+2^t (K^2-(t-j+1)^2 ) _m=1^M _m(j). Then the reuse-uniformity factor under the K-step retention policy admits the exact representation (25) ~π(t)=(KNπ(t)−D∂(1)(t))2Nπ(t)(K2Nπ(t)−D∂(2)(t)). V^π(t)= (KN^π(t)-D_∂^(1)(t) )^2N^π(t) (K^2N^π(t)-D_∂^(2)(t) ). Hence, the finite-horizon deviation of ~π(t) V^π(t) from one is determined entirely by the boundary deficits induced by the samples admitted in the most recent K−1K-1 rounds. 5.2. Online Admission Control with Time-Varying Rectangular Constraints We next formalize the server-side online admission control, including the virtual queue, the Lyapunov function, the penalty term, and a new DPP admission rule with time-varying rectangular constraints. Cost-Debt Queue. Let Z(t)Z(t) denote the cost-debt queue at the beginning of round t. It evolves as (26) Z(t+1)=[Z(t)+Ct−C]+,Z(t+1)= [Z(t)+C_t-C ]^+, where C>0C>0 is the prescribed per-round sampling-cost budget and (27) Ct≜c(t)Λ(t),Λ(t)≜∑m=1Mλm(t),C_t c(t) (t), (t) _m=1^M _m(t), is the aggregate sampling cost incurred in round t under the DPP policy, with initialization Z(0)=0Z(0)=0. The queue Z(t)Z(t) measures the accumulated violation of the budget constraint: when Ct>C_t>C, the system incurs positive debt and Z(t)Z(t) grows; otherwise the debt is reduced. Hence, a large value of Z(t)Z(t) indicates that the system has been operating above the desired average cost level. Lyapunov Function and Penalty Function. We adopt the quadratic Lyapunov function (28) L(t)=12Z(t)2,L(t)= 12Z(t)^2, which captures the evolution of the cost-debt dynamics. Motivated by the learning-error bound in Theorem 1 together with the K-step retention structure developed in Section 5.1, we introduce the following per-round penalty, whose cumulative sum will serve as a surrogate objective for online control: (29) p(t) p(t) ≜Dσ1nπ(t)−1Nπ(t)+η~σ2(1nπ(t)−1Nπ(t)) Dσ 1n^π(t)- 1N^π(t)+ ησ^2 ( 1n^π(t)- 1N^π(t) ) +10BPdim(ℓ∘ℋ)Nπ(t)1+log(Nπ(t)Pdim(ℓ∘ℋ)). +0B Pdim( )N^π(t) 1+ \! ( N^π(t)Pdim( ) ). Accordingly, the cumulative quantity ∑t=1Tp(t) _t=1^Tp(t) serves as a surrogate objective in place of the learning upper bound ℰ¯T(π) E_T(π). One-Slot Drift-Plus-Penalty. Let (t):=Z(t),qm,it,Am,itm,iO(t):=\Z(t),q_m,i^t,A_m,i^t\_m,i denote the system state at the beginning of the local training phase of round t.222Under K-step retention, qm,itq_m,i^t and Am,itA_m,i^t are induced by the historical admission process and are therefore inferable from server-side actions. Their use in the drift analysis does not require access to raw client data. We define the one-slot Lyapunov drift as (30) Δ((t))≜[L(t+1)−L(t)∣(t)]. (O(t)) \! [L(t+1)-L(t) (t) ]. The DPP framework minimizes a weighted sum of the one-slot drift and the per-round penalty. Accordingly, we consider the drift-plus-penalty expression (31) Δ((t))+V[p(t)∣(t)], (O(t))+VE[p(t) (t)], where V>0V>0 is a control parameter that trades off learning performance and budget satisfaction. Substituting the queue evolution of Z(t)Z(t) into (30) and using standard quadratic-drift bounds yields (32) Δ((t))+V[p(t)∣(t)]≤B+[Jt()∣(t)], (O(t))+VE[p(t) (t)]≤ B+E\! [J_t( λ) (t) ], where B<∞B<∞ is a uniform constant independent of the control action, and (33) Jt()≜Z(t)(c(t)Λ(t)−C)+Vp(t),J_t( λ) Z(t) (c(t) (t)-C )+Vp(t), with (t)≜(λ1(t),…,λM(t)). λ(t) ( _1(t),…, _M(t)). Acitve-Constraint DPP Admission Rule. Motivated by the upper bound in (32), the ACDPP policy selects, at each round t, an admission action vector ⋆(t) λ (t) that minimizes the right-hand side of (33), namely, (34) ⋆(t)∈argminJt()s.t.∑m=1Mλm(t)∈[Λmin(t),Λmax(t)]. λ (t)∈ _ λ\;J_t( λ) .t. _m=1^M _m(t)∈[ _ (t), _ (t)]. Here, the bounds Λmin _ and Λmax _ impose a rectangular constraint on the aggregate admission rate. Unlike the standard DPP policy, we set time-varying constraints as follows: (35) Λmin(t)=Λ¯(1−ρt),Λmax(t)=Λ¯1−ρt, _ (t)= (1-ρ^t), _ (t)= 1-ρ^t, for some constant ρ∈(0,1)ρ∈(0,1). As t→∞t→∞, the admissible interval shrinks to the singleton Λ¯\ \. The parameter ρ controls the contraction speed: smaller ρ leads to faster concentration, while larger ρ preserves more flexibility for a longer period. We will discuss how to choose ρ, which depends on T, after we derive the regret and sampling-cost violation bounds in Section 6. This design is motivated by the structure of the learning-error surrogate. For sufficiently large t, the dominant terms depend primarily on the instantaneous training sample size nπ(t)n^π(t). Under the buffer constraints, these terms are minimized when nπ(t)n^π(t) is stable over time and close to its time average. This follows from the Cauchy–Schwarz inequality: for a fixed time-average sample size, temporal fluctuations in nπ(t)n^π(t) increase the cumulative contribution of terms involving 1/nπ(t)1/n^π(t), whereas a constant sample size yields the smallest value. Accordingly, the time-varying rectangular constraint allows the admission rate to vary more freely in the early stage so as to adapt to the time-varying sampling cost, while gradually shrinking the feasible interval to promote a more stable long-term batch-size profile. Although (34) is written in terms of the admission vector (t) λ(t), the objective depends on the control only through the aggregate admission rate Λ(t)=∑m=1Mλm(t) (t)= _m=1^M _m(t). Therefore, the optimization reduces to a one-dimensional per-round problem, which yields low-complexity online implementation. 6. Performance Guarantees This section analyzes the performance of the proposed ACDPP policy through a multi-step comparison framework. Our goal is to derive a regret bound for ACDPP relative to a costless oracle benchmark, together with explicit constraint-violation guarantees. We first establish a T-slot upper bound on the surrogate penalty induced by ACDPP. We then construct a comparison chain from the ACDPP-induced learning upper bound to the costless oracle benchmark and characterize the order of each correction term along this chain. These ingredients are finally combined to obtain the regret bound, the sampling-cost violation bound, and an offline method for selecting the retention horizon K to control the buffer-occupancy violation. 6.1. Preliminaries To analyze the performance of the proposed ACDPP policy, we first introduce the ingredients used in the subsequent regret analysis. We begin with a costless oracle benchmark, together with the regret and constraint-violation metrics used to evaluate the proposed policy over a finite horizon. We then introduce an auxiliary constant-admission policy under the K-step retention rule, which serves as a tractable intermediate comparison object for both parameter selection and regret analysis. 6.1.1. Costless Oracle Benchmark, Regret, and Constraint Violations We first introduce an idealized costless oracle benchmark together with the regret and constraint-violation metrics. Consider the system without the long-term sampling-cost constraint. In this costless regime, the upper bound in (20) is minimized when training samples are always fresh and no sample reuse occurs. Under the per-client buffer constraint BmB_m, this idealized behavior is achieved by the following costless oracle policy: at every round t, client m admits exactly BmB_m new samples, uses each sample once for local training, and immediately discards it. This policy satisfies the buffer constraints and maximizes the number of distinct samples used for learning. Let ℰ¯TACDPP E_T^ACDPP denote the upper bound on the cumulative excess population risk under the proposed ACDPP policy up to round T, and let ℰ¯Toracle E_T^oracle denote the corresponding quantity under the costless oracle policy. We define the regret as (36) Reg(T)≜ℰ¯TACDPP−ℰ¯Toracle.Reg(T) E_T^ACDPP- E_T^oracle. The regret in (36) will be used to quantify the finite-horizon performance gap between the proposed online policy and the costless oracle benchmark. To measure the extent to which a policy violates the sampling-cost and buffer constraints, we define the cumulative sampling-cost violation and cumulative buffer-occupancy violation up to horizon T as (37) VioS(T)≜[∑t=1T[c(t)∑m=1Mλm(t)−C]]+,Vio^S(T) [ _t=1^TE\! [c(t) _m=1^M _m(t)-C ] ]^+, and (38) VioB(T)≜∑m=1M[∑t=1T[nm(t)−Bm]]+.Vio^B(T) _m=1^M [ _t=1^TE\! [n_m(t)-B_m ] ]^+. These quantities will be used together with the regret to characterize the finite-horizon performance of the proposed policy. 6.1.2. Auxiliary Constant-Admission Policy We next introduce an auxiliary comparison policy under the K-step retention rule. Definition 0 (Auxiliary constant-admission policy). Fix nonnegative admission rates λmm=1M\ _m\_m=1^M. A server-side policy is called a constant-admission policy if, for every round t and client m, (39) ∑iam,i(t)=λm,∀m,t. _ia_m,i(t)= _m, ∀ m,t. Combined with the K-step retention policy in Definition 1, this yields the joint policy πCKπ^CK. Under πCKπ^CK, each client admits a constant number of new samples per round, while each admitted sample is retained for exactly K rounds. Consequently, for all sufficiently large t, the buffer occupancy at client m satisfies (40) nm(t)=Kλm,n_m(t)=K _m, and the total training sample size is (41) nCK(t)=KΛ¯,Λ¯≜∑m=1Mλm.n^CK(t)=K , _m=1^M _m. Moreover, the cumulative number of distinct samples used in local training up to round t grows linearly as (42) NCK(t)=Λ¯t.N^CK(t)= t. Substituting (40)–(42) into Theorem 1, together with the exact finite-horizon reuse-uniformity factor induced by πCKπ^CK, yields the following specialization of the cumulative excess-risk bound. Corollary 0. For the auxiliary constant-admission policy πCKπ^CK, the cumulative excess population risk satisfies (43) ℰT(πCK)≤ℰ¯T(πCK),E_T(π^CK)≤ E_T(π^CK), where (44) ℰ¯T(πCK) E_T(π^CK) =∑t=1T[Dσ1Λ¯K−1Λ¯t~CK(t)+ησ2(1Λ¯K−1Λ¯t~CK(t)) = _t=1^T [Dσ 1 K- 1 t\, V^CK(t)+ησ^2 ( 1 K- 1 t\, V^CK(t) ) +10BPdim(ℓ∘ℋ)Λ¯t~CK(t)1+log(Λ¯tPdim(ℓ∘ℋ))+C2], +0B Pdim( ) t\, V^CK(t) 1+ \! ( tPdim( ) )+C_2 ], and (45) ~CK(t)=(Kt−K(K−1)2)2t(K2t−K(K−1)(2K−1)6). V^CK(t)= (Kt- K(K-1)2 )^2t (K^2t- K(K-1)(2K-1)6 ). The specialized bound in Corollary 2 depends on the aggregate admission level Λ¯ , the retention horizon K, and the finite-horizon reuse-uniformity factor ~CK(t) V^CK(t). We therefore choose these parameters so as to optimize the benchmark bound under the sampling-cost and buffer constraints. Under the auxiliary constant-admission policy πCKπ^CK, the average sampling cost over horizon T must satisfy (46) c¯TΛ¯≤C, c_T\, ≤ C, and the per-client buffer constraint requires (47) Kλm≤Bm,∀m.K _m≤ B_m, ∀ m. Accordingly, the benchmark parameter design is formulated as (48) minλmm=1M,K∈ℕℰ¯T(πCK):Kλm≤Bm,∀m,c¯T∑m=1Mλm≤C,λm≥0,∀m. _\ _m\_m=1^M,\,K \ E_T(π^CK)\!:\!K _m≤ B_m,\!∀ m,\ c_T\! _m=1^M _m≤ C,\! _m≥ 0,\!∀ m \. Because ℰ¯T(πCK) E_T(π^CK) depends on the admission vector λmm=1M\ _m\_m=1^M only through the induced aggregate level Λ¯=∑m=1Mλm = _m=1^M _m, the problem is low-dimensional. In particular, for any fixed horizon T, the benchmark parameters can be obtained by searching over feasible values of the integer variable K together with the corresponding admissible aggregate admission levels. The following corollary gives the resulting closed-form benchmark choice in the infinite-horizon regime. Corollary 0. In the infinite-horizon regime, an optimal benchmark solution is obtained by saturating the per-client buffer constraints, i.e., (49) λm⋆=BmK⋆,∀m, _m = B_mK , ∀ m, where K⋆K is chosen as the better of the two nearest feasible integers, namely (50) K⋆=⌈c¯∑m=1MBmC⌉orK⋆=max⌊c¯∑m=1MBmC⌋, 1.K = c _m=1^MB_mC K = \! \ c _m=1^MB_mC ,\,1 \. In the sequel, we adopt the benchmark design in Corollary 3, then the per-client buffer constraint is saturated in steady state. In particular, for all t>Kt>K, the buffer occupancy satisfies nm(t)=Bm,∀m.n_m(t)=B_m, ∀ m. 6.2. T-Slot ACDPP Upper Bound We next establish a standard T-slot upper bound for the surrogate penalty induced by the proposed ACDPP policy. This Lyapunov-based result provides the key control relation used in the subsequent regret analysis. Lemma 0. The cumulative surrogate penalty under the proposed ACDPP policy satisfies (51) [L(T+1)−L(1)]+V∑t=1T[p(t)]≤BT+V∑t=1Tp¯CK(t),E[L(T+1)-L(1)]+V _t=1^TE[p(t)]≤ BT+V _t=1^T p^CK(t), where (52) p¯CK(t) p^CK(t) =Dσ1(K−1)Λmin(t−K)+Λ¯−1∑τ=1t−1Λmin(τ)+Λ¯ =Dσ 1(K-1) _ (t-K)+ - 1 _τ=1^t-1 _ (τ)+ +ησ2(1(K−1)Λmin(t−K)+Λ¯−1∑τ=1t−1Λmin(τ)+Λ¯) +ησ^2 ( 1(K-1) _ (t-K)+ - 1 _τ=1^t-1 _ (τ)+ ) +10BPdim(ℓ∘ℋ)∑τ=1t−1Λmin(τ)+Λ¯1+log(∑τ=1t−1Λmax(τ)+Λ¯Pdim(ℓ∘ℋ)). +0B Pdim( ) _τ=1^t-1 _ (τ)+ 1+ \! ( _τ=1^t-1 _ (τ)+ Pdim( ) ). Proof. See Appendix B in (Zhao and Liang, 2026). ∎ 6.3. Regret Decomposition To derive the regret bound, we decompose the gap between the ACDPP-induced learning upper bound and the costless oracle benchmark into a sequence of finite-horizon correction terms. The key idea is to connect ℰ¯TACDPP E_T^ACDPP to ℰ¯Toracle E_T^oracle through several intermediate quantities. In particular, we introduce the auxiliary comparison target (53) p¯∞CK(t) p_∞^CK(t) ≜Dσ1Λ¯K−1Λ¯t+ησ2(1Λ¯K−1Λ¯t) Dσ 1 K- 1 t+ησ^2 ( 1 K- 1 t ) +10BPdim(ℓ∘ℋ)Λ¯t1+log(Λ¯tPdim(ℓ∘ℋ)). +0B Pdim( ) t 1+ \! ( tPdim( ) ). which corresponds to the surrogate penalty of the constant-admission policy in the infinite-horizon. The overall comparison chain is ℰ¯TACDPP→∑t=1T[p(t)]→∑t=1Tp¯CK(t)→∑t=1Tp¯∞CK(t)→ℰ¯Toracle, E_T^ACDPP\;→\; _t=1^TE[p(t)]\;→\; _t=1^T p^CK(t)\;→\; _t=1^T p_∞^CK(t)\;→\; E_T^oracle, where each arrow represents a finite-horizon comparison step. Intuitively, the first step relates the actual ACDPP-induced learning upper bound to its surrogate penalty; the second step uses the T-slot ACDPP upper bound to compare this surrogate with the finite-horizon comparison form induced by the auxiliary constant-admission policy; the third step removes the transient effects caused by the time-varying rectangular action space; and the final step connects the resulting infinite-horizon comparison target to the costless oracle benchmark. More precisely, define (54) Ω1(T)≜ℰ¯TACDPP−∑t=1T[p(t)], _1(T) E_T^ACDPP- _t=1^TE[p(t)], (55) Ω2(T)≜∑t=1Tp¯CK(t)−∑t=1Tp¯∞CK(t), _2(T) _t=1^T p^CK(t)- _t=1^T p_∞^CK(t), and (56) Ω3(T)≜∑t=1Tp¯∞CK(t)−ℰ¯Toracle. _3(T) _t=1^T p_∞^CK(t)- E_T^oracle. In addition, the T-slot ACDPP upper bound in Lemma 4 yields (57) ∑t=1T[p(t)]≤BVT+∑t=1Tp¯CK(t)+[L(1)]V. _t=1^TE[p(t)]≤ BVT+ _t=1^T p^CK(t)+ E[L(1)]V. Combining (54)–(57), we obtain (58) ℰ¯TACDPP−ℰ¯Toracle≤−Ω1(T)+Ω2(T)+Ω3(T)+O(TV). E_T^ACDPP- E_T^oracle≤- _1(T)+ _2(T)+ _3(T)+O\! ( TV ). It therefore remains to characterize the orders of the three correction terms. The technical proofs are deferred to the appendix. Lemma 0. Under the K-step retention policy, (59) Ω1(T)=O(1). _1(T)=O(1). Proof. See Appendix C in (Zhao and Liang, 2026). ∎ Lemma 0. Under the time-varying rectangular constraint (35), (60) Ω2(T)=O(11−ρ). _2(T)=O\! ( 11-ρ ). Proof. See Appendix D in (Zhao and Liang, 2026). ∎ Lemma 0. For any fixed comparison operating point (Λ¯,K)( ,K) satisfying Λ¯K=B¯ K= B, (61) Ω3(T)=O(logT). _3(T)=O( T). Proof. See Appendix E in (Zhao and Liang, 2026). ∎ 6.4. Regret and Constraint Guarantees Combining the T-slot ACDPP upper bound in Lemma 4 with the regret decomposition in Section 6.3 yields the main guarantees of the proposed policy: a regret bound relative to the costless oracle benchmark and a sampling-cost violation bound. We also provide an offline method for selecting the retention horizon K such that the cumulative buffer-occupancy violation remains bounded as O(1)O(1). Theorem 8. For any fixed ACDPP parameter V>0V>0 and any fixed 0<ρ<10<ρ<1, the regret as defined in (36) satisfies (62) Reg(T)=O(TV)+O(11−ρ)+O(logT).Reg(T)=O\! ( TV )+O\! ( 11-ρ )+O( T). Proof. Substituting Lemmas 5–7 into (58) and absorbing the O(1)O(1) term into the constants proves (62). ∎ Theorem 9. For any fixed ACDPP parameter V>0V>0 and any fixed 0<ρ<10<ρ<1, the cumulative sampling-cost constraint violation satisfies (63) VioS(T)=O(VT+V1−ρ).Vio^S(T)=O\! ( VT+ V1-ρ ). Proof. See Appendix F in (Zhao and Liang, 2026). ∎ Remark 1. Let V=Tγ,V=T^γ, and ρ=1−T−ϕρ=1-T^-φ. Then the cumulative regret and cumulative sampling-cost violation satisfy (64) Reg(T)=O(T1−γ)+O(Tϕ)+O(logT),Reg(T)=O\! (T^1-γ )+O\! (T^φ )+O( T), and (65) VioS(T)=O(T1+γ2+Tγ+ϕ2).Vio^S(T)=O\! (T 1+γ2+T γ+φ2 ). Therefore, for any γ∈(0,1)γ∈(0,1) and ϕ∈(0,1)φ∈(0,1), both Reg(T)Reg(T) and VioS(T)Vio^S(T) are sublinear in T. Remark 2. The cumulative buffer-occupancy violation is controlled through the offline selection of the retention horizon K. Since K is a time-invariant policy parameter rather than an online control variable, it must be chosen prior to execution of the proposed policy. Accordingly, one may evaluate the buffer-occupancy violation induced under candidate values of K and select a feasible retention horizon such that the resulting violation remains uniformly bounded over the horizon of interest. For such a choice of K, the cumulative buffer-occupancy violation satisfies (66) VioB(T)=O(1).Vio^B(T)=O(1). Thus, unlike the sampling-cost violation, which is regulated online through the virtual queue, the buffer-occupancy violation is absorbed into the offline parameter-selection stage through the choice of K. (a) Test accuracy on MNIST (non-i.i.d.) (b) Test 2 on CIFAR-10 (non-i.i.d.) (c) Test accuracy on ImageNette (i.i.d.) Figure 1. Current best test accuracy over communication rounds on MNIST, CIFAR-10, and ImageNette. (a) Buffer occupancy over communication rounds. (b) Sampling cost evolution over communication rounds. Figure 2. Buffer occupancy and cost evolution over communication rounds. 7. Numerical Evaluation In addition to the regret analysis in Section 6, we further evaluate the ACDPP policy on three image classification datasets: MNIST (LeCun, 1998), CIFAR-10 (Krizhevsky and others, 2009), and ImageNette (Deng and others, 2009).333Code is available at https://github.com/zhuoyijoeyzhao/AdaSamplingSFL. We compare the proposed ACDPP policy against three baselines: the costless oracle benchmark, the constant-admission policy, and a hybrid policy inspired by (Marfoq and others, 2023) that combines fresh-sample admission with stale-sample reuse under the same cost budget. Methods in (Zhou and others, 2020; Hu and others, 2024; Gong and others, 2024; Shi and others, 2023; Sun and others, 2025) cannot be included as baselines, since they do not explicitly model the admission-quantity decision as explained in Section 2.2. 7.1. Experimental Setup We consider a federated learning system with M=10M=10 clients. For MNIST and CIFAR-10, we adopt a non-i.i.d. partition in which each client contains samples from only two out of the ten classes. For ImageNette, the training data are partitioned i.i.d. and evenly across clients. We adopt LeNet (LeCun and others, 2002) as the prediction model for MNIST, while for CIFAR-10 and ImageNette we use ResNet-9 (He and others, 2016). For MNIST, the client buffer capacities are set to 8,9,10,11,12,8,9,10,11,12\8,9,10,11,12,8,9,10,11,12\, and the long-term sampling-cost budget is C=55C=55. For CIFAR-10 and ImageNette, due to the increased task difficulty, both the client buffer capacities and the sampling-cost budget are set to be, respectively, 2×2× and 4×4× those of MNIST. The per-sample acquisition cost c(t)c(t) is independently drawn from Unif[1,10]Unif[1,10]. In each communication round, every client performs E=10E=10 local epochs for all three datasets. The learning rates are set to η=0.5η=0.5 for MNIST, η=5×10−3η=5× 10^-3 for CIFAR-10, and η=5×10−4η=5× 10^-4 for ImageNette. For the hybrid baseline, five clients train only on retained stale samples, while the other five admit new samples according to the constant-admission rule under the same cost budget. 7.2. Main Results We report the current-best test accuracy on all three datasets in Figure 1. Each curve is averaged over 10 independent runs, and the shaded region indicates the 80%80\% confidence interval. For brevity, we present the buffer occupancy and per-round sampling cost evolution on ImageNette only in Figure 2, since the same qualitative behavior is observed on the other datasets. As shown in Figure 1, the proposed ACDPP policy consistently outperforms both the hybrid baseline and the constant-admission baseline, while remaining close to the oracle policy. On MNIST in Figure 1(a), ACDPP improves the average test accuracy by approximately 1.9 and 3.5 percentage points over the hybrid and constant-admission baselines, respectively. On CIFAR-10 in Figure 1(b), the corresponding improvements are 26.7 and 3.5 percentage points. On ImageNette in Figure 1(c), ACDPP further improves the average test accuracy by 4.1 and 1.8 percentage points over the hybrid and constant-admission baselines, respectively. This advantage is also reflected in the convergence speed visible in Figure 1. To quantify this effect, we use the first communication round at which each policy reaches a target test accuracy, with target levels set to 85%85\% for MNIST, 70%70\% for CIFAR-10, and 70%70\% for ImageNette. Under this criterion, ACDPP converges about 2.3×2.3× and 2.2×2.2× faster than the hybrid baseline on MNIST and ImageNette, respectively, while on CIFAR-10 the hybrid baseline fails to reach the target accuracy within the experiment horizon, as seen in Figure 1(b). Relative to the constant-admission baseline, the corresponding speedups are 2.6×2.6×, 1.7×1.7×, and 1.3×1.3× on MNIST, CIFAR-10, and ImageNette, respectively. An additional observation is that the hybrid baseline behaves very differently across tasks. Similar to the interpretation in (Marfoq and others, 2023), it can converge faster than constant-admission on a simple task such as MNIST. However, on more difficult tasks, especially under distribution heterogeneity, its weakness becomes much more pronounced. As shown in Figure 1(b), on non-i.i.d. CIFAR-10 the hybrid baseline performs substantially worse than both ACDPP and constant-admission, even though its fresh-sample component is scheduled according to the optimal constant-admission constant-admission rule under the same cost budget. Figure 2 further verifies that the proposed ACDPP policy satisfies both the buffer and sampling-cost constraints. In particular, the buffer occupancy in Figure 2(a) remains within the prescribed memory budget, while the stability of the cost-debt queue in Figure 2(b) is consistent with the long-term sampling-cost guarantee established by the Lyapunov analysis. This reflects the two-level design of ACDPP: sampling cost is controlled online, while buffer feasibility is enforced offline through the choice of the retention horizon K. Consequently, ACDPP remains resource-feasible while still achieving performance close to the costless oracle benchmark. 8. Conclusion In this work, we have studied streaming FL with limited client memory and time-varying sampling costs. We consider a framework of joint server-side sample-admission and client-side memory-management with the objective of minimizing the cumulative excess population risk under sampling-cost and buffer constraints. To tackle this problem, we first derive a learning-error bound that explicitly captures the roles of instantaneous training sample size, distinct-sample growth, and reuse imbalance through an effective sample size representation. The proposed ACDPP policy leverages a novel learning-error bound that captures the impacts of sample reuse and effective sample size, as well as DPP minimization with a surrogate penalty and time-varying rectangular admission constraints. Through a multi-step comparison analysis together with Lyapunov drift arguments, we have established explicit guarantees in terms of sublinear regret and sampling-cost violation, while showing that the buffer-occupancy violation can be controlled through offline selection of the retention horizon. Experimental results on multiple datasets further demonstrate that the proposed policy achieves strong learning performance in comparison with common baselines and the oracle benchmark. An interesting direction for future work is to extend the present framework to settings with concept drift and to integrate online sample admission with labeling decisions. References K. Bonawitz et al. (2019) Towards federated learning at scale: system design. Proc. Mach. Learn. Syst. 1, p. 374–388. Cited by: §1. G. Cormode and S. Muthukrishnan (2005) An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55 (1). Cited by: §2.1. M. De Lange et al. (2021) A continual learning survey: defying forgetting in classification tasks. IEEE Trans. Pattern Anal. Mach. Intell. 44 (7), p. 3366–3385. Cited by: §2.1. J. Deng et al. (2009) Imagenet: a large-scale hierarchical image database. In IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), p. 248–255. Cited by: §7. J. Gama et al. (2013) On evaluating stream learning algorithms. Mach. Learn. 90 (3), p. 317–346. Cited by: §2.1. H. M. Gomes et al. (2019) Machine learning for streaming data: state of the art, challenges, and opportunities. ACM SIGKDD Explor. Newsl. 21 (2). Cited by: §2.1. C. Gong et al. (2024) ODE: an online data selection framework for federated learning with limited storage. IEEE/ACM Trans. Netw. 32 (4), p. 2794–2809. Cited by: §1, §1, §2.2, §7. K. He et al. (2016) Deep residual learning for image recognition. In IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), p. 770–778. Cited by: §7.1. C. Hu et al. (2024) Energy-efficient federated edge learning with streaming data: a lyapunov optimization approach. IEEE Trans. Commun.. Cited by: §1, §1, §2.2, §7. T. Huynh et al. (2025) Streaming federated learning with markovian data. arXiv preprint arXiv:2503.18807. Cited by: §1, §2.2. P. Kairouz and H. B. McMahan (2021) Advances and open problems in federated learning. Found. Trends Mach. Learn. 14 (1-2), p. 1–210. Cited by: §1. S. P. Karimireddy et al. (2020) Scaffold: stochastic controlled averaging for federated learning. In Int. Conf. Mach. Learn. (ICML), Cited by: §1. A. Krizhevsky et al. (2009) Learning multiple layers of features from tiny images. Cited by: §7. Y. LeCun et al. (2002) Gradient-based learning applied to document recognition. Proc. IEEE 86 (11). Cited by: §7.1. Yann. LeCun (1998) The mnist database of handwritten digits. http://yann. lecun. com/exdb/mnist/. Cited by: §7. O. Marfoq et al. (2023) Federated learning for data streams. In Int. Conf. Artif. Intell. Stat. (AISTATS), Cited by: §A.1, §A.1, §A.1, §A.1, §A.3, §1, §2.2, §4.2, §7.2, §7. B. McMahan et al. (2017) Communication-efficient learning of deep networks from decentralized data. In Int. Conf. Artif. Intell. Stat. (AISTATS), Cited by: §1. M. J. Neely (2010) Stability and capacity regions or discrete time queueing networks. arXiv preprint arXiv:1003.3396. Cited by: Appendix F. M. Neely (2022) Stochastic network optimization with application to communication and queueing systems. Springer Nature. Cited by: §5. J. Shi et al. (2023) Self-supervised on-device federated learning from unlabeled streams. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 42 (12). Cited by: §1, §1, §2.2, §7. Y. Sun et al. (2025) Learn how to query from unlabeled data streams in federated learning. In AAAI Conf. Artif. Intell. (AAAI), Cited by: §1, §1, §2.2, §7. A. Z. Tan et al. (2022) Towards personalized federated learning. IEEE Trans. Neural Netw. Learn. Syst. 34 (12). Cited by: §1. J. Wang et al. (2020) Tackling the objective inconsistency problem in heterogeneous federated optimization. In Adv. Neural Inf. Process. Syst. (NeurIPS), Cited by: §1. L. Wang et al. (2024) A comprehensive survey of continual learning: theory, method and application. IEEE Trans. Pattern Anal. Mach. Intell. 46 (8). Cited by: §2.1. S. Wang et al. (2019) Adaptive federated learning in resource constrained edge computing systems. IEEE J. Sel. Areas Commun.. Cited by: §1. R. Zhang et al. (2024) Federating from history in streaming federated learning. In Int. Symp. Theory Algorithmic Found. Protocol Des. Mobile Netw. Mobile Comput. (MobiHoc), p. 151–160. Cited by: §1, §2.2. Z. Zhao and B. Liang (2026) Adaptive data admission and retention for streaming federated learning. Note: https://tinyurl.com/AdaDataSamplingSFL Cited by: §4.2, §6.2, §6.3, §6.3, §6.3, §6.4. Z. Zhou et al. (2020) CEFL: online admission control, data scheduling, and accuracy tuning for cost-efficient federated learning across edge nodes. IEEE Internet Things J. 7 (10), p. 9341–9356. Cited by: §1, §1, §2.2, §7. Supplementary Material for the paper “Adaptive Data Admission and Retention for Streaming Federated Learning” Zhuoyi Zhao and Ben Liang Appendix A Proof of Theorem 1 We prove Theorem 1 by combining an optimization recursion (which yields an optimization-regret bound) with (i) a variance/bias control term expressed via the instantaneous mini-batch size ntn_t and the effective sample size NefftN_eff^t, and (i) a uniform generalization bound controlled by the pseudo-dimension. A.1. Optimization regret bound from recursion We first isolate the optimization component of the cumulative excess-risk bound. The derivation builds on the recursion-based proof framework in Appendix B.5 of (Marfoq and others, 2023), adapted to the present full-batch memory-based streaming federated learning model. In particular, we follow the same empirical-optimization viewpoint as (Marfoq and others, 2023): the optimization recursion is first established with respect to a policy-induced empirical objective, and the gap between this empirical objective and the population objective is then controlled by a separate uniform generalization bound. Under policy π, let (67) ωiπ(t)≜Aiπ(t)∑j=1Nπ(t)Ajπ(t),i=1,…,Nπ(t), _i^π(t) A_i^π(t) _j=1^N^π(t)A_j^π(t), i=1,…,N^π(t), and define the cumulative multiplicity-weighted empirical objective (68) F^tall(θ)≜∑i=1Nπ(t)ωiπ(t)ℓ(θ;zi). F_t all(θ) _i=1^N^π(t) _i^π(t) (θ;z_i). This objective is the analogue of the global weighted empirical objective LS(λ)L_S^(λ) in (Marfoq and others, 2023). It aggregates all distinct samples used up to round t, with weights proportional to their cumulative reuse counts. In contrast, the actual local update at round t is performed using only the samples currently stored in the clients’ memories. We denote the corresponding memory-induced empirical objective by (69) F^tmem(θ)≜1nπ(t)∑z∈Q(t)ℓ(θ;z). F_t mem(θ) 1n^π(t) _z∈ Q(t) (θ;z). The cumulative empirical optimization error is defined as (70) ℰTopt(π)≜∑t=1T[F^tall(θ(t))−F^tall,⋆].E_T opt(π) _t=1^TE\! [ F_t all(θ^(t))- F_t all, ]. where F^tall,⋆≜minθ∈ΘF^tall(θ). F_t all, _θ∈ F_t all(θ). The key round-dependent quantity is therefore the empirical gradient mismatch between the cumulative multiplicity-weighted objective and the current memory-induced objective: (71) σ¯2(t)≜[supθ∈Θ‖∇F^tall(θ)−∇F^tmem(θ)‖22]. σ^2(t) \! [ _θ∈ \|∇ F_t all(θ)-∇ F_t mem(θ) \|_2^2 ]. Thus, σ¯2(t) σ^2(t) measures how far the gradient used by the round-t memory-based update deviates from the gradient of the policy-induced cumulative empirical objective. The following lemma rewrites the one-step optimization recursion in Appendix B.5 of (Marfoq and others, 2023) under our notation and derives the corresponding cumulative empirical optimization-error bound. Lemma 0. Under Assumptions 1–4, the iterates θ(t)t=1T\θ^(t)\_t=1^T generated under policy π satisfy the following one-step optimization recursion: (72) [‖θ(t+1)−θ⋆‖22] \! [\|θ^(t+1)\!-\!θ \|_2^2 ] ≤[‖θ(t)−θ⋆‖22]−2η[F^tall(θ(t))−F^tall,⋆] \!≤\!E\! [\|θ^(t)\!-\!θ \|_2^2 ]\!-\!2η\,E\! [ F_t all(θ^(t))\!-\! F_t all, ] +2ηDσ¯(t)+η2(2σ¯2(t)+C1)+η4C2, +2η D\, σ(t)+η^2\! (2 σ^2(t)+C_1 )+η^4C_2, where (73) C1≜G(5G+2LD2(1−E−1)),C2≜4L2G2(1−E−1),C_1 G\! (5G+2LD 2(1-E^-1) ), C_2 4L^2G^2(1-E^-1), and (74) ℰTopt(π)≤D22η+D∑t=1Tσ¯(t)+η2∑t=1T(2σ¯2(t)+C1)+η32C2T.E_T opt(π)≤ D^22η+D _t=1^T σ(t)+ η2 _t=1^T\! (2 σ^2(t)+C_1 )+ η^32C_2T. Proof. The one-step recursion in (72) follows directly from the derivation in Appendix B.5 of (Marfoq and others, 2023), after rewriting the empirical objective and the empirical gradient mismatch under the notation introduced above. The higher-order terms are regrouped into the constants C1C_1 and C2C_2 in (73). Rearranging (72) gives (75) 2η[F^tall(θ(t))−F^tall,⋆] 2 \! [ F_t all(θ^(t))- F_t all, ] ≤[‖θ(t)−θ⋆‖22]−[‖θ(t+1)−θ⋆‖22] \! [\|θ^(t)-θ \|_2^2 ]-E\! [\|θ^(t+1)-θ \|_2^2 ] +2ηDσ¯(t)+η2(2σ¯2(t)+C1)+η4C2. +2η D σ(t)+η^2\! (2 σ^2(t)+C_1 )+η^4C_2. Summing (75) over t=1,…,Tt=1,…,T telescopes the squared-distance terms: ∑t=1T(‖θ(t)−θ⋆‖22−‖θ(t+1)−θ⋆‖22)=‖θ(1)−θ⋆‖22−‖θ(T+1)−θ⋆‖22≤D2, _t=1^T\!\! (\!E\|θ^(t)\!\!-\!θ \|_2^2\!-\!E\|θ^(t+1)\!\!\!-\!θ \|_2^2\! )\!=\!E\|θ^(1)-θ \|_2^2\!-\!E\|θ^(T+1)\!\!-\!θ \|_2^2\!≤\!D^2, where the last inequality follows from the boundedness of Θ and the nonnegativity of squared norms. Dividing both sides by 2η2η yields (74). ∎ A.2. Variance control via effective sample size We next refine the empirical gradient mismatch σ¯2(t) σ^2(t) by explicitly separating the effects of distinct-sample growth and sample-reuse imbalance. Recall from Assumption 4 that the single-sample population-gradient variance satisfies (76) z∼[‖∇θℓ(θ;z)−∇F(θ)‖22]≤σ2,∀θ∈Θ.E_z [\| _θ (θ;z)-∇ F_P(θ)\|_2^2 ]≤σ^2, ∀θ∈ . Under the effective-sample-size variance control induced by repeated sample reuse, the empirical gradient mismatch at round t satisfies (77) σ¯2(t)≤σ2(1nπ(t)−1Nπ(t)~π(t)). σ^2(t)≤σ^2\! ( 1n^π(t)\!-\! 1N^π(t) V^π(t) ). Substituting (77) into Lemma 1 yields (78) ℰTopt(π) _T opt(π) ≤D22η+Dσ∑t=1T1nπ(t)−1Nπ(t)~π(t) ≤ D^22η+Dσ _t=1^T 1n^π(t)- 1N^π(t) V^π(t) +ησ2∑t=1T(1nπ(t)−1Nπ(t)~π(t))+ηC12T+η3C22T. +ησ^2 _t=1^T ( 1n^π(t)- 1N^π(t) V^π(t) )+ η C_12T+ η^3C_22T. A.3. Generalization term controlled by pseudo-dimension We next bound the generalization gap between the population objective F_P and the cumulative multiplicity-weighted empirical objective F^tall F_t all. It is essentially an application of Theorem 4.1 in (Marfoq and others, 2023) to our setting, with the effective sample size decomposition. As a result, the generalization bound is expressed explicitly in terms of cumulative distinct-sample growth and reuse imbalance. The key point is that, under repeated sample reuse, the effective statistical complexity is governed not only by the number of distinct samples, but also by the uniformity of their reuse. Lemma 0 (Uniform generalization bound with effective sample size). Assume ℓ(θ;z)∈[0,B] (θ;z)∈[0,B] for all θ∈Θθ∈ and z. Then for each round t, the expected generalization gap is bounded by (79) [supθ∈Θ| [ _θ∈ | F(θ)−F^tall(θ)|] F_P(θ)- F_t all(θ) | ] ≤10BPdim(ℓ∘ℋ)Nπ(t)~π(t)1+log(Nπ(t)Pdim(ℓ∘ℋ)). ≤ 0B Pdim( )N^π(t) V^π(t) 1+ \! ( N^π(t)Pdim( ) ). Proof. Recall the policy-induced weights ωiπ(t) _i^π(t) and the cumulative multiplicity-weighted empirical objective F^tall F_t all defined in (67)–(68). Consider the loss-composed hypothesis class (80) ℱ≜z↦ℓ(θ;z):θ∈Θ,F \z (θ;z):θ∈ \, which is uniformly bounded in [0,B][0,B] by assumption. By a standard weighted symmetrization argument, the expected uniform generalization gap is bounded by twice the weighted empirical Rademacher complexity of ℱF. Moreover, the effective normalization is determined by the ℓ2 _2 norm of the weight vector: (81) ∑i=1Nπ(t)(ωiπ(t))2=∑i=1Nπ(t)(Aiπ(t))2(∑i=1Nπ(t)Aiπ(t))2=1Neffπ(t)=1Nπ(t)~π(t), _i=1^N^π(t)( _i^π(t))^2= _i=1^N^π(t)(A_i^π(t))^2 ( _i=1^N^π(t)A_i^π(t) )^2= 1N_eff^π(t)= 1N^π(t) V^π(t), Applying the standard pseudo-dimension bound for bounded real-valued function classes yields (82) [supθ∈Θ| \! [ _θ∈ | F(θ)−F^tall(θ)|] F_P(θ)- F_t all(θ) | ] ≤10BPdim(ℓ∘ℋ)Nπ(t)~π(t)1+log(Nπ(t)Pdim(ℓ∘ℋ)), ≤ 0B Pdim( )N^π(t) V^π(t) 1+ \! ( N^π(t)Pdim( ) ), which proves (79). ∎ A.4. Proof of Theorem 1 Proof of Theorem 1. We combine the optimization-error bound in (78) with the generalization bound in Lemma 2. Specifically, (78) controls the cumulative optimization component ℰTopt(π)E_T opt(π) with respect to the cumulative multiplicity-weighted empirical objective F^tall F_t all in terms of the policy-induced training sample size nπ(t)n^π(t) and effective sample size Nπ(t)~π(t)N^π(t) V^π(t), while Lemma 2 bounds the generalization gap between the population objective F_P and F^tall F_t all by a term depending on the pseudo-dimension and the effective sample size. Combining the optimization bound in (78) with the generalization bound in Lemma 2 yields the desired cumulative excess-risk upper bound. Finally, absorbing the initialization term D22η D^22η and other lower-order constants into the constant term C2C_2 gives the statement of Theorem 1. ∎ Appendix B Proof of Lemma 4 Consider the feasible constant-admission comparison policy associated with the benchmark operating point (Λ¯,K)( ,K). For an arbitrary round t, let (t)O(t) denote the realized system state induced by the proposed ACDPP policy over rounds 1,…,t−11,…,t-1, and suppose that at round t the server switches to the comparison admission vector CK(t) λ^CK(t). Under the K-step retention policy, each admitted sample remains in memory for exactly K rounds. Hence the instantaneous batch size and cumulative distinct sample count under the comparison policy satisfy (83) nC(t)=n(t)−Λ(t−K)+Λ¯,NC(t)=N(t−1)+Λ¯.n^C(t)=n(t)- (t-K)+ , N^C(t)=N(t-1)+ . Substituting (83) into the penalty definition (29) gives the one-slot drift-plus-penalty objective (84) Jt(CK(t))=Z(t)(c(t)Λ¯−C)+VpCK(t),J_t( λ^CK(t))=Z(t) (c(t) -C )+V\,p^CK(t), where pCK(t)p^CK(t) is the per-round penalty induced by the comparison policy. Next, since the admissible action space satisfies (85) Λmin(t)≤Λ(t)≤Λmax(t), _ (t)≤ (t)≤ _ (t), we have the lower bounds (86) nC(t)≥(K−1)Λmin(t−K)+Λ¯,n^C(t)≥(K-1) _ (t-K)+ , and (87) NC(t)≥∑τ=1t−1Λmin(τ)+Λ¯.N^C(t)≥ _τ=1^t-1 _ (τ)+ . Since the penalty function in (29) is decreasing in both the instantaneous batch size and the cumulative distinct-sample count, it follows that (88) pCK(t)≤p¯CK(t),p^CK(t)≤ p^CK(t), where p¯CK(t) p^CK(t) is given by (52). Therefore, (89) Jt(CK(t))≤Z(t)(c(t)Λ¯−C)+Vp¯CK(t).J_t( λ^CK(t))≤ Z(t) (c(t) -C )+V p^CK(t). Recall that the one-slot drift-plus-penalty upper bound holds for any feasible admission vector λ: (90) Δ((t))+V[p(t)∣(t)]≤B+[Jt()∣(t)]. (O(t))+VE[p(t) (t)]≤ B+E[J_t( λ) (t)]. By definition, the ACDPP policy chooses (91) ⋆(t)∈argminJt(), λ (t)∈ _ λJ_t( λ), and hence (92) Jt(⋆(t))≤Jt(CK(t)).J_t( λ (t))≤ J_t( λ^CK(t)). Substituting (92) into (90) yields (93) Δ((t))+V[p(t)∣(t)]≤B+[Jt(CK(t))∣(t)]. (O(t))+VE[p(t) (t)]≤ B+E[J_t( λ^CK(t)) (t)]. Using (89), we obtain (94) Δ((t))+V[p(t)∣(t)]≤B+[Z(t)(c(t)Λ¯−C)∣(t)]+Vp¯CK(t). (O(t))\!+\!VE[p(t)\! \!O(t)]\!≤\!B\!+\!E\! [Z(t) (c(t) -C )\! \!O(t) ]\!+\!V p^CK(t). Now take total expectation. Since the sampling-cost process c(t)\c(t)\ is independent of the queue state Z(t)Z(t) under the comparison policy, we have (95) [Z(t)(c(t)Λ¯−C)]=[Z(t)][c(t)Λ¯−C].E\! [Z(t) (c(t) -C ) ]=E[Z(t)]\,E\! [c(t) -C ]. Because the benchmark comparison policy is feasible, it satisfies the long-term sampling-cost constraint, and therefore (96) [c(t)Λ¯−C]≤0.E\! [c(t) -C ]≤ 0. Hence (94) implies (97) [L(t+1)−L(t)]+V[p(t)]≤B+Vp¯CK(t).E[L(t+1)-L(t)]+VE[p(t)]≤ B+V p^CK(t). Summing (97) over t=1,…,Tt=1,…,T gives (98) [L(T+1)−L(1)]+V∑t=1T[p(t)]≤BT+V∑t=1Tp¯CK(t),E[L(T+1)-L(1)]+V _t=1^TE[p(t)]≤ BT+V _t=1^T p^CK(t), which proves (51). Appendix C Proof of Lemma 5 The only difference between the finite-horizon learning upper bound ℰ¯TACDPP E_T^ACDPP and the cumulative surrogate penalty ∑t=1T[p(t)] _t=1^TE[p(t)] comes from the reuse-uniformity factor ~π(t) V^π(t), since the surrogate penalty replaces 1Nπ(t)~π(t) 1N^π(t) V^π(t) by 1Nπ(t) 1N^π(t). Here and below, Ot(⋅)O_t(·) and Θt(⋅) _t(·) denote big-O and big-Θ with respect to the per-round index t. Under the K-step retention policy, only the samples admitted in the most recent K−1K-1 rounds fail to complete their full K reuse cycles by round t. Therefore, the first- and second-moment deficits of the reuse counts are both Ot(1)O_t(1), while the cumulative number of distinct samples satisfies Nπ(t)=Θt(t)N^π(t)= _t(t). It follows that (99) 1−~π(t)=Ot(t−1),1- V^π(t)=O_t(t^-1), and hence (100) 1Nπ(t)~π(t)−1Nπ(t)=1−~π(t)Nπ(t)~π(t)=Ot(t−2). 1N^π(t) V^π(t)- 1N^π(t)= 1- V^π(t)N^π(t) V^π(t)=O_t(t^-2). Now compare the terms in the learning upper bound with their surrogate counterparts. Since nπ(t)=Θt(1)n^π(t)= _t(1) under K-step retention and Nπ(t)=Θt(t)N^π(t)= _t(t), the quantity 1nπ(t) 1n^π(t)−-1Nπ(t)~π(t) 1N^π(t) V^π(t) remains bounded away from zero for all sufficiently large t. Therefore, the square-root function is locally Lipschitz in a neighborhood of this argument, and the square-root term differs from its surrogate counterpart by at most Ot(t−2)O_t(t^-2). The same order follows immediately for the linear term. For the pseudo-dimension term, define xt≜1Nπ(t)~π(t),yt≜1Nπ(t).x_t 1N^π(t) V^π(t), y_t 1N^π(t). By (100), we have xt−yt=Ot(t−2)x_t-y_t=O_t(t^-2). Since the map x↦10BPdim(ℓ∘ℋ)x1+log(1xPdim(ℓ∘ℋ))x 10B Pdim( )\,x 1+ \! ( 1x\,Pdim( ) ) is locally Lipschitz for sufficiently small positive x, the pseudo-dimension term also differs from its surrogate counterpart by at most Ot(t−2)O_t(t^-2). Combining the square-root, linear, and pseudo-dimension terms yields a per-round discrepancy of order Ot(t−2)O_t(t^-2). Summing over t=1,…,Tt=1,…,T gives (101) ℰ¯TACDPP−∑t=1T[p(t)]=O(1), E_T^ACDPP- _t=1^TE[p(t)]=O(1), which proves Lemma 5. Appendix D Proof of Lemma 6 Under the time-varying rectangular constraint (35), the lower bounds on the instantaneous training sample size and the cumulative number of distinct samples are (102) nlb(t)=KΛ¯−(K−1)Λ¯ρt−K,Nlb(t)=Λ¯t−Λ¯∑τ=1t−1ρτ.n_lb(t)=K -(K-1) \,ρ^\,t-K, N_lb(t)= t- _τ=1^t-1ρ^τ. It follows from (102) that, for all t≥Kt≥ K, (103) 1nlb(t)−1Λ¯K 1n_lb(t)- 1 K =1Λ¯(1K−(K−1)ρt−K−1K) = 1 ( 1K-(K-1)ρ^t-K- 1K ) =(K−1)ρt−KΛ¯K(K−(K−1)ρt−K)≤κ1ρt−K, = (K-1)ρ^t-K K (K-(K-1)ρ^t-K )≤ _1ρ^t-K, where the inequality follows from K−(K−1)ρt−K≥1K-(K-1)ρ^t-K≥ 1, and κ1=K−1Λ¯K _1= K-1 K. Similarly, because ∑τ=1t−1ρτ=ρ(1−ρt−1)1−ρ≤11−ρ, _τ=1^t-1ρ^τ= ρ(1-ρ^t-1)1-ρ≤ 11-ρ, we have Nlb(t)=Λ¯t−δt,0≤δt≤Λ¯1−ρ.N_lb(t)= t- _t, 0≤ _t≤ 1-ρ. Therefore, 1Nlb(t)−1Λ¯t=δt(Λ¯t)(Λ¯t−δt). 1N_lb(t)- 1 t= _t( t)( t- _t). Using the bound on δt _t, we obtain (104) 1Nlb(t)−1Λ¯t≤Λ¯/(1−ρ)(Λ¯t)(Λ¯t−Λ¯/(1−ρ))=1Λ¯((1−ρ)t2−t). 1N_lb(t)- 1 t≤ /(1-ρ)( t) ( t- /(1-ρ) )= 1 ((1-ρ)t^2-t ). We now compare p¯CK(t) p^CK(t) with p¯∞CK(t) p_∞^CK(t) term by term. For the square-root term, define ut≜1nlb(t)−1Nlb(t),vt≜1Λ¯K−1Λ¯t.u_t 1n_lb(t)- 1N_lb(t), v_t 1 K- 1 t. By (LABEL:eq:app-nlb-recip) and (104), ut−vt≤κ1ρt−K+1Λ¯((1−ρ)t2−t).u_t-v_t≤ _1ρ^\,t-K+ 1 ((1-ρ)t^2-t ). Since vtv_t is bounded away from zero for all sufficiently large t, the map x↦x x is locally Lipschitz around vtv_t. Therefore, there exists a constant κ2>0 _2>0 such that the square-root term in p¯CK(t) p^CK(t) differs from its counterpart in p¯∞CK(t) p_∞^CK(t) by at most κ2ρt−K+κ2(1−ρ)t2−t. _2ρ^\,t-K+ _2(1-ρ)t^2-t. The same bound also applies to the linear term. For the pseudo-dimension term, the only dependence is through the reciprocal sample-size factor and the logarithmic factor. Using (104), together with the local Lipschitz continuity of the map x↦10BPdim(ℓ∘ℋ)x1+log(1xPdim(ℓ∘ℋ)),x 10B Pdim( )\,x 1+ \! ( 1x\,Pdim( ) ), there exists a constant κ3>0 _3>0 such that the pseudo-dimension term differs by at most κ3ρt−K+κ3(1−ρ)t2−t. _3ρ^\,t-K+ _3(1-ρ)t^2-t. Combining the three terms, there exists a constant κ4>0 _4>0 such that (105) |p¯CK(t)−p¯∞CK(t)|≤κ4ρt−K+κ4(1−ρ)t2−t,t≥K. | p^CK(t)- p_∞^CK(t) |≤ _4ρ^\,t-K+ _4(1-ρ)t^2-t, t≥ K. Summing (105) over t=1,…,Tt=1,…,T gives (106) ∑t=1T|p¯CK(t)−p¯∞CK(t)| _t=1^T | p^CK(t)- p_∞^CK(t) | ≤∑t=1K−1|p¯CK(t)−p¯∞CK(t)|+κ4∑t=KTρt−K ≤ _t=1^K-1 | p^CK(t)- p_∞^CK(t) |+ _4 _t=K^Tρ^\,t-K +κ4∑t=1T1(1−ρ)t2−t. + _4 _t=1^T 1(1-ρ)t^2-t. The first term is finite because it contains only finitely many indices. The second term is bounded by κ4∑j=0∞ρj=κ41−ρ. _4 _j=0^∞ρ^j= _41-ρ. For the third term, let t0≜⌈21−ρ⌉.t_0 21-ρ . We split the sum as ∑t=1Tκ4(1−ρ)t2−t=∑t=1t0−1κ4(1−ρ)t2−t+∑t=t0Tκ4(1−ρ)t2−t. _t=1^T _4(1-ρ)t^2-t= _t=1^t_0-1 _4(1-ρ)t^2-t+ _t=t_0^T _4(1-ρ)t^2-t. Since t0=O((1−ρ)−1)t_0=O((1-ρ)^-1) and the per-round discrepancy is uniformly bounded, the first sum contributes O((1−ρ)−1)O((1-ρ)^-1). For the second sum, when t≥t0t≥ t_0, we have t≥21−ρ,t≥ 21-ρ, which implies 12(1−ρ)t2≥t, 12(1-ρ)t^2≥ t, or equivalently, (1−ρ)t2−t≥12(1−ρ)t2.(1-ρ)t^2-t≥ 12(1-ρ)t^2. Hence, when t>=t0t>=t_0, κ4(1−ρ)t2−t≤2κ4(1−ρ)t2. _4(1-ρ)t^2-t≤ 2 _4(1-ρ)t^2. Therefore, ∑t=t0Tκ4(1−ρ)t2−t≤2κ41−ρ∑t=t0∞1t2=O(11−ρ). _t=t_0^T _4(1-ρ)t^2-t≤ 2 _41-ρ _t=t_0^∞ 1t^2=O\! ( 11-ρ ). Combining the two parts yields ∑t=1T1(1−ρ)t2−t=O(11−ρ). _t=1^T 1(1-ρ)t^2-t=O\! ( 11-ρ ). Hence (107) ∑t=1T|p¯CK(t)−p¯∞CK(t)|=O(11−ρ), _t=1^T | p^CK(t)- p_∞^CK(t) |=O\! ( 11-ρ ), which proves Lemma 6. Appendix E Proof of Lemma 7 Recall that, under the costless oracle policy, the cumulative learning upper bound takes the form (108) ℰ¯Toracle E_T^oracle =∑t=1T[Dσ1B¯−1B¯t+ησ2(1B¯−1B¯t) = _t=1^T [Dσ 1 B- 1 Bt+ησ^2 ( 1 B- 1 Bt ) +10BPdim(ℓ∘ℋ)B¯t1+log(B¯tPdim(ℓ∘ℋ))], +0B Pdim( ) Bt 1+ \! ( BtPdim( ) ) ], where B¯≜∑m=1MBm B _m=1^MB_m. Compare the per-round term in p¯∞CK(t) p_∞^CK(t) with the corresponding per-round term in (108). Under the condition Λ¯K=B¯ K= B, the steady-state terms coincide exactly: 1Λ¯K=1B¯. 1 K= 1 B. Thus the only mismatch comes from the distinct-sample-growth terms 1Λ¯tand1B¯t. 1 t 1 Bt. Their difference is (109) 1Λ¯t−1B¯t=1Λ¯t−1Λ¯Kt=K−1B¯t=Ot(t−1). 1 t- 1 Bt= 1 t- 1 K\,t= K-1 B\,t=O_t(t^-1). We again compare the three terms separately. For the square-root term, since the underlying argument is bounded away from zero for sufficiently large t, the square-root map is locally Lipschitz, and the discrepancy is therefore Ot(t−1)O_t(t^-1). The same order follows immediately for the linear term. For the pseudo-dimension term, note that 10BPdim(ℓ∘ℋ)Λ¯t1+log(Λ¯tPdim(ℓ∘ℋ))10B Pdim( ) t 1+ \! ( tPdim( ) ) and its oracle counterpart differ only through the factor 1/(Λ¯t)1/( t) versus 1/(B¯t)1/( Bt). Since the map x↦10BPdim(ℓ∘ℋ)x1+log(1xPdim(ℓ∘ℋ))x 10B Pdim( )\,x 1+ \! ( 1x\,Pdim( ) ) is locally Lipschitz for sufficiently small positive x, the resulting discrepancy is of lower order than t−1t^-1 and can be absorbed into the same bound. Hence the per-round difference between p¯∞CK(t) p_∞^CK(t) and the oracle term is Ot(t−1)O_t(t^-1). Summing over t=1,…,Tt=1,…,T yields (110) ∑t=1Tp¯∞CK(t)−ℰ¯Toracle=O(logT), _t=1^T p_∞^CK(t)- E_T^oracle=O( T), which proves Lemma 7. Appendix F Proof of Theorem 9 From Lemma 4 and the nonnegativity of the penalty term, (111) [L(T+1)−L(1)]≤BT+V∑t=1Tp¯CK(t).E[L(T+1)-L(1)]≤ BT+V _t=1^T p^CK(t). Using Lemma 6, we have ∑t=1Tp¯CK(t)=∑t=1Tp¯∞CK(t)+O(11−ρ). _t=1^T p^CK(t)= _t=1^T p_∞^CK(t)+O\! ( 11-ρ ). Since each term p¯∞CK(t) p_∞^CK(t) is uniformly bounded in t, it follows that (112) ∑t=1Tp¯CK(t)=O(T)+O(11−ρ). _t=1^T p^CK(t)=O(T)+O\! ( 11-ρ ). Substituting (112) into (111) yields (113) [L(T+1)]=O(VT)+O(V1−ρ).E[L(T+1)]=O(VT)+O\! ( V1-ρ ). Since L(t)=12Z(t)2L(t)= 12Z(t)^2, it follows that (114) [Z(T+1)2]=O(VT)+O(V1−ρ),E[Z(T+1)^2]=O(VT)+O\! ( V1-ρ ), and therefore, by Jensen’s inequality, (115) [Z(T+1)]=O(VT+V1−ρ).E[Z(T+1)]=O\! ( VT+ V1-ρ ). By the standard virtual-queue argument in Lyapunov optimization (e.g., (Neely, 2010, Theorem 2.8)), the cumulative constraint violation is upper bounded by [Z(T+1)]E[Z(T+1)]. Therefore, (116) VioS(T)≤O(VT+V1−ρ),Vio^S(T)≤ O\! ( VT+ V1-ρ ), which proves (63).