Memory–Regret Tradeoffs for Federated Online Learning When Clients Come and Go

A federated model, meaning one shared model trained across many devices that keep their data private, is usually deployed to every user, but only the devices that happen to be awake send back feedback. When who is awake depends on what they would say, such as phones in one time zone sleeping while another time zone is active, the server sees a biased slice of the population every round. The best known fix is to cache each client's most recent gradient and reuse it while that client is away. That cache costs memory proportional to the number of clients times the model size, which is impractical for millions of devices, and it serves outdated information once user behaviour drifts. This proposal treats server memory as the computational resource in an efficiency–regret tradeoff, in the sense used in online learning. The question is how much regret, meaning the cumulative excess loss over the best fixed model in hindsight, one gives up by remembering absent clients approximately instead of exactly.

The core idea is to store absent clients' gradients as a low-rank factorization rather than as raw vectors. Each client keeps only $m$ coefficients on the server, against a shared basis of $m$ directions maintained by a streaming sketch borrowed from second-order online learning. Each stored entry is also pulled back toward the population average as it ages, so stale feedback is trusted less over time. We expect a regret bound with three separable error terms: one for the usual learning cost, one for how much absent clients' losses drift while they are away, and one for the energy in the client-gradient matrix beyond its top $m$ directions. Together these trace a measurable memory–regret frontier. At one end ($m=N$) sits full caching; at the other ($m=0$) sits plain averaging of whoever shows up.

Core Claim

Under data-correlated partial participation in an online stream, the regret gap between naive averaging and full gradient caching can be largely closed with server memory of order $Nm + md$ instead of $Nd$, where $N$ is the number of clients, $d$ the model dimension and $m \ll d$ the sketch rank. This holds whenever the matrix of per-client gradients is approximately low rank. The same mechanism with age-based shrinkage should beat full caching outright when client losses drift.

Concretely, let $g_t$ be the true population gradient at round $t$ and $\hat g_t$ the server's estimate built from active clients plus sketched surrogates for inactive ones. The standard inexact-gradient argument for online gradient descent over a domain of diameter $B$ with gradient bound $G$ gives

$$\mathrm{Regret}_T \le O(GB\sqrt{T}) + B\sum_{t=1}^T \|\hat g_t - g_t\|.$$

We will then bound $\|\hat g_t - g_t\|$ by the sum of two pieces. The first is a staleness term, the gradient change of each inactive client since its last visit, controlled by a path-variation measure of drift times the client's age. The second is a compression term, the tail singular values of the client-gradient matrix beyond rank $m$. Age-based shrinkage trades the staleness term against a bias term, and choosing its rate per client is the knob the theory should set. This decomposition is the testable object: each term can be measured separately in experiments.

Where This Sits

Two results motivate the gap. Federated Optimization Under Intermittent Client Availability introduced FedLaAvg, which caches every client's latest gradient. It showed that under diurnal availability, staleness is preferable to bias, but it studied only static objectives and paid $O(Nd)$ server memory. Federated Online and Bandit Convex Optimization set up federated online convex optimization and proved regret bounds, but assumed every machine joins every communication round. Neither asks what partial participation does to regret, or what remembering absent clients costs.

A second group constrains or contrasts with the design. FAST avoids per-client state entirely by forcing periodic uniform "snapshot" rounds. That assumption fails when a whole time zone is unreachable, which is the case we target. Patel et al.'s no-collaboration theorem is a real constraint: with exact gradients against an adaptive adversary, collaboration gives no worst-case regret advantage over independent learners. We therefore do not claim gains in that regime. We work with a single deployed model whose loss is the population average, under stochastic client losses with bounded drift (close in spirit to the hybrid settings of Oracle-efficient Hybrid Learning with Constrained Adversaries). We also examine bandit feedback as a secondary regime, where Patel et al. show collaboration does help. Debiasing by participation probabilities (Debiasing Federated Learning with Correlated Client Participation) and variance reduction (Fedvarp) are the main memory-light competitors.

The method itself comes from the efficiency–regret literature in online learning. Efficient Second Order Online Learning by Sketching keeps $m \ll d$ directions with Frequent Directions or Oja's rule to approximate a curvature matrix cheaply, and reports that the dominant subspace is identified within the first 500–2000 examples. We reuse that sketch for a different matrix: client gradients stacked across clients, not one learner's gradients stacked across time. The budget-buffer idea in Nearly Optimal Algorithms with Sublinear Computational Complexity for Online Kernel Regression plays a similar role. There, a novelty test decides which examples deserve memory, and it reached strong accuracy with a buffer of 13 examples. Here we use it as an optional rule for when a returning client's residual should update the shared basis. Earlier hardness results in this literature, such as Online Sparse Linear Regression, establish that compute–regret frontiers can be genuinely unavoidable. We will try to show a matching lower bound in our setting: without a low-rank structure assumption, $o(Nd)$ memory forces regret that grows linearly with the bias.

Research Program

The algorithm, which we call Sketched Latest Averaging, runs plain online gradient descent on the server. At each round, active clients send current gradients at the deployed model. For a returning client $i$, the server projects its gradient onto the current basis $V \in \mathbb{R}^{m\times d}$ to refresh its coefficients $u_i \in \mathbb{R}^m$, and feeds the residual into a Frequent Directions update of $V$. For an inactive client, the surrogate gradient is $\lambda^{a_i} u_i^\top V + (1-\lambda^{a_i})\bar g_t$. Here $a_i$ is the client's age in rounds since last contact, $\bar g_t$ is the running mean over active clients, and $\lambda \in (0,1]$ is the shrinkage rate. Because clients send only gradients, privacy exposure and communication are the same as in FedLaAvg. Server memory is $Nm + md$ numbers, and per-round server compute is $O(|S_t| md)$ for the active set $S_t$.

