PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-parametric Stochastic Approximation with Large Step sizes

Aymeric Dieuleveut, Francis Bach

arXiv:1408.0361v3math.ST

TL;DR

The paper addresses random-design least-squares learning in an RKHS when the optimal predictor may lie outside the space. It analyzes averaged unregularized LMS with suitable step-sizes and shows optimal rates across several smoothness regimes.

  • Problem

    Regularized empirical-risk methods require choosing a regularization parameter and approximately solving a convex optimization problem, while RKHS regression may target a function outside the RKHS.

  • Method

    The paper studies a one-pass stochastic-approximation algorithm using averaged unregularized LMS with step-sizes selected according to the horizon and spectral assumptions.

  • Results

    The method attains optimal convergence rates in several smoothness regimes, including regimes characterized by prediction-function and RKHS spectral behavior.

  • Takeaways & Limitations

    Sufficiently large step-sizes with averaging provide optimal-rate guarantees for non-parametric RKHS regression in the analyzed regimes.

  • Takeaways & Limitations

    The algorithm has O(n^2) running-time complexity after n steps when kernel evaluations are O(1), and some rates remain suboptimal in specified regimes.

Abstract

from arXiv · show

We consider the random-design least-squares regression problem within the reproducing kernel Hilbert space (RKHS) framework. Given a stream of independent and identically distributed input/output data, we aim to learn a regression function within an RKHS $\mathcal{H}$, even if the optimal predictor (i.e., the conditional expectation) is not in $\mathcal{H}$. In a stochastic approximation framework where the estimator is updated after each observation, we show that the averaged unregularized least-mean-square algorithm (a form of stochastic gradient), given a sufficient large step-size, attains optimal rates of convergence for a variety of regimes for the smoothnesses of the optimal prediction function and the functions in $\mathcal{H}$.

1. Introduction.

The paper studies stochastic approximation for random-design least-squares regression in RKHSs, targeting settings where regularization and optimization must be handled jointly. It shows that averaged LMS with suitably large step-sizes achieves optimal convergence rates in broad finite- and infinite-dimensional regimes.

  • Problem and framework: The framework uses one pass through observations, treating stochastic step-sizes as regularization parameters and avoiding overfitting through early stopping.This jointly addresses choosing regularization and approximately solving empirical-risk problems.
  • Step-size motivation: Constant or longer step-sizes with averaging can improve convergence in Hilbert-space settings required for non-parametric regression.Longer step-sizes are useful for ill-conditioned problems, although conventional decreasing step-sizes may have worse rates there.
  • Contributions: The results cover both finite-horizon and online settings, with bounds for the last iterate in the former and each iterate asymptotically in the latter.The finite-horizon step-size may depend on the known sample count.
  • Contributions: The analysis derives improved convergence rates for averaged LMS and extends finite-dimensional stochastic-approximation results to infinite-dimensional RKHS settings.The problem had previously been stated as open.
  • Evaluation: The paper compares its rates with prior work and evaluates the approach using synthetic spline-smoothing simulations.Complete proofs are provided in appendices.

2. Learning with positive-definite kernels.

The paper formulates RKHS regression through prediction error, covariance operators, and spectral decompositions. Its general assumptions accommodate non-attainment of the RKHS optimum, relaxed topology, and distinct regularity of the prediction function and RKHS.

  • Learning objective: The target regression function is the conditional expectation, while learning minimizes mean squared prediction error over an RKHS that may not contain that function.The RKHS projection gH characterizes the best achievable prediction in the space, even when the minimum is not attained.
  • Learning objective: Performance is measured in L2ρX prediction distance, allowing the analysis to avoid assuming gρ belongs to H or that H is dense in L2ρX.The paper does not generally claim convergence in stricter norms.
  • Learning objective: The loss is non-coercive because the covariance operator has positive eigenvalues decreasing to zero, so RKHS-norm convergence may fail and estimator norms can diverge when gρ is outside H.This spectral degeneracy is central to the minimization problem.
  • Covariance and spectrum: Under basic assumptions, the extended covariance operator is bounded, self-adjoint, positive, trace-class, and admits an eigenbasis with summable positive eigenvalues.The covariance operator and its spectrum characterize estimator convergence rates.
  • Covariance and spectrum: The covariance operator on H has an eigen-system and Hilbertian basis, while powers of the extended operator quantify regularity of the prediction function.The Mercer-kernel setting also provides an isometric relationship between the spectral space and H.
  • Assumptions: The assumptions are relaxed beyond compact topological spaces and continuous kernels while preserving the main convergence framework.The generalized result identifies the relevant supplements through an isometry between S and p(H).
  • Assumptions: The parameters δ and α separately describe the prediction function’s coordinate decay and the RKHS’s eigenvalue decay.This separation supports interpreting regularity of the target independently from the chosen RKHS.

