Random Fourier Features for Operator-Valued Kernels
  Devoted to multi-task learning and structured output learning,
operator-valued kernels provide a flexible tool to build vector-valued
functions in the context of Reproducing Kernel Hilbert Spaces. To scale up
these methods, we extend the celebrated Random Fourier Feature methodology to
get an approximation of operator-valued kernels. We propose a general principle
for Operator-valued Random Fourier Feature construction relying on a
generalization of Bochner's theorem for translation-invariant operator-valued
Mercer kernels. We prove the uniform convergence of the kernel approximation
for bounded and unbounded operator random Fourier features using appropriate
Bernstein matrix concentration inequality. An experimental proof-of-concept
shows the quality of the approximation and the efficiency of the corresponding
linear models on example datasets.
