Adaptive Data Admission and Retention for Streaming Federated Learning Zhuoyi Zhao
Ben Liang
University of Toronto Toronto, ON, Canada [email protected]
University of Toronto Toronto, ON, Canada [email protected]
arXiv:2607.23987v1 [cs.LG] 27 Jul 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 DriftPlus-Penalty (ACDPP) policy that combines a structured client-side 𝐾-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 constantadmission 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 bufferoccupancy 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.
CCS Concepts • Computing methodologies → Machine learning; Distributed computing methodologies; • Networks → Network dynamics.
Keywords streaming federated learning, online sampling, stochastic optimization ACM Reference Format: Zhuoyi Zhao and Ben Liang. 2026. Adaptive Data Admission and Retention for Streaming Federated Learning. In . ACM, New York, NY, USA, 15 pages.
1
Introduction
Federated learning (FL) enables multiple devices to collaboratively train a shared model without directly transferring their raw data to a central server [11, 17]. By keeping data local, FL has emerged as a promising paradigm for privacy-aware and large-scale model training in mobile and edge systems [1, 25]. 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 Conference’17, Washington, DC, USA 2026.
in user behavior, sensing environments, and local data-generation processes and generalization [12, 22, 23]. Moreover, in many realworld applications, local datasets evolve over time as new samples are continuously generated, collected, or labeled [7, 10, 20, 21, 26]. 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-theloop labeling systems, where new samples arrive sequentially and may incur non-negligible acquisition, annotation, or transmission costs before they can be used for training [9, 28]. 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 [9, 28], and sample selection [7, 16, 20, 21] 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 [9, 28], whereas learningcentric sample selection methods typically do not explicitly account for long-term sampling cost, buffer occupancy, or the coupled effect of sample admission and retention [7, 20, 21]. 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 clientside 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.
Conference’17, July 2017, Washington, DC, USA
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 driftplus-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.
Zhao et al.
propose gradient-norm based selection to accelerate convergence, Shi et al. [20] employ contrastive learning for importance scoring in unlabeled settings, and Sun et al. [21] learn query policies via multiagent 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. [16] 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. [26] propose Fed-HIST to leverage historical model knowledge. Huynh et al. [10] 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.
2 Related Work 2.1 Centralized Learning with Streaming Data
3 Preliminaries 3.1 Network Model
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 [5, 6]. This is often due to limited storage or the use of memory-efficient stream summaries in high-volume data streams [2, 3, 24]. 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.
We consider a streaming FL system consisting of a parameter server (PS) and 𝑀 clients, operating over discrete communication rounds indexed by 𝑡 ∈ {1, 2, . . . ,𝑇 }. Each client is indexed by 𝑚 ∈ {1, 2, . . . , 𝑀 }. Training samples are generated in a streaming manner: at the beginning of each round 𝑡, the PS determines the admission decisions, and the admitted samples are stored locally at the clients for future training.1 We assume that client 𝑚 is associated with a local data distribution P𝑚 , and that each sample admitted at client 𝑚 is drawn independently and identically distributed (i.i.d.) from P𝑚 . 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.
2.2
Streaming Federated Learning
Several works have studied online resource management for streaming FL using Lyapunov optimization. CEFL [28] jointly optimizes admission control, load balancing, and accuracy tuning to minimize operational costs. Hu et al. [9] 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. [7]
1 An 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.
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
Server-side admission actions and sampling cost. At each round 𝑡, the PS decides how many new samples to admit at each client. For each client 𝑚, samples are indexed by their generation order, and (𝑚, 𝑖) denotes the 𝑖-th sample generated at client 𝑚. To represent the sample-level admission status for subsequent buffer and age evolution, we define the binary admission indicator 𝑎𝑚,𝑖 (𝑡) ∈ {0, 1},
(1)
where 𝑎𝑚,𝑖 (𝑡) = 1 means that sample (𝑚, 𝑖) is admitted to the local buffer of client 𝑚 in round 𝑡. Accordingly, we define the admission amount at client 𝑚 in round 𝑡 as ∑︁ 𝜆𝑚 (𝑡) ≜ 𝑎𝑚,𝑖 (𝑡), ∀𝑚, (2) 𝑖
which is the number of samples admitted at client 𝑚 in round 𝑡. Admitting one new sample in round 𝑡 incurs a time-varying persample sampling cost 𝑐 (𝑡) ≥ 0, revealed to the PS at the beginning Í of round 𝑡. Let 𝑐¯𝑇 ≜ 𝑇1 𝑇𝑡=1 E[𝑐 (𝑡)] denote the average per-sample sampling cost over the horizon 𝑇 . We impose the average samplingcost constraint " # 𝑇 𝑀 ∑︁ 1 ∑︁ E 𝑐 (𝑡) 𝜆𝑚 (𝑡) ≤ 𝐶, (3) 𝑇 𝑡 =1 𝑚=1 where 𝐶 > 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 𝑡 𝑞𝑚,𝑖 ∈ {0, 1} indicate whether sample (𝑚, 𝑖) is present in the local buffer of client 𝑚 at the beginning of the local training phase of round 𝑡, i.e., after the admission and dropping actions in round 𝑡 have been executed. The resulting buffer occupancy is defined as ∑︁ 𝑡 𝑛𝑚 (𝑡) ≜ 𝑞𝑚,𝑖 , (4)
0 = 0 for all 𝑚, 𝑖. Thus, the age of a sample is with initialization 𝐴𝑚,𝑖 incremented while it remains in the buffer, initialized to 1 when it newly enters the buffer, and frozen once it is no longer stored.
3.2
Distributed Learning Model
Let 𝜃 (𝑡 ) ∈ Θ denote the global model at the beginning of the local training phase of round 𝑡. 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 ℓ (𝜃 ; 𝑧) denote the sample-wise loss of model parameter 𝜃 on data sample 𝑧. The empirical risk over the local buffer of client 𝑚 in round 𝑡 is defined as ∑︁ 1 𝐹b𝑚,𝑡 (𝜃 ) ≜ ℓ (𝜃 ; 𝑧). (7) 𝑛𝑚 (𝑡) 𝑧 ∈ Q𝑚 (𝑡 )
Accordingly, the corresponding local gradient is ∑︁ 1 ∇𝜃 ℓ (𝜃 ; 𝑧). ∇𝐹b𝑚,𝑡 (𝜃 ) = 𝑛𝑚 (𝑡)
Starting from 𝜃𝑚(𝑡,0) = 𝜃 (𝑡 ) , each client performs 𝐸 ≥ 1 steps of gradient descent with stepsize 𝜂 > 0 on the empirical risk 𝐹b𝑚,𝑡 : 𝜃𝑚(𝑡,𝑒+1) = 𝜃𝑚(𝑡,𝑒 ) − 𝜂 ∇𝐹b𝑚,𝑡 𝜃𝑚(𝑡,𝑒 ) , 𝑒 = 0, . . . , 𝐸 − 1. (9) After the local updates, client 𝑚 uploads the model difference (𝑡 ) Δ𝑚 ≜ 𝜃𝑚(𝑡,𝐸 ) − 𝜃 (𝑡 ) .
where 𝐵𝑚 > 0 is the prescribed average memory budget of client 𝑚. Client 𝑚 independently manages its local buffer through a binary drop action 𝑑𝑚,𝑖 (𝑡) ∈ {0, 1}, where 𝑑𝑚,𝑖 (𝑡) = 1 means that sample (𝑚, 𝑖) is removed from the local buffer of client 𝑚 in round 𝑡. Dropping actions are determined locally based solely on client-side information. 𝑡 Sample age and its evolution. For each sample (𝑚, 𝑖), let 𝐴𝑚,𝑖 ∈N denote its age at the beginning of the local training phase of round 𝑡. 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, 𝐴𝑡 + 1, 𝑚,𝑖 𝑡 +1 𝐴𝑚,𝑖 = 1, 𝐴𝑡 , 𝑚,𝑖
𝑡 𝑡 +1 = 1, if 𝑞𝑚,𝑖 = 1 and 𝑞𝑚,𝑖 𝑡 𝑡 +1 = 1, if 𝑞𝑚,𝑖 = 0 and 𝑞𝑚,𝑖 𝑡 +1 = 0, if 𝑞𝑚,𝑖
(6)
(10)
Let 𝛼𝑚 ≥ 0 denote the prescribed importance weight of client 𝑚, Í𝑀 with 𝑚=1 𝛼𝑚 = 1. The server then aggregates the client updates according to a FedAvg-style rule:
𝑖
which is the number of samples stored in the local buffer of client 𝑚 in round 𝑡. Accordingly, let Q𝑚 (𝑡) denote the set of samples stored in the local buffer of client 𝑚 in round 𝑡, so that 𝑛𝑚 (𝑡) = |Q𝑚 (𝑡)|. To capture limited memory, we impose an average buffer-occupancy constraint on each client: 𝑇 1 ∑︁ E[𝑛𝑚 (𝑡)] ≤ 𝐵𝑚 , 𝑚 = 1, . . . , 𝑀, (5) 𝑇 𝑡 =1
(8)
𝑧 ∈ Q𝑚 (𝑡 )
𝜃 (𝑡 +1) = 𝜃 (𝑡 ) +
𝑀 ∑︁
(𝑡 ) 𝑤𝑚,𝑡 Δ𝑚 ,
𝑤𝑚,𝑡 ≥ 0,
𝑚=1
𝑀 ∑︁
𝑤𝑚,𝑡 = 1, (11)
𝑚=1
where a natural choice of 𝑤𝑚 , 𝑡, for example, is memory-proportional weighting, i.e. 𝛼𝑚 𝑛𝑚 (𝑡) 𝑤𝑚,𝑡 = Í𝑀 . (12) 𝑗=1 𝛼 𝑗 𝑛 𝑗 (𝑡)
3.3
Problem Formulation
Learning objective. We define the target population distribution as the weighted mixture P≜
𝑀 ∑︁
𝛼𝑚 P𝑚 .
(13)
𝑚=1
Our goal is to learn a model that minimizes the population risk 𝐹 P (𝜃 ) ≜ E𝑧∼P [ℓ (𝜃 ; 𝑧)],
𝜃 ∈ Θ,
(14)
and let 𝜃 ★ ∈ arg min𝜃 ∈Θ 𝐹 P (𝜃 ). Server and client control variables. The system is controlled through a decomposed architecture. On the server side, the PS 𝑀 determines the admission amounts {𝜆𝑚 (𝑡)}𝑚=1 at each round 𝑡, which can be equivalently represented by the sample-level admission indicators {𝑎𝑚,𝑖 (𝑡)}𝑚,𝑖 via (2). On the client side, each client 𝑚 independently determines the sample-level dropping actions {𝑑𝑚,𝑖 (𝑡)}𝑖 to manage its local buffer. Together, the admission and
Conference’17, July 2017, Washington, DC, USA
Zhao et al.
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 denote the server-side policy that maps server-observable information (e.g., the history of communicated updates and the C current cost 𝑐 (𝑡)) to admission actions. For each client 𝑚, let 𝜋𝑚 denote the client-side policy that maps local buffer states (including sample ages) to dropping actions. We denote the resulting joint policy by C 𝑀 𝜋 ≜ 𝜋 S, {𝜋𝑚 }𝑚=1 . (15) Optimization objective and constraint violation. Under the learning dynamics in Section 3.2, the global model sequence {𝜃 (𝑡 ) }𝑇𝑡=1 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 𝑇 as 𝑇 ∑︁ E𝑇 (𝜋) ≜ E 𝐹 P (𝜃 (𝑡 ) ) − 𝐹 P (𝜃 ★) . (16) 𝑡 =1
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 E𝑇 (𝜋) 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 𝐷, i.e., ∥𝜃 − 𝜃 ′ ∥ 2 ≤ 𝐷, ∀𝜃, 𝜃 ′ ∈ Θ. Assumption 2 (Smoothness and bounded gradients). The population risk 𝐹 P is 𝐿-smooth on Θ, i.e., ∥∇𝐹 P (𝜃 ) − ∇𝐹 P (𝜃 ′ )∥ 2 ≤ 𝐿∥𝜃 − 𝜃 ′ ∥ 2,
∀𝜃, 𝜃 ′ ∈ Θ.
Moreover, the loss ℓ (𝜃 ; 𝑧) is differentiable in 𝜃 , and its per-sample gradients are uniformly bounded: ∥∇𝜃 ℓ (𝜃 ; 𝑧)∥ 2 ≤ 𝐺,
∀𝜃 ∈ Θ, 𝑧.
Hence, any empirical gradient formed as an average over stored samples is also bounded in norm by 𝐺. Assumption 3 (Bounded loss and finite pseudo-dimension). The loss is bounded as ℓ (𝜃 ; 𝑧) ∈ [0, 𝐵] for all 𝜃 ∈ Θ and 𝑧. In addition, the loss-composed hypothesis class ℓ ◦ H has finite pseudo-dimension, denoted by Pdim(ℓ ◦ H ). 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: E𝑧∼P ∥∇𝜃 ℓ (𝜃 ; 𝑧) − ∇𝐹 P (𝜃 )∥ 22 ≤ 𝜎 2, ∀𝜃 ∈ Θ. (17)
4.2
Learning Error Bound
We next derive an upper bound on the cumulative excess population risk E𝑇 (𝜋) 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 𝑛𝜋 (𝑡) denote the total number of stored samples used for training at round 𝑡 under policy 𝜋. Further, let 𝑁 𝜋 (𝑡) denote the number of distinct samples that have been used in local training up to round 𝑡. Since retained samples may be reused multiple times across rounds, the quantity 𝑁 𝜋 (𝑡) 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 𝑖 ∈ {1, . . . , 𝑁 𝜋 (𝑡)}, let 𝐴𝑖𝜋 (𝑡) denote the cumulative number of times that sample 𝑖 has been used in local training up to round 𝑡. We define 𝐴¯𝜋 (𝑡) 2 e𝜋 (𝑡) ≜ V , (18) 𝐴¯𝜋 (𝑡) 2 + Var(𝐴𝜋 (𝑡)) and 𝜋 e𝜋 (𝑡), 𝑁 eff (𝑡) ≜ 𝑁 𝜋 (𝑡) V
(19) 𝜋 𝜋 ¯ where 𝐴 (𝑡) and Var(𝐴 (𝑡)) are the empirical mean and variance 𝑁 𝜋 (𝑡 ) e𝜋 (𝑡) ∈ (0, 1] measures of {𝐴𝑖𝜋 (𝑡)}𝑖=1 , respectively. The factor V the uniformity of sample reuse: it is close to 1 when the reuse counts are nearly uniform, and becomes smaller when the reuse pattern 𝜋 (𝑡) = 𝑁 𝜋 (𝑡) V e𝜋 (𝑡) quantifies is highly uneven. Accordingly, 𝑁 eff 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, (ii) variance control for stochastic gradients under sample reuse, and (iii) 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 streaminglearning analysis of Theorem 4.4 in [16], but is specialized here to the present full-batch memory-based federated setting. Rather than giving an abstract order-level characterization as in [16], we express
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
the bound explicitly in terms of the policy-induced quantities 𝑛𝜋 (𝑡), e𝜋 (𝑡) through 𝑁 𝜋 (𝑡) = 𝑁 𝜋 (𝑡) V e𝜋 (𝑡). This explicit 𝑁 𝜋 (𝑡), and V eff 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 {𝜃 𝜋(𝑡 ) }𝑇𝑡=1 be the model sequence generated by the learning dynamics under a given joint policy 𝜋. Then the cumulative excess population risk satisfies E𝑇 (𝜋) ≤ Ē𝑇 (𝜋),
(20)
where 𝑇 ∑︁
" √︄
1 1 1 1 2 +𝜂𝜎 𝜋 − Ē𝑇 (𝜋) = 𝐷𝜎 𝜋 − e𝜋 (𝑡) e𝜋 (𝑡) 𝑛 (𝑡) 𝑁 𝜋(𝑡) V 𝑛 (𝑡) 𝑁 𝜋(𝑡) V 𝑡 =1 √︄ √︄ # Pdim(ℓ ◦ H ) 𝑁 𝜋(𝑡) + 10𝐵 1 + log + 𝐶2 . e𝜋 (𝑡) Pdim(ℓ ◦ H ) 𝑁 𝜋(𝑡) V (21) Here, 𝐶 2 collects initialization and lower-order constant terms, includ2 ing 𝐷2𝜂 and other algorithm-dependent constants. Proof. See Appendix A in [27].
5
0 }, {𝐴0 }, 𝑁 (0), 𝑛(0), 𝐶, Inputs: 𝜃 (1) , 𝑍 (1) = 0, {𝑞𝑚,𝑖 𝑚,𝑖 𝑀 {𝐵𝑚 }𝑚=1 , 𝐾, 𝑉 , Λ̄, 𝜌 +1 Output: {𝜃 (𝑡 ) }𝑇𝑡 =1 1 for 𝑡 = 1, 2, . . . ,𝑇 do 2 The server does: 3 Observe O(𝑡) and 𝑐 (𝑡) 4 Solve (34) to obtain 𝝀★ (𝑡) 𝑡 +1 } using (26) and (6) 5 Update 𝑍 (𝑡 + 1) and {𝐴𝑚,𝑖 6 Update 𝑁 𝜋 (𝑡) and 𝑛𝜋 (𝑡) 7 8 9
10 11 12
Each client 𝑚 in parallel does: Admit 𝜆𝑚 (𝑡) new samples using 𝝀★ (𝑡) (𝑡 ) using (8), Perform local training and compute Δ𝑚 (9), and (10) 𝑡 +1 } using (22) Update {𝑞𝑚,𝑖 The server does: Aggregate and update 𝜃 (𝑡 +1) using (11)
□
Active-Constraint DPP Policy
Utilizing the excess-risk bound in (20), we develop a joint admissionretention 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 e𝜋 (𝑡) depends on the entire sample-retention pattern. To address V 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 [18] 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.
5.1
Algorithm 1: Active-Constraint DPP Algorithm
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 reusee𝜋 (𝑡) can be expressed in closed form. uniformity factor V Definition 1 (K-step retention policy). Fix an integer retention horizon 𝐾 ≥ 1. A client-side policy is called a K-step retention policy
if, for every client 𝑚 ∈ {1, . . . , 𝑀 }, every admitted sample (𝑚, 𝑖), and every round 𝑡 ∈ {1, . . . ,𝑇 }, the dropping action satisfies 𝑡 𝑑𝑚,𝑖 (𝑡) = 1{𝐴𝑚,𝑖 = 𝐾 },
∀𝑚, 𝑖, 𝑡 .
(22)
That is, each sample is retained in the local buffer for exactly 𝐾 rounds after admission and is removed when its age reaches 𝐾. We next characterize the reuse-uniformity factor under the Kstep retention policy. Under this policy, every sample admitted no later than round 𝑡 −𝐾 + 1 has already contributed exactly 𝐾 training uses by round 𝑡, while only the samples admitted in the most recent 𝐾 − 1 rounds incur a reuse deficit. Define 𝐷 𝜕(1) (𝑡) ≜
𝑡 ∑︁
𝐾 − (𝑡 − 𝑗 + 1)
𝑀 ∑︁
𝜆𝑚 ( 𝑗),
𝑗=𝑡 −𝐾+2
𝑚=1
𝑡 ∑︁
𝑀 ∑︁
(23)
and 𝐷 𝜕(2) (𝑡) ≜
𝑗=𝑡 −𝐾+2
𝐾 2 − (𝑡 − 𝑗 + 1) 2
𝜆𝑚 ( 𝑗).
(24)
𝑚=1
Then the reuse-uniformity factor under the K-step retention policy admits the exact representation 2 𝐾𝑁 𝜋 (𝑡) − 𝐷 𝜕(1) (𝑡) 𝜋 e V (𝑡) = (25) . 𝑁 𝜋 (𝑡) 𝐾 2 𝑁 𝜋 (𝑡) − 𝐷 𝜕(2) (𝑡) e𝜋 (𝑡) from one is deterHence, the finite-horizon deviation of V mined entirely by the boundary deficits induced by the samples admitted in the most recent 𝐾 − 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.
Conference’17, July 2017, Washington, DC, USA
Zhao et al.
Cost-Debt Queue. Let 𝑍 (𝑡) denote the cost-debt queue at the beginning of round 𝑡. It evolves as + 𝑍 (𝑡 + 1) = 𝑍 (𝑡) + 𝐶𝑡 − 𝐶 , (26) where 𝐶 > 0 is the prescribed per-round sampling-cost budget and 𝐶𝑡 ≜ 𝑐 (𝑡)Λ(𝑡),
Λ(𝑡) ≜
𝑀 ∑︁
𝜆𝑚 (𝑡),
(27)
is the aggregate sampling cost incurred in round 𝑡 under the DPP policy, with initialization 𝑍 (0) = 0. The queue 𝑍 (𝑡) measures the accumulated violation of the budget constraint: when 𝐶𝑡 > 𝐶, the system incurs positive debt and 𝑍 (𝑡) grows; otherwise the debt is reduced. Hence, a large value of 𝑍 (𝑡) indicates that the system has been operating above the desired average cost level. Lyapunov Function and Penalty Function. We adopt the quadratic Lyapunov function 1 𝐿(𝑡) = 𝑍 (𝑡) 2, (28) 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: √︂ 1 1 1 1 2 ˜ 𝑝 (𝑡) ≜ 𝐷𝜎 − + 𝜂𝜎 − 𝑛𝜋 (𝑡) 𝑁 𝜋 (𝑡) 𝑛𝜋 (𝑡) 𝑁 𝜋 (𝑡) √︄ √︄ (29) Pdim(ℓ ◦ H ) 𝑁 𝜋 (𝑡) + 10𝐵 1 + log . 𝑁 𝜋 (𝑡) Pdim(ℓ ◦ H ) Í Accordingly, the cumulative quantity 𝑇𝑡=1 𝑝 (𝑡) serves as a surrogate objective in place of the learning upper bound Ē𝑇 (𝜋). One-Slot Drift-Plus-Penalty. Let 𝑡 𝑡 O(𝑡) := {𝑍 (𝑡), 𝑞𝑚,𝑖 , 𝐴𝑚,𝑖 }𝑚,𝑖
denote the system state at the beginning of the local training phase of round 𝑡.2 We define the one-slot Lyapunov drift as (30)
The DPP framework minimizes a weighted sum of the one-slot drift and the per-round penalty. Accordingly, we consider the driftplus-penalty expression Δ(O(𝑡)) + 𝑉 E[𝑝 (𝑡) | O(𝑡)],
(31)
where 𝑉 > 0 is a control parameter that trades off learning performance and budget satisfaction. Substituting the queue evolution of 𝑍 (𝑡) into (30) and using standard quadratic-drift bounds yields Δ(O(𝑡)) + 𝑉 E[𝑝 (𝑡) | O(𝑡)] ≤ 𝐵 + E[𝐽𝑡 (𝝀) | O(𝑡)] ,
Acitve-Constraint DPP Admission Rule. Motivated by the upper bound in (32), the ACDPP policy selects, at each round 𝑡, an admission action vector 𝝀★ (𝑡) that minimizes the right-hand side of (33), namely, 𝑀 ∑︁ 𝝀★ (𝑡) ∈ arg min 𝐽𝑡 (𝝀) s.t. 𝜆𝑚 (𝑡) ∈ [Λmin (𝑡), Λmax (𝑡)]. 𝝀
𝑚=1
Δ(O(𝑡)) ≜ E[𝐿(𝑡 + 1) − 𝐿(𝑡) | O(𝑡)] .
𝝀(𝑡) ≜ (𝜆1 (𝑡), . . . , 𝜆𝑀 (𝑡)).
(32)
where 𝐵 < ∞ is a uniform constant independent of the control action, and 𝐽𝑡 (𝝀) ≜ 𝑍 (𝑡) 𝑐 (𝑡)Λ(𝑡) − 𝐶 + 𝑉 𝑝 (𝑡), (33) with 2 Under K-step retention, 𝑞𝑡 𝑡 𝑚,𝑖 and 𝐴𝑚,𝑖 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.
𝑚=1
(34) 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: Λ̄ Λmin (𝑡) = Λ̄(1 − 𝜌 𝑡 ), Λmax (𝑡) = , (35) 1 − 𝜌𝑡 for some constant 𝜌 ∈ (0, 1). As 𝑡 → ∞, 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 𝑇 , 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 𝑡, the dominant terms depend primarily on the instantaneous training sample size 𝑛𝜋 (𝑡). Under the buffer constraints, these terms are minimized when 𝑛𝜋 (𝑡) 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 𝑛𝜋 (𝑡) increase the cumulative contribution of terms involving 1/𝑛𝜋 (𝑡), 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 𝝀(𝑡), the objective depends on the control only through the aggregate Í𝑀 admission rate Λ(𝑡) = 𝑚=1 𝜆𝑚 (𝑡). 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 𝑇 -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 𝐾 to control the bufferoccupancy 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
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
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 constantadmission 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 𝐵𝑚 , this idealized behavior is achieved by the following costless oracle policy: at every round 𝑡, client 𝑚 admits exactly 𝐵𝑚 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 Ē𝑇ACDPP denote the upper bound on the cumulative excess population risk under the proposed ACDPP policy up to round 𝑇 , and let Ē𝑇oracle denote the corresponding quantity under the costless oracle policy. We define the regret as Reg(𝑇 ) ≜ Ē𝑇ACDPP − Ē𝑇oracle .
(36)
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 samplingcost and buffer constraints, we define the cumulative sampling-cost violation and cumulative buffer-occupancy violation up to horizon 𝑇 as "𝑇 " ##+ 𝑀 ∑︁ ∑︁ S Vio (𝑇 ) ≜ E 𝑐 (𝑡) 𝜆𝑚 (𝑡) − 𝐶 , (37) 𝑡 =1
𝑚=1
and the total training sample size is 𝑛 CK (𝑡) = 𝐾 Λ̄,
Vio (𝑇 ) ≜
"𝑇 𝑀 ∑︁ ∑︁ 𝑚=1
𝑁 CK (𝑡) = Λ̄𝑡 .
(42)
Corollary 1. For the auxiliary constant-admission policy 𝜋 CK , the cumulative excess population risk satisfies E𝑇 (𝜋 CK ) ≤ Ē𝑇 (𝜋 CK ),
(38)
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 2 (Auxiliary constant-admission policy). Fix nonneg𝑀 . A server-side policy is called a ative admission rates {𝜆𝑚 }𝑚=1 constant-admission policy if, for every round 𝑡 and client 𝑚, ∑︁ 𝑎𝑚,𝑖 (𝑡) = 𝜆𝑚 , ∀𝑚, 𝑡 . (39) 𝑖
Combined with the K-step retention policy in Definition 1, this yields the joint policy 𝜋 CK . Under 𝜋 CK , each client admits a constant number of new samples per round, while each admitted sample is retained for exactly 𝐾 rounds. Consequently, for all sufficiently large 𝑡, the buffer occupancy at client 𝑚 satisfies (40)
(43)
where Ē𝑇 (𝜋
and
CK
𝑇 ∑︁
"
√︄
1 1 1 1 2 )= 𝐷𝜎 − − + 𝜂𝜎 eCK (𝑡) eCK (𝑡) Λ̄𝐾 Λ̄𝑡 V Λ̄𝐾 Λ̄𝑡 V 𝑡 =1 √︄ √︄ # Pdim(ℓ ◦ H ) Λ̄𝑡 1 + log + 𝐶2 , + 10𝐵 eCK (𝑡) Pdim(ℓ ◦ H ) Λ̄𝑡 V (44) 2 𝐾𝑡 − 𝐾 (𝐾2−1) CK e . V (𝑡) = (45) 𝑡 𝐾 2𝑡 − 𝐾 (𝐾 −1)6(2𝐾 −1)
The specialized bound in Corollary 1 depends on the aggregate admission level Λ̄, the retention horizon 𝐾, and the finite-horizon eCK (𝑡). We therefore choose these paramereuse-uniformity factor V ters so as to optimize the benchmark bound under the sampling-cost and buffer constraints. Under the auxiliary constant-admission policy 𝜋 CK , the average sampling cost over horizon 𝑇 must satisfy 𝑐¯𝑇 Λ̄ ≤ 𝐶,
.
(41)
Substituting (40)–(42) into Theorem 1, together with the exact finite-horizon reuse-uniformity factor induced by 𝜋 CK , yields the following specialization of the cumulative excess-risk bound.
(46)
and the per-client buffer constraint requires
𝑡 =1
𝑛𝑚 (𝑡) = 𝐾𝜆𝑚 ,
𝜆𝑚 .
Moreover, the cumulative number of distinct samples used in local training up to round 𝑡 grows linearly as
#+ E[𝑛𝑚 (𝑡) − 𝐵𝑚 ]
𝑀 ∑︁ 𝑚=1
and B
Λ̄ ≜
𝐾𝜆𝑚 ≤ 𝐵𝑚 ,
∀𝑚.
(47)
Accordingly, the benchmark parameter design is formulated as ( ) 𝑀 ∑︁ CK min Ē𝑇 (𝜋 ) :𝐾𝜆𝑚 ≤ 𝐵𝑚 ,∀𝑚, 𝑐¯𝑇 𝜆𝑚 ≤ 𝐶,𝜆𝑚 ≥ 0,∀𝑚 . 𝑀 , 𝐾 ∈N {𝜆𝑚 }𝑚=1
𝑚=1
(48) 𝑀 Because Ē𝑇 (𝜋 CK ) depends on the admission vector {𝜆𝑚 }𝑚=1 Í𝑀 only through the induced aggregate level Λ̄ = 𝑚=1 𝜆𝑚 , the problem is low-dimensional. In particular, for any fixed horizon 𝑇 , the benchmark parameters can be obtained by searching over feasible values of the integer variable 𝐾 together with the corresponding admissible aggregate admission levels. The following corollary gives the resulting closed-form benchmark choice in the infinite-horizon regime. Corollary 2. In the infinite-horizon regime, an optimal benchmark solution is obtained by saturating the per-client buffer constraints, i.e., 𝐵𝑚 ★ ∀𝑚, (49) 𝜆𝑚 = ★, 𝐾
Conference’17, July 2017, Washington, DC, USA
Zhao et al.
where 𝐾 ★ is chosen as the better of the two nearest feasible integers, namely & Í ' ($ Í % ) 𝑀 𝑀 𝑐¯ 𝑚=1 𝐵𝑚 𝑐¯ 𝑚=1 𝐵𝑚 𝐾★ = or 𝐾 ★ = max , 1 . (50) 𝐶 𝐶
connects the resulting infinite-horizon comparison target to the costless oracle benchmark. More precisely, define 𝑇 ∑︁ Ω1 (𝑇 ) ≜ Ē𝑇ACDPP − E[𝑝 (𝑡)], (54) 𝑡 =1
In the sequel, we adopt the benchmark design in Corollary 2, then the per-client buffer constraint is saturated in steady state. In particular, for all 𝑡 > 𝐾, the buffer occupancy satisfies 𝑛𝑚 (𝑡) = 𝐵𝑚 ,
6.2
∀𝑚.
Ω2 (𝑇 ) ≜
𝑇 ∑︁
𝑝¯𝐶𝐾 (𝑡) −
𝑡 =1
and Ω3 (𝑇 ) ≜
T-Slot ACDPP Upper Bound
𝑇 ∑︁
𝑇 ∑︁
𝑝¯𝐶𝐾 ∞ (𝑡),
(55)
𝑡 =1 oracle 𝑝¯𝐶𝐾 . ∞ (𝑡) − Ē𝑇
(56)
𝑡 =1
We next establish a standard 𝑇 -slot upper bound for the surrogate penalty induced by the proposed ACDPP policy. This Lyapunovbased result provides the key control relation used in the subsequent regret analysis.
In addition, the 𝑇 -slot ACDPP upper bound in Lemma 1 yields
Lemma 1. The cumulative surrogate penalty under the proposed ACDPP policy satisfies 𝑇 𝑇 ∑︁ ∑︁ E[𝐿(𝑇 + 1) − 𝐿(1)] + 𝑉 E[𝑝 (𝑡)] ≤ 𝐵𝑇 + 𝑉 𝑝¯𝐶𝐾 (𝑡), (51)
Combining (54)–(57), we obtain
𝑡 =1
where
𝑡 =1
√︄
1 1 − Í𝑡 −1 (𝐾 − 1)Λmin (𝑡 − 𝐾) + Λ̄ Λ (𝜏) + Λ̄ min 𝜏=1 1 1 + 𝜂𝜎 2 − Í𝑡 −1 (𝐾 − 1)Λmin (𝑡 − 𝐾) + Λ̄ 𝜏=1 Λmin (𝜏) + Λ̄ √︄ √︄ Í𝑡 −1 Λmax (𝜏) + Λ̄ Pdim(ℓ ◦ H ) . + 10𝐵 Í𝑡 −1 1 + log 𝜏=1 Pdim(ℓ ◦ H ) 𝜏=1 Λmin (𝜏) + Λ̄ (52) Proof. See Appendix B in [27]. □
𝑝¯𝐶𝐾 (𝑡) = 𝐷𝜎
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 Ē𝑇ACDPP to Ē𝑇oracle through several intermediate quantities. In particular, we introduce the auxiliary comparison target √︂ 1 1 1 1 2 𝑝¯𝐶𝐾 (𝑡) ≜ 𝐷𝜎 − + 𝜂𝜎 − ∞ Λ̄𝐾 Λ̄𝑡 Λ̄𝐾 Λ̄𝑡 √︄ √︂ (53) Pdim(ℓ ◦ H ) Λ̄𝑡 + 10𝐵 1 + log . Pdim(ℓ ◦ H ) Λ̄𝑡 which corresponds to the surrogate penalty of the constant-admission policy in the infinite-horizon. The overall comparison chain is Ē𝑇ACDPP →
𝑇 ∑︁ 𝑡 =1
E[𝑝 (𝑡)] →
𝑇 ∑︁ 𝑡 =1
𝑝¯𝐶𝐾 (𝑡) →
𝑇 ∑︁
oracle 𝑝¯𝐶𝐾 , ∞ (𝑡) → Ē𝑇
𝑇 ∑︁ 𝑡 =1
E[𝑝 (𝑡)] ≤
𝑇 ∑︁ E[𝐿(1)] 𝐵 𝑇+ 𝑝¯𝐶𝐾 (𝑡) + . 𝑉 𝑉 𝑡 =1
(57)
𝑇 . (58) 𝑉 It therefore remains to characterize the orders of the three correction terms. The technical proofs are deferred to the appendix. Ē𝑇ACDPP − Ē𝑇oracle ≤ −Ω1 (𝑇 ) + Ω2 (𝑇 ) + Ω3 (𝑇 ) + 𝑂
Lemma 2. Under the K-step retention policy, Ω1 (𝑇 ) = 𝑂 (1). Proof. See Appendix C in [27].
(59) □
Lemma 3. Under the time-varying rectangular constraint (35), 1 . (60) Ω2 (𝑇 ) = 𝑂 1−𝜌 Proof. See Appendix D in [27].
□
Lemma 4. For any fixed comparison operating point ( Λ̄, 𝐾) satisfy¯ ing Λ̄𝐾 = 𝐵, Ω3 (𝑇 ) = 𝑂 (log𝑇 ). (61) Proof. See Appendix E in [27].
6.4
□
Regret and Constraint Guarantees
Combining the 𝑇 -slot ACDPP upper bound in Lemma 1 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 𝐾 such that the cumulative buffer-occupancy violation remains bounded as 𝑂 (1). Theorem 2. For any fixed ACDPP parameter 𝑉 > 0 and any fixed 0 < 𝜌 < 1, the regret as defined in (36) satisfies 𝑇 1 Reg(𝑇 ) = 𝑂 +𝑂 + 𝑂 (log𝑇 ). (62) 𝑉 1−𝜌
𝑡 =1
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 𝑇 -slot ACDPP upper bound to compare this surrogate with the finite-horizon comparison form induced by the auxiliary constantadmission policy; the third step removes the transient effects caused by the time-varying rectangular action space; and the final step
Proof. Substituting Lemmas 2–4 into (58) and absorbing the 𝑂 (1) term into the constants proves (62). □ Theorem 3. For any fixed ACDPP parameter 𝑉 > 0 and any fixed 0 < 𝜌 < 1, the cumulative sampling-cost constraint violation satisfies √︄ ! 𝑉 S Vio (𝑇 ) = 𝑂 𝑉𝑇 + . (63) 1−𝜌
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
Proof. See Appendix F in [27].
□
Remark 1. Let 𝑉 = 𝑇 𝛾 , and 𝜌 = 1 −𝑇 −𝜙 . Then the cumulative regret and cumulative sampling-cost violation satisfy Reg(𝑇 ) = 𝑂 𝑇 1−𝛾 + 𝑂 𝑇 𝜙 + 𝑂 (log𝑇 ),
(64)
and 1+𝛾 𝛾 +𝜙 VioS (𝑇 ) = 𝑂 𝑇 2 + 𝑇 2 .
(65)
Therefore, for any 𝛾 ∈ (0, 1) and 𝜙 ∈ (0, 1), both Reg(𝑇 ) and VioS (𝑇 ) are sublinear in 𝑇 . Remark 2. The cumulative buffer-occupancy violation is controlled through the offline selection of the retention horizon 𝐾. Since 𝐾 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 𝐾 and select a feasible retention horizon such that the resulting violation remains uniformly bounded over the horizon of interest. For such a choice of 𝐾, the cumulative buffer-occupancy violation satisfies VioB (𝑇 ) = 𝑂 (1).
(66)
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 𝐾.
7
Numerical Evaluation
In addition to the regret analysis in Section 6, we further evaluate the ACDPP policy on three image classification datasets: MNIST [14], CIFAR-10 [13], and ImageNette [4].3 We compare the proposed ACDPP policy against three baselines: the costless oracle benchmark, the constant-admission policy, and a hybrid policy inspired by [16] that combines fresh-sample admission with stale-sample reuse under the same cost budget. Methods in [7, 9, 20, 21, 28] 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 𝑀 = 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 [15] as the prediction model for MNIST, while for CIFAR-10 and ImageNette we use ResNet-9 [8]. For MNIST, the client buffer capacities are set to {8, 9, 10, 11, 12, 8, 9, 10, 11, 12}, and the long-term sampling-cost budget is 𝐶 = 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× and 4× those of MNIST. The per-sample acquisition cost 𝑐 (𝑡) is independently drawn from Unif [1, 10]. In each communication round, every client performs 𝐸 = 10 local epochs for all three datasets. The learning rates are set to 𝜂 = 0.5 for MNIST, 𝜂 = 5 × 10−3 for CIFAR-10, and 𝜂 = 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. 3 Code is available at https://github.com/zhuoyijoeyzhao/AdaSamplingSFL.
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% 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 constantadmission 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% for MNIST, 70% for CIFAR-10, and 70% for ImageNette. Under this criterion, ACDPP converges about 2.3× and 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×, 1.7×, and 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 [16], 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 constantadmission 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 𝐾. 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 memorymanagement 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
Conference’17, July 2017, Washington, DC, USA
(a) Test accuracy on MNIST (non-i.i.d.)
Zhao et al.
(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. 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 [1] Keith Bonawitz et al. 2019. Towards federated learning at scale: System design. Proc. Mach. Learn. Syst. 1 (2019), 374–388. [2] Graham Cormode and Shan Muthukrishnan. 2005. An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55, 1 (2005). [3] Matthias De Lange et al. 2021. A continual learning survey: Defying forgetting in classification tasks. IEEE Trans. Pattern Anal. Mach. Intell. 44, 7 (2021), 3366–3385. [4] Jia Deng et al. 2009. Imagenet: A large-scale hierarchical image database. In IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR). 248–255. [5] Joao Gama et al. 2013. On evaluating stream learning algorithms. Mach. Learn. 90, 3 (2013), 317–346. [6] Heitor Murilo Gomes et al. 2019. Machine learning for streaming data: state of the art, challenges, and opportunities. ACM SIGKDD Explor. Newsl. 21, 2 (2019). [7] Chen Gong et al. 2024. ODE: An online data selection framework for federated learning with limited storage. IEEE/ACM Trans. Netw. 32, 4 (2024), 2794–2809. [8] Kaiming He et al. 2016. Deep residual learning for image recognition. In IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR). 770–778. [9] Chung-Hsuan Hu et al. 2024. Energy-efficient federated edge learning with streaming data: A lyapunov optimization approach. IEEE Trans. Commun. (2024).
[10] Tan-Khiem Huynh et al. 2025. Streaming federated learning with Markovian data. arXiv preprint arXiv:2503.18807 (2025). [11] Peter Kairouz and H Brendan McMahan. 2021. Advances and open problems in federated learning. Found. Trends Mach. Learn. 14, 1-2 (2021), 1–210. [12] Sai Praneeth Karimireddy et al. 2020. Scaffold: Stochastic controlled averaging for federated learning. In Int. Conf. Mach. Learn. (ICML). [13] Alex Krizhevsky et al. 2009. Learning multiple layers of features from tiny images. (2009). [14] Yann. LeCun. 1998. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/ (1998). [15] Yann LeCun et al. 2002. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (2002). [16] Othmane Marfoq et al. 2023. Federated learning for data streams. In Int. Conf. Artif. Intell. Stat. (AISTATS). [17] Brendan McMahan et al. 2017. Communication-efficient learning of deep networks from decentralized data. In Int. Conf. Artif. Intell. Stat. (AISTATS). [18] Michael Neely. 2022. Stochastic Network Optimization with Application to Communication and Queueing Systems. Springer Nature. [19] Michael J Neely. 2010. Stability and capacity regions or discrete time queueing networks. arXiv preprint arXiv:1003.3396 (2010). [20] Jiahe Shi et al. 2023. Self-supervised on-device federated learning from unlabeled streams. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 42, 12 (2023). [21] Yuchang Sun et al. 2025. Learn how to query from unlabeled data streams in federated learning. In AAAI Conf. Artif. Intell. (AAAI). [22] Alysa Ziying Tan et al. 2022. Towards personalized federated learning. IEEE Trans. Neural Netw. Learn. Syst. 34, 12 (2022). [23] Jianyu Wang et al. 2020. Tackling the objective inconsistency problem in heterogeneous federated optimization. In Adv. Neural Inf. Process. Syst. (NeurIPS). [24] Liyuan Wang et al. 2024. A comprehensive survey of continual learning: Theory, method and application. IEEE Trans. Pattern Anal. Mach. Intell. 46, 8 (2024). [25] Shiqiang Wang et al. 2019. Adaptive federated learning in resource constrained edge computing systems. IEEE J. Sel. Areas Commun. (2019). [26] Ruirui Zhang et al. 2024. Federating from History in Streaming Federated Learning. In Int. Symp. Theory Algorithmic Found. Protocol Des. Mobile Netw. Mobile Comput. (MobiHoc). 151–160. [27] Zhuoyi Zhao and Ben Liang. 2026. Adaptive Data Admission and Retention for Streaming Federated Learning. https://tinyurl.com/AdaDataSamplingSFL. [28] Zhi 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 (2020), 9341–9356.
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
Supplementary Material for the paper “Adaptive Data Admission and Retention for Streaming Federated Learning” Zhuoyi Zhao and Ben Liang
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 𝑛𝑡 𝑡 , and (ii) a uniform generalization and the effective sample size 𝑁 eff 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 [16], adapted to the present full-batch memory-based streaming federated learning model. In particular, we follow the same empirical-optimization viewpoint as [16]: 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 𝐴𝜋 (𝑡) 𝜔𝑖𝜋 (𝑡) ≜ Í𝑁 𝜋 (𝑡𝑖 ) , 𝐴𝜋𝑗 (𝑡) 𝑗=1
𝑖 = 1, . . . , 𝑁 𝜋 (𝑡),
𝜋 (𝑡 ) 𝑁∑︁
𝜔𝑖𝜋 (𝑡)ℓ (𝜃 ; 𝑧𝑖 ).
(68)
𝑖=1
This objective is the analogue of the global weighted empirical objective 𝐿𝑆(𝜆) in [16]. It aggregates all distinct samples used up to round 𝑡, with weights proportional to their cumulative reuse counts. In contrast, the actual local update at round 𝑡 is performed using only the samples currently stored in the clients’ memories. We denote the corresponding memory-induced empirical objective by ∑︁ 1 ℓ (𝜃 ; 𝑧). (69) 𝐹b𝑡mem (𝜃 ) ≜ 𝜋 𝑛 (𝑡) 𝑧 ∈𝑄 (𝑡 )
The cumulative empirical optimization error is defined as opt
E𝑇 (𝜋) ≜
𝑇 h i ∑︁ E 𝐹b𝑡all (𝜃 (𝑡 ) ) − 𝐹b𝑡all,★ .
(70)
𝑡 =1
where 𝐹b𝑡all,★ ≜ min𝜃 ∈Θ 𝐹b𝑡all (𝜃 ). The key round-dependent quantity is therefore the empirical gradient mismatch between the cumulative multiplicity-weighted objective and the current memoryinduced objective: 2 𝜎¯ 2 (𝑡) ≜ E sup ∇𝐹b𝑡all (𝜃 ) − ∇𝐹b𝑡mem (𝜃 ) . (71) 𝜃 ∈Θ
2
Lemma 5. Under Assumptions 1–4, the iterates {𝜃 (𝑡 ) }𝑇𝑡=1 generated under policy 𝜋 satisfy the following one-step optimization recursion: h i E ∥𝜃 (𝑡 +1) −𝜃 ★ ∥ 22 ≤ E ∥𝜃 (𝑡 ) −𝜃 ★ ∥ 22 −2𝜂 E 𝐹b𝑡all (𝜃 (𝑡 ) ) − 𝐹b𝑡all,★ (72) + 2𝜂𝐷 𝜎¯ (𝑡) + 𝜂 2 2𝜎¯ 2 (𝑡) + 𝐶 1 + 𝜂 4𝐶 2, where √︁ 𝐶 1 ≜ 𝐺 5𝐺 + 2𝐿𝐷 2(1 − 𝐸 −1 ) ,
𝐶 2 ≜ 4𝐿 2𝐺 2 (1 − 𝐸 −1 ), (73)
and opt
E𝑇 (𝜋) ≤
𝑇 𝑇 ∑︁ 𝜂3 𝜂 ∑︁ 2 𝐷2 +𝐷 𝜎¯ (𝑡) + 2𝜎¯ (𝑡) + 𝐶 1 + 𝐶 2𝑇 . (74) 2𝜂 2 𝑡 =1 2 𝑡 =1
(67)
and define the cumulative multiplicity-weighted empirical objective 𝐹b𝑡all (𝜃 ) ≜
Thus, 𝜎¯ 2 (𝑡) measures how far the gradient used by the round-𝑡 memory-based update deviates from the gradient of the policyinduced cumulative empirical objective. The following lemma rewrites the one-step optimization recursion in Appendix B.5 of [16] under our notation and derives the corresponding cumulative empirical optimization-error bound.
Proof. The one-step recursion in (72) follows directly from the derivation in Appendix B.5 of [16], after rewriting the empirical objective and the empirical gradient mismatch under the notation introduced above. The higher-order terms are regrouped into the constants 𝐶 1 and 𝐶 2 in (73). Rearranging (72) gives i h 2𝜂E 𝐹b𝑡all (𝜃 (𝑡 ) ) − 𝐹b𝑡all,★ ≤ E ∥𝜃 (𝑡 ) − 𝜃 ★ ∥ 22 − E ∥𝜃 (𝑡 +1) − 𝜃 ★ ∥ 22 + 2𝜂𝐷 𝜎¯ (𝑡) + 𝜂 2 2𝜎¯ 2 (𝑡) + 𝐶 1 + 𝜂 4𝐶 2 . (75) Summing (75) over 𝑡 = 1, . . . ,𝑇 telescopes the squared-distance terms: 𝑇 ∑︁ E∥𝜃 (𝑡 )−𝜃 ★ ∥ 22 −E∥𝜃 (𝑡 +1)−𝜃 ★ ∥ 22 =E∥𝜃 (1) −𝜃 ★ ∥ 22−E∥𝜃 (𝑇 +1)−𝜃 ★ ∥ 22 ≤ 𝐷 2, 𝑡 =1
where the last inequality follows from the boundedness of Θ and the nonnegativity of squared norms. Dividing both sides by 2𝜂 yields (74). □
A.2
Variance control via effective sample size
We next refine the empirical gradient mismatch 𝜎¯ 2 (𝑡) by explicitly separating the effects of distinct-sample growth and samplereuse imbalance. Recall from Assumption 4 that the single-sample population-gradient variance satisfies E𝑧∼P ∥∇𝜃 ℓ (𝜃 ; 𝑧) − ∇𝐹 P (𝜃 )∥ 22 ≤ 𝜎 2, ∀𝜃 ∈ Θ. (76) Under the effective-sample-size variance control induced by repeated sample reuse, the empirical gradient mismatch at round 𝑡
Conference’17, July 2017, Washington, DC, USA
Zhao et al.
satisfies
which proves (79). 2
𝜎¯ (𝑡) ≤ 𝜎
2
1 1 − . e𝜋 (𝑡) 𝑛𝜋 (𝑡) 𝑁 𝜋 (𝑡) V
(77)
Substituting (77) into Lemma 5 yields √︄ 𝑇 ∑︁ 𝐷2 1 1 opt E𝑇 (𝜋) ≤ + 𝐷𝜎 − 𝜋 (𝑡) 𝜋 e𝜋 (𝑡) 2𝜂 𝑛 𝑁 (𝑡) V 𝑡 =1 𝑇 ∑︁ 𝜂𝐶 1 𝜂 3𝐶 2 1 1 + 𝜂𝜎 2 − + 𝑇 + 𝑇. e𝜋 (𝑡) 𝑛𝜋 (𝑡) 𝑁 𝜋 (𝑡) V 2 2 𝑡 =1 (78)
A.3
Generalization term controlled by pseudo-dimension
We next bound the generalization gap between the population objective 𝐹 P and the cumulative multiplicity-weighted empirical objective 𝐹b𝑡all . It is essentially an application of Theorem 4.1 in [16] 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 6 (Uniform generalization bound with effective sample size). Assume ℓ (𝜃 ; 𝑧) ∈ [0, 𝐵] for all 𝜃 ∈ Θ and 𝑧. Then for each round 𝑡, the expected generalization gap is bounded by " # all E sup 𝐹 P (𝜃 ) − 𝐹b𝑡 (𝜃 ) 𝜃 ∈Θ
√︄ ≤ 10𝐵
Pdim(ℓ ◦ H ) e𝜋 (𝑡) 𝑁 𝜋 (𝑡) V
(79)
√︄
1 + log
𝑁 𝜋 (𝑡) Pdim(ℓ ◦ H )
.
A.4
□
Proof of Theorem 1
Proof of Theorem 1. We combine the optimization-error bound in (78) with the generalization bound in Lemma 6. Specifically, (78) opt controls the cumulative optimization component E𝑇 (𝜋) with respect to the cumulative multiplicity-weighted empirical objective 𝐹b𝑡all in terms of the policy-induced training sample size 𝑛𝜋 (𝑡) and e𝜋 (𝑡), while Lemma 6 bounds the geneffective sample size 𝑁 𝜋 (𝑡) V eralization gap between the population objective 𝐹 P and 𝐹b𝑡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 6 yields the desired cumulative excess-risk 2 upper bound. Finally, absorbing the initialization term 𝐷2𝜂 and other lower-order constants into the constant term 𝐶 2 gives the statement of Theorem 1. □
B
Proof of Lemma 1
Consider the feasible constant-admission comparison policy associated with the benchmark operating point ( Λ̄, 𝐾). For an arbitrary round 𝑡, let O(𝑡) denote the realized system state induced by the proposed ACDPP policy over rounds 1, . . . , 𝑡 − 1, and suppose that at round 𝑡 the server switches to the comparison admission vector 𝝀𝐶𝐾 (𝑡). Under the K-step retention policy, each admitted sample remains in memory for exactly 𝐾 rounds. Hence the instantaneous batch size and cumulative distinct sample count under the comparison policy satisfy 𝑛𝐶 (𝑡) = 𝑛(𝑡) − Λ(𝑡 − 𝐾) + Λ̄,
𝑁 𝐶 (𝑡) = 𝑁 (𝑡 − 1) + Λ̄.
(83)
Substituting (83) into the penalty definition (29) gives the one-slot drift-plus-penalty objective 𝐽𝑡 (𝝀𝐶𝐾 (𝑡)) = 𝑍 (𝑡) 𝑐 (𝑡) Λ̄ − 𝐶 + 𝑉 𝑝𝐶𝐾 (𝑡), (84)
Proof. Recall the policy-induced weights 𝜔𝑖𝜋 (𝑡) and the cumulative multiplicity-weighted empirical objective 𝐹b𝑡all defined in (67)– (68). Consider the loss-composed hypothesis class
where 𝑝𝐶𝐾 (𝑡) is the per-round penalty induced by the comparison policy. Next, since the admissible action space satisfies
F ≜ {𝑧 ↦→ ℓ (𝜃 ; 𝑧) : 𝜃 ∈ Θ},
Λmin (𝑡) ≤ Λ(𝑡) ≤ Λmax (𝑡),
(80)
which is uniformly bounded in [0, 𝐵] 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 norm of the weight vector: 𝜋 (𝑡 ) Í𝑁 𝜋 (𝑡 ) 𝜋 𝑁∑︁ (𝐴𝑖 (𝑡)) 2 1 1 𝜋 2 (𝜔𝑖 (𝑡)) = 𝑖=1 = = , Í𝑁 𝜋 (𝑡 ) 𝜋 2 𝑁 𝜋 (𝑡) 𝑁 𝜋 (𝑡) V e𝜋 (𝑡) eff 𝑖=1 𝐴𝑖 (𝑡) 𝑖=1 (81) Applying the standard pseudo-dimension bound for bounded realvalued function classes yields " # E sup 𝐹 P (𝜃 ) − 𝐹b𝑡all (𝜃 ) 𝜃 ∈Θ
√︄ ≤ 10𝐵
Pdim(ℓ ◦ H ) e𝜋 (𝑡) 𝑁 𝜋 (𝑡) V
√︄
(82)
𝑁 𝜋 (𝑡) 1 + log , Pdim(ℓ ◦ H )
(85)
we have the lower bounds 𝑛𝐶 (𝑡) ≥ (𝐾 − 1)Λmin (𝑡 − 𝐾) + Λ̄,
(86)
and 𝑁 𝐶 (𝑡) ≥
𝑡 −1 ∑︁
Λmin (𝜏) + Λ̄.
(87)
𝜏=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) where 𝑝¯𝐶𝐾 (𝑡) is given by (52). Therefore, 𝐽𝑡 (𝝀𝐶𝐾 (𝑡)) ≤ 𝑍 (𝑡) 𝑐 (𝑡) Λ̄ − 𝐶 + 𝑉 𝑝¯𝐶𝐾 (𝑡).
(89)
Recall that the one-slot drift-plus-penalty upper bound holds for any feasible admission vector 𝝀: Δ(O(𝑡)) + 𝑉 E[𝑝 (𝑡) | O(𝑡)] ≤ 𝐵 + E[𝐽𝑡 (𝝀) | O(𝑡)].
(90)
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
For the pseudo-dimension term, define 1 1 𝑥𝑡 ≜ , 𝑦𝑡 ≜ 𝜋 . 𝜋 𝜋 e 𝑁 (𝑡) 𝑁 (𝑡) V (𝑡)
By definition, the ACDPP policy chooses ★
𝝀 (𝑡) ∈ arg min 𝐽𝑡 (𝝀),
(91)
𝐽𝑡 (𝝀★ (𝑡)) ≤ 𝐽𝑡 (𝝀𝐶𝐾 (𝑡)).
(92)
𝝀
and hence Substituting (92) into (90) yields Δ(O(𝑡)) + 𝑉 E[𝑝 (𝑡) | O(𝑡)] ≤ 𝐵 + E[𝐽𝑡 (𝝀𝐶𝐾 (𝑡)) | O(𝑡)].
(93)
Using (89), we obtain Δ(O(𝑡))+𝑉 E[𝑝 (𝑡) | O(𝑡)] ≤ 𝐵+E 𝑍 (𝑡) 𝑐 (𝑡) Λ̄ − 𝐶 | O(𝑡) +𝑉 𝑝¯𝐶𝐾 (𝑡). (94) Now take total expectation. Since the sampling-cost process {𝑐 (𝑡)} is independent of the queue state 𝑍 (𝑡) under the comparison policy, we have E 𝑍 (𝑡) 𝑐 (𝑡) Λ̄ − 𝐶 = E[𝑍 (𝑡)] E 𝑐 (𝑡) Λ̄ − 𝐶 . (95) Because the benchmark comparison policy is feasible, it satisfies the long-term sampling-cost constraint, and therefore E 𝑐 (𝑡) Λ̄ − 𝐶 ≤ 0. (96) Hence (94) implies E[𝐿(𝑡 + 1) − 𝐿(𝑡)] + 𝑉 E[𝑝 (𝑡)] ≤ 𝐵 + 𝑉 𝑝¯𝐶𝐾 (𝑡).
(97)
Summing (97) over 𝑡 = 1, . . . ,𝑇 gives E[𝐿(𝑇 + 1) − 𝐿(1)] + 𝑉
𝑇 ∑︁
E[𝑝 (𝑡)] ≤ 𝐵𝑇 + 𝑉
𝑡 =1
𝑇 ∑︁
is locally Lipschitz for sufficiently small positive 𝑥, the pseudodimension term also differs from its surrogate counterpart by at most 𝑂𝑡 (𝑡 −2 ). Combining the square-root, linear, and pseudo-dimension terms yields a per-round discrepancy of order 𝑂𝑡 (𝑡 −2 ). Summing over 𝑡 = 1, . . . ,𝑇 gives Ē𝑇ACDPP −
𝑇 ∑︁
𝑝¯𝐶𝐾 (𝑡),
which proves Lemma 2.
D
Proof of Lemma 3
Under the time-varying rectangular constraint (35), the lower bounds on the instantaneous training sample size and the cumulative number of distinct samples are 𝑁 lb (𝑡) = Λ̄𝑡 − Λ̄
𝑡 −1 ∑︁
It follows from (102) that, for all 𝑡 ≥ 𝐾, 1 1 1 1 1 − − = 𝑛 lb (𝑡) Λ̄𝐾 Λ̄ 𝐾 − (𝐾 − 1)𝜌 𝑡 −𝐾 𝐾
Proof of Lemma 2
=
The only difference between the finite-horizon learning upper Í bound Ē𝑇ACDPP and the cumulative surrogate penalty 𝑇𝑡=1 E[𝑝 (𝑡)] 𝜋 e (𝑡), since the surrogate comes from the reuse-uniformity factor V penalty replaces 𝜋 1f𝜋 by 𝑁 𝜋1(𝑡 ) . 𝑁 (𝑡 ) V (𝑡 ) Here and below, 𝑂𝑡 (·) and Θ𝑡 (·) denote big-𝑂 and big-Θ with respect to the per-round index 𝑡. Under the K-step retention policy, only the samples admitted in the most recent 𝐾 − 1 rounds fail to complete their full 𝐾 reuse cycles by round 𝑡. Therefore, the first- and second-moment deficits of the reuse counts are both 𝑂𝑡 (1), while the cumulative number of distinct samples satisfies 𝑁 𝜋 (𝑡) = Θ𝑡 (𝑡). It follows that (99)
and hence e𝜋 (𝑡) 1−V = 𝑂𝑡 (𝑡 −2 ). 𝜋 e𝜋 (𝑡) 𝑁 (𝑡) V
(101)
𝜌 𝜏 . (102)
𝜏=1
(98)
𝑡 =1
e𝜋 (𝑡) = 𝑂𝑡 (𝑡 −1 ), 1−V
E[𝑝 (𝑡)] = 𝑂 (1),
𝑡 =1
𝑛 lb (𝑡) = 𝐾 Λ̄ − (𝐾 − 1) Λ̄ 𝜌 𝑡 −𝐾 ,
which proves (51).
C
By (100), we have 𝑥𝑡 − 𝑦𝑡 = 𝑂𝑡 (𝑡 −2 ). Since the map √︄ √︁ 1 𝑥 ↦→ 10𝐵 Pdim(ℓ ◦ H ) 𝑥 1 + log 𝑥 Pdim(ℓ ◦ H )
(𝐾 − 1)𝜌 𝑡 −𝐾 ≤ 𝜅 1 𝜌 𝑡 −𝐾 , Λ̄𝐾 𝐾 − (𝐾 − 1)𝜌 𝑡 −𝐾
(103)
where the inequality follows from 𝐾 − (𝐾 − 1)𝜌 𝑡 −𝐾 ≥ 1, and 𝜅 1 = 𝐾 −1 . Λ̄𝐾 Similarly, because 𝑡 −1 ∑︁ 𝜏=1
𝜌𝜏 =
𝜌 (1 − 𝜌 𝑡 −1 ) 1 ≤ , 1−𝜌 1−𝜌
we have 𝑁 lb (𝑡) = Λ̄𝑡 − 𝛿𝑡 ,
0 ≤ 𝛿𝑡 ≤
Λ̄ . 1−𝜌
Therefore, 1 1 𝛿𝑡 . − = 𝑁 lb (𝑡) Λ̄𝑡 ( Λ̄𝑡)( Λ̄𝑡 − 𝛿𝑡 ) Using the bound on 𝛿𝑡 , we obtain
(100)
Λ̄/(1 − 𝜌) 1 1 1 = . (104) − ≤ 𝑁 lb (𝑡) Λ̄𝑡 ( Λ̄𝑡) Λ̄𝑡 − Λ̄/(1 − 𝜌) Λ̄ (1 − 𝜌)𝑡 2 − 𝑡
Now compare the terms in the learning upper bound with their surrogate counterparts. Since 𝑛𝜋 (𝑡) = Θ𝑡 (1) under K-step retention and 𝑁 𝜋 (𝑡) = Θ𝑡 (𝑡), the quantity 𝑛𝜋1(𝑡 ) − 𝜋 1f𝜋 remains 𝑁 (𝑡 ) V (𝑡 ) bounded away from zero for all sufficiently large 𝑡. 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 𝑂𝑡 (𝑡 −2 ). The same order follows immediately for the linear term.
We now compare 𝑝¯𝐶𝐾 (𝑡) with 𝑝¯𝐶𝐾 ∞ (𝑡) term by term. For the square-root term, define 1 1 1 1 − , 𝑣𝑡 ≜ − . 𝑢𝑡 ≜ 𝑛 lb (𝑡) 𝑁 lb (𝑡) Λ̄𝐾 Λ̄𝑡 By (??) and (104), 1 . 𝑢𝑡 − 𝑣𝑡 ≤ 𝜅 1 𝜌 𝑡 −𝐾 + Λ̄ (1 − 𝜌)𝑡 2 − 𝑡
1 e𝜋 (𝑡) 𝑁 𝜋 (𝑡) V
−
1 𝑁 𝜋 (𝑡)
=
Conference’17, July 2017, Washington, DC, USA
Zhao et al.
Since 𝑣𝑡 is bounded away from zero for all sufficiently large 𝑡, the √ map 𝑥 ↦→ 𝑥 is locally Lipschitz around 𝑣𝑡 . Therefore, there exists a constant 𝜅 2 > 0 such that the square-root term in 𝑝¯𝐶𝐾 (𝑡) differs from its counterpart in 𝑝¯𝐶𝐾 ∞ (𝑡) by at most 𝜅2 𝜅 2 𝜌 𝑡 −𝐾 + . (1 − 𝜌)𝑡 2 − 𝑡 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 √︄ √︁ 1 𝑥 ↦→ 10𝐵 Pdim(ℓ ◦ H ) 𝑥 1 + log , 𝑥 Pdim(ℓ ◦ H )
Therefore, 𝑇 ∑︁ 𝑡 =𝑡 0
∞ 𝜅4 2𝜅 4 ∑︁ 1 1 ≤ = 𝑂 . (1 − 𝜌)𝑡 2 − 𝑡 1 − 𝜌 𝑡 =𝑡 𝑡 2 1−𝜌 0
Combining the two parts yields 𝑇 ∑︁
1 1 =𝑂 . (1 − 𝜌)𝑡 2 − 𝑡 1−𝜌 𝑡 =1
Hence 𝑇 ∑︁
𝑝¯𝐶𝐾 (𝑡) − 𝑝¯𝐶𝐾 ∞ (𝑡) = 𝑂
𝑡 =1
1 , 1−𝜌
(107)
which proves Lemma 3. there exists a constant 𝜅 3 > 0 such that the pseudo-dimension term differs by at most 𝜅3 𝜅 3 𝜌 𝑡 −𝐾 + . (1 − 𝜌)𝑡 2 − 𝑡 Combining the three terms, there exists a constant 𝜅 4 > 0 such that 𝜅4 𝑡 −𝐾 , 𝑡 ≥ 𝐾 . (105) 𝑝¯𝐶𝐾 (𝑡) − 𝑝¯𝐶𝐾 + ∞ (𝑡) ≤ 𝜅 4 𝜌 (1 − 𝜌)𝑡 2 − 𝑡 Summing (105) over 𝑡 = 1, . . . ,𝑇 gives 𝑇 ∑︁
𝑝¯𝐶𝐾 (𝑡) − 𝑝¯𝐶𝐾 ∞ (𝑡) ≤
𝑡 =1
𝐾 −1 ∑︁
𝑝¯𝐶𝐾 (𝑡) − 𝑝¯𝐶𝐾 ∞ (𝑡) + 𝜅 4
𝑡 =1
𝑇 ∑︁
𝜌 𝑡 −𝐾
𝑡 =𝐾
+ 𝜅4
𝑇 ∑︁
1 . 2 −𝑡 (1 − 𝜌)𝑡 𝑡 =1
(106) The first term is finite because it contains only finitely many indices. The second term is bounded by ∞ ∑︁ 𝜅4 𝜅4 𝜌𝑗 = . 1 −𝜌 𝑗=0 For the third term, let 𝑡0 ≜
2 . 1−𝜌
We split the sum as 𝑡∑︁ 𝑇 0 −1 ∑︁ 𝜅4 𝜅4 𝜅4 = + . 2 2 2 −𝑡 (1 − 𝜌)𝑡 − 𝑡 (1 − 𝜌)𝑡 − 𝑡 (1 − 𝜌)𝑡 𝑡 =𝑡 𝑡 =1 𝑡 =1
𝑇 ∑︁
0
= 𝑂 ((1 − 𝜌) −1 ) and the per-round discrepancy is uniformly
Since 𝑡 0 bounded, the first sum contributes 𝑂 ((1 − 𝜌) −1 ). For the second sum, when 𝑡 ≥ 𝑡 0 , we have 2 𝑡≥ , 1−𝜌 which implies 1 (1 − 𝜌)𝑡 2 ≥ 𝑡, 2 or equivalently, 1 (1 − 𝜌)𝑡 2 − 𝑡 ≥ (1 − 𝜌)𝑡 2 . 2 Hence, when 𝑡 >= 𝑡 0 , 𝜅4 2𝜅 4 ≤ . (1 − 𝜌)𝑡 2 − 𝑡 (1 − 𝜌)𝑡 2
E
Proof of Lemma 4
Recall that, under the costless oracle policy, the cumulative learning upper bound takes the form " √︂ 𝑇 ∑︁ 1 1 1 1 oracle Ē𝑇 = 𝐷𝜎 − + 𝜂𝜎 2 − ¯ ¯ 𝐵¯ 𝐵𝑡 𝐵¯ 𝐵𝑡 𝑡 =1 √︄ √︂ # (108) ¯ Pdim(ℓ ◦ H ) 𝐵𝑡 1 + log , + 10𝐵 ¯ Pdim(ℓ ◦ H ) 𝐵𝑡 Í𝑀 where 𝐵¯ ≜ 𝑚=1 𝐵𝑚 . Compare the per-round term in 𝑝¯𝐶𝐾 ∞ (𝑡) with the corresponding ¯ the steadyper-round term in (108). Under the condition Λ̄𝐾 = 𝐵, state terms coincide exactly: 1 1 = . Λ̄𝐾 𝐵¯ Thus the only mismatch comes from the distinct-sample-growth terms 1 1 and . ¯ Λ̄𝑡 𝐵𝑡 Their difference is 1 1 1 𝐾 −1 1 − = − = = 𝑂𝑡 (𝑡 −1 ). (109) ¯ Λ̄𝑡 𝐵𝑡 Λ̄𝑡 Λ̄𝐾 𝑡 𝐵¯ 𝑡 We again compare the three terms separately. For the squareroot term, since the underlying argument is bounded away from zero for sufficiently large 𝑡, the square-root map is locally Lipschitz, and the discrepancy is therefore 𝑂𝑡 (𝑡 −1 ). The same order follows immediately for the linear term. For the pseudo-dimension term, note that √︄ √︂ Pdim(ℓ ◦ H ) Λ̄𝑡 10𝐵 1 + log Pdim(ℓ ◦ H ) Λ̄𝑡 and its oracle counterpart differ only through the factor 1/( Λ̄𝑡) ¯ Since the map versus 1/(𝐵𝑡). √︄ √︁ 1 𝑥 ↦→ 10𝐵 Pdim(ℓ ◦ H ) 𝑥 1 + log 𝑥 Pdim(ℓ ◦ H ) is locally Lipschitz for sufficiently small positive 𝑥, the resulting discrepancy is of lower order than 𝑡 −1 and can be absorbed into the same bound.
Adaptive Data Admission and Retention for Streaming Federated Learning
Conference’17, July 2017, Washington, DC, USA
Hence the per-round difference between 𝑝¯𝐶𝐾 ∞ (𝑡) and the oracle term is 𝑂𝑡 (𝑡 −1 ). Summing over 𝑡 = 1, . . . ,𝑇 yields 𝑇 ∑︁
oracle 𝑝¯𝐶𝐾 = 𝑂 (log𝑇 ), ∞ (𝑡) − Ē𝑇
(114)
! 𝑉 . 𝑉𝑇 + 1−𝜌
(115)
and therefore, by Jensen’s inequality, √︄
From Lemma 1 and the nonnegativity of the penalty term, 𝑇 ∑︁
𝑝¯𝐶𝐾 (𝑡).
E[𝑍 (𝑇 + 1)] = 𝑂 (111)
𝑡 =1
Using Lemma 3, we have
𝑡 =1
𝑉 , 1−𝜌
E[𝑍 (𝑇 + 1) 2 ] = 𝑂 (𝑉𝑇 ) + 𝑂
E[𝐿(𝑇 + 1) − 𝐿(1)] ≤ 𝐵𝑇 + 𝑉
𝑇 ∑︁ 𝑡 =1
𝑝¯𝐶𝐾 ∞ (𝑡) + 𝑂
(113)
Since 𝐿(𝑡) = 12 𝑍 (𝑡) 2 , it follows that
Proof of Theorem 3
𝑝¯𝐶𝐾 (𝑡) =
𝑉 . 1−𝜌
(110)
which proves Lemma 4.
𝑇 ∑︁
E[𝐿(𝑇 + 1)] = 𝑂 (𝑉𝑇 ) + 𝑂
𝑡 =1
F
Substituting (112) into (111) yields
1 . 1−𝜌
Since each term 𝑝¯𝐶𝐾 ∞ (𝑡) is uniformly bounded in 𝑡, it follows that 𝑇 ∑︁ 1 𝑝¯𝐶𝐾 (𝑡) = 𝑂 (𝑇 ) + 𝑂 . (112) 1−𝜌 𝑡 =1
By the standard virtual-queue argument in Lyapunov optimization (e.g., [19, Theorem 2.8]), the cumulative constraint violation is upper bounded by E[𝑍 (𝑇 + 1)]. Therefore, √︄ ! 𝑉 S Vio (𝑇 ) ≤ 𝑂 𝑉𝑇 + , (116) 1−𝜌 which proves (63).