Similarly we obtain

$$ \mathbf{E}_{\widehat{\text{Haar}},\rho} [\cos(e, \omega) A(\omega)^2] = K_e(e) \mathbf{E}_{\widehat{\text{Haar}},\rho} [A(\omega)] + \text{Cov}_{\widehat{\text{Haar}},\rho} [\cos(e, \omega) A(\omega), A(\omega)] $$

Therefore

$$ \begin{aligned} \text{Var}_{\widehat{\text{Haar}},\rho} [\tilde{K}_e(\delta)] &= \frac{1}{2D} \left( (K_e(2\delta) + K_e(e)) \mathbf{E}_{\widehat{\text{Haar}},\rho} [A(\omega)] - 2K_e(\delta)^2 \right. \\ & \qquad \left. + \text{Cov}_{\widehat{\text{Haar}},\rho} [\cos(2\delta, \omega) + \cos(e, \omega)] A(\omega), A(\omega)] \right) \\ &= \frac{1}{2D} \left( (K_e(2\delta) + K_e(e)) \mathbf{E}_{\widehat{\text{Haar}},\rho} [A(\omega)] - 2K_e(\delta)^2 \right. \\ & \qquad \left. + \text{Cov}_{\widehat{\text{Haar}},\rho} [\cos(\delta, \omega))^2 A(\omega), A(\omega)] \right) \\ & \lesssim \frac{1}{2D} \left( (K_e(2\delta) + K_e(e)) \mathbf{E}_{\widehat{\text{Haar}},\rho} [A(\omega)] - 2K_e(\delta)^2 + \text{Var}_{\widehat{\text{Haar}},\rho} [A(\omega)] \right) \end{aligned} $$

■

## B.3 Learning

### B.3.1 PROOF OF THEOREM 34

**Proof** Since $f(x) = K_x^*f$, the optimization problem reads

$$ f_s = \arg\min_{f \in \mathcal{H}_K} \frac{1}{N} \sum_{i=1}^{N} c(K_{x_i}^* f, y_i) + \frac{\lambda}{2} \|f\|_K^2 $$

Let $W_s : \mathcal{H}_K \to \bigoplus_{i=1}^N \mathcal{Y}$ be the restriction<fnref n="14" /> linear operator defined as $W_s f = \bigoplus_{i=1}^N K_{x_i}^* f$, with $K_{x_i}^* : \mathcal{H}_K \to \mathcal{Y}$ and $K_{x_i} : \mathcal{Y} \to \mathcal{H}_K$. Let $Y = \bigoplus_{i=1}^N y_i \in \mathcal{Y}^N$. We have $\langle Y, W_s f \rangle_{\bigoplus_{i=1}^N \mathcal{Y}} = \sum_{i=1}^N \langle y_i, K_{x_i}^* f \rangle_{\mathcal{Y}} = \sum_{i=1}^N \langle K_{x_i} y_i, f \rangle_{\mathcal{H}_K}$. Thus the adjoint operator $W_s^* : \bigoplus_{i=1}^N \mathcal{Y} \to \mathcal{H}_K$ is $W_s^* Y = \sum_{i=1}^N K_{x_i} y_i$, and the operator $W_s^* W_s : \mathcal{H}_K \to \mathcal{H}_K$ is $W_s^* W_s f = \sum_{i=1}^N K_{x_i} K_{x_i}^* f$.

Let $\mathfrak{R}_\lambda(f, s) = \frac{1}{N} \sum_{i=1}^N c(f(x_i), y_i) + \frac{\lambda}{2} \|f\|_K^2$. To ensure that $\mathfrak{R}_\lambda$ has a global minimizer we need the following technical lemma (which is a consequence of the Hahn-Banach theorem for lower-semicontinuous functional, see Kurdila and Zabarankin (2006)).

**Lemma 50**
Let $\mathfrak{R}$ be a proper, convex, lower semi-continuous functional, defined on a Hilbert space $\mathcal{H}$. If $\mathfrak{R}$ is strongly convex, then $\mathfrak{R}$ is coercive.

Let $W_s$ is sometimes called the sampling or evaluation operator as in Minh et al. (2016). However we prefer calling it “restriction operator” as in Rosasco et al. (2010) since $W_s f$ is the restriction of $f$ to the points in $s$.

