Perceptron and Online Learning

Status: placeholder — write lecture notes here before teaching.

Goals¶

• Linear separators

• The perceptron update rule

• Perceptron convergence theorem (idea)

• Online learning mistake bound (sketch)

• Connection to gradient descent / SGD (see the notebooks in this folder)

Outline¶

1. Linear score functions

2. Perceptron algorithm

3. Why it converges on separable data

4. From batch to online updates

5. Demo: 2D perceptron vs kNN

Sources¶

• Blum, Hopcroft, Kannan, Foundations of Data Science, Ch. 12–13 (selected)