Optimal Convergence for Distributed Learning with Stochastic Gradient Methods and Spectral Algorithms

Distributed SGM

• Distributed SGM achieves optimal generalization error up to logarithmic factors when the partition level m is not too large.The method partitions N samples, runs multi-pass mini-batch SGM locally, and averages the resulting estimators.Source: §1 · p. 2

Computational advantages

• Distributed SGM has lower theoretical computational complexity than classic SGM and distributed KRR, while retaining a convergence rate of O(N^-1/2 log N).Its stated complexity is O(N) space and O(N^3/2) time, versus O(N) space and O(N^2) time for classic SGM and O(N^3/2) space and O(N^2) time for distributed KRR.Source: §1 · pp. 2–3

Distributed spectral algorithms

• The analysis extends optimal generalization results to distributed spectral algorithms, including distributed gradient methods as a special case.The proof uses an error decomposition into bias, sample variance, and computational variance, together with an integral-operator analysis.Source: §1 · pp. 2–3

Non-attainable cases

• The distributed spectral results improve prior partition-number conditions and provide the first optimal rates for non-attainable cases where the regression function may not lie in the RKHS.These results improve earlier distributed KRR and distributed spectral-algorithm results while requiring a less strict condition on m.Source: §1 · p. 3

Non-distributed spectral algorithms

• The paper also gives the first optimal, capacity-dependent rates for non-distributed spectral algorithms in non-attainable cases.This fills a theoretical gap for kernel ridge regression analyzed through the integral-operator approach.Source: §1 · p. 3

• The data consist of N i.i.d. samples from an unknown probability measure on a compact-metric input space with real-valued outputs, whose input marginal has full support.Source: §2 · p. 3
• Predictor quality is measured by expected square-loss risk and its excess over the risk of the regression function, the measurable-function minimizer.Source: §2 · pp. 3–4
• Kernel methods use a reproducing kernel to define a reproducing kernel Hilbert space as the hypothesis space.Source: §2 · p. 4
• Given only the samples, the learning objective is to recover the regression function through efficient algorithms.Source: §2 · p. 4

3.1 Distributed SGM

• Distributed SGM randomly partitions N = mn samples, runs b-mini-batch local SGM for T iterations, and averages the local predictors.When m = 1, the method becomes classic multi-pass SGM; parameters η_t, b, T, and m govern generalization and computational complexity.Source: §3.1 · pp. 4–5

3.2 Generalization Properties for Distributed Stochastic Gradient Methods

• Distributed SGM achieves nearly minimax-optimal convergence after roughly one pass when the partition level m is not too large, with O(N) space and O(N^1.5) time versus classic SGM’s O(N^2) time.Averaging reduces sample and computational variance without changing bias, creating an iteration-dependent bias–variance trade-off; suitable step-size, mini-batch, and partition choices preserve optimal rates up to logarithmic factors.Source: §3.2 · pp. 6, 8
• Under regularity and capacity assumptions, easier learning problems permit faster convergence and larger partitions, while distributed SGM saturates for ζ > 1 because averaging cannot reduce bias.The condition 2ζ + γ > 1 characterizes problems sufficiently easy for distributed computation to reduce costs.Source: §3.2 · pp. 7–8

3.3 Optimal Rate for Multi-pass SGM on a Single Dataset

• For m = 1, multi-pass SGM attains minimax-optimal convergence up to logarithmic factors for every ζ ∈ ]0, ∞] and improves prior results without requiring their extra condition m ≥ mδ.The corollary provides four parameter regimes combining step-size, mini-batch size, and iteration choices to achieve these rates.Source: §3.3 · p. 9

4.1 Distributed Spectral Algorithms

• Distributed spectral algorithms split the data into m random partitions, compute local spectral estimates using filter functions, and average the resulting estimators.The regularization parameter λ must be appropriately chosen, often through cross-validation; different filters yield methods such as KRR, gradient methods, and spectral cut-off.Source: §4.1 · pp. 9–10

4.2 Optimal Convergence for Distributed Spectral Algorithms

• Distributed spectral algorithms attain the minimax convergence rate, outperform distributed SGM by avoiding its extra logarithmic factor, provided the number of partitions is not too large.The result is optimal even in the non-attainable case, and its allowable partition count is weaker than prior requirements; the bound reflects a bias–sample-variance trade-off and saturates when ζ > 1.Source: §4.2 · p. 11

