An L1 Representer Theorem for Multiple-Kernel Regression

Shayan Aziznejad, Michael UnserarXiv 2018 · arXiv

Abstract

Traditional supervised learning often relies on Reproducing Kernel Hilbert Space (RKHS) theory, which typically results in models where the number of kernels scales linearly with the number of data points and kernel centers are fixed at training locations. This paper introduces a novel theoretical framework for multiple-kernel regression using the generalized total-variation (gTV) norm within a Banach-space setting. By extending the Fisher-Jerome theorem to vector-valued functions, the authors prove a new "Representer Theorem" (Theorem 8). This theorem demonstrates that optimal solutions are naturally sparse expansions with adaptive kernel centers, providing a rigorous continuous-domain foundation for sparse optimization techniques like the generalized LASSO.

Introduction

In the field of supervised learning, the objective is to recover an unknown function from a finite set of noisy measurements. For decades, the Reproducing Kernel Hilbert Space (RKHS) framework has served as the mathematical backbone for this task. RKHS methods utilize quadratic regularization to ensure smoothness, leading to the well-known representer theorem where the solution is a linear combination of kernels centered at the training data points.

However, this classical approach has significant limitations. The resulting models are often redundant, as the number of kernels used is tied directly to the number of samples. Furthermore, the kernels are "stuck" at the sample locations, offering no flexibility in positioning. While researchers have historically applied $\ell_1$-type penalties (such as LASSO) to enforce sparsity, these have often been treated as discrete approximations rather than being derived from a continuous-domain principle. This paper addresses these gaps by proposing a Banach-space framework that naturally yields sparse, adaptive solutions.

The Shift to Banach Spaces and gTV Regularization

The authors depart from the standard Hilbert space setting, which is characterized by its inner-product structure and quadratic norms, in favor of a more flexible Banach-space framework. The core of this transition is the use of the generalized total-variation (gTV) norm as a regularizer.

Unlike the squared-norm regularizers used in RKHS, the gTV norm is specifically designed to promote sparsity in the continuous domain. To handle complex scenarios such as multi-task learning, the authors extend the existing scalar theory of gTV to vector-valued functions. This extension requires a generalization of the Fisher-Jerome theorem, a powerful mathematical tool that identifies the "extremal points" of optimization problems as sparse Dirac impulses in a transform domain. This theoretical heavy lifting allows the authors to characterize the structure of optimal solutions in a way that was previously impossible in the RKHS setting.

The L1 Representer Theorem

The primary contribution of the paper is Theorem 8, which establishes the existence and form of the solution for multiple-kernel regression under gTV regularization. The theorem provides several critical insights:

  1. Existence and Form: A solution always exists and takes the form of a finite expansion: $f(x) = \sum a_{n,j} k_n(x - z_{n,j})$.
  2. Adaptive Kernel Centers: Unlike traditional methods where kernel centers are fixed at data points $(x_m)$, this framework treats the centers $(z_{n,j})$ as adaptive parameters. The optimization process can move these centers to find the most efficient representation of the underlying data.
  3. Inherent Sparsity: The theorem proves that the total number of active kernels in the optimal solution is at most the number of data samples ($N \le M$). This holds true regardless of how many different types of kernels are available in the dictionary, effectively preventing redundancy.
  4. Natural L1 Penalty: The regularization term in the optimization problem is shown to be exactly the $\ell_1$ norm of the coefficients, emerging naturally from the properties of the gTV norm rather than being added as an external constraint.

Kernel Admissibility and Properties

A notable distinction of this framework is its requirement for kernel properties. In RKHS theory, kernels must be positive-definite. In the gTV framework, kernels must be stationary (shift-invariant) but do not necessarily need to be positive-definite. This opens the door to a broader variety of basis functions.

However, the theory does impose an "admissibility" condition: kernels must have "heavy-tailed" Fourier transforms. The authors illustrate this using specific families:

  • Bessel Potentials: These are used to show how parameter settings influence smoothness and decay within the gTV context.
  • Sub-Gaussian Kernels: While the popular Gaussian kernel is technically excluded because it lacks the required heavy tails, the authors demonstrate that sub-Gaussian kernels can be used to approximate Gaussian behavior while remaining compatible with the gTV framework.

Conclusion and Future Work

This research provides the "missing link" between continuous-domain function estimation and discrete sparse optimization. By proving that sparse, adaptive solutions are the mathematical consequence of gTV regularization in Banach spaces, the authors provide a rigorous justification for the generalized LASSO in a continuous setting.

Despite the theoretical elegance, practical challenges remain. The adaptive nature of the kernel positions makes the resulting optimization problem non-convex and computationally demanding, particularly in high-dimensional spaces. Future work will likely focus on developing efficient numerical algorithms that can navigate these non-convex landscapes to leverage the benefits of adaptive kernel placement in real-world machine learning applications.

Summary updated

Abstract

In this paper, we provide a Banach-space formulation of supervised learning with generalized total-variation (gTV) regularization. We identify the class of kernel functions that are admissible in this framework. Then, we propose a variation of supervised learning in a continuous-domain hybrid search space with gTV regularization. We show that the solution admits a multi-kernel expansion with adaptive positions. In this representation, the number of active kernels is upper-bounded by the number of data points while the gTV regularization imposes an $\ell_1$ penalty on the kernel coefficients. Finally, we illustrate numerically the outcome of our theory.
BibTeX
@misc{aziznejad2018l,
  author = {Shayan Aziznejad and Michael Unser},
  title = {{An L1 Representer Theorem for Multiple-Kernel Regression}},
  year = {2018},
  eprint = {1811.00836},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.00836},
}
Figure