Source-linked AI summary
Regularization in kernel learning
Shahar Mendelson, Joseph Neeman
TL;DR
The paper addresses whether RKHS regularization must grow quadratically with the RKHS norm, a dependence associated with standard L∞-based analyses. It develops isomorphic and localized complexity arguments that avoid those bounds, establishing substantially slower regularization growth and best-known error-rate dependence under mild kernel assumptions. The results require bounded outputs and eigenvalue and eigenfunction conditions, while practical constants remain uncomputed.
Problem
Standard RKHS error bounds relied on quadratic regularization in the RKHS norm, motivating the question of whether this growth is necessary.
Method
The paper combines isomorphic coordinate projections with localized complexity analysis over RKHS balls, avoiding the L∞-based bounds responsible for quadratic growth.
Results
Under mild kernel assumptions, the analysis establishes substantially slower regularization growth and the best known dependence on r and n.
Takeaways & Limitations
Regularized RKHS learning can use a penalty that grows more slowly than the standard quadratic dependence on the RKHS norm.
Takeaways & Limitations
The results require bounded outputs and eigenvalue and eigenfunction conditions, and the theorem leaves constants uncomputed, including quantities dependent on ∥Y∥∞.
Abstract
from arXiv · showhide
Under mild assumptions on the kernel, we obtain the best known error rates in a regularized learning scenario taking place in the corresponding reproducing kernel Hilbert space (RKHS). The main novelty in the analysis is a proof that one can use a regularization term that grows significantly slower than the standard quadratic growth in the RKHS norm.
1. Introduction.
The paper studies regularized learning in RKHSs and challenges the standard quadratic dependence on the RKHS norm. Its analysis uses isomorphic coordinate projections and avoids loose L∞-based bounds to obtain substantially slower regularization growth under kernel assumptions.
- Motivation: Regularized learning addresses overfitting by balancing approximation and sample error within a large function class.The regularization term selects an appropriate radius r for empirical minimization over scaled RKHS balls.
- Problem and novelty: Prior RKHS error bounds generally used a quadratic regularization term η_n∥f∥_H^2, while the paper targets a slower dependence on ∥f∥_H.The paper identifies improving the power of the RKHS norm as its main goal.
- Problem and novelty: L∞-based analysis produces quadratic growth because bounded kernels convert RKHS norms into uniform bounds and squared-loss Lipschitz factors.The paper attributes this dependence to an overly loose analysis rather than an intrinsic requirement of the learning problem.
- Method: The analysis extends isomorphic coordinate projections to regularized learning, with bounds whose dependence on the radius r determines the regularization term.Earlier kernel-class results did not address how the bounds scale with r, which is essential for choosing regularization.
- Results: Under mild kernel assumptions, the paper establishes improved regularization bounds and claims the best known dependence on r and n.The theorem assumes bounded outputs and eigenvalue-decay conditions, with high-probability guarantees for sufficiently large n.
- Method: Localized intersection-body complexity grows sublinearly in r because only an increasingly small number of directions influence the complexity.This localization supplies the mechanism for improving on the standard r^2 growth.
- Limitations: The analysis uses a weaker eigenfunction condition than uniform boundedness, though constants are not computed and may depend on unknown quantities such as ∥Y∥∞.The paper also notes that practical parameter selection and optimality are not fully addressed.
2. Preliminaries.
The preliminaries frame regularized learning as empirical minimization over an ordered hierarchy of function classes, controlled through isomorphic bounds. These bounds yield high-probability guarantees for regularized minimizers and expose the approximation–sample-error trade-off.
- Hierarchies: An ordered, parameterized hierarchy is a monotone family of subclasses whose union is the full class and whose risk-minimizer path is continuous.Each subclass has a unique risk minimizer, and the hierarchy satisfies closure and coverage properties.
- Isomorphic bounds: Isomorphic bounds control empirical and population losses uniformly over each hierarchy member with high probability.Theorem 2.5 assumes a radius- and confidence-dependent bound ρ_n(r,u) and transfers it to regularized learning.
- Regularized estimators: The resulting regularized estimator minimizes empirical loss plus a radius-dependent penalty determined by the isomorphic bound.The penalty can be increased at the cost of a correspondingly larger error bound.
- Error decomposition: The hierarchy formulation separates the approximation error A(r) from estimation error and yields a high-probability oracle-style bound.A(r) decreases as the hierarchy expands, while Corollary 2.7 combines this approximation term with the regularization guarantee.
3. Regularization in kernel classes.
This section applies the hierarchy and isomorphic framework to RKHS balls under eigenvalue-decay assumptions. The initial L∞-based analysis improves earlier estimates but retains quadratic dependence on the RKHS radius, while the resulting bound is explicit and high probability.
- RKHS hierarchy: RKHS balls form the hierarchy used to analyze regularized learning, with Fr=(r^-1)B_H in the paper’s parameterization.The RKHS is represented through an ℓ2 feature map, making balls in H correspond to Euclidean balls in parameter space.
- L∞ approach: The first RKHS approach uses L∞ bounds and produces a regularization term proportional to ∥f∥_H^2.The quadratic term arises from bounding the loss class through the RKHS norm.
- Result: The resulting rate improves earlier estimates, but the analysis still retains quadratic radius dependence and therefore motivates a smaller regularization parameter.The section explicitly identifies the quadratic term as an artifact to be removed by the subsequent approach.
- Isomorphic analysis: The isomorphic analysis scales the localized complexity with the RKHS radius and combines eigenvalue decay with model selection to obtain an explicit high-probability error bound.The hierarchy is taken as Fr=rB_2 in the ℓ2 representation, and the bound is applied through Corollary 2.7.
4. Toward a smaller regularization parameter.
The section explains why L∞-based analysis produces overly large quadratic radius dependence and develops a localized, geometric alternative. Under eigenfunction and eigenvalue assumptions, the resulting bounds have smaller radius dependence and motivate removing the quadratic regularization term.
- Goal: The main technical goal is to replace the r^2 term in the bound by a smaller power of the RKHS radius.The paper identifies this replacement as the main source of novelty.
- Localization: Localization restricts attention to excess-loss functions with small variance, whose corresponding parameter sets are intersections such as √xD∩T.This geometry can be substantially smaller than the full radius-r class.
- Geometric improvement: The L∞ approach yields a radius-quadratic term, whereas the localized argument identifies a contribution of order x rather than quadratic growth in r.The paper attributes the improvement to bypassing L∞-based bounds and analyzing localized intersection bodies.
- Assumptions: Uniformly bounded eigenfunctions are imposed as a technical assumption, although the authors state that a weaker condition may suffice.The authors explicitly note that they could not remove this assumption and that it is crucial to their analysis.
- Radius dependence: The intersection-body geometry produces sublinear radius dependence because scaling enlarges only some directions, with the number of growing directions decreasing quickly.The resulting fixed point can scale with a smaller power of r and, in the worst case described, linearly in r.
- Implication: The improved high-probability bounds suggest that quadratic RKHS-norm regularization over-regularizes when the sample size is large.The paper then states that the quadratic term can be removed entirely in the following section.
5. Removing the r2 term.
The analysis removes the large-radius r^2/n term from the regularization functional on the relevant minimizer set, yielding a slower-growing penalty while preserving the learning guarantee. This requires decomposing the RKHS and showing that minimizers lie in a controlled subset.
- Removing the r2 term: The regularization functional has leading term Θ^(2/(1+p)) and an r^2/n term that is dominant only at very large r.The large-radius term can be removed because it does not affect the minimization problem under study.
- Controlling minimizers: Minimizers are confined to functions satisfying E(f−Y)^2≤2 and Ef^2≤9, allowing the analysis to focus on the subset H1 containing {f:Ef^2≤9}.This confinement follows by comparing the objective at a minimizer with its value at f=0.
- Controlling minimizers: The hierarchy H̄r=H1∩(r−1)BH supports an isomorphic bound whose dominant regularization term is Θ^(2/(1+p)).The hierarchy is ordered and parameterized by r(f)=∥f∥H+1.
- Excluding H2: Functions outside H1 cannot minimize the objective with high probability because empirical squared loss is bounded below on the complementary set H2.The shell decomposition and Lemma 5.4 establish this exclusion over the stated range of u.
- Result: The resulting error rate is better by a polynomial factor than the previous rate n^(−2σ/(p+1)) whenever σ<1/2.This comparison is the stated consequence of removing the r^2 term.
APPENDIX: PROOFS
The appendix proves the regularized-learning result by extending bounds from a discrete sequence of radii to all radii, then applying the general hierarchy theorem. Continuity and induction control the radius construction and uniformity of the bound.
- Proof strategy: The proof starts from Bartlett’s theorem and applies it to an ordered, parameterized hierarchy with a positive continuous increasing control function.The general result is stated as Theorem A.1 for classes Fr indexed by r.
- Radius discretization: A sequence of radii ri is chosen with r1=1 and ri→∞, while confidence parameters ui grow logarithmically with i.A union bound then gives simultaneous control over every index i.
- Uniform extension: Bounds for adjacent radii are combined to extend the almost-isomorphic condition from the discrete sequence to every r≥1.For r∈[rj−1,rj], the proof derives inequalities in both directions before selecting the largest admissible next radius.
- Conclusion: Induction establishes the required radius and confidence relations, after which Theorem A.1 yields the final uniform statement with probability at least 1−e^(−u).Continuity ensures that the supremum defining the largest admissible radius is attained.