4.3 Optimal Rates for Spectral Algorithms on a Single Dataset

• Classic spectral algorithms achieve optimal capacity-dependent rates in the non-attainable case when λ is well chosen, without the saturation effect of distributed spectral algorithms.The paper identifies this as the first such result for a general spectral algorithm.Source: §4.3 · p. 12

KRR and spectral algorithms

• Corollary 6 provides the best stated convergence rates for spectral algorithms across both non-attainable and attainable cases without extra assumptions.The bounds are derived in expectation; high-probability bounds are left for future work.Source: §5 · pp. 12–13

Computational comparison

• Table 1 compares distributed SGM with KRR, GM, SA, Nyström, and distributed alternatives, while the discussion identifies advantages for distributed SGM in both memory and time.The computational comparison covers the summarized convergence rates and costs of the listed approaches.Source: Table 1 · p. 13, §5 · pp. 14–15

SGM

• Corollary 3 improves on Lin and Rosasco (2017b), matches averaging online learning when ζ ≤1 and 2ζ + γ > 1, but is worse when 2ζ + γ ≤1 while avoiding averaging OL’s saturation for ζ >1.The comparison concerns rates for multi-pass SGM and averaging one-pass SGM.Source: §5 · p. 14

Nyström methods

• Nyström and sketching methods reduce kernel-matrix size and achieve generalization bounds under suitably chosen subsampling, but distributed SGM is reported to retain computational advantages.The cited comparison concerns both memory and time.Source: §5 · p. 14

Distributed learning

• Distributed SGM can achieve an optimal rate when the partition number is not too large, with a less strict partition condition than distributed SA.This conclusion is stated for distributed SGM with appropriate parameter choices.Source: §5 · p. 14

Open questions

• The paper leaves open parameter tuning by cross-validation, improving the SGM and SA rate when 2ζ + γ ≤1, and deriving high-probability guarantees.The stated low-capacity-regime rate is O(N^-2ζ(1 ∨log N^γ)), compared with O(N^-2ζ) for averaging OL.Source: §5 · p. 15

6.1 Notations

• The notation appendix defines expectations, norms, sampling and covariance operators, regularized operators, reproducing identities, and index sets for the distributed samples.These definitions establish the operator and sampling notation used throughout the proofs.Source: §6 · p. 15, §6.1 · pp. 15–16

6.2 Error Decomposition

• The error decomposition compares distributed gradient and pseudo-gradient auxiliary sequences, with the latter depending on the unknown regression function and therefore serving only as an analytical device.The pseudo GM cannot be implemented in practice because fρ is generally unknown.Source: §6.2 · pp. 16–17
• The proofs organize distributed SGM analysis around an error decomposition into bias, sample variance, and computational variance.The three terms are estimated separately and then combined to derive total error bounds.Source: §6.2 · pp. 16–17
• The proof uses spectral theory and a new bias decomposition to cover both non-attainable and unbounded-output cases.This strategy differs from the cited classic multi-pass SGM analysis and supports refined local-bias estimates.Source: §6.2 · p. 17

6.3 Estimating Bias

• Distributed SGM is rewritten through a population sequence and a filter function Gt, enabling operator-based bounds for the bias.The filter has regularization parameter λt and can have arbitrary positive qualification.Source: §6.3 · pp. 18–19
• The bias analysis bounds local-estimator deviations from the population sequence using operator inequalities and compact-operator spectral arguments.These bounds are developed through lemmas on filter functions, positive operators, and singular-value decompositions.Source: §6.3 · p. 19

Estimating Bias.3

• The detailed bias estimates decompose the remaining error into several random quantities and control them with high-probability concentration bounds.The arguments use Hilbert-space-valued concentration and concentration inequalities for self-adjoint operators, including Lemmas 16–19.Source: Estimating Bias.3 · pp. 23–24
• Under Assumptions 2 and 3, Propositions 2 and 3 analyze ˜λ = n−1+θ for θ ∈[0, 1], with Proposition 3 covering the fully averaged estimator’s bias.A cited lemma enables deriving convergence results in expectation from convergence results in high probability.Source: Estimating Bias.3 · pp. 26, 29

6.4 Estimating Sample Variance

