Regularization: From Inverse Problems to Large-Scale Machine Learning

We discuss regularization methods in machine learning with an emphasis on the interplay between statistical and computational aspects. We begin recalling a connection between inverse problem and machine learning. Then, we discuss how it allows to translate modeling principles into computational procedures, suggesting strategies to deal with large-scale learning problems.

1. 1.

   More precisely, two continuous functions that are equal almost everywhere, they coincide only on \(\mathcal{X}_\rho \).

2. 2.

   Or rather the second moment matrix.

This chapter evolved from a set of notes for the Summer School “Applied Harmonic Analysis and Machine Learning” in Genova, as well as the Summer School “Structured Regularization for High-Dimensional Data Analysis” at IHP Paris, and the Spring School “Structural Inference” Malente, Germany. The results we present are an overview of the work with and of a number of collaborators and colleagues. Among others, we would like to thank Gilles Blanchard, Andrea Caponnetto, Luigi Carratino, Raffaello Camoriano, Junhong Lin, Nicole Mücke, Nicoló Pagliana, Steve Smale, Alessandro Verri, Silvia Villa and Ding-Xuan Zhou.

This material is based on work supported by the Center for Brains, Minds and Machines (CBMM), funded by NSF STC award CCF-1231216. We gratefully acknowledge the support of NVIDIA Corporation for the donation of the Titan Xp GPUs and the Tesla k40 GPU used for this research. L. R. acknowledges the financial support of the European Research Council (grant SLING 819789), the AFOSR projects FA9550-18-1-7009, FA9550-17-1-0390 and BAA-AFRL-AFOSR-2016-0007 (European Office of Aerospace Research and Development), and the EU H2020-MSCA-RISE project NoMADS-DLV-777826. Part of this work was funded by the French government under management of Agence Nationale de la Recherche as part of the “Investissements d’ avenir program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). A. R. acknowledges the financial support of the European Research Council (grant REAL 947908). E.D.V. is a member of the Gruppo Nazionale per l’Analisi Matematica, la Probabilità e le loro Applicazioni (GNAMPA) of the Istituto Nazionale di Alta Matematica (INdAM).

Authors and Affiliations

1. DIMA & MaLGA, Universita di Genova, Via Dodecaneso 35, Genova, Italy

   Ernesto De Vito & Lorenzo Rosasco

2. Inria and Ecole Normale Supérieure, PSL Research University, Paris, France

   Alessandro Rudi

Corresponding author

Correspondence to Ernesto De Vito .

Editors and Affiliations

1. Dipartimento di Matematica, Università di Genova, Genova, Italy

   Filippo De Mari

2. Dipartimento di Matematica, Università di Genova, Genova, Italy

   Ernesto De Vito

Appendix

In this section, we collect the notation and some basic mathematical facts, adapted to our setting.

We recall the following results.

• Trace class operators: an operator \(A:\mathcal {H}\rightarrow \mathcal {H}\) is trace class if there exists (any) a base \((v_\ell )_{\ell \in \Lambda }\) of \(\mathcal {H}\) such that the series \(\sum _{\ell \in \Lambda } \left\langle {|{A}|v_\ell },{v_\ell }\right\rangle _\mathcal {H}\) converges and

  $$ {\text {Tr}} A = \sum _{\ell \in \Lambda } \left\langle {A v_\ell },{v_\ell }\right\rangle _\mathcal {H} $$

  is called the trace of A. An \(A:\mathcal {H}\rightarrow \mathcal{G}\) is trace class if \(|{A}|\) is trace class and the space \(\mathcal S_1(\mathcal {H},\mathcal{G})\) of trace class operators from \(\mathcal {H}\) to \(\mathcal{G}\) is a Banach space with respect the norm

  $$ \bigl \Vert {A}\bigr \Vert _{ \mathcal S_1(\mathcal {H},\mathcal{G})} = {\text {Tr}}(|{A}|). $$

