Source-linked AI summary
Semi-Cyclic Stochastic Gradient Descent
Hubert Eichner, Tomer Koren, H. Brendan McMahan, Nathan Srebro, Kunal Talwar
TL;DR
Block-cyclic sampling can substantially slow SGD when successive blocks have different data distributions. The paper proposes pluralistic predictors for this setting and reports guarantees matching homogeneous i.i.d. data, with potential to outperform the i.i.d. baseline when component distributions differ.
Problem
Method
Results
The pluralistic approach matches the worst-case guarantee for homogeneous i.i.d. data without degradation by the number of blocks, and can outperform the i.i.d. baseline when component distributions differ.
Source: §8 · p. 8Takeaways & Limitations
Pluralism can be a critical tool for heterogeneous data by embracing heterogeneity rather than insisting on a consensus solution.
Source: §8 · p. 8The analysis covers convex objectives and sequential SGD; non-convex settings are presented as a direction for further analysis.
Source: §8 · p. 8
Abstract
from arXiv · showhide
We consider convex SGD updates with a block-cyclic structure, i.e. where each cycle consists of a small number of blocks, each with many samples from a possibly different, block-specific, distribution. This situation arises, e.g., in Federated Learning where the mobile devices available for updates at different times during the day have different characteristics. We show that such block-cyclic structure can significantly deteriorate the performance of SGD, but propose a simple approach that allows prediction with the same performance guarantees as for i.i.d., non-cyclic, sampling.
1. Introduction
Block-cyclic sampling models settings such as Federated Learning, where data distributions can differ across blocks and sampling order is difficult to avoid. The paper shows that even a small number of blocks can cause severe SGD slowdowns, and proposes pluralistic models to address the heterogeneity.
1. Introduction
- The paper models semi-cyclicity as blocks visited in a fixed order, with samples drawn from a block-specific distribution.This captures cyclic patterns that can arise in real-time or federated training.Source: §1 · p. 1
- Federated Learning motivates the setting because device eligibility varies by time of day, making the available data distributions differ across blocks.Devices must be idle, charging, and on a free wireless connection; language-model devices from India and America may therefore be available at different times.Source: §1 · p. 1
- Even two blocks can cause an arbitrarily bad slowdown, and the slowdown is unavoidable for iterative methods based on semi-cyclic samples.This challenges the hope that performance degrades gracefully as the number of blocks increases.Source: §1 · p. 1
- A pluralistic approach gives the same performance guarantees as i.i.d. non-cyclic sampling by allowing a potentially different model for each block.The paper also reports that its approach is demonstrated empirically and can remain competitive with separately learned predictors when component differences are high.Source: §1 · pp. 1–2
2. Setup
The setup studies convex stochastic optimization with samples drawn from block-specific distributions in a fixed cyclic order. It compares this setting with i.i.d. SGD under standard convexity and bounded-norm assumptions.
2. Setup
- Each block component Di represents its associated data distribution, and the setup assumes a uniform mixture that can be extended to non-uniform weights and block lengths.The distribution may be viewed as a population for fresh samples or as an empirical distribution partitioned into m groups.Source: §2 · p. 2
- The analysis assumes a convex, 1-Lipschitz loss and competes with the best predictor whose norm is at most B.The predictor is evaluated by excess objective error relative to F(w⋆).Source: §2 · p. 2
- With independently drawn samples from D and appropriately chosen step sizes, SGD attains the stated minimax-optimal error guarantee.The setup contrasts this i.i.d. baseline with block-cyclic sampling.Source: §2 · p. 2
- Block-Cyclic SGD runs K cycles of m blocks, drawing n samples from each block-specific distribution per cycle, for T = Kmn updates.The blocks occur in a fixed order, so samples are no longer identically distributed.Source: §2 · p. 2
3. Lower Bounds for Block-Cyclic Sampling
Block-cyclic sampling can impose large lower bounds on optimization error, even with few blocks per cycle. These bounds apply beyond standard SGD, and smoothness does not eliminate the gap with i.i.d. sampling.
3. Lower Bounds for Block-Cyclic Sampling
- With two deterministic components, optimizing their composite objective requires alternating between components at least Ω(B/ϵ) times, regardless of iterations per cycle.In this extreme setting, each block supplies gradients from only one of the two objective terms.Source: §3 · p. 2
- The practical example is only a rough match: the cited Gboard work used Federated Averaging with communication every 400 steps, rather than averaging gradients every step.The paper notes this difference when relating the example to its setting.Source: §3 · p. 2
- Ω(B/K) excess error is unavoidable for some 1-Lipschitz convex problems, even for methods that choose query points adaptively from semi-cyclic samples.The lower bound applies to any method accessing the objective and its gradient on those samples, not just standard SGD.Source: §3 · p. 3
- The block-cyclic lower bound is worse than i.i.d. sampling by a factor of mn/K, which can be large when samples per block n exceed cycles K.The cited Gboard example used 1.2 × 10^6 sequential steps over 4–5 days as a rough estimate of a realistic regime.Source: §3 · pp. 2–3
- Even with smooth objectives, the excess-error lower bound is Ω(B²/K²), and the comparison with i.i.d. sampling has a K³ factor.The lower bound can still be arbitrarily worse than i.i.d. sampling as iterations per block n increase.Source: §3 · p. 3
4. A Pluralistic Approach
The pluralistic approach learns a separate predictor for each block, using the block identity at prediction time. Its trade-off depends on how the component distributions relate: separate predictors can help with conflicting components, but may cost a factor of m when components are similar.
4. A Pluralistic Approach
- The approach learns a separate model for each component and uses the observed component index at prediction time.In Federated Learning, a client can be associated with the hours when it is available for training.Source: §4 · p. 4
- Training a separate SGD chain on each block gives each model i.i.d. samples, but uses only T/m samples per model and slows learning by a factor of m.The stated iteration requirement is T = O(mB^2/ϵ^2), a factor-m slowdown relative to overall i.i.d. sampling.Source: §4 · p. 4
- When component subproblems conflict, their separate predictors can outperform a consensus predictor, even apart from semi-cyclic sampling.The passage describes this as a potential benefit when the component-specific optima are incompatible.Source: §4 · p. 4
- For orthogonal component problems, a smaller norm bound for the separate predictors cancels the pluralistic method’s slowdown in m and recovers i.i.d. performance.The passage states that the required bound is B/√m, √m times smaller than for a single consensus model.Source: §4 · p. 4
- When component distributions are similar, training separate models can waste updates; if all components are identical, block-cyclic sampling is i.i.d.The paper suggests a single-SGD approach might be adequate for similar components.Source: §4 · p. 4
- The goal differs from multi-task learning: the method seeks to handle heterogeneity without assumptions about how component tasks are related.The passage contrasts this with multi-task methods that rely on a chosen relatedness assumption.Source: §4 · p. 5
5. Pluralistic Averaging
Pluralistic averaging turns one semi-cyclic SGD chain into a separate predictor for each component by averaging only that component’s iterates. The resulting guarantee matches the i.i.d. consensus guarantee without depending on the number of blocks.
5. Pluralistic Averaging
- A single semi-cyclic SGD chain can produce one predictor per component by averaging only the iterates from that component’s blocks.This replaces averaging all iterates into one predictor; the paper states the approach needs no assumptions about component relatedness.Source: §5 · p. 5
- Averaging within each component supports an online-to-batch conversion over that component’s i.i.d. samples, although the overall sequence is semi-cyclic.The paper’s explanation is that the online guarantee applies to any sequence, while i.i.d. sampling is needed for the usual conversion from online gradient descent to SGD.Source: §5 · p. 5
- The guarantee does not deteriorate as the number of blocks m increases, unlike separate training for each component and most multi-task approaches.The stated added cost of more blocks is memory and engineering for storing, distributing, and handling more models, not accuracy or direct computation.Source: §5 · p. 6
6. Pluralistic Hedging
Pluralistic hedging addresses uncertainty about whether to use a shared model or separate block-specific models. It combines a full SGD chain and block-specific chains with learned weights, then uses pluralistic averaging to form the final predictors.
6. Pluralistic Hedging
- The method targets both guarantees: those for separately trained component models and the guarantee of pluralistic averaging.The motivation is to avoid needing to know in advance which components benefit from separate models versus information from other components.Source: §6 · p. 6
- The method combines a full SGD chain with block-specific chains using learned weights, then averages iterates within each component to form the predictors.The full-chain weight is fixed, while the weights on the block-specific chains are learned with multiplicative updates.Source: §6 · p. 6
- The method’s stated condition is m ≤ B^2Kn.The paper characterizes this requirement as extremely mild when there are many iterations per block and only a mild number of blocks.Source: §6 · p. 6
7. Experiments
On Sentiment140, the experiments compare block-cyclic training and evaluation approaches with an idealized i.i.d. model. Single-chain pluralistic models outperform same-chain consensus and perform on par with or better than the i.i.d. model.
7. Experiments
- Tweets are split into 90% training and 10% test sets, grouped into six time-of-day components, and divided across ten cycles.The fixed model is a linear bag-of-words classifier over the top 1,024 words with minibatches of 128.Source: §7 · p. 7
- The evaluation compares consensus block-cyclic training, per-component SGD chains, pluralistic evaluation of one SGD chain, and an idealized i.i.d. model.The idealized model trains on the complete shuffled training set; the other approaches use block-specific training or evaluation.Source: §7 · pp. 7–8
- Consensus-model accuracy varies across the midnight and noon test components as training proceeds, with iterates quickly specializing to the active block under label bias.The model can become too specific to the block being processed instead of finding a predictor that works across groups.Source: §7 · p. 8, Figure 1 · p. 8
- Single-chain pluralistic models consistently outperform same-chain consensus and perform on par with or better than idealized i.i.d. SGD.Figure 2 compares the training and testing methodologies; the result depends on how long training proceeds, dataset size, and number of components.Source: §7 · p. 8, Figure 2 · p. 8
- Separate SGD chains for each component converge more slowly because they train on less data, and may or may not surpass the i.i.d. and single-chain pluralistic models.The comparison depends on training duration, dataset size, and number of components.Source: §7 · p. 8
8. Summary
The paper concludes that pluralistic prediction can resolve the block-cyclic slowdown without a block-count penalty, but its analysis covers convex objectives with sequential SGD.
8. Summary
- Pluralistic prediction can match homogeneous i.i.d. guarantees in the worst case without performance degradation based on the number of blocks.When component distributions differ, pluralism can outperform the idealized i.i.d. baseline in the experiments.Source: §8 · p. 8
- Pluralistic solutions may be relevant to heterogeneous learning settings, including Federated Learning with varied devices and distinct client data.Other cited sources of heterogeneity include processing time, latency, data amount, availability, and reliability.Source: §8 · p. 8
- The analysis considers convex objectives with sequential SGD; non-convex training and parallel SGD are left for further exploration.The paper describes its convex semi-cyclic study as potentially indicative of non-convex scenarios, while noting that tight analysis of parallel SGD is lacking even for i.i.d. data.Source: §8 · pp. 8–9
A. Deferred Proofs from Section 6
The deferred proofs establish expert-regret results using a PROD algorithm and derive Lemma 1 as a special case of a corollary.
A. Deferred Proofs from Section 6
- The appendix provides a full proof of Lemma 1, a result previously shown by Even-Dar et al. (2008) and Sani et al. (2014), building on Cesa-Bianchi et al. (2007).The authors give the proof for completeness.Source: A. Deferred Proofs from Section 6 · p. 11
- For K + 1 experts with losses in [-M, M], the PROD algorithm samples an expert proportional to its weight and updates weights multiplicatively.Lemma 3 states a regret result for this algorithm when 0 < η ≤ 1/(4M).Source: A. Deferred Proofs from Section 6 · p. 11
- The corollary optimizes parameters to give regret bounds, and Lemma 1 follows from its K = 1 case.The corollary specifies a choice of η subject to a condition on M and T.Source: A. Deferred Proofs from Section 6 · pp. 11–12
B.1. Dataset
The appendix describes the time-based Sentiment140 split, the label-skew adjustment used in experiments, and how consensus and pluralistic models are evaluated.
B.1. Dataset
- Sentiment140 posts are grouped into six four-hour time-of-day blocks after a random 90/10 training-test split.The training and test sets contain 1,440,000 and 160,000 examples, respectively; the experiments simulate ten cycles.Source: §B.1 · p. 12
B.2. Artificially balanced labels
- The raw time-grouped data has some block-cyclic characteristics, but its label distribution is considered artificially balanced because positive and negative posts were queried separately with a 100-result cap.The experiments adjust positive-sentiment rates by time of day to make differences between pluralistic approaches clearer.Source: §B.2 · p. 12, Figure 3 · p. 12
B.3. Details of evaluation methodology
- For block-cyclic consensus evaluation, the method averages results across all m² model-component evaluations; pluralistic single-chain evaluation uses only the diagonal component-specific evaluations.The consensus method samples an iteration corresponding to a random block, matching the expected number of iterations of the pluralistic approach.Source: §B.3 · p. 12