3. Stochastic approximation in Hilbert spaces.

The paper analyzes averaged stochastic approximation in RKHS regression, showing how step-size choices control bias, variance, and convergence rates in finite-horizon and online settings.

  • Setup: The algorithm estimates the best function in H from i.i.d. data by minimizing mean-squared prediction error, even when the regression function need not belong to H.The framework uses a single-pass stochastic approximation procedure rather than requiring repeated optimization over the data.
  • Practical considerations: The method makes one pass through the data and computes only the new coefficient at each step, but its full-kernel implementation costs O(n^2) after n steps.Subset expansions can reduce complexity to linear overall time, at the expense of the sharp generalization errors established here.
  • Main results: Constant step-sizes with averaging can match the performance of the best estimator in H, under the paper’s assumptions and suitable boundedness conditions.Theorem 1 establishes this qualitative convergence result, while later corollaries characterize its rates.
  • Main results: The error decomposes into variance and bias: larger steps increase variance from noise but decrease bias from the initial estimate.This trade-off motivates choosing the step-size as a regularization-like parameter.
  • Finite horizon: The finite-horizon optimal rate scales as n^[-2α min{r,1}/(2α min{r,1}+1)], with an optimized constant step-size Γ(n) under the stated regimes.For 0 < r < (α−1)/(2α), a constant step-size γ0 is used; other regimes use n-dependent choices.
  • Online setting: Optimality regions depend on α and r: finite-horizon results cover r < 1, whereas online averaging shrinks the region to r < (2α−1)/(2α).The online restriction arises because constant averaging gives no further variance improvement once the decreasing step-size exponent exceeds 1/2.

4. Links with existing results.

The paper connects averaged stochastic-gradient results to finite-dimensional and RKHS regression, showing that larger step-sizes yield improved or optimal rates under spectral-decay and smoothness assumptions.

  • Averaged stochastic gradient descent previously achieved O(1/n) in finite-dimensional least-squares under comparable assumptions.
  • The analysis recovers finite-dimensional results from its more general theorem, with comparable constants and learning rates proportional to nThe supplied passage truncates the rate expression after n.
  • The estimator adapts to covariance spectral decay and optimal-prediction-function smoothness by selecting step-sizes accordingly.
  • Under the stated eigenvalue and smoothness assumptions, the method attains minimax-optimal rates in specified finite-horizon and online regions.The finite-horizon region is α−1/(2α) < r < 1; the online region is α−1/(2α) < r < (2α−1)/(2α).
  • Compared with related methods, the rates improve from n−2r/(2r+1) to n−2αr/(2αr+1) when α > 1.
  • The method saturates for r > 1, while a non-averaged comparison framework does not; non-uniform averaging is proposed as a possible remedy.

5. Experiments on artificial data.

Experiments use smoothing-spline RKHS models to test predicted rates and learning-rate choices across optimality regimes, comparing the proposed algorithm with three alternatives.

  • 5.1. Model: For smoothing splines, the covariance eigenvalues have multiplicity two and satisfy λi = (2πi)−2m.
  • 5.4. Comparison: The comparison evaluates the proposed method against Ying and Pontil, Tarrès and Yao, and Zhang using their prescribed parameter choices.
  • 5.2. Experimental set-up: The experiments use four parameter choices spanning the different optimality regions and always adopt the finite-horizon setting.
  • 5.3. Optimal learning rate: The best finite-horizon learning rate is estimated by testing many constant rates and averaging prediction error over 30 independent samples for each horizon.
  • 5.4. Comparison: The observed rates approximately match predictions in most cases, and the proposed rates improve on existing work.

6. Conclusion.

The conclusion presents averaged unregularized stochastic-gradient analysis as delivering optimal rates in several kernel and smoothness regimes, while identifying probabilistic, averaging, loss-function, and computational extensions.

  • The current stochastic-approximation procedures have quadratic running-time complexity in the number of samples n.

34 Appendices

The appendices formalize the function-space setting, separability assumptions, canonical projection, and the approximation interpretation of the RKHS regression problem.

  • The analysis works with square-integrable functions in L2 under a separability assumption.
  • The canonical projection maps RKHS functions into L2, allowing H and its image p(H) to be identified under stated assumptions.
  • The regression minimization problem is formulated as an approximation problem in L2.