<footnote n="14">14. $W_s$ is sometimes called the sampling or evaluation operator as in Minh et al. (2016). However we prefer calling it “restriction operator” as in Rosasco et al. (2010) since $W_s f$ is the restriction of $f$ to the points in $s$.</footnote>
Since c is proper, lower semi-continuous and convex by assumption, thus the term $\mathfrak{R}_c$ is also proper, lower semi-continuous and convex. Moreover the term $\frac{\lambda}{2}\|f\|_K^2$ is strongly convex. Thus $\mathfrak{R}_\lambda$ is strongly convex. Apply Lemma 50 to obtain the coercivity of $\mathfrak{R}_\lambda$, and then Mazur-Schauder's theorem (see Górniewicz (1999); Kurdila and Zabarankin (2006)) to show that $\mathfrak{R}_\lambda$ has a unique minimizer and is attained. Then let $\mathcal{H}_{K,s} = \{ \sum_{j=1}^N K_{x_j} u_j \mid \forall (u_i)_{i=1}^N \in \mathcal{Y}^N \}$.

For $f \in \mathcal{H}_{K,s}^{\perp}$<fnref n="15" />, the operator $W_s$ satisfies $\langle Y, W_s f \rangle_{\oplus_{i=1}^N \mathcal{Y}} = \langle \underbrace{f}_{\in \mathcal{H}_{K,s}^{\perp}}, \sum_{i=1}^N K_{x_i} V^* y_i \rangle_{\mathcal{H}_K} = 0$ for all sequences $(y_i)_{i=1}^N$, since $y_i \in \mathcal{Y}$. Hence,

$$ (f(x_i))_{i=1}^N = 0 \qquad (39) $$

In the same way, $\sum_{i=1}^N \langle K_{x_i}^* f, u_i \rangle_{\mathcal{Y}} = \langle \underbrace{f}_{\in \mathcal{H}_{K,s}^{\perp}}, \sum_{j=1}^N K_{x_j} u_j \rangle_{\mathcal{H}_K} = 0$. for all sequences $(u_i)_{i=1}^N \in \mathcal{Y}^N$. As a result,

$$ (f(x_i))_{i=1}^N = 0. \qquad (40) $$

Now for an arbitrary $f \in \mathcal{H}_K$, consider the orthogonal decomposition $f = f^{\perp} + f^{\parallel}$, where $f^{\perp} \in \mathcal{H}_{K,s}^{\perp}$ and $f^{\parallel} \in \mathcal{H}_{K,s}$. Then since $\|f^{\perp} + f^{\parallel}\|_{\mathcal{H}_K}^2 = \|f^{\perp}\|_{\mathcal{H}_K}^2 + \|f^{\parallel}\|_{\mathcal{H}_K}^2$, Equation 39 and Equation 40 shows that if $\lambda > 0$, clearly then $\mathfrak{R}_\lambda(f, s) = \mathfrak{R}_\lambda(f^{\perp} + f^{\parallel}, s) \ge \mathfrak{R}_\lambda(f^{\parallel}, s)$. The last inequality holds only when $\|f^{\perp}\|_{\mathcal{H}_K} = 0$, that is when $f^{\perp} = 0$. As a result since the minimizer of $\mathfrak{R}_\lambda$ is unique and attained, it must lies in $\mathcal{H}_{K,s}$. ■

### B.3.2 PROOF OF THEOREM 35

**Proof** Since $\tilde{K}$ is an operator-valued kernel, from Theorem 34, Equation 24 has a solution of the form

$$ \tilde{f}_s = \sum_{i=1}^{N} \tilde{K}(\cdot, x_i)u_i = \sum_{i=1}^{N} \tilde{\phi}(\cdot)^* \tilde{\phi}(x_i)u_i = \tilde{\phi}(\cdot)^* \underbrace{\left(\sum_{i=1}^{N} \tilde{\phi}(x_i)u_i\right)}_{=\theta \in (\text{Ker } \tilde{W})^{\perp} \subset \tilde{\mathcal{H}}} $$

