Source-linked AI summary
When is there a representer theorem? Vector versus matrix regularizers
Andreas Argyriou, Charles Micchelli, Massimiliano Pontil
TL;DR
The paper asks which regularizers guarantee representer-theorem solutions for vector and matrix learning problems. It proves a complete vector characterization and develops a broader matrix characterization based on matrix nondecreasing functions, with examples including trace norm and rank regularization. The results support shared multi-task representations and computational reductions for the covered matrix problems.
Problem
The paper addresses the missing necessary characterization of regularizers yielding representer theorems and the need for a matrix version suited to jointly related multi-task parameters.
Method
The paper relates interpolation and regularization, then uses geometric and matrix-order arguments to characterize vector and matrix regularizers.
Results
The vector condition is necessary and sufficient, while matrix nondecreasing regularizers yield the modified theorem; covered examples include trace norm and rank, with rank regularization remaining computationally reducible by the theorem.
Takeaways & Limitations
The matrix result broadens representer-theorem methods to regularizers that can couple tasks, including practical multi-task-learning examples.
Takeaways & Limitations
The paper leaves additional constraints, positive-semidefinite matrix cones, and operators between Hilbert spaces for future study.
Abstract
from arXiv · showhide
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 inner product then the learned vector is a linear combination of the input data. This result, known as the {\em representer theorem}, is at the basis of kernel-based methods in machine learning. In this paper, we prove the necessity of the above condition, thereby completing the characterization of kernel methods based on regularization. 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 for these class of matrix regularizers and highlight them with some concrete examples of practical importance. Our analysis uses basic principles from matrix theory, especially the useful notion of matrix nondecreasing function.
1 Introduction
The paper characterizes when vector regularization admits the standard representer theorem and extends the analysis to matrix regularizers motivated by multi-task learning. The matrix formulation permits shared representations across tasks and supports a broader class of regularizers.
- Vector regularization: Regularization combines an error term with a regularizer that favors desirable properties, and certain regularizers yield solutions that are linear combinations of the data.This representer property can reduce optimization in high- or infinite-dimensional spaces to identifying one parameter per input.
- Vector regularization: The paper seeks necessary and sufficient conditions for representer theorems, studying interpolation because its results transfer to regularization under stated conditions on the error function.A representer theorem for interpolation implies one for regularization with the same regularizer and any error function; the converse requires weak qualifications.
- Vector regularization: For vector interpolation, a solution has the standard representer form if and only if the regularizer is a nondecreasing function of the Hilbert space norm.The paper presents this as a complete characterization of regularizers producing standard representer theorems.
- Matrix regularization: Matrix regularization jointly learns task-specific parameter columns, allowing prior relations among tasks to influence the shared optimization problem.Each task has its own inputs and outputs, while the regularizer is intended to favor useful task relations.
- Matrix regularization: Frobenius-norm regularizers give task-separate representations, so each optimal task vector uses only its own inputs and tasks can be optimized independently.The paper therefore regards such regularizers as unsuitable when the tasks are expected to be related.
- Matrix regularization: The modified matrix representer theorem allows every column of the optimal matrix to use input vectors from all tasks, expanding the class of admissible regularizers.The paper connects this broader class to matrix nondecreasing functions and discusses examples with practical multi-task-learning relevance.
2 Regularization versus Interpolation
The paper establishes an equivalence between linear representer theorems for regularization and interpolation under broad conditions, then applies it to common loss functions and special input configurations.
- Equivalence: Interpolation representer theorems imply regularization representer theorems without conditions on the error function.The converse requires analytical assumptions on the error function, including a nonzero unique minimizer along some direction.
- Equivalence: Under lower semicontinuity, bounded sublevel sets, and a stated error-function condition, regularization representer theorems also imply interpolation representer theorems.The proof constructs regularization problems with γ approaching zero and extracts a convergent sequence of span-representable solutions.
- Common losses: For square, hinge, or logistic loss with m ≥ 2, regularization and interpolation satisfy the linear representer theorem if and only if each other does.This conclusion assumes that the regularizer is lower semicontinuous with bounded sublevel sets.
- Common losses: The converse condition on the error function is weak enough to allow nonconvex losses, but excludes overly flat choices such as a constant loss.The paper explicitly notes that constant loss does not meet the required condition.
- Special case: When inputs are linearly independent, hinge- or logistic-loss regularization satisfies the linear representer theorem for any lower-semicontinuous norm-based regularizer with bounded sublevel sets.The paper notes that linear independence occurs frequently when the dimensionality d is high.
3 Representer Theorems for Interpolation Problems
The paper characterizes interpolation regularizers that guarantee span-based solutions: differentiable admissible regularizers must be nondecreasing functions of the Hilbert-space norm, with strict admissibility requiring strict increase.
- Definitions: An admissible regularizer guarantees an interpolation solution in the span of the input data whenever the constraints are satisfiable.The definition permits existence of at least one span-representable solution for every such dataset.
- Characterization: Theorem 3.1 states that, for differentiable Ω on a Hilbert space of dimension at least 2, admissibility is equivalent to a nondecreasing function of the squared norm.The functional condition is expressed as Ω(w) = h(⟨w,w⟩), with h nondecreasing.
- Geometric interpretation: Geometrically, the regularizer cannot decrease when adding a component orthogonal to the input span, so its contours are spherical or bounded by spheres.This orthogonal-direction monotonicity is the geometric condition underlying the theorem.
- Proof idea: The proof decomposes a solution into components in the input span and its orthogonal complement, then removes the orthogonal component without increasing the regularizer.The resulting span component preserves the interpolation constraints.
- Strict admissibility: Strict admissibility, requiring every solution to lie in the input span, is equivalent to Ω(w) = h(⟨w,w⟩) with h strictly increasing.The strict version strengthens the orthogonal monotonicity condition so equality occurs only when the orthogonal component is zero.
- Examples: For p-norms, the representer condition fails for every p ≥ 0 with p ≠ 2 because these norms cannot be expressed as functions of the Hilbert-space norm.The paper contrasts them with the Hilbert norm, which corresponds to p = 2.
4 Matrix Learning Problems
The paper extends representer theorems from vector regularization to matrix problems motivated by multi-task learning. It characterizes matrix regularizers supporting task-coupled representations through matrix nondecreasing functions and gives practical examples.
- Exploiting Matrix Structure: Matrix constraints preserve task structure, unlike vectorized constraints, and lead to representations using data from all tasks.The resulting representation differs from Frobenius-inner-product formulations, which use only each task’s own data.
- Matrix Learning Problems: Matrix representer theorems address jointly learning n task vectors while incorporating relationships among tasks through matrix regularization.Each task corresponds to a column of W, and regularization can encode shared structure across tasks.
- Exploiting Matrix Structure: Trace-norm regularization jointly learns tasks by favoring low-rank parameter matrices whose columns are combinations of a small set of basis vectors.The paper notes that this structure can support accurate estimation when each task has few data points.
- Exploiting Matrix Structure: The matrix problem class is richer than standard matrix-vectorized constraints, and its representer theorem includes the trace norm and other useful regularizers.The trace-norm theorem guarantees a solution with the stated cross-task representation.
- Characterization of Matrix Regularizers: For differentiable regularizers, the characterization uses matrix nondecreasing functions, yielding a necessary-and-sufficient condition under the theorem’s dimension assumption d ≥ 2n.The condition is expressed through a functional form involving a matrix nondecreasing function of the relevant positive-semidefinite matrix argument.
- Characterization of Matrix Regularizers: The same representer regularizers apply whether tasks share one sample or each task has its own sample.The paper states that the two matrix problem types do not differ with respect to representer theorems of the relevant form.
- Examples: The class includes Schatten Lp norms and prenorms, including the trace norm and matrix rank, while an extension supports dimensionality reduction across multiple subspaces.Rank regularization is computationally difficult, but the representer theorem reduces dependence to the total sample size.
5 Conclusion
The paper characterizes vector and matrix regularizers that yield representer theorems, extending the analysis to matrix-valued learning. It also identifies directions for studying constrained and operator-valued extensions.
- The vector case establishes necessity of the condition underlying the standard representer theorem.
- The matrix case identifies a broader class of regularizers based on matrix nondecreasing functions that yields a modified representer theorem.
- The analysis is motivated by regularizers used in multi-task learning and collaborative filtering.
- Future work includes studying orthogonally invariant matrix regularizers, additional convex-cone constraints, and operators between Hilbert spaces.
Appendix
The appendix develops auxiliary matrix results used in the analysis, including rotational connectedness and monotonicity properties of the trace norm.
- For vectors in R^d with d ≥ 2, an orientation-preserving orthogonal transformation maps one vector to another exactly when their norms are equal.
- The rotation lemma constructs the transformation from orthonormal bases of the complements of the two vectors.
- If W^T P = 0, adding P to W cannot decrease the trace norm.
- The trace-norm result follows by applying matrix monotonicity of the square-root function to W^T W + P^T P and P^T P.