Characterizing the Representer Theorem

Yaoliang Yu, Hao Cheng, Dale Schuurmans, Csaba SzepesváriICML 2013 · OpenReview

Introduction

This paper provides the definitive mathematical answer to a fundamental question in machine learning: exactly what kind of penalty functions (regularizers) allow us to use kernel methods? The authors prove that the "Representer Theorem" holds if and only if the regularizer is a weakly increasing function of the norm, finally closing a theoretical gap that has existed for decades.

In kernel methods, such as Support Vector Machines, we often try to find a function in a Reproducing Kernel Hilbert Space (RKHS) that minimizes a combination of data loss and a penalty term (the regularizer). The inherent challenge is that these spaces can be infinite-dimensional, making direct optimization seemingly impossible.

The Representer Theorem acts as the "magic trick" of machine learning: it proves that the optimal function can always be written as a simple linear combination of the training data points. This collapses an infinite-dimensional problem into a finite one that a computer can actually solve.

For a long time, researchers knew that if the regularizer was an increasing function of the norm (like $\|f\|^2$), the theorem worked. However, the minimum requirements remained unknown. Could we design exotic new regularizers that still allow for this computational shortcut? This paper sets out to find the "necessary and sufficient" conditions—the exact boundaries of what is mathematically possible.

Methods and Geometric Proof

The paper is purely theoretical, utilizing tools from functional analysis and geometry. The authors focus on the interpolation problem: finding a function that perfectly hits specific data points while minimizing the regularizer.

Their primary innovation is a novel geometric proof. They use a "rotation argument" in Hilbert space to show that if a regularizer allows the Representer Theorem to hold, it must behave consistently as you move further from the origin.

Geometric rotation argument in Hilbert space

By rotating vectors and using the properties of inner product spaces, they demonstrate that the penalty cannot decrease as the norm of the function increases.

Key Insights and Results

The authors establish several foundational rules for regularizers in RKHS:

  • The "Weakly Increasing" Condition (Theorem 2): The core result shows that a regularizer is "admissible" (meaning the Representer Theorem holds) if and only if it is a weakly increasing function of the RKHS norm. Mathematically, for a regularizer $\Omega(f)$, if $\|g\| > \|f\|$, then $\Omega(g) \ge \Omega(f)$. It doesn't strictly require the penalty to go up, just that it cannot go down as the function gets "larger."
  • Strict Admissibility: If you want the solution to be unique and always lie exactly in the span of the data, the regularizer must be strictly increasing.
  • Simplicity over Continuity: Previous attempts to characterize the theorem required the regularizer to be differentiable or "lower semicontinuous." This paper proves those assumptions are entirely unnecessary. The result holds even for "ugly," discontinuous functions.
  • Radial vs. Non-Radial: While most common regularizers are "radial" (they only care about the length of the function, not its direction), the authors show that non-radial regularizers can work. However, they must be "almost" radial—specifically, they can only differ from a radial function on a "countable" number of spheres.
  • Homogeneity: If a regularizer is "positively homogeneous" (like a standard norm) and admissible, it must be a simple multiple of the RKHS norm. This effectively rules out using other norms (like the $L_1$ norm) directly as admissible regularizers in an RKHS if you want the standard Representer Theorem to apply.

Limitations and Future Work

While the paper definitively solves the scalar case, it leaves a few open challenges:

  • Matrix Domain: When moving from vectors to matrices (useful in multi-task learning), the conditions become much more complex. The simple relationship between the norm and the penalty partially breaks down, requiring more sophisticated matrix orderings (Löwner ordering). The authors acknowledge their characterization here is "less complete."
  • Vector-Valued Kernels: For vector-valued kernels (where the output is a vector rather than a scalar), their results serve as a sufficient condition, but a complete characterization seems to require substantially new ideas.

Ultimately, the practical impact of this paper is a "negative" one for researchers hoping to find exotic regularizers. It essentially proves that if you want to leverage the computational shortcut of the Representer Theorem, you are strictly bound to functions that behave very much like the standard norm.

Summary updated

Abstract

The representer theorem assures that kernel methods retain optimality under penalized empirical risk minimization. While a sufficient condition on the form of the regularizer guaranteeing the repre...
BibTeX
@inproceedings{yu2013characterizing,
  author = {Yaoliang Yu and Hao Cheng and Dale Schuurmans and Csaba Szepesvári},
  title = {{Characterizing the Representer Theorem}},
  booktitle = {International Conference on Machine Learning},
  year = {2013},
  url = {https://openreview.net/forum?id=ByVnEi-u-H},
}
Figure