where $u_i \in \mathcal{Y}$ and $x_i \in \mathcal{X}$. Let $\theta_s = \arg \min_{\theta \in (\text{Ker } \tilde{W})^{\perp}} \frac{1}{N} \sum_{i=1}^N c(\tilde{\phi}(x_i)^* \theta, y_i) + \frac{\lambda}{2} \|\tilde{\phi}(\cdot)^* \theta\|_{\tilde{K}}^2$. Since $\theta \in (\text{Ker } \tilde{W})^{\perp}$ and $W$ is an isometry from $(\text{Ker } \tilde{W})^{\perp} \subset \tilde{\mathcal{H}}$ onto $\mathcal{H}_{\tilde{K}}$, we have $\|\tilde{\phi}(\cdot)^* \theta\|_{\tilde{K}}^2 = \|\theta\|_{\tilde{\mathcal{H}}}^2$. Hence $\theta_s = \arg \min_{\theta \in (\text{Ker } \tilde{W})^{\perp}} \frac{1}{N} \sum_{i=1}^N c(\tilde{\phi}(x_i)^* \theta, y_i) + \frac{\lambda}{2} \|\theta\|_{\tilde{\mathcal{H}}}^2$. Finding a minimizer $\theta_s$ over $(\text{Ker } \tilde{W})^{\perp}$ is not the same as finding a minimizer over $\tilde{\mathcal{H}}$. Although in both cases Mazur-Schauder's theorem guarantees that the respective minimizers are unique, they

<footnote n="15">15. $\mathcal{H}_{K,s}^{\perp} \oplus \mathcal{H}_{K,s} = \mathcal{H}_K$ because $W_s$ is bounded.</footnote>
might not be the same. Since $\tilde{W}$ is bounded, $\text{Ker } \tilde{W}$ is closed, so that we can perform the decomposition $\tilde{\mathcal{H}} = (\text{Ker } \tilde{W})^{\perp} \oplus (\text{Ker } \tilde{W})$. Then clearly by linearity of $W$ and the fact that for all $\theta^{\|} \in \text{Ker } \tilde{W}$, $\tilde{W}\theta^{\|} = 0$, if $\lambda > 0$ we have $\theta_s = \arg \min_{\theta \in \tilde{\mathcal{H}}} \frac{1}{N} \sum_{i=1}^{N} c(\tilde{\phi}(x_i)^*\theta, y_i) + \frac{\lambda}{2}\|\theta\|_{\tilde{\mathcal{H}}}^2$

Thus $\theta_s = \arg \min_{\substack{\theta^{\perp} \in (\text{Ker } \tilde{W})^{\perp}, \\ \theta^{\|} \in \text{Ker } \tilde{W}}} \frac{1}{N} \sum_{i=1}^{N} c \left( (\tilde{W}\theta^{\perp})(x) + \underbrace{(\tilde{W}\theta^{\|})(x), y_i}_{=0 \text{ for all } \theta^{\|}} \right) + \frac{\lambda}{2}\|\theta^{\perp}\|_{\tilde{\mathcal{H}}}^2 + \underbrace{\frac{\lambda}{2}\|\theta^{\|}\|_{\tilde{\mathcal{H}}}^2}_{=0 \text{ only if } \theta^{\|}=0}$
Thus $\theta_s = \arg \min_{\theta^{\perp} \in (\text{Ker } \tilde{W})^{\perp}} \frac{1}{N} \sum_{i=1}^{N} c((\tilde{W}\theta^{\perp})(x), y_i) + \frac{\lambda}{2}\|\theta^{\perp}\|_{\tilde{\mathcal{H}}}^2$

Hence minimizing over $(\text{Ker } \tilde{W})^{\perp}$ or $\tilde{\mathcal{H}}\omega$ is the same when $\lambda > 0$. Eventually, $\theta_s = \arg \min_{\theta \in \tilde{\mathcal{H}}} \frac{1}{N} \sum_{i=1}^{N} c(\tilde{\phi}(x_i)^*\theta, y_i) + \frac{\lambda}{2}\|\theta\|_{\tilde{\mathcal{H}}}^2$. ■

## References

R. Ahlswede and A. Winter. Strong converse for identification via quantum channels. *IEEE Trans. Inform. Theory* 48(3), pages 569–679, 2002.

