Recommender models spend most of their parameters on embedding tables, with one learned vector per item. Interaction data is extremely sparse: a few popular items appear in almost every user's history, and millions of niche items appear in only a handful. When such a model is trained across several machines over slow links, each machine taking many local steps and occasionally averaging its copy of the model with the others (local SGD), every item row is synchronized on the same schedule. That uniformity is wasteful in a specific way. "Client drift" is the error that comes from machines pulling a shared parameter in different directions between averaging steps. It can only arise for a row that several machines are updating. A cold item row that one machine touches has almost no one to disagree with, so it hardly needs synchronizing. A hot row is fought over by every machine and drifts quickly.
We propose to give each embedding row its own synchronization interval, set by how much the machines actually disagree about that row. Hot, contested rows get averaged often. Cold, uncontested rows get averaged rarely. The averaging itself uses the popularity correction from federated submodel training, so cold updates are not diluted. Because cold rows make up most of the traffic in long-tail catalogs, the method should cut communicated bytes substantially without hurting accuracy on rare items. It also offers a concrete resolution to a standing disagreement about whether synchronization should become more or less frequent as training proceeds.
Core Claim
Two analyses of local SGD give opposite advice. Faster Federated Learning With Decaying Number of Local SGD Steps shows that on heterogeneous data the number of local steps should shrink over training, because drift dominates near the optimum. Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization shows that on smooth objectives satisfying the Polyak-Łojasiewicz condition, the averaging interval should grow as the loss falls. Our claim is that in sparse recommendation both are right, but about different parameters. The decay advice applies to rows with high cross-worker heterogeneity, which are the hot items and the dense layers. The growth advice applies to rows with low heterogeneity, which are the cold items. Any single global schedule must therefore be wrong for most of the table.
The prescription follows from where drift comes from. In standard local SGD analyses the drift term for a parameter grows roughly with the square of the interval times the step size squared times the heterogeneity of the updates. Holding per-row drift below a budget therefore gives
$$\tau_m = \mathrm{clip}\Big(\tau_0 \sqrt{\delta / D_m},\ 1,\ \tau_{\max}\Big),$$
where $\tau_m$ is the number of local steps between averagings of row $m$, $\tau_0$ is a base interval, $\delta$ is the drift budget, and $D_m$ is the measured disagreement for row $m$. We define $D_m$ as the variance of the workers' accumulated updates to that row at its last synchronization, normalized by the squared norm of their mean. A row touched by a single worker has $D_m \approx 0$ and is pushed to $\tau_{\max}$. This rule is a heuristic motivated by the drift bound. Part of the research program is to check whether a per-coordinate analysis actually supports it.
Research Program
The system targets cross-silo or geo-distributed data-parallel training, where a fixed set of persistent workers each hold a shard of users. This is the setting in which deferring a row's synchronization is meaningful. In cross-device federated learning, a rarely sampled client may never return, so deferral does not make sense there, and we scope that setting out explicitly. Dense layers, such as a sequence encoder or interaction network, are synchronized on a global decaying schedule following Mills et al. Embedding rows are synchronized per row with interval $\tau_m$. When a row is averaged, the server applies the correction from Federated Submodel Optimization for Hot and Cold Data Features (FedSubAvg). That paper divides the summed update by the number of workers that touched the row rather than by the total number of workers, and shows this correction acts as a diagonal preconditioner. Without it, cold rows that are rarely synchronized would also be scaled down by a factor of up to thousands. Computing $D_m$ costs one scalar per touched row at each synchronization, which is small next to the row itself.
The work has three components. The first is the system: per-row interval bookkeeping, a bounded staleness cap so that a newly arriving worker which starts touching a cold row triggers an early synchronization, and accounting of communicated bytes. The second is analysis. We extend the LUPA-SGD style argument to a block-separable objective with block-specific heterogeneity and intervals, and ask whether the optimal intervals scale as $D_m^{-1/2}$. We also test whether the two published schedules emerge as the high- and low-heterogeneity limits. The third is diagnostics. We track embedding effective rank and hypersphere uniformity, the quantity Are Graph Augmentations Necessary? (SimGCL) identifies as the real source of contrastive gains, to test whether rare synchronization of cold rows worsens the dimensional collapse documented in A Model-agnostic Strategy to Mitigate Embedding Degradation in Personalized Federated Recommendation. The method is backbone-agnostic. We run it on LightGCN with the SimGCL embedding-noise loss as the main backbone, and on DIN for click-through-rate prediction.
Baselines
The naive reference point is local SGD with uniform averaging (FedAvg-style), a fixed interval, and every touched row synchronized every round. It sets the communication ceiling, and per FedSubAvg it should underperform on cold items. FedSubAvg reports that on Alibaba click-through data plain FedAvg stagnated below 0.6 AUC even after 5,000 rounds, while FedSubAvg reached 0.626 AUC.
The strongest existing method is FedSubAvg with full per-round synchronization of touched rows, combined with the better of the two global schedules: decaying local steps (Mills et al.) or the loss-adaptive growing interval ADA-LUPA-SGD. It is the strongest competitor because it already fixes cold-row dilution and already adapts synchronization over time. Our method differs only in making the interval per-row. Its reported figure on our chosen backbone benchmarks is missing: no reported result found on Lacuna for FedSubAvg or decaying-step local SGD on Amazon-Book, Yelp2018, or ML-1M with LightGCN. The only reference figure is the 0.626 AUC above. We will rerun it ourselves.
The communication-compression baseline is magnitude-based top-k sparsification with error feedback on embedding updates, in the spirit of the bidirectional compression with local training in BiCoLoR. It is the natural "just compress" competitor.
Fairness is enforced in four ways. All methods use the same user partition, the same total local-step budget, and the same wall-clock compute. All are tuned with the same number of trials over step size and the method's own knob: $\tau_0$ and $\delta$ for ours, the schedule constants for the global schedules, and k for top-k. All are compared at matched communicated bytes.
Beating the field means one of two outcomes. Either our method matches FedSubAvg-with-best-schedule on overall Recall@20 and tail-item Recall@20 within seed noise while using at least 3× fewer bytes, or it gives strictly higher tail recall at equal bytes.
Two ablations isolate the key ingredient. The first replaces $D_m$ with raw popularity $n_m$, the count of workers touching the row, which tests whether measured disagreement adds anything beyond heat. The second removes the FedSubAvg correction, which tests whether infrequent cold synchronization only works when dilution is fixed.
Why not just…?
Why not just use one global adaptive schedule? Mills et al. and Haddadpour et al. each tune a single interval, and they disagree on its direction. Our hypothesis is that any single interval is too frequent for the long tail and too infrequent for the head. The decisive test is a Pareto plot of tail recall against bytes. If the best global schedule sits on the same frontier as per-row intervals, the idea fails, and we will report that.
Why not just compress with top-k and error feedback? This is a real threat, because error feedback also defers small updates. But it ranks rows by update size, not by disagreement. A cold row being learned for the first time by one worker can have a large update. Top-k would send it every round although no one else needs it. Meanwhile it would truncate small but conflicting updates to hot rows, which is exactly where drift lives. We will measure, per popularity decile, the bytes spent and the drift incurred under each method. If top-k matches us at equal bytes, we will instead study combining the two, using disagreement to choose rows and compression to encode them.
Why not just scale per-row learning rates by popularity? Scaling step sizes changes how far a row moves, but every row is still transmitted every round, so it saves no communication. Mills et al. also show that shrinking step sizes instead of local steps leaves expensive computation that barely moves the model. The ablation that sets intervals by $n_m$ alone covers the strongest popularity-only variant.
Why not just use a convex formulation with provable round complexity? Efficient and Robust Regularized Federated Recommendation achieves $O(\log 1/\epsilon)$ rounds, but only for linear matrix factorization, and its authors leave deep backbones open. We include it as a reference only on ML-1M with a matrix factorization backbone.
Proposed Experiments
The main benchmarks are Amazon-Book and Yelp2018 with LightGCN plus the SimGCL noise loss, chosen because SimGCL reports over 25% Recall@20 gain over LightGCN on Amazon-Book centrally. They are complemented by ML-1M and by Amazon Electronics with DIN, the latter following FedSubAvg. The centrally trained model gives an accuracy ceiling. Users are partitioned across 8, 16, and 64 workers, both at random and clustered by interest, to vary heterogeneity. Metrics are Recall@20 and NDCG@20, overall and on the bottom 80% of items by popularity; total bytes; simulated wall-clock under a 1 Gbps inter-site link; and the effective rank of the item embedding matrix.
Three checks decide the question. The first is the tail-recall-versus-bytes frontier against FedSubAvg with the best global schedule. The second is a direct measurement of per-row drift: the distance between each worker's copy and the average, binned by popularity. This test confirms that cold rows drift little even at $\tau_{\max}$ and hot rows drift a lot at $\tau_0$. If cold rows drift heavily, the core premise is false. The third repeats the frontier test under clustered partitions, where cold items concentrate on single workers. There the method should gain most, and the staleness cap should be what prevents collapse in effective rank.
References
- Faster Federated Learning with Decaying Number of Local SGD Steps
- Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization.
- Federated Submodel Optimization for Hot and Cold Data Features
- Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation
- A Model-agnostic Strategy to Mitigate Embedding Degradation in Personalized Federated Recommendation
- BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training
- Efficient and Robust Regularized Federated Recommendation