• Hilbert–Schmidt operators: \(A:\mathcal {H}\rightarrow \mathcal{G}\) is a Hilbert–Schmidt operator if \(A^*A\) is a trace class operator. The space \(\mathcal S_2(\mathcal {H},\mathcal{G})\) of Hilbert–Schmidt operators from \(\mathcal {H}\) to \(\mathcal{G}\) is a Hilbert space with respect to the scalar product

  $$ \left\langle {A},{B}\right\rangle _{ \mathcal S_2(\mathcal {H},\mathcal{G})} ={\text {Tr}}(B^*A), $$

  and \(\mathcal S_1(\mathcal {H},\mathcal{G})\subset \mathcal S_2(\mathcal {H},\mathcal{G})\).

• Hilbert–Schmidt theorem: if \(A:\mathcal {H}\rightarrow \mathcal {H}\) is a Hilbert–Schmidt self-adjoint operator, there exists a base \((v_\ell )_{\ell \in \Lambda }\) of \(\mathcal {H}\) and a sequence \((v_\ell )_{\ell \in \Lambda }\) of real numbers such that

  $$\begin{aligned} A v_\ell =\sigma _\ell v_\ell . \end{aligned}$$

• Functional calculus: if \(A:\mathcal {H}\rightarrow \mathcal {H}\) is a Hilbert–Schmidt self-adjoint operator and \(\varphi :{\mathbb {R}}\rightarrow {\mathbb {R}}\) is a bounded function, by the functional calculus the operator \(\varphi (A):\mathcal {H}\rightarrow \mathcal {H}\) is defined as

  $$ \varphi (A) f =\sum _{\ell \in \Lambda } \varphi (\sigma _\ell ) \left\langle {f},{v_\ell }\right\rangle _\mathcal {H} v_\ell . $$

  where the series converges in \(\mathcal {H}\).

• For any operator \(A:\mathcal {H}\rightarrow \mathcal{G}\)

  $$\begin{aligned} \Vert A\Vert ^2_\infty = \Vert AA^*\Vert _\infty \end{aligned}$$

  (68)

• Cordes inequality: for any pair of positive operator \(A, B:\mathcal {H}\rightarrow \mathcal {H}\) and \(s \in (0,1]\)

  $$\begin{aligned} \Vert A^s B^s\Vert _\infty \le \Vert A B\Vert ^s_\infty \end{aligned}$$

  (69)