M. A. Álvarez, L. Rosasco, and N. D. Lawrence. Kernels for vector-valued functions: a review. *Foundations and Trends in Machine Learning*, 4(3):195–266, 2012.

P.-O. Amblard and H. Kadri. Operator-valued kernel recursive least squares algorithm. In *Signal Processing Conference (EUSIPCO), 2015 23rd European*, pages 2376–2380. IEEE, 2015.

A. Argyriou, C. A. Micchelli, and M. Pontil. When is there a representer theorem? Vector vs matrix regularizers. *Journal of Machine Learning Research*, 10:2507–2529, 2009.

N. Aronszajn. Theory of reproducing kernels. *Transactions of the American mathematical society*, pages 337–404, 1950.

J. Audiffren and H. Kadri. Online learning with operator-valued kernels. In *European symposium on artificial neural networks (ESANN)*, 2015.

F. Bach. On the equivalence between quadrature rules and random features. HAl-report-/hal-01118276, 2015.

L. Baldassarre, L. Rosasco, A. Barla, and A. Verri. Vector field learning via spectral filtering. In J. Balcazar, F. Bonchi, A. Gionis, and M. Sebag, editors, *ECML/PKDD*, volume 6321 of LNCS, pages 56–71. Springer Berlin / Heidelberg, 2010.

L. Baldassarre, L. Rosasco, A. Barla, and A. Verri. Multi-output learning via spectral filtering. *Machine Learning*, 87(3):259–301, 2012.

S. Boucheron, G. Lugosi, and P. Massart. *Concentration Inequalities*. Oxford Press, 2013.
R. Brault, M. Heinonen, and F. d'Alché Buc. Random fourier features for operator-valued
kernels. In *Proceedings of The 8th Asian Conference on Machine Learning*, pages 110–125,
2016.

C. Brouard, F. d'Alché-Buc, and M. Szafranski. Semi-supervised penalized output kernel regression for link prediction. In *Proc. of the 28th Int. Conf. on Machine Learning*, 2011.

C. Brouard, F. d'Alché-Buc, and M. Szafranski. Input output kernel regression. to appear in *JMLR*, 2016a.

C. Brouard, H. Shen, K. Dührkop, F. d'Alché Buc, S. Böcker, and J. Rousu. Fast metabolite identification with input output kernel regression. *Bioinformatics*, 32(12):i28-i36, 2016b.

R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu. A limited memory algorithm for bound constrained optimization. *SIAM Journal on Scientific Computing*, 16(5):1190-1208, 1995.

A. Caponnetto, C. A. Micchelli, M. , and Y. Ying. Universal multitask kernels. *Journal of Machine Learning Research*, 9:1615–1646, 2008.

C. Carmeli, E. De Vito, and A. Toigo. Vector valued reproducing kernel hilbert spaces of integrable functions and mercer theorem. *Analysis and Applications*, 4(04):377–408, 2006.

C. Carmeli, E. De Vito, A. Toigo, and V. Umanità. Vector valued reproducing kernel hilbert spaces and universality. *Analysis and Applications*, 8:19–61, 2010.

C. Ciliberto, Y. Mroueh, T. Poggio, and L. Rosasco. Convex Learning of Multiple Tasks and their Structure. In *Proc. of the 32nd International Conference on Machine Learning*, 2015.

J. B. Conway. *A course in functional analysis*, volume 96. Springer Science & Business Media, 2013.

F. Cucker and S. Smale. On the mathematical foundation of learning. *AMERICAN MATHEMATICAL SOCIETY*, 39(1):1–49, 2001.

B. Dai, B. Xie, N. He, Y. Liang, A. Raj, M.-F. F. Balcan, and L. Song. Scalable kernel methods via doubly stochastic gradients. In *Advances in Neural Information Processing Systems*, pages 3041–3049, 2014.

F. Dinuzzo, C. Ong, P. Fehler, and G. Pillonetto. Learning output kernels with block coordinate descent. In *Proc. of the 28th Int. Conf. on Machine Learning*, 2011.

P. Drineas and M. W. Mahoney. On the nyström method for approximating a gram matrix for improved kernel-based learning. *journal of machine learning research*, 6(Dec):2153–2175, 2005.

