COV883: Special Module in Theoretical Computer Science
Topic: Efficient approximations of kernel functions

II semester: 2019-20

Amitabha Bagchi

Next class: TBA.


Kernel functions play an important role in machine learning, especially in classification settings. In this course we will study some of the basic properties of kernel functions and their uses in classification in order to understand better the efficient kernel approximation methods of Rahimi and Recht (NIPS 2009).


Kernels and their role in classification and pattern analysis, Functional analysis refresher including the Reisz Representation Theorem, Mercer's theorem with (partial) proof, Bochner's theorem, light introduction to matrix concentration inequalities, kernel approximations.

Background required: Probability theory, linear algebra.

Lecture record

Lecture notes. Updated 4 May 2020.

Texts and other supplementary material


Evaluation will be through scribing class notes.


Amitabha Bagchi