Topic: Efficient approximations of kernel functions

Background required: Probability theory, linear algebra.

- Lecture 1. Motivation: Support vector machines; introduction to positive definite kernels. 14 Jan 2020.
- Lecture 2. Some basic properties of positive definite and conditionally negative definite kernels. [BCR84] pages 67-69. 22 Jan 2020.
- Lecture 3. Some basic properties of p.d. and c.n.d. kernels continued. [BCR84] pages 69-70. 29 Jan 2020.
- Lecture 4. Relationships betwed p.d. and c.n.d. kernels. [BCR84] pages 71-75. 12 Feb 2020.
- Lecture 5. Basic functional analysis: Inner product spaces and norms. Mainly from [Heil06]. 19 Feb 2020.
- Lecture 6. Hilbert spaces; A Mercer theorem for finite sets; Reproducing Kernel Hilbert Spaces. 26 Feb 2020.
- Lecture 7. Random Fourier Features. [Tu16]. 4 Mar 2020.
- Lecture 8. Characterstic functions and Bochner's theorem; The Cramer-Chernoff method for concentration of random variables; Hoeffding's inequality; A tail bound for Random Fourier Features. [BLM16,Tu16]. 12 Mar 2020.
- Lecture 9. (Video Lecture) Matrix theory background; A Cramer-Chernoff-like bound for random matrices. [Tropp14]. Uploaded 14 May 2020.
- Lecture 10. (Video Lecture) The Matrix Bernstein Inequality; Matrix sampling estimators; An error estimate for Random Fourier Features. [Tropp15]. Uploaded 21 May 2020.

- [SS01] Bernhard Scholkopf and Alexander J. Smola. Learning with Kernels Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, 2001.
- [NM19] Andrew Ng, Tengyu Ma. Support vector machines, Lecture notes for
*CS229: Machine Learning*, Stanford University, 2019. - [BCR84] Christian Berg, Jens Peter Reus Christensen, Paul Ressel. Harmonic analysis on semigroups: Theory of positive definite and related functions, Springer, 1984.
- [Heil06] Christopher Heil. Chapter 1: Hilbert Spaces, Functional Analysis lecture notes, 2006.
- [Tu16] Stephen Tu. Discussion 12: A discussion of random Fourier features. Discussion Notes for CS189 Fall 2016, Stanford University, 2016.
- [BLM16] Stephane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2016.
- [Tropp15] Joel A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learn., 8(1-2):1–230, May 2015.

- Each student will be expected to scribe at least one lecture. This
will involve taking careful and complete notes during the lecture and
then typing them out in latex.

- Please download the template file and the
latex class file that will be needed.

- The first draft of the notes will be due three days after the lecture. This will
have to be emailed either to me.

- I will return
the draft with comments and, three days after that, a final version will
have to be made and submitted with all the required changes
incorporated.

- Here are some general
guidelines which may help you with scribing class notes. Please
read them before you begin typing.

- Also the tex source for some notes scribed in a previous course are available for your reference: lecture 1 and lecture 4 of CSL863, I Sem 2007-08 (local access only.)
- Some latex tips here.

Amitabha Bagchi