R. M. Dudley. The sizes of compact subsets of hilbert space and continuity of gaussian processes. *Journal of Functional Analysis*, 1(3):290–330, 1967.

T. Evgeniou, C. A. Micchelli, and M. Pontil. Learning multiple tasks with kernel methods. *JMLR*, 6:615–637, 2005.
X. Y. Felix, A. T. Suresh, K. M. Choromanski, D. N. Holtmann-Rice, and S. Kumar. Orthogonal random features. In *Advances in Neural Information Processing Systems*, pages 1975–1983, 2016.

G. B. Folland. *A course in abstract harmonic analysis*. CRC press, 1994.

E. Fuselier. *Refined Error Estimates for Matrix-Valued Radial Basis Functions*. PhD thesis, Texas A&M University, 2006.

L. Górniewicz. *Topological fixed point theory of multivalued mappings*, volume 495. Springer, 1999.

G. Guennebaud, B. Jacob, et al. Eigen v3, 2010. URL http://eigen.tuxfamily.org.

M. Ha Quang, S. H. Kang, and T. M. Le. Image and video colorization using vector-valued reproducing kernel hilbert spaces. *Journal of Mathematical Imaging and Vision*, 37(1): 49–65, 2010.

R. Hamid, Y. Xiao, A. Gittens, and D. DeCoste. Compact random feature maps. In *ICML*, pages 19–27, 2014.

E. Jones, T. Oliphant, and P. Peterson. {SciPy}: open source scientific tools for {Python}. 2014.

H. Kadri, E. Duflos, P. Preux, S. Canu, and M. Davy. Nonlinear functional regression: a functional rkhs approach. In *JMLR Proc. of International Conference on Artificial Intelligence and Statistics*, volume 9, 2010.

H. Kadri, A. Rakotomamonjy, P. Preux, and F. R. Bach. Multiple operator-valued kernel learning. In *Advances in NIPS*, pages 2429–2437, 2012.

H. Kadri, M. Ghavamzadeh, and P. Preux. A generalized kernel approach to structured output learning. In *Proc. of the 30th International Conference on Machine Learning*, 2013.

H. Kadri, E. Duflos, P. Preux, S. Canu, A. Rakotomamonjy, and J. Audiffren. Operator-valued kernels for learning from functional response data. *Journal of Machine Learning Research*, 16:1–54, 2015.

P. Kar and H. Karnick. Random feature maps for dot product kernels. In *AISTATS*, volume 22, pages 583–591, 2012.

V. Koltchinskii et al. A remark on low rank matrix recovery and noncommutative bernstein type inequalities. In *From Probability to Statistics and Back: High-Dimensional Models and Processes–A Festschrift in Honor of Jon A. Wellner*, pages 213–226. Institute of Mathematical Statistics, 2013.

A. J. Kurdila and M. Zabarankin. Convex functional analysis, 2006.

Q. V. Le, T. Sarlós, and A. J. Smola. Fastfood - computing hilbert space expansions in loglinear time. In *Proc. of ICML 2013, Atlanta, USA, 16-21 June 2013*, pages 244–252, 2013.
Y. LeCun, Y. Bengio, et al. Convolutional networks for images, speech, and time series. *The handbook of brain theory and neural networks*, 3361(10):1995, 1995.

M. Ledoux and M. Talagrand. *Probability in Banach Spaces: isoperimetry and processes*. Springer Science & Business Media, 2013.

F. Li, C. Ionescu, and C. Sminchisescu. *Pattern Recognition: 32nd DAGM Symposium, Darmstadt, Germany, September 22-24, 2010. Proc.*, chapter Random Fourier Approximations for Skewed Multiplicative Histogram Kernels, pages 262–271. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.

N. Lim, Y. Şenbabaoğlu, G. Michailidis, and F. d'Alché Buc. Okvar-boost: a novel boosting algorithm to infer nonlinear dynamics and interactions in gene regulatory networks. *Bioinformatics*, 29(11):1416–1423, 2013.

N. Lim, F. d'Alché-Buc, C. Auliac, and G. Michailidis. Operator-valued kernel-based vector autoregressive models for network inference. *Machine Learning*, 99(3):489–513, 2015a.

