PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed learning with regularized least squares

Shao-Bo Lin, Xin Guo, Ding-Xuan Zhou

arXiv:1608.03339v2cs.LGstat.ML

TL;DR

The paper asks whether distributed regularized least squares can approximate whole-data learning in an RKHS without restrictive eigenfunction assumptions. It analyzes averaged local estimators using integral operators and a second-order inverse-operator decomposition, obtaining sharp expectation error bounds and best learning rates in the stated general setting.

  • Problem

    The paper addresses the need to analyze distributed regularized least squares and its approximation to whole-data learning without eigenfunction assumptions.

  • Method

    The algorithm partitions data across machines, applies least squares regularization locally, averages the local estimators, and analyzes operator differences with a second-order decomposition.

  • Results

    The paper derives sharp expectation error bounds for the distributed estimator in both the L^2-metric and RKHS-metric, and gives best learning rates in the general-kernel setting.

  • Takeaways & Limitations

    Distributed regularized least squares can approximate the estimator obtained by processing all data on one machine within the paper’s stated general setting.

  • Takeaways & Limitations

    The analysis considers regularized least squares with Mercer kernels and notes the need to minimize assumptions on the kernel and domain to broaden applications.

Abstract

from arXiv · show

We study distributed learning with the least squares regularization scheme in a reproducing kernel Hilbert space (RKHS). By a divide-and-conquer approach, the algorithm partitions a data set into disjoint data subsets, applies the least squares regularization scheme to each data subset to produce an output function, and then takes an average of the individual output functions as a final global estimator or predictor. We show with error bounds in expectation in both the $L^2$-metric and RKHS-metric that the global output function of this distributed learning is a good approximation to the algorithm processing the whole data in one single machine. Our error bounds are sharp and stated in a general setting without any eigenfunction assumption. The analysis is achieved by a novel second order decomposition of operator differences in our integral operator approach. Even for the classical least squares regularization scheme in the RKHS associated with a general kernel, we give the best learning rate in the literature.

1. Introduction and Distributed Learning Algorithms

The paper analyzes distributed regularized least squares in an RKHS, where local estimators are averaged to approximate whole-data learning while reducing computational costs. It develops an operator-based error analysis without eigenfunction assumptions.

  • Distributed Learning Algorithm: Distributed learning partitions data into disjoint subsets, trains a local estimator on each subset, and averages the outputs into a global estimator.The divide-and-conquer procedure assigns subsets to separate machines or processors before communicating local estimators to a central processor.
  • Research Aim: The study targets approximation of the whole-data estimator by the global output of distributed regularized least squares in an RKHS.The analysis concerns error bounds for the difference between the distributed and single-machine output functions.
  • Motivation: Kernel ridge regression requires O(N^3) time and O(N^2) memory for standard matrix inversion on N samples.The computational burden motivates distributing the least squares regularization scheme across machines.
  • Related Work: A prior matrix-analysis study derived expectation error bounds under eigenfunction assumptions for the associated integral operator.The paper positions its analysis relative to this earlier eigenfunction-dependent treatment.
  • Analysis: The paper uses a novel integral-operator approach and a second-order decomposition of empirical-operator differences to analyze distributed errors.The decomposition represents operator differences and supports the subsequent error analysis.
  • Contributions: The resulting bounds are stated in a general setting without eigenfunction assumptions, alongside best learning rates for least squares regularization with a general kernel.The authors identify these rates as the best available in the literature for this general-kernel setting.

2. Main Results

The paper establishes expectation error bounds for distributed regularized least squares in RKHS and L2 metrics under general kernel settings, including sharp learning rates and minimax behavior under stated assumptions.

  • Framework: The analysis uses a compact positive kernel integral operator and effective dimension to characterize the RKHS complexity relative to the input distribution.The effective dimension is defined through Tr((L_K + λI)^−1L_K).
  • Assumptions: The error analysis assumes independently sampled data, compact metric inputs, and initially uniformly bounded outputs, with bounds expressed through approximation error.The output condition is |y| ≤ M almost surely.
  • Distributed learning: The distributed estimator partitions data across m machines, computes local regularized least-squares estimators, and averages them into a global estimator.The results cover arbitrary m subject to the stated partition-size and regularization restrictions.
  • Learning rates: Under the regression-function source condition fρ in the range of L_K^r, the analysis derives convergence rates for 0 < r ≤ 1, including the RKHS case r = 1/2.The source condition is stated using powers of the compact positive operator L_K.
  • Error bounds: The results provide expectation error bounds in both RKHS and L2 metrics, with L2 bounds directly related to generalization error under the kernel norm inequality.The RKHS bound also applies when generalization is measured under a mismatched L2 distribution.
  • Learning rates: The paper also gives sharp bounds for least squares regularization while relaxing uniform boundedness to a moment condition.The paper states that the resulting convergence rate is sharp in the relevant setting.
  • Learning rates: Distributed learning can attain minimax expectation rates when the number of partitions satisfies the stated restriction, while its optimal regularization parameter is independent of m.The analysis covers 1/2 < r ≤ 1 and removes the eigenfunction assumptions used in earlier analysis.

3. Comparisons and Discussion

