Learning Theory from First Principles

Python & Matlab code for the figures from the book "Learning Theory from First Principles" by Francis Bach (in preparation)

See available draft of the book here.

Contributors :

• Matlab Figures : Francis Bach
• Reproduction in Python : Maria Bastiani, Gabriel Fiastre, Shane Hoeberichts, Camille Leempoels, Berné Nortier

Table of Contents

To Do | Contribution guidelines | Python code | Matlab code

To Do

Figures still to be done in python :

• Figure 5.3
• Figure 7.3
• Figure 8.2
• Figures 9.1, 9.2

Contribution Guidelines

You can edit the python notebooks to reproduce missing figures (they are all done in Matlab, but a couple of them are not reproduced in python yet, see To Do)

Make sure you have a Github account and git installed on your local machine.

0. Contact Me

Contact me before so we can discuss any potential contribution, what is needed etc.

1. Fork the repository & clone it

Go to the repository page & click on the "Fork" button in the top-right corner of the page. This creates a personal copy of the repository under your GitHub account.

After creating your personnal copy, you can clone the repository :

git clone https://github.com/your-username/Learning_Theory_from_First_Principles/
cd Learning_Theory_from_First_Principles/

Replace your-username with your Github username.

2. Make changes, commit & push

When you are satisfied with your changes, you can commit and push them. Please use a descriptive commit message.

git add . && git commit -am "<Your commit description>" && git push

3. Create a pull request

Once you are done with all your changes and would like to submit your contribution to the main repository, you can open a Pull Request

• Visit your fork on GitHub.
• Click on the "Compare & pull request" button.
• Provide a meaningful title and description for your pull request (e.g. "Adding missing figure fig-3-2")
• Click on the "Create pull request" button.

Python Code

The Python code is organized into individual notebooks for each chapter :

• Chapter 1: Mathematical preliminaries
• Chapter 2: Introduction to supervised learning
• Chapter 3: Linear least-squares regres
• Chapter 4: Empirical risk minimization
• Chapter 5: Optimization
• Chapter 6: Local averaging methods
• Chapter 7: Kernel methods
• Chapter 8: Sparse methods
• Chapter 9: Neural networks

Matlab code

Generic helper functions

• affine_fit.m
• sq_dist.m

Chapter 1: Mathematical preliminaries

• Figure 1.1 (expectation of maximum of Gaussian random variables)

Chapter 2: Introduction to supervised learning

• Figure 2.1 (polynomial regression with increasing orders - predictions)
• Figure 2.2 (polynomial regression with increasing orders - errors)

Chapter 3: Linear least-squares regression

• Figure 3.1 (polynomial regression with varying number of observations)
• Figure 3.2 (convergence rate for polynomial regression)
• Figure 3.3 (polynomial ridge regression)

Chapter 4: Empirical risk minimization

• Figure 4.1 (convex surrogates)
• Figure 4.2 (optimal score functions for Gaussian class-conditional densities)

Chapter 5: Optimization

• Figure 5.1 (gradient descent on two least-squares problems)
• Figure 5.2 (comparison of step-sizes for SGD for the support vector machine)
• Figure 5.3 (comparison of step-sizes for SGD for logistic regression)

Chapter 6: Local averaging methods

• Figure 6.2 (regressogram in one dimension)
• Figure 6.3 (k-nearest neighbor in one dimension)
• Figure 6.4 (Nadaraya-Watson in one dimension)
• Figure 6.5 (learning curves for local averaging)
• Figure 6.6 (locally linear partitioning estimate)

Chapter 7: Kernel methods

• Figure 7.2 (minimum norm interpolator)
• Figure 7.3 (comparison of kernels)

Chapter 8: Sparse methods

• Figure 8.1 (regularization path)
• Figure 8.2 (comparison of estimators) + script_model_selection.m + script_model_selectionROT.m

Chapter 9: Neural networks

• Figure 9.1 (global convergence for different numbers of neurons) + launch_training_relu_nn.m
• Figure 9.2 (random features - kernels)
• Figure 9.3 (neural networks fitting)