• Propositions 4 and 5 control local and distributed sample variance for ˜λ = n^θ−1, reducing the global variance to the corresponding local estimator variance.The derivation exploits independence of centered noise terms and the averaging relation across local estimators.Source: §6.4 · pp. 29, 31

6.5 Estimating Computational Variance

• Propositions 6 and 7 assume that (70) holds for any t ∈ [T] with t ≥ 2 and set ˜λ = n−θ+1 for some θ ∈ [0, 1].The global computational variance can be estimated in terms of local computational variances.Source: §6.5 · pp. 31–32

6.6 Deriving Total Errors

• Theorem 1 and its corollaries follow by combining the bias, sample-variance, and computational-variance estimates under the stated step-size and regularization conditions.The proof explicitly uses Propositions 1, 3, 5, and 7, then specializes the theorem to derive the corollaries.Source: §6.6 · p. 33

Appendix

• Appendix C proves distributed spectral-algorithm results through an error decomposition into bias and sample variance, followed by separate estimates and recombination.Appendix B contains proofs of selected Section 6 lemmas and propositions.Source: Appendix · p. 38

Appendix A. List of Notations

• Appendix A defines notation for the RKHS hypothesis space, probability measures, sample sizes and partitions, SGM iterates, minibatch size, iterations, and random sample indices.The notation includes total sample size N, local sample size n, and partition count m with N = nm.Source: Appendix A · p. 38
• It specifies local and distributed random-index sets across iterations, together with conditional expectations over algorithmic indices and response noise.These include J_s, J, E_Js, E_J, E_y, and {η_t}_t.Source: Appendix A · p. 38
• It records constants and parameters for the RKHS analysis, including Assumption-based positivity, regression regularity, effective dimension, and the square-integrable function space.The notation includes L_2, γ and c_γ, {g_s,t}_t, and f_ρ.Source: Appendix A · p. 38
• It names the sequences generated by gradient, distributed, pseudo, and distributed pseudo gradient methods: {ḡ_t}_t, {h_s,t}_t, {h̄_t}_t, and {r_t}_t.These sequences correspond respectively to local, distributed, pseudo, and distributed pseudo gradient-method constructions.Source: Appendix A · p. 38
• It defines sampling operators and proof-specific quantities, along with local, distributed, pseudo, and population spectral-algorithm estimators.The listed objects include S_x, S*, L_x, g_zs, ḡ_z, h_zs, h̄_z, and the population spectral estimator.Source: Appendix A · pp. 38–39

• The appendix provides proofs omitted from Section 3, covering its lemmas and propositions.Source: Appendix B · p. 39

• An inductive argument establishes the relevant relationship for every s ∈[m] (Lin and Rosasco, 2017b).Source: §B.1 · p. 39
• Conditioning on J_s,t while using the dependence structure of f_s,t yields the iterative relationship in (31).The conditional expectation is taken with respect to J_s,t given z_s, while f_s,t depends only on earlier sampled variables.Source: §B.1 · p. 39
• Further conditioning with respect to J and the responses, together with (75), leads to the desired result.The response-side step uses the conditional expectation with respect to y_s given x_s.Source: §B.1 · p. 40

B.2 Proof of Lemma 7

• Jensen’s inequality is the proof’s central tool.Source: §B.2 · p. 40
• The argument uses Jensen’s inequality to establish the desired result.Source: §B.2 · p. 40
• The passage identifies Jensen’s inequality as sufficient for completing the proof.Source: §B.2 · p. 40

B.3 Proof of Lemma 9

• For α = 0 or 1, the proof is straightforward and follows Yao et al. (2007).Source: §B.3 · p. 40
• For 0 < α < 1, equation (77) converts the target expression into Π_t 1(u)u^α, after which Conclusion 3 yields the result.Source: §B.3 · p. 40
• The third step uses a basic inequality, as in Lin and Rosasco (2017b, Page 17), and bounds e^−cuu^α by maximizing it at u_max = α/c.Source: §B.3 · pp. 40–41

B.4 Proof of Lemma 10

• Lemma 10’s first conclusion follows from the spectral theorem combined with Part 1) of Lemma 9.Source: §B.4 · p. 41
• Its second conclusion uses the spectral theorem, Part 2) of Lemma 9, and, when α > 1, Hölder’s inequality.Source: §B.4 · p. 41
• The third conclusion of Lemma 10 is obtained by directly applying the spectral theorem and Part 3) of Lemma 9.Source: §B.4 · p. 41