The paper compares its distributed and single-machine regularized least-squares results with prior rates, emphasizing broader assumptions and sharper expectation bounds. It also identifies scope boundaries and directions for extending distributed learning theory.

  • Comparison with prior rates: The paper reports the best learning rates for regularized least squares in a general-kernel setting without eigenfunction assumptions.Its comparison includes prior results requiring eigenvalue conditions, moment or bounded-output assumptions, and, in some cases, projection onto [−M, M].
  • Comparison with prior rates: The analysis derives expectation learning rates by removing the logarithmic factor present in prior results for r = 1.It uses a novel second-order decomposition for differences of operator inverses.
  • Comparison with prior distributed results: The paper’s rates for distributed learning do not require the eigenfunction assumption needed in earlier matrix-analysis results.The cited comparison notes that the earlier assumption is difficult to verify for widely used kernels, including Gaussian kernels.
  • Distributed-versus-centralized behavior: The distributed bounds quantify the difference between the averaged distributed output and the whole-data regularized least-squares output.For r = 1, the sample-related error decreases as the number of local processors increases, while the regression approximation error increases.
  • Scope and future directions: The approach remains restricted to regularized least squares with Mercer kernels and leaves parameter selection, data partitioning, and distributed extensions to other algorithms for future work.The authors also identify reducing assumptions on the kernel and domain as an open direction.

4. Second Order Decomposition of Operator Differences and Norms

The paper develops an integral-operator analysis of empirical operators and introduces a second-order decomposition for inverse-operator differences. It combines this decomposition with effective-dimension and concentration estimates to control relevant operator norms.

  • Operator representations: The analysis represents estimator differences using empirical integral operators and differences of inverse operators.This representation is introduced to analyze f_D,λ − f_D,λ and related quantities.
  • Empirical integral operators: The empirical integral operator is formed from the input data and provides the sample-based counterpart to the population operator L_K.The construction is made on the RKHS, where the Mercer kernel yields finite-rank positive empirical operators.
  • Second-order decomposition: The central operator difference is A^-1 − B^-1, with A = L_K,D(x) + λI and B = L_K + λI.The decomposition compares regularized empirical and population operators through their inverses.
  • Second-order decomposition: A^-1 − B^-1 is expressed as a first-order term plus a second-order remainder containing two factors of B − A.The stated identity is B^-1{B − A}B^-1 + B^-1{B − A}A^-1{B − A}B^-1.
  • Norm estimates: Effective dimensions and probability estimates are used to bound operator norms involving regularized population and empirical operators.The bounds include confidence-dependent estimates and also control terms involving Δ′ and Δ_D after multiplication by (L_K + λI)^-1/2.

5. Deriving of Error Bounds for Least Squares Regularization Scheme

The error analysis applies the second-order operator decomposition to least squares regularization and separates the estimator error into terms controlled by probabilistic and operator-norm bounds. The resulting theorem and corollaries provide error estimates under stated moment, regularity, and parameter conditions.

  • Main error analysis: The main proof applies the second-order decomposition to derive error bounds for the least squares regularization scheme.The analysis combines the decomposition with operator estimates and the triangle inequality relating empirical, regularized, and target functions.
  • Main error analysis: Proposition 18 assumes E[y^2] < ∞ and condition (11), then establishes an error estimate for the regularized estimator.The proposition is used with the triangle inequality to prove the corresponding theorem.
  • Termwise bounds: The proof separates operator differences into terms and bounds them using unbiasedness, independence, Hölder's inequality, and operator estimates.The resulting estimates are combined to obtain the desired bound.
  • Corollaries: Corollary 7 specializes the general estimate using effective-dimension restrictions and the restriction (8) with m = 1.The proof substitutes these restrictions into the error bound (12).

6. Proof of Error Bounds for the Distributed Learning Algorithm

The distributed-learning proof controls the difference between subset-based and whole-data estimators by decomposing it into three terms. It establishes bounds in both the L2_ρX and H_K metrics, including settings with unequal subset sizes.

  • Distributed estimator error: The result allows different sizes for the data subsets {D_j}, extending the analysis beyond equal partitioning.This generality is stated for the error analysis in the L2_ρ metric.
  • Rates and corollaries: Theorem 20 assumes |y| ≤ M almost surely and supplies a bound used in the distributed-learning result.Subsequent corollaries derive convergence rates under additional conditions and choices of λ.
  • Distributed estimator error: The analysis treats the distributed estimator by expressing its error through three terms J1, J2, and J3.Each term is handled separately before the bounds are combined.
  • Termwise analysis: The first error component is analyzed using the second-order decomposition and unbiasedness of the associated random terms.Independence and conditional mean-zero properties support the treatment of the relevant summands.
  • Metric-specific bounds: The three termwise estimates combine to yield the desired error bound in the L2_ρX metric.The proof applies operator and probability estimates to the decomposed terms.
  • Metric-specific bounds: The corresponding H_K bound follows from the L2_ρX derivation after removing the leading L_K^1/2 factor and accounting for an additional λ-dependent factor.The proof then completes the theorem for the distributed algorithm.

Appendix

The appendix supplies concentration tools for Hilbert-space-valued random variables and operator-valued empirical estimates. It applies effective-dimension and Mercer-operator representations to establish the auxiliary inequalities used in the main proofs.

  • Concentration tools: The appendix introduces a probability inequality for bounded Hilbert-space-valued random variables.Lemma 21 provides the concentration tool used to estimate random operators and vector-valued quantities.
  • Operator concentration: The operator-valued random variable η1 is analyzed in the Hilbert-Schmidt space to control empirical approximations of L_K.The Hilbert-Schmidt space is equipped with its trace inner product and norm.
  • Operator concentration: Effective dimensions estimate norms involving η1 through the population and empirical integral operators.The analysis uses an orthonormal eigenfunction basis of L_K and the Mercer expansion.
  • Auxiliary bounds: The appendix derives the desired bounds for the operator-valued variables and their regularized versions.These include the bounds referenced in Parts (a), (b), and (c) of Lemma 16.
  • Vector-valued quantities: The variables η2 and η3 encode regularized kernel sections and regularized functions g(z)K_x in H_K.Their definitions support the vector-valued concentration estimates in Lemma 17.
Loading 1608.03339v2…