This chapter introduces the key concepts of optimal recovery, such as model sets, quantities of interest, intrinsic errors, and optimal recovery maps. It emphasizes two situations where recovery maps that are optimal over symmetric and convex model sets can be chosen as linear maps: the estimation of linear functionals and the Hilbert setting. Natural splines are introduced as a concrete example of the latter situation.

This chapter focuses exclusively on linear programs. It first describes the simplex algorithm used to solve linear programs in standard form. It then presents a series of examples illustrating the usefulness of slack variables to transform some geometric problems into linear programs.

This appendix starts by presenting some results about the uniform approximation of functions, some of them well known (Stone–Weierstrass, Jackson, and Bersntein theorems) and some of them lesser known (Korovkin theorem). It proceeds by establishing the Riesz-Fejér and Carathéodory—Toeplitz theorems, as they play a role related to semidefinite programming. It concludes with a proof of the Kolmogorov superposition theorem, since this theorem is significant in connection with neural networks.

This chapter is concerned with the number of linear observations enabling the standard compressive sensing problem to be solved in a stable way. The upper estimate derived from the previous chapter is matched by a lower estimate obtained by a combinatorial argument. A connection with the Gelfand width of ?1-balls is then drawn. Finally, it is explained why stability quantified in ?2 is irrelevant in the context of compressive sensing.

The duality theory for linear programs is fully justified in this chapter. It is exploited, in the spirit of robust optimization, to deal with problems from optimal recovery and from compressive sensing, namely with Chebyshev balls computation and owl-norm minimization. Duality results for conic programming, and in particular for semidefinite programming, are also provided without proof.

This chapter introduces different notions of tractability and intractability. Most notably, the curse of dimensionality occurs when the solution of a multivariate problem would necessitate a number of observations growing exponentially with the number of variables involved. As illustrations, relying on reproducing-kernel techniques, it is shown on the one hand that the integration of trigonometric polynomials is an intractable problem, and on the other hand that integration in weighted Sobolev spaces is a tractable problem provided the weights decay fast enough.

After having determined optimal recovery maps when observation functionals were fixed, this chapter intends to further determine optimal observation functionals. Two examples for which this quest is realizable are given: the Hilbert setting, and the integration of Lipschitz functions. In passing, it is shown that adaptive observations are not really superior to nonadaptive observations for the estimation of linear functionals over symmetric and convex model sets.

This first chapter introduces the key concepts of statistical learning theory, such as generalization error, empirical risk minimization, bias-complexity tradeoff, and validation. It also describes the probably approximately correct (PAC) framework and establishes that finite hypothesis classes are PAC-learnable.

This chapter provides a theoretical analysis of reproducing kernel Hilbert spaces. It starts by showing that every Hilbert space of functions in which point evaluations are continuous linear functionals possesses a reproducing kernel. It proceeds by showing that every positive semidefinite kernel gives rise to a reproducing kernel Hilbert space—this is the Moore--Aronszajn theorem. Finally, the Mercer theorem offers an explicit representation of this reproducing kernel Hilbert space under additional conditions on the kernel.

This appendix highlights some striking phenomena occurring in high dimensions. In passing, it isolates some useful facts about volumes and covering numbers. The projected cross-polytope is also discussed in connection with compressive sensing.

In this chapter, the notion of the Vapnik--Chervonenkis dimension is formally defined and illustrated on several examples. The behavior of the related shatter function is elucidated through the Sauer lemma, proved with the help of the Pajor lemma.

This chapter contains the proof of the fundamental theorem of PAC-learning for binary classification. In particular, the so-called uniform convergence property is introduced and used to show that finite VC-dimension implies PAC-learnability. Conversely, the so-called no-free-lunch theorem is used to show that PAC-learnability implies finite VC-dimension.