When is there a representer theorem? Vector versus matrix regularizers

By Andreas Argyriou, Charles A. Micchelli, Massimiliano Pontil. 2008

174 citations recorded by the source corpus.

We consider a general class of regularization methods which learn a vector of parameters on the basis of linear measurements. It is well known that if the regularizer is a nondecreasing function of the L2 norm, then the learned vector is a linear combination of the input data. This result, known as the representer theorem, lies at the basis of kernel-based methods in machine learning. In this paper, we prove the necessity of the above condition, in the case of differentiable regularizers. We further extend our analysis to regularization methods which learn a matrix, a problem which is motivated by the application to multi-task learning. In this context, we study a more general representer theorem, which holds for a larger class of regularizers. We provide a necessary and sufficient condition characterizing this class of matrix regularizers and we highlight some concrete examples of practical importance. Our analysis uses basic principles from matrix theory, especially the useful notion of matrix nondecreasing functions.

Subfields: Computational Mechanics, Control and Systems Engineering, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Control and Systems Engineering

In Mathematical Physics

Citations in the corpus

A Survey on Multi-Task Learning (2017, background): “mation theory, is used in [227] to bound the generalization performance. Besides generalization bounds, there are some works to discuss other theoretical problems in MTL. For example, Argyriou et al. [228], [229] discuss conditions for regularized MTL algorithms that representer theorems hold. Sever”
Random Feature Maps for Dot Product Kernels (2012, background): “t 2012 by the authors. tion in these non linear feature spaces and is at the risk of incurring the curse of dimensionality. The solution to this problem comes in the form of Representer Theorems (see Argyrioua et al., 2009, for recent results) which act as an implicit dimensionality reduction step b”
An embarrassingly simple approach to zero-shot learning (2015, methodology): “First, if the regularizer Ω is of the form Ω(B) = Ψ B B for an appropriate choice of the function Ψ , then by using the representer theorem [3], this leads to a kernel version of the problem, where only inner products between instances are used:”
The representer theorem for Hilbert spaces: a necessary and sufficient condition (2012, background): “More recently, the question of whether condition (2) is also necessary for the existence of linear representer theorems has been investigated [15].”
Learning Sparse Task Relations in Multi-Task Learning (2017, background): “(4) and (5), the 1 regularization on Ω leads to a ‘sparse’ representer theorem in Corollary 1, which is different from the conventional multi-task representer theorem (Argyriou, Micchelli, and Pontil 2009) where each wi lies in the span of the training data from all the tasks.”
On Spectral Learning (2010, methodology): “This type of representer theorem arises inmulti-task learningas described in Argyriou et al. (2009).”
Convex Discriminative Multitask Clustering (2013, methodology): “We may use the kernel decomposition techniques, such as kernel principle component analysis or Cholesky decomposition, to get fð Þ approximately and explicitly, or the methods described in [8], [63] to incorporate the kernels.”
Learning Multiple Tasks using Manifold Regularization (2010, background): “Argyriou et. al. extend their work [4] in [2] [3] where non-linearity is introduced by considering a kernel function on the input data, and then learning the linear subspace in the Hilbert space.”
Semi-supervised Penalized Output Kernel Regression for Link Prediction (2011, unknown): “We must emphasize the series of works (Caponnetto et al., 2008; Argyriou et al., 2009) that developed this theory to solve a multi-tasks learning problem and the recent work of Kadri et al. (2010) who achieved functional regression by applying this theory for input and output functional space.”