A.2. Isomorphism.

The section establishes an isomorphism between the relevant subspaces of L2 and the RKHS projection through T^1/2, while characterizing null spaces, eigensystems, and density.

  • Best approximation: The best approximation gH is the unique minimizer of prediction error over the closed convex space p(H).It is the orthogonal projection of the regression function onto p(H).
  • Operator structure: T is a self-adjoint positive operator on L2 whose image lies in H, and its eigenbasis also describes the covariance structure.The corresponding covariance operator may be non-injective, with null spaces handled explicitly.
  • Isomorphism: T^1/2 maps the orthogonal complement of Ker(T) isometrically and bijectively onto p(H).This isomorphism is the central relationship between the L2 and RKHS decompositions.
  • Range and density: For every r > 0, powers T^r have the same effective range S, while p(H) is dense in L2 exactly when T is injective.For r ≥ 1/2, the relevant powers map into H.

A.3. Mercer theorem generalized.

The section generalizes Mercer’s decomposition without topological assumptions and states the moment conditions used for the convergence analysis.

  • Generalized Mercer theorem: The kernel admits an absolutely convergent decomposition under the stated RKHS assumptions, without additional topological assumptions on X.The resulting space S is itself an RKHS, and its optimization problem is equivalent to the one in H.
  • Moment assumptions: The analysis permits a fourth-moment formulation controlling E[K(X,X)f(X)^2] by R^2E[f(X)^2], rather than requiring an almost-sure kernel bound.This condition is paired with the covariance-noise bound E[Ξ ⊗ Ξ] ≼ σ^2Σ.
  • Convergence results: The main convergence results are Theorems 2 and 3 for the finite-horizon and online settings, with corollaries obtained by optimizing the step-size parameter γ.These theorems provide the section’s link from the operator framework to algorithmic rates.

B. Sketch of the proofs.

The proof decomposes stochastic LMS error into initialization and noise contributions, then bounds each through deterministic semi-stochastic recursions in finite-horizon and online settings.

  • Online proof: The same proof strategy is applied to the online setting, producing a similar decomposition and convergence analysis.The paper presents the finite-horizon and online arguments as closely related.
  • Finite-horizon proof: The estimator error follows a stochastic recursion combining a random covariance update with a residual-noise term.The residual is defined as Ξn = (yn − gH(xn))Kxn and has zero mean.
  • Finite-horizon proof: The recursion is split into initialization and noise components to isolate the effects of starting conditions and stochastic residuals.The total error is then bounded by combining these components with Minkowski’s inequality.
  • Finite-horizon proof: Replacing Kxn ⊗ Kxn by its expectation T yields deterministic semi-stochastic recursions used to control the residual terms.This comparison supports separate bounds for bias and variance contributions.
  • Assumptions and setup: The analysis is developed under separable-RKHS, finite-moment, and square-integrability assumptions, with stronger kernel bounds implying bounded RKHS functions.The framework also acknowledges possible non-identification of distinct RKHS functions in L2.

I.1. Properties of the minimization problem.

The minimization problem has a unique regression solution in L2 and a unique RKHS-projection solution, while covariance operators admit compact spectral decompositions linking the two spaces.

  • Minimization problem: The prediction-error minimizer over L2 is the regression function gρ, the conditional expectation of Y given X.The minimizer over p(H) is its unique orthogonal projection gH.
  • Covariance operator: The covariance operator Σ is well defined, continuous, self-adjoint, and satisfies ⟨f, Σf⟩K = ∥f∥L2ρX^2.Its kernel corresponds to functions that vanish almost everywhere under ρX.
  • Extended operator: The extended operator T is continuous, positive, self-adjoint, and has image contained in p(H).Under the assumptions, T is trace class and therefore Hilbert-Schmidt.
  • Spectral decomposition: T has an orthonormal eigenbasis on the orthogonal complement of its null space, with positive summable eigenvalues.This spectral structure supports the decompositions used throughout the analysis.
  • Space relationship: The subspace p(H) equals the orthogonal complement of Ker(T), and T^1/2 provides the corresponding isometric isomorphism between the decomposed spaces.The construction identifies the effective RKHS component while retaining possible null spaces.
  • Scope boundary: The framework does not establish surjectivity of T^1/2 onto H without stronger assumptions, though surjectivity onto p(H) is proved.Thus the isomorphism is stated for the projected space rather than necessarily the full RKHS.

