Daniel Hsu | Notes

Here are some notes I've written. Some have not been subjected to any scrutiny whatsover, so I welcome suggestions, corrections, and other comments.

Scribe notes

These are notes taken from lectures by others.

The spectrum of the Laplacian: Facts about the (normalized) Laplacian of a graph. For Math 261A, Fall 2005. The lecture is by Fan Chung Graham. This note is part of a collection maintained by Paul Horn.
Pigeons, primes, and probabilistic algorithms: The "plentiful pigeons" technique as applied to verifying straight-line arithmetic programs. For CSE 203A, Spring 2006. The lecture is by Russell Impagliazzo.
PAC learning: Some elementary reductions in PAC learning. For CSE 291, Fall 2006. The lecture is by Sanjoy Dasgupta.
Uniform convergence: Handwritten (scanned) notes from an introductory learning theory course. For CSE 291, Fall 2006. The lecture is by Sanjoy Dasgupta.

These are other notes written by me.

A note on the label complexity of the Cohn-Atlas-Ladner selective sampling method: An analysis of the label complexity of the active learning strategy due to Cohn, Atlas, and Ladner (1994) in terms of Hanneke's disagreement coefficient (2007).
Approximating finite metrics by distributions over tree metrics: On the paper "A tight bound on approximating arbitrary metrics by tree metrics" by Fakcharoenphol, Rao, and Talwar (2003). Lecture given in CSE 254, Winter 2007. A bonus (sort of): solution to Exercise 1.
Kernel PCA and LDA: On kernelizing PCA and LDA (Mika et al, 1999; Schölkopf, Smola, and Müller, 1998). Lecture given in CSE 291, Spring 2007.
Note on sparse signal recovery: On the paper "Decoding by linear programming" by Candes and Tao (2005). Lecture given in August/September 2007.
Note on the Frank-Wolfe algorithm: On the paper "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm" by Clarkson (2008), which is a truly excellent paper.

These are probably useless.

Gel'fand and Kolmogorov $n$-width duality: Duality relation between Gel'fand and Kolmogorov $n$-widths.
The multivariate Gaussian distribution in exponential form: Derivation of the Gaussian exponential form and corresponding Bregman divergence.