Source-linked AI summary
Sparsity in multiple kernel learning
Vladimir Koltchinskii, Ming Yuan
TL;DR
The paper addresses sparse multiple kernel learning when the kernel dictionary is large and the design distribution and component smoothness are unknown. It uses double penalization with data-driven regularization parameters and establishes oracle inequalities whose error adapts to sparsity and distribution-dependent complexity.
Problem
The problem is to learn a sparse target representation from a large kernel dictionary while accounting for unknown design-dependent smoothness and differing component complexities.
Method
The estimator uses empirical L2 penalties for sparsity, RKHS penalties for smoothness, and data-driven regularization parameters based on kernel complexity.
Results
The paper establishes oracle inequalities comparing excess risk with an additive oracle, with error depending on the oracle’s number of nonzero components.
Takeaways & Limitations
The framework is adaptive to unknown design distributions, component smoothness, and the sparsity of the target representation.
Takeaways & Limitations
The analysis assumes a bounded convex domain D and kernels satisfying supx∈S Kj(x,x) ≤ 1.
Abstract
from arXiv · showhide
The problem of multiple kernel learning based on penalized empirical risk minimization is discussed. The complexity penalty is determined jointly by the empirical $L_2$ norms and the reproducing kernel Hilbert space (RKHS) norms induced by the kernels with a data-driven choice of regularization parameters. The main focus is on the case when the total number of kernels is large, but only a relatively small number of them is needed to represent the target function, so that the problem is sparse. The goal is to establish oracle inequalities for the excess risk of the resulting prediction rule showing that the method is adaptive both to the unknown design distribution and to the sparsity of the problem.
1. Introduction.
The paper develops multiple kernel learning for sparse representations, combining empirical L2 and RKHS penalties with data-driven regularization to adapt to unknown design distributions and sparsity. It establishes oracle inequalities for excess risk and relates eigenvalue decay to minimax convergence rates.
- Learning in reproducing kernel Hilbert spaces: Kernel smoothness depends on the eigenvalue decay of the integral operator, which is determined jointly by the RKHS and the unknown design distribution Π.For eigenvalues λk ≍ k−2β with β > 1/2, the squared-risk rate is n−2β/(2β+1).
- Learning in reproducing kernel Hilbert spaces: For Sobolev RKHSs on a d-dimensional torus, the resulting rate is n−2α/(2α+d), matching the minimax convergence rate.The eigenvalues arise from the Fourier representation of the Sobolev kernel, with α > d/2.
- Sparse recovery via regularization: Multiple kernel learning seeks prediction rules by minimizing empirical risk while selecting among a potentially large dictionary of kernels.The framework targets settings where only a relatively small subset of kernels is needed to represent the target function.
- Sparse recovery via regularization: The double penalty combines empirical L2 norms to enforce sparsity with RKHS norms to enforce component smoothness.The regularization parameters are chosen data-dependently to adapt to unknown smoothness determined by distribution-dependent kernel eigenvalues.
- Sparse recovery via regularization: The regularization scales each component according to its one-component minimax rate and yields excess risk of order d n−2α/(2α+1), where d is the sparsity degree.For additive blocks with dimensions mj, the appropriate parameters differ across components and depend on mj.
- Adaptive choice of regularization parameters: The main theoretical result establishes oracle inequalities comparing the estimator’s excess risk with that of an additive oracle, with error depending on the oracle’s number of nonzero components.The proof uses empirical-process bounds and data-driven regularization parameters controlled by their population counterparts.
2. Oracle inequalities.
The paper establishes sparsity oracle inequalities for multiple kernel learning under boundedness, loss regularity, and dictionary-geometry conditions. The bounds adapt to component smoothness through data-dependent regularization and depend on the oracle’s sparsity, while also controlling component-wise estimation error.
- Assumptions: The analysis assumes a bounded convex parameter domain, uniformly bounded kernel diagonals, and losses of quadratic type with controlled derivatives.These conditions yield bounded components and Lipschitz behavior needed for the oracle inequalities.
- Dictionary geometry: The dictionary is characterized through dependence measures such as β2,b(J;Π), restricted isometry constants, Gram-matrix eigenvalues, and inter-subspace correlations.Small dependence measures correspond to weakly correlated or nearly orthogonal component spaces.
- Regularization: The estimator uses penalized empirical risk minimization with data-dependent regularization parameters ǫj = τˆǫj, allowing different kernels to receive penalties reflecting their smoothness properties.The parameters ˆǫj are linked to distribution-dependent RKHS characteristics and may differ across kernel machines.
- Oracle inequalities: Theorem 2 compares the estimator’s excess risk with an oracle’s risk, with an error term governed by oracle sparsity and dictionary geometry.The result applies with probability at least 1 − 3N^−A/2 and also bounds L2(Π) distances between estimated and oracle components under quadratic-type losses.
- Oracle inequalities: Theorem 3 yields excess-risk control essentially proportional to d(f)˘ǫ^2 and component-distance control proportional to d(f)˘ǫ.Here d(f) is the number of nonzero oracle components, so the estimator is approximately sparse.
- Sparse additive models: For sparse additive Sobolev models, the resulting rate essentially matches the minimax lower bound up to a constant and remains minimax optimal with adaptive regularization under nonuniform design.The cited sparse model has d active components with RKHS norm at most 1.
3. Preliminary bounds.
This section establishes high-probability comparisons between empirical and population L2 norms and between data-dependent regularization quantities. These preliminary results support the subsequent oracle inequalities.
- 3.1. Comparison of ∥·∥L2(Πn) and ∥·∥L2(Π).: Theorem 4 controls the discrepancy between empirical and population L2 norms for functions in a single RKHS.The comparison has an error term proportional to the RKHS norm.
- 3.2. Comparison of ˆǫ(K), ¯ǫ(K), ˘ǫ(K) and ˇǫ(K).: If eigenvalues decay polynomially as λk ≍ k^-2β with β > 1/2, then ˘ǫ(K) ≍ n^-β/(2β+1).This links the regularization scale to the eigenvalue decay of the integral operator.
- 3.2. Comparison of ˆǫ(K), ¯ǫ(K), ˘ǫ(K) and ˇǫ(K).: Theorem 6 compares empirical and population versions of the regularization quantity associated with each kernel under log N ≥ 2log log n.The comparison is obtained uniformly over the dictionary using high-probability bounds and a union bound.
- 3.2. Comparison of ˆǫ(K), ¯ǫ(K), ˘ǫ(K) and ˇǫ(K).: Theorem 7 provides a further comparison of the kernel-dependent quantities used in the regularization analysis.Its conclusion is combined with Theorems 4 and 6 across all N kernels.
- 3.2. Comparison of ˆǫ(K), ¯ǫ(K), ˘ǫ(K) and ˇǫ(K).: The preliminary comparisons hold simultaneously over the dictionary with probability at least 1 − N^-A/2 under additional constraints such as A ≥ 4 and N ≥ 3.The simultaneous statement follows from combining individual bounds and a union bound.
4. Proofs of the oracle inequalities.
This section proves the oracle inequalities by controlling empirical and population quantities, bounding the empirical process, and treating separately the main and degenerate cases. The resulting theorem holds uniformly over admissible oracle decompositions with high probability.
- Proof of the main oracle inequality.: Theorem 8 gives a uniform oracle bound for all admissible oracle decompositions when τ is at least a constant multiple of L∗.The statement uses data-dependent regularization parameters ǫj = τˆǫj.
- Consequences for Theorems 2 and 3.: The final probability bound is at least 1 − 3N^-A/2, with A ≥ 4 appearing in the definitions of the regularization quantities.Theorems 2 and 3 are then deduced from the technical inequality through comparisons between geometric quantities.
- Proof of the main oracle inequality.: The proof first replaces empirical regularization and L2 quantities with population counterparts on a high-probability event.This step relies on the preliminary comparison results for all kernels.
- Proof of the main oracle inequality.: The empirical process term is bounded using a technical lemma, after which the resulting estimate is combined with the earlier oracle bound.The argument uses the loss assumptions and constants chosen to satisfy the required inequalities.
- Exceptional case.: When the principal conditions fail, the proof shows that the oracle inequality becomes trivial because its right-hand side is sufficiently large while the left-hand side remains controlled.The estimator’s penalized empirical risk is compared with the value at f = 0.
5. Bounding the empirical process.
This section bounds the loss empirical process uniformly over localized function classes. It combines symmetrization, Rademacher contraction, concentration, discretization, and union bounds.
- Empirical-process control.: The empirical process is controlled by first applying symmetrization to the localized loss class.The loss is treated on function ranges where its Lipschitz constant is bounded by L∗.
- Empirical-process control.: Rademacher contraction transfers the bound from the loss class to the underlying function class.The same bounded Lipschitz constant is used in this reduction.
- Concentration bounds.: Talagrand concentration yields high-probability bounds for the localized Rademacher process and the empirical process.The argument applies concentration conditionally on the observed data and then combines the resulting events.
- Uniformization.: The proof discretizes localization parameters and extends the resulting inequalities to their full admissible range by monotonicity.A union bound controls the intersections over the discretized parameter values.
- Uniformization.: The resulting inequalities hold uniformly with probability at least 1 − 2N^-A/2 for the relevant localization parameters.The choice of t is proportional to A log N plus logarithmic constants.