I.4. Kernel decomposition.

The paper works with an RKHS-related subspace of L2ρX, establishing its kernel representation and equivalence to the original optimization problem almost surely.

  • Kernel representation: The subspace S is itself an RKHS with kernel KS defined through the positive-eigenvalue decomposition.The construction uses the Hilbertian eigenbasis of the covariance operator and retains eigenvalues λk > 0.
  • Optimization equivalence: Optimization problems in S and H have equivalent solutions almost surely.The equivalence is stated for the regression optimization under the paper’s identification of functions through L2ρX.
  • Function-space issues: Mild assumptions require treating H through subspaces of L2ρX rather than identifying all RKHS functions directly.A function may have zero L2ρX norm while having nonzero RKHS norm, especially when ρ’s support is not X.
  • Stronger assumptions: Under compactness, continuity, and supp(ρ)=X, the relevant map is injective and therefore bijective.These stronger assumptions resolve the support and null-function problems described for general settings.
  • Algorithmic recursion: The algorithm’s recursion can be written as gn − gH = (I − γ Kxn ⊗ Kxn)(gn−1 − gH) + γΞn.Here Ξn represents the observation noise relative to gH, and the covariance operator satisfies Σ = E(Kx ⊗ Kx).

4. Var

The variance analysis separates noise from initialization, replaces random kernel operators by their expectation in a semi-stochastic recursion, and derives finite-horizon bounds under covariance and noise assumptions.

  • Variance trade-off: The variance term increases with the step size, while the initial-condition term decreases, creating a step-size trade-off.The paper chooses γ to balance these competing contributions.
  • Semi-stochastic analysis: Proposition 24 bounds the finite-horizon semi-stochastic recursion ηn = (I − γnΣ)ηn−1 + γnΞn under assumptions A1-6.The semi-stochastic recursion replaces the sampled operator with the covariance operator Σ.
  • Stochastic extension: The complete stochastic result extends the semi-stochastic bound to the true stochastic recursion.Theorem 2 is presented as this extension, with the random operators Kxn ⊗ Kxn restored.
  • Error decomposition: The proof decomposes error into noise and initial-condition components, then bounds each component using Minkowski’s inequality and stochastic-recursion lemmas.The finite-horizon proof uses a constant step size that may depend on the total sample size n.

II.3.4. Initial conditions.

The finite-horizon proof isolates the effect of initial conditions, bounds it through a semi-stochastic recursion, and combines it with the noise contribution to obtain the theorem’s bound.

  • Initial-condition bound: The proof uses a semi-stochastic recursion for the initial-condition term and applies triangular inequalities to control residual contributions.The target is an upper bound comparable to the bias term.
  • Conclusion: The finite-horizon theorem follows by summing the initial-condition and noise bounds.The resulting cases distinguish r < 1 from r > 1.
  • Step-size choice: The complete bound assumes a constant step size γ = Γ(n) over the n observations and requires γR^2 ⩽ 1/4 after simplification.The parameter choice is then made to balance the dominant terms.

II.4.1. A Lemma on stochastic recursions

The online analysis extends the stochastic-recursion argument to decreasing step sizes, deriving asymptotic bounds while treating a distinct difficulty when the smoothness parameter satisfies r ⩾ 1/2.

  • Online recursion: The online recursion uses a decreasing sequence (γn) and requires γnR^2 ⩽ 1 at every iteration.The recursion retains the sampled operators Kxn ⊗ Kxn and martingale-noise conditions.
  • Proof strategy: The online proof follows the finite-horizon decomposition but reports asymptotic results because decreasing step sizes introduce more complicated constants.It separately analyzes noise and initial-condition effects.
  • Conclusion: The online theorem is obtained by combining the asymptotic initial-condition and noise bounds with the bias and variance lemmas.The paper states that corollaries follow directly from Theorem 3.
  • High-smoothness case: For r ⩾ 1/2, the proof controls the noiseless recursion through an explicit expansion of ||Σ^1/2η̄n||^2.The expansion uses products of sampled operators and matrix-operator bounds.
  • Operator bound: γP ≼ (γ^-1 + R^2γ^1/αn^1/α tr(Σ^1/α))Σ^-1 provides the operator bound used in the r ∈ [1/2, 1] analysis.The resulting estimate includes the factor n^2−2r||Σ^-rη0||^2.
Loading 1408.0361v3…