The theory has three parts. First, an upper bound in the form above, with explicit staleness, compression and shrinkage terms, and a rule for $\lambda$ given a drift budget. Second, a lower-bound construction showing that with memory $o(Nd)$ and no low-rank assumption, some participation pattern forces regret linear in $T$. This would show that the low-rank condition is what makes cheap memory possible, not an artifact of the analysis. Third, an extension of the upper bound to two-point bandit feedback, where averaging surrogate gradients should keep part of Patel et al.'s $\sqrt{M}$ speedup. That speedup scales with the effective number of represented clients, not the number active.

Baselines

The naive reference point is FedAvg in its online form: average whichever clients are active and ignore the rest. FAST reports that under Gamma-distributed arbitrary participation on Fashion-MNIST (Dirichlet $\alpha=0.05$), FedAvg reaches 66.65% accuracy against 84.10% under ideal uniform participation. We will reproduce that setup to calibrate our pipeline.

The strongest existing method on the question we ask is full-cache FedLaAvg (Federated Optimization Under Intermittent Client Availability). It is the $m=N$ end of our frontier and is the method whose memory we aim to remove. The file gives no reported result on Lacuna for FedLaAvg's accuracy on MNIST or Sentiment140, so we will rerun it on its own diurnal MNIST and Sentiment140 protocols. Beating it means matching its cumulative online loss within a few percent at under 10% of its memory on stationary streams, and achieving strictly lower cumulative loss under drift.

The strongest memory-free competitor is FAST. Its reported Fashion-MNIST results are 77.39% at snapshot probability $q=0.5$ and 71.48% for its adaptive variant using snapshots in 8.2% of rounds. We will run FAST with snapshots constrained to clients that are actually reachable, which is the honest version for our regime, and also unconstrained so it can be compared with the paper.

We also include an importance-weighting baseline in the style of Debiasing Federated Learning with Correlated Client Participation, with participation probabilities estimated online, and Fedvarp. For a no-collaboration reference, each client runs its own online gradient descent while awake, evaluated on its own deployed loss.

Three ablations isolate the key ingredient. In the first, $u_i$ is restricted to one-hot vectors, so each client is assigned to a single learned cluster. In the second, a cache of $m$ randomly retained raw gradients is used at matched memory. In the third, shrinkage is removed ($\lambda=1$).

Fairness rules apply to every method. All methods see the same stream order and the same participation trace, and their server memory is reported in floats. Each method gets the same number of step-size and hyperparameter trials, 20, chosen on a held-out prefix of the stream.

Why not just…?

Why not just keep the full FedLaAvg cache? At thousands of clients it is affordable and will likely be the best method on stationary data. That is why it defines the top of our frontier rather than serving as a foil. The claim fails if, at realistic $N$, the sketch needs $m$ close to $d$ to approach it. The measured singular spectrum of the client-gradient matrix settles this directly. Under drift, FedLaAvg has no mechanism to discount stale gradients, and the drift experiments test whether that costs it.

Why not just reweight active clients by inverse participation probability? This needs no memory and is unbiased if the probabilities are right, so it is a real threat. It fails when some clients' probabilities are near zero for long stretches, as in diurnal troughs: weights then explode, or the client is simply unrepresented. We expect our method to win precisely in those troughs and possibly lose when participation is near-uniform. Logging regret per hour of simulated day will show where each wins.

Why not just cache one gradient per known group, such as time zone? If participation is driven entirely by a known grouping, a per-group cache is essentially our one-hot ablation with oracle labels, and it may suffice. We include it with oracle groups. Our method is only worth its extra machinery if dense coefficients beat oracle clusters when within-group data is heterogeneous. That is the Dirichlet-$0.05$ partition case, in which groups and label skew are not aligned.

Why not just let each device learn alone? Patel et al.'s theorem says this is minimax-optimal against adaptive adversaries with exact gradients. In that regime we expect no win and will say so. In our population-loss, drifting-stochastic setting, a rarely-awake client sees few rounds. The independent-learner baseline measures directly how much collaboration buys, and we report it alongside all other results.

Proposed Experiments

We construct online streams from three file benchmarks. The first is diurnal non-IID MNIST with multinomial logistic regression, which is convex and matches the theory. The second is Sentiment140 partitioned by user, which yields thousands of clients and real memory pressure, with the sleep-pattern availability trace of the FedLaAvg study and a small LSTM. The third is Fashion-MNIST with Gamma-distributed participation, as in FAST. Data arrive sequentially, and drift is injected by rotating label skew or the tweet time window across the stream.

The primary metric is cumulative population loss of the deployed model minus that of the best fixed model in hindsight, computed offline. We also report server memory and the final accuracy needed to compare against FAST's numbers. For bandit feedback, we reuse the convex MNIST task with two-point gradient estimates.

The decisive checks are four. First, plotting regret against $m$ should show a knee at the rank where the measured spectral tail flattens; a frontier with no knee would undercut the low-rank premise. Second, on stationary streams our method should approach full FedLaAvg at small $m$, and under injected drift it should beat FedLaAvg, with the advantage growing with drift rate as the staleness term predicts. Third, the three measured error terms should sum to roughly the observed excess regret, which checks that the bound describes what actually happens. Fourth, the dense-coefficient version should beat both the oracle-group cache and importance weighting during low-participation periods; if it does not, the simpler alternatives win and we will report that.