Task allocation for distributed training stops assuming fixed worker speeds: a sliding window keeps up when slow nodes drift

A task allocation algorithm can now estimate worker speeds from a recent stretch of observations instead of averaging the whole history into one fixed value. Earlier adaptive task allocation targeted computation times that do not change across iterations, and its guarantees rested on that assumption. On synthetic distributed stochastic optimization with worker delay means following a slowing sinusoid, the sliding-window version clearly beats the original adaptive allocation and uniform allocation, and its runtime stays close to an oracle that knows the true means.

Each iteration the algorithm first commits to an allocation, then observes how long each worker took, and uses those durations to update its estimate of worker delay means. It keeps the lower-confidence-bound idea of choosing the allocation that looks best under optimism, but restricts the statistics to the most recent window of observations so stale data is forgotten. The window size trades off accuracy against staleness: too small and the mean estimate is noisy, too large and outdated observations enter, for example when a worker is fast early and slow later.

In the fixed-distribution setting, a new counting argument reduces the regret bound's dependence on suboptimality gaps from a squared order to a linear one. Earlier analyses of adaptive task allocation replaced the actual allocation of an over-allocated worker by a worst-case value, which is loose for large batches. In an example with a batch much larger than the worker pool, the old gap term grows with the number of workers while the new bound stays smaller, and the gap between them can be arbitrarily large.

The report covers task allocation under both fixed and round-to-round drifting delay distributions, for readers working on distributed optimization scheduling and online learning. Experiments run synthetic drifting-delay distributed stochastic optimization across several worker pool sizes, with delay means following a slowing sinusoid. The theory provides improved regret bounds for the fixed setting, a sliding-window guarantee for the drifting setting, and lower bounds for two batch regimes.

The drifting guarantee depends on a variation budget that is unknown in real systems, so the window size must be chosen from a reference budget. Upper and lower bounds still disagree in their dependence on the batch parameters, and designing a method that matches the lower bound remains open. The experimental drift is a constructed sinusoid and does not cover more abrupt speed changes seen in real clusters.