N. Lim, F. d'Alché Buc, C. Auliac, and G. Michailidis. Operator-valued kernel-based vector autoregressive models for network inference. *Machine learning*, 99(3):489–513, 2015b.

Z. Lu, A. May, K. Liu, A. B. Garakani, D. Guo, A. Bellet, L. Fan, M. Collins, B. Kingsbury, M. Picheny, et al. How to scale up kernel methods to be as good as deep neural nets. *arXiv preprint arXiv:1411.4000*, 2014.

Y. Macedo and R. Castro. Learning div-free and curl-free vector fields by matrix-valued kernels. Technical report, Preprint A 679/2010 IMPA, 2008.

L. Mackey, M. I. Jordan, R. Chen, B. Farrel, and J. Tropp. Matrix concentration inequalities via the method of exchangeable pairs. *The Annals of Probability*, 42:3:906–945, 2014.

A. Maurer. A vector-contraction inequality for rademacher complexities. In *International Conference on Algorithmic Learning Theory*, pages 3–17. Springer, 2016.

C. A. Micchelli and M. Pontil. Kernels for multi-task learning. In *NIPS*, volume 86, page 89, 2004.

C. A. Micchelli and M. A. Pontil. On learning vector-valued functions. *Neural Computation*, 17:177–204, 2005.

M. Micheli and J. Glaunes. Matrix-valued kernels for shape deformation analysis. Technical report, Arxiv report, 2013.

H. Q. Minh. Operator-valued bochner theorem, fourier feature maps for operator-valued kernels, and vector-valued learning. *arXiv preprint arXiv:1608.05639*, 2016.

H. Q. Minh, L. Bazzani, and V. Murino. A unifying framework for vector-valued manifold regularization and multi-view learning. In *Proc. of the 30th International Conference on Machine Learning*, 2013a.
H. Q. Minh, L. Bazzani, and V. Murino. A unifying framework for vector-valued manifold regularization and multi-view learning. In *ICML (2)*, pages 100–108, 2013b.

H. Q. Minh, L. Bazzani, and V. Murino. A unifying framework in vector-valued reproducing kernel hilbert spaces for manifold regularization and co-regularized multi-view learning. *Journal of Machine Learning Research*, 17(25):1–72, 2016.

S. Minsker. On some extensions of bernstein's inequality for self-adjoint operators. *arXiv preprint arXiv:1112.5448*, 2011.

Y. Mroueh, T. Poggio, L. Rosasco, and J.-j. Slotine. Multiclass learning with simplex coding. In *Advances in NIPS*, pages 2789–2797, 2012.

Y. Mukuta and T. Harada. Kernel approximation via empirical orthogonal decomposition for unsupervised feature learning. In *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, pages 5222–5230, 2016.

A. Naor. On the banach-space-valued azuma inequality and small-set isoperimetry of alon–roichman graphs. *Combinatorics, Probability and Computing*, 21(04):623–634, 2012.

K.-H. Neeb. Operator-valued positive definite kernels on tubes. *Monatshefte für Mathematik*, 126(2):125–160, 1998.

T. E. Oliphant. *A guide to NumPy*, volume 1. Trelgol Publishing USA, 2006.

R. I. Oliveira. Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. *arXiv preprint arXiv:0911.0600*, 2009.

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. Scikit-learn: Machine learning in python. *Journal of Machine Learning Research*, 12(Oct):2825–2830, 2011.

G. Pedrick. Theory of reproducing kernels for hilbert spaces of vector-valued functions. Technical report, University of Kansas, Department of Mathematics, 1957.

T. Penzl. Numerical solution of generalized lyapunov equations. *Advances in Computational Mathematics*, 8(1):33–48, 1998.

N. Pham and R. Pagh. Fast and scalable polynomial kernels via explicit feature maps. In *Proceedings of the 19th ACM SIGKDD*, pages 239–247. ACM, 2013.

I. Pinelis. Optimum bounds for the distributions of martingales in banach spaces. *The Annals of Probability*, pages 1679–1706, 1994.

A. Rahimi and B. Recht. Random features for large-scale kernel machines. In *NIPS 2007*, pages 1177–1184, 2007.

L. Rosasco, M. Belkin, and E. D. Vito. On learning with integral operators. *Journal of Machine Learning Research*, 11(Feb):905–934, 2010.
A. Rudi, R. Camoriano, and L. Rosasco. Generalization properties of learning with random features. *arXiv preprint arXiv:1602.04474*, 2016.