• Take two operators \(B,C:\mathcal {H}\rightarrow \mathcal{G}\) such that

  $$\begin{aligned} B B^* \le CC^*, \end{aligned}$$

  (70)

  then

  $$\begin{aligned} \bigl \Vert {AB}\bigr \Vert _\infty \le \bigl \Vert {AC}\bigr \Vert _\infty \end{aligned}$$

  (71)

  for any operator \(A:\mathcal{G}\rightarrow \mathcal{G}'\). Indeed, by (70)

  $$ ABB^*A^* \le ACC^*A^* \qquad \Longrightarrow \qquad \bigl \Vert {ABB^*A^*}\bigr \Vert _\infty \le \bigl \Vert {ACC^*A^*}\bigr \Vert _\infty . $$

  Then,

  $$\begin{aligned} \bigl \Vert {AB}\bigr \Vert ^2_\infty&= \bigl \Vert {ABB^*A^*}\bigr \Vert _\infty \le \bigl \Vert {CBB^*C^*}\bigr \Vert _\infty = \bigl \Vert {AC}\bigr \Vert ^2_\infty . \end{aligned}$$

• If \(A:\mathcal {H}\rightarrow \mathcal{G}\) and \(\lambda >0\)

  $$\begin{aligned} ((A^*A + \lambda I)^{-1}A^*A - I) = \lambda (A^*A + \lambda I)^{-1} \end{aligned}$$

  (72)

  see [22].

• For any positive operator \(C:\mathcal {H}\rightarrow \mathcal {H}\) and projection \(P:\mathcal {H}\rightarrow \mathcal {H}\)

  $$\begin{aligned} P(PCP + \lambda I)^{-1}P \le P(C + \lambda I)^{-1}P \end{aligned}$$

  (73)

  see, for example, Theorem V.2.3-(iv) of [3] for the proof of this property of operator convex functions, and Cor. V.2.6 together with Exercise V.1.10-(ii) and Exercise V.2.11, in the same book, for the proof of operator convexity of \((\cdot +\lambda )^{-1}\).

• For any pair \(A,B:\mathcal {H}\rightarrow \mathcal {H}\) of positive operators with bounded inverse such that

  $$\begin{aligned} \bigl \Vert {B^{-\frac{1}{2}} (A-B) B^{-\frac{1}{2}}}\bigr \Vert _{\infty } < 1 \end{aligned}$$

  (74)

  then

  $$\begin{aligned} \bigl \Vert {A^{-\frac{1}{2}} B^{\frac{1}{2}} }\bigr \Vert _{\infty }&\le \sqrt{\frac{1}{1 - \bigl \Vert {B^{-\frac{1}{2}} (A-B) B^{-\frac{1}{2}}}\bigr \Vert _{\infty }}}. \end{aligned}$$

  (75)

  Indeed, observe that

  $$\begin{aligned} (A^{-\frac{1}{2}} B^{\frac{1}{2}})^* A^{-\frac{1}{2}} B^{\frac{1}{2}}&= B^{\frac{1}{2}} A^{-1} B^{\frac{1}{2}}=B^{\frac{1}{2}} \left( A-B+B\right) ^{-1} B^{\frac{1}{2}} \\&= B^{\frac{1}{2}} \left( B^{\frac{1}{2}}\left( B^{-\frac{1}{2}}(A-B) B^{-\frac{1}{2}}+I\right) B^{\frac{1}{2}}\right) ^{-1} B^{\frac{1}{2}}\\&= \left( B^{-\frac{1}{2}}(A-B) B^{-\frac{1}{2}}+I\right) ^{-1}=\sum _{\ell =0}^{+\infty } (-1)^\ell \left( B^{-\frac{1}{2}}(A-B) B^{-\frac{1}{2}}\right) ^{\ell }, \end{aligned}$$

  where the Neumann series converges by (74). Hence, triangular inequality gives

  $$\begin{aligned} \bigl \Vert {A^{-\frac{1}{2}} B^{\frac{1}{2}}}\bigr \Vert ^2_\infty&= \bigl \Vert {\left( B^{-\frac{1}{2}}(A-B) B^{-\frac{1}{2}}+I\right) ^{-1}}\bigr \Vert _{\infty } \le \frac{1}{1 - \bigl \Vert { B^{-\frac{1}{2}} (A-B) B^{-\frac{1}{2}}}\bigr \Vert _{\infty }}. \end{aligned}$$

• Höeffidng inequality in separable Hilbert spaces [35, 36, 51] : take a family

  $$\begin{aligned} \xi _1,\ldots ,\xi _n:\Omega \rightarrow \mathcal {H}\end{aligned}$$

  of independent zero mean random variables such that \(\Vert {\xi _i}\Vert _\mathcal {H}\le \kappa \), then for all \(\epsilon >0\)

  $$ \mathbb P\left[ \Vert {\frac{1}{n} \sum _{i=1}^n \xi _i}\Vert _\mathcal {H} >\epsilon \right] \le 2 \exp \left( -\frac{\epsilon ^2 n }{4 \kappa ^2}\right) , $$

  i.e., for all \(\tau >0\) with probability at least \(1- 2 e^{-\tau }\)

  $$\begin{aligned} \Vert {\frac{1}{n} \sum _{i=1}^n \xi _i}\Vert _\mathcal {H} \le \dfrac{2\kappa \sqrt{\tau }}{\sqrt{n}}. \end{aligned}$$

  (76)

Reprints and permissions

© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics