Fast Random Feature Expansions for Nonlinear Regression
Channel: David Duvenaud
Date: 2014-01-18

0:01 The theoretical aspects of the random projection method
49:00 The practical part of the tutorial starts.
1:08:53 Explanation of the Fastfood algorithm

A tutorial given to the Cambridge Machine Learning Group by 
David Lopez-Paz
http://people.tuebingen.mpg.de/dlopez/
and
David Duvenaud
http://mlg.eng.cam.ac.uk/duvenaud/

The first half derives the Johnson-Lindenstrauss Lemma, which states that one may randomly project a collection of data points into a lower dimensional space while preserving pairwise point distances. 

The second half discusses recent developments that have gone even further: non-linear randomised projections can be used to approximate kernel machines and scale them to datasets with millions of features and samples.

Slides available at:
http://mlg.eng.cam.ac.uk/duvenaud/talks/random-kitchen-sinks-tutorial.pdf

Q.V. Le, T. Sarlos, A.J. Smola. (2013)
Fastfood: Approximating Kernel Expansions in Loglinear Time
http://cs.stanford.edu/~quocle/LeSarlosSmola_ICML13.pdf