M. Sangnier, O. Fercoq, and F. d'Alché Buc. Joint quantile regression in vector-valued rkhss. *Neural Information Processing Systems*, 2016.

E. Senkene and A. Tempel'man. Hilbert spaces of operator-valued functions. *Lithuanian Mathematical Journal*, 13(4):665-670, 1973.

V. Sindhwani, H. Q. Minh, and A. Lozano. Scalable matrix-valued kernel learning for high-dimensional nonlinear multivariate regression and granger causality. In *Proc. of UAI'13, Bellevue, WA, USA, August 11-15, 2013*. AUAI Press, Corvallis, Oregon, 2013.

G. L. Sleijpen, P. Sonneveld, and M. B. Van Gijzen. Bi-cgstab as an induced dimension reduction method. *Applied Numerical Mathematics*, 60(11):1100-1114, 2010.

S. Smale and D.-X. Zhou. Learning theory estimates via integral operators and their approximations. *Constructive approximation*, 26(2):153-172, 2007.

A. J. Smola, B. Schölkopf, and K.-R. Müller. The connection between regularization operators and support vector kernels. *Neural networks*, 11(4):637-649, 1998.

B. Sriperumbudur and Z. Szabo. Optimal rates for random fourier features. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, *Advances in NIPS 28*, pages 1144-1152, 2015.

D. J. Sutherland and J. G. Schneider. On the error of random fourier features. In *Proc. of UAI 2015, July 12-16, 2015, Amsterdam, The Netherlands*, pages 862-871, 2015.

J. A. Tropp. User-friendly tail bounds for sums of random matrices. *Foundations of computational mathematics*, 12(4):389-434, 2012.

J. A. Tropp et al. An introduction to matrix concentration inequalities. *Foundations and Trends in Machine Learning*, 8(1-2):1-230, 2015.

A. W. Van Der Vaart and J. A. Wellner. Weak convergence. In *Weak Convergence and Empirical Processes*, pages 16–28. Springer, 1996.

J.-P. Vert. Regularization of kernel methods by decreasing the bandwidth of the gaussian kernel.

G. Wahba. *Spline model for observational data*. Philadelphia, Society for Industrial and Applied Mathematics, 1990.

N. Wahlström, M. Kok, T. Schön, and F. Gustafsson. Modeling magnetic fields using gaussian processes. In *in Proc. of the 38th ICASSP*, 2013.

S. v. d. Walt, S. C. Colbert, and G. Varoquaux. The numpy array: a structure for efficient numerical computation. *Computing in Science & Engineering*, 13(2):22-30, 2011.
B. Xie, Y. Liang, and L. Song. Scale up nonlinear component analysis with doubly stochastic gradients. In *Advances in Neural Information Processing Systems*, pages 2341–2349, 2015.

J. Yang, V. Sindhwani, H. Avron, and M. Mahoney. Quasi-monte carlo feature maps for shift-invariant kernels. In *Proceedings of The 31st International Conference on Machine Learning (ICML-14)*, pages 485–493, 2014a.

J. Yang, V. Sindhwani, Q. Fan, H. Avron, and M. W. Mahoney. Random laplace feature maps for semigroup kernels on histograms. In *Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*, pages 971–978, 2014b.

T. Yang, Y.-F. Li, M. Mahdavi, R. Jin, and Z. Zhou. Nyström method vs random fourier features: A theoretical and empirical comparison. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, *NIPS 25*, pages 476–484, 2012.

Z. Yang, M. Moczulski, M. Denil, N. de Freitas, A. Smola, L. Song, and Z. Wang. Deep fried convnets. In *Proceedings of the IEEE International Conference on Computer Vision*, pages 1476–1483, 2015a.

Z. Yang, A. G. Wilson, A. J. Smola, and L. Song. A la carte - learning fast kernels. In *Proc. of AISTATS 2015, San Diego, California, USA, 2015*, 2015b.

H. Zhang, Y. Xu, and Q. Zhang. Refinement of operator-valued reproducing kernels. *Journal of Machine Learning Research*, 13:91–136, 2012.