Source-linked AI summary
L2 Regularization for Learning Kernels
Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh
TL;DR
Kernel choice is usually specified by the user, so the paper studies learning a kernel from non-negative combinations of base kernels using L2 regularization in regression. It derives and computes the L2-regularized KRR solution, analyzes its stability, and finds that L2 avoids degradation and improves performance with many kernels.
Problem
Kernel selection is typically left to the user, motivating data-driven kernel learning from a family of base-kernel combinations.
Method
The paper analyzes kernel ridge regression with L2-regularized non-negative combinations of base kernels, deriving the optimizer, an iterative algorithm, and stability-based learning bounds.
Results
L2 regularization never degrades performance and achieves significant improvements with a large number of kernels, while L1 can degrade performance at larger scale.
Takeaways & Limitations
For orthogonal kernels, the generalization bound adds only O(p/m) to the standard KRR stability bound, supporting the use of many kernels.
Takeaways & Limitations
The stated bound is proven for orthogonal base kernels, although the authors expect a similar weaker bound in the general case.
Abstract
from arXiv · showhide
The choice of the kernel is critical to the success of many learning algorithms but it is typically left to the user. Instead, the training data can be used to learn the kernel by selecting it out of a given family, such as that of non-negative linear combinations of p base kernels, constrained by a trace or L1 regularization. This paper studies the problem of learning kernels with the same family of kernels but with an L2 regularization instead, and for regression problems. We analyze the problem of learning kernels with ridge regression. We derive the form of the solution of the optimization problem and give an efficient iterative algorithm for computing that solution. We present a novel theoretical analysis of the problem based on stability and give learning bounds for orthogonal kernels that contain only an additive term O(pp/m) when compared to the standard kernel ridge regression stability bound. We also report the results of experiments indicating that L1 regularization can lead to modest improvements for a small number of kernels, but to performance degradations in larger-scale cases. In contrast, L2 regularization never degrades performance and in fact achieves significant improvements with a large number of kernels.
1 Introduction
The paper addresses kernel selection by studying L2-regularized learning of kernel combinations for regression with kernel ridge regression. It combines an optimization solution, stability-based bounds, and experiments showing advantages of L2 regularization as the number of kernels grows.
- Kernel choice is critical but is typically left to the user, motivating data-driven selection from a specified kernel family.
- The study uses non-negative combinations of fixed kernels with L2 regularization in kernel ridge regression for regression problems.
- The paper derives novel learning bounds for L2-regularized KRR whose complexity term depends on m and p through O(1/√p/m).
- For orthogonal kernels, the bound adds O(p/m) to the standard KRR stability bound without an additional logarithmic factor.
- The paper reports an efficient iterative algorithm and experiments comparing L1- and L2-regularized kernel learning.
2 Optimization Problem
The optimization problem restricts kernels to non-negative combinations of fixed positive definite base kernels within an L2 ball around a reference combination. The resulting kernel-learning KRR objective is convex in the combination weights.
- The training sample contains m labeled examples, and KRR uses the label vector y together with feature mappings Φ(x).
- The kernel family consists of non-negative combinations of p fixed positive definite kernels, constrained by an L2 distance from μ0.
- The regularization set uses μ ≥ 0 and ∥μ − μ0∥2 ≤ Λ2, where μ0 is fixed and Λ controls the constraint.
- The kernel-learning problem is formulated from the dual KRR objective using the Gram matrices Kk of the base kernels.
- The optimization is convex in μ because its objective is linear in μ inside a pointwise maximum over α, while M is convex.
3 Form of the Solution
The paper gives an explicit optimizer for the L2-constrained kernel weights. The solution depends on the base-kernel quadratic responses evaluated at the KRR dual coefficients and is compared with standard KRR using the reference kernel.
- Theorem 1 gives the solution as μ = μ0 + Λv.
- The minimax reformulation and KKT conditions show that the nonnegativity multipliers satisfy β = 0 at the optimum.
- The vector v contains the base-kernel responses v_k = α⊤K_kα, which determine how the learned weights move from μ0.
- The learned solution is evaluated relative to standard KRR with the μ0-kernel K0.
- For fixed K, the KRR dual coefficients are α = (K + λI)−1y, with λ = m/C.
4 Stability analysis
The stability analysis bounds how LKRR changes when one training point is replaced, separating sample-induced and kernel-induced variation. Under orthogonal-base-kernel assumptions, the resulting stability and generalization bounds are favorable, while the analysis also yields a tighter bound for standard KRR.
- Stability setup: The analysis compares hypotheses from samples differing in one point and bounds their prediction change to establish LKRR stability.The stability coefficient controls the squared-loss difference for any labeled test point.
- Analysis contribution: The proofs use the explicit solution for α and µ to obtain tighter stability bounds for LKRR and standard KRR.The analysis is technically more involved because a sample change affects both the data and the learned positive-definite-symmetric kernel.
- Stability decomposition: The prediction difference is decomposed into sample variation for a fixed kernel and kernel variation for a fixed sample.These terms require separate bounds because changing the training sample also changes the learned kernel.
- Sample variation: Theorem 2 bounds sample-induced prediction variation using the smallest eigenvalue of the feature covariance matrix plus regularization.The resulting bound is identified as a stability bound for standard KRR and is tighter than an earlier convexity-based bound.
- Kernel variation: The kernel-variation analysis uses bounds for the base-kernel coefficients and assumes orthogonal base kernels for one central proposition.Orthogonality means the base kernels admit feature mappings into the same Hilbert space with the required pairwise orthogonality property; the assumption covers the paper’s n-gram experiments.
- Generalization: Theorem 3 converts LKRR’s uniform stability into a high-probability generalization bound under a bounded prediction-error assumption.The conversion uses standard stability results or McDiarmid’s inequality.
5 Experimental Results
Experiments compare L2 kernel learning with evenly weighted and L1-regularized alternatives across small and large kernel-learning settings. L2 performs especially well when many orthogonal base kernels are used, while L1 can degrade performance.
- UCI datasets: The experiments validate the iterative L2 implementation on UCI datasets and compare it with single-kernel, evenly weighted, and L1-regularized alternatives.The evaluation includes RMSE and misclassification rate for classification datasets.
- Sequence-based datasets: The large-scale experiments use thousands of sequence kernels built from frequently occurring bigrams, with parameters selected by 10-fold cross-validation.The Reuters ACQ task uses 2,000 training points subsampled from 9,603 training examples, while sentiment datasets contain 2,000 reviews per domain.
- Sequence-based datasets: The figure reports RMSE using absolute error in the upper plots and error normalized by baseline error in the lower plots, with error bars showing ±1 standard deviation.The datasets are Reuters and sentiment-analysis tasks involving kitchen, DVDs, and electronics.
- UCI datasets: On UCI datasets, kernel-learning methods never perform worse than selecting the best single kernel, but they also do not significantly improve over it.All differences are within one standard deviation; absolute misclassification rates are 0.03, 0.08, 0.16, and 0.17 for breast, ionosphere, sonar, and heart.
- Sequence-based datasets: For large-scale sequence-kernel learning, L2 regularization significantly outperforms the evenly weighted baseline, whereas L1 regularization can harm performance.The reported comparisons cover Reuters ACQ and sentiment-analysis datasets including books, DVDs, and kitchen appliances.
6 Conclusion
The conclusion combines an L2-regularized ridge-regression analysis, an efficient iterative algorithm, stability-based bounds, and empirical evidence favoring L2 for many orthogonal kernels.
- 6 Conclusion: The paper analyzes learning kernels with ridge regression under L2 regularization and provides an efficient iterative algorithm.The conclusion identifies stability as the basis of the analysis.
- 6 Conclusion: For relatively many orthogonal kernels, the generalization bound suggests that estimation error is not significantly increased.The favorable theoretical result is corroborated by some empirical findings.
- 6 Conclusion: The authors do not expect similar uniform-stability guarantees for L1 regularization.The stated reason is that L1 typically does not ensure the same uniform stability guarantees.
A Expression of ∆µk
This appendix section introduces the relationship between changes in µ_k and changes in v_k for two samples.
- A Expression of ∆µ_k: Lemma 1 states that ∆µ_k can be expressed in terms of ∆v_k for any samples S and S′.The following proof derives the expression from the definition of µ_k.
- A Expression of ∆µ_k: Substituting the identity involving ∥v∥ + ∥v′∥ into the preceding relation yields the lemma.The passage identifies this substitution as the final proof step.
B Proof of Proposition 1
The proof bounds the terms in the stability analysis by decomposing V1 and applying Cauchy–Schwarz-based inequalities to its components.
- B Proof of Proposition 1: The proof expands the terms ∆K v_k appearing in V1 and decomposes V1 into V11 and V12.The two components are bounded separately, with V11 handled similarly to V12.
- B Proof of Proposition 1: V12 is bounded under the assumption that ∥v′∥ ≥ ∥v∥, without loss of generality.The bound uses the explicit expression for V1 and the representation K_k = Φ^⊤.
- B Proof of Proposition 1: Cauchy–Schwarz inequalities simplify and bound the sums contributing to V12.The proof applies the inequality repeatedly to control the relevant terms.
- B Proof of Proposition 1: Applying the same strategy to V11 produces a bound of the form ∥V11∥ ≤ 2Λ√… .The supplied passage gives the beginning of the resulting bound but not its complete expression.
C Proof of Proposition 2
The proof bounds V2 by decomposing it into terms involving feature-vector norms, weight-vector differences, and kernel-weight differences. Cauchy–Schwarz inequalities and orthogonality assumptions provide the needed bounds.
- V2 is related to the difference ∆Sw between the weight vectors h and h′, whose bound follows from Theorem 2.The proof’s stated main idea is to bound V2 in terms of ∆Sw.
- The proof rewrites V2 using vk = ∥wk∥2, where wk = Φk(S)α, and then bounds the resulting sums separately.This representation is introduced in connection with equation (12).
- The first factor is controlled by repeated Cauchy–Schwarz applications, assuming without loss of generality that ∥v∥≤∥v′∥.The calculation bounds F1 by a constant, with intermediate steps omitted.
- The second sum is bounded using inequalities involving ∥v∥ and ∥v′∥, yielding a bound on F2 proportional to ∥v∥1/2+∥v′∥1/2.The derivation also uses Cauchy–Schwarz inequalities and omits intermediate steps.
- Under orthogonality of the feature vectors wk, the proof invokes the corresponding norm simplification; kernel-feature orthogonality is also identified as a sufficient condition.The stated condition is Φk(xi)⊤Φk′(xi) = 0 for k ≠ k′ and i = 1, . . . , m.