B.5 Proof of Lemma 16

• Lemma 25 provides a high-probability concentration inequality for i.i.d. random variables in a separable Hilbert space under boundedness and variance assumptions.Source: §B.5 · p. 41
• Lemma 16 follows by applying Lemma 25 to ξ_i = f(x_i)K_xi with B′ = 2κ∥f∥∞ and σ = κ∥f∥ρ.Source: §B.5 · p. 42

B.6 Proof of Lemma 17

• Lemma 17 is proved by applying Lemma 25 under H ≤ κ^2 with B′ = 2κ^2 and σ′ = κ^2.Source: §B.6 · p. 42

B.7 Proof of Lemma 18

• Lemma 26 supplies a concentration inequality for bounded, centered self-adjoint Hilbert-Schmidt operators on a separable Hilbert space, enabling the proof of Lemma 18.The result assumes E[X1^2] ≼ V and holds with probability at least 1 − δ.Source: §B.7 · p. 42
• Applying Lemma 26 proves Lemma 18 for any λ > 0, without the λ ≤ ∥T∥ restriction required by Rudi et al. (2015).The proof uses normalized random operators and bounds their moments through the stated assumptions and equation (24).Source: §B.7 · p. 43

B.8 Proof of Lemma 21

• The proofs of Lemmas 21 and 22 use independence, conditional independence, and expectation-taking to establish their desired results.Lemma 21 conditions on the relevant independent variables, while Lemma 22 uses conditional independence of J_s, · · ·, J_m given z̄.Source: §B.8 · p. 44, §B.9 · p. 44

Appendix C. Proofs for Distributed Spectral Algorithms

• The distributed spectral-algorithm analysis extends the distributed-gradient-method proof but requires delicate modifications because general spectral algorithms have fixed qualification τ.For gradient methods, qualification can be any positive number, whereas general spectral algorithms use a fixed constant.Source: Appendix C · p. 44

C.1 Error Decomposition

• The spectral-algorithm error is decomposed using an unimplementable pseudo-spectral estimator into bias and sample-variance terms.The pseudo-estimator averages local estimators and depends on the unknown regression function fρ, so it serves only as an analysis device.Source: §C.1 · pp. 44–45

C.2 Estimating Bias

• Bias estimation introduces a deterministic population function and filter-function bounds whose admissible exponent range is ζ − τ ≤ a ≤ ζ.The restriction differs from the gradient-method case because τ is fixed for spectral algorithms, making the bias proof distinct.Source: §C.2 · p. 45

Estimating Bias.3

• Proposition 10 combines Proposition 9 with Lemma 27 to transfer the component bounds to the bias of the fully averaged estimators.It applies under Assumptions 2 and 3 for ˜λ = n^−1+θ with θ ∈ [0, 1], with separate stated results for ζ ≤ 1 and ζ > 1.Source: Estimating Bias.3 · p. 51

C.3 Estimating Sample Variance

• The sample variance of the average of m local estimators is controlled through the sample variance of one local estimator.This reduction is stated via Lemma 31.Source: §C.3 · p. 52
• Proposition 11 analyzes the local sample variance under Assumption 3 with ˜λ = n^(θ−1), where θ ∈ [0,1].Its constant depends only on κ, cγ, ∥T∥, E, and related stated quantities.Source: §C.3 · p. 52
• The local-variance proof represents the noise through ϵ_i = y_i − fρ(x_i) and uses independence to eliminate cross terms in expectation.The argument also invokes the definitions of the local estimators and the isometric property.Source: §C.3 · p. 52
• Proposition 12 combines Proposition 11 with Lemma 31 to obtain sample-variance bounds for every iteration t ∈ [T].The proposition uses the same scaling ˜λ = n^(θ−1), and its constant is inherited from Proposition 11.Source: §C.3 · p. 53

C.4 Deriving Total Error Bounds

• The variance estimates support the total-error analysis by supplying Proposition 12 to the previously established Proposition 8.The proof of Theorem 2 is described as a direct application of Propositions 12 and 10 within Proposition 8.Source: §C.4 · p. 53
• Corollary 6 follows directly from Theorem 2, completing the derivation of the stated total error bounds.The supplied passage characterizes the corollary’s proof as an immediate consequence of Theorem 2.Source: §C.4 · p. 53