Generalization I

on YouTube ↗01h 17m

" summary

Proves a concrete generalization claim: the perceptron update makes at most 1/γ^2 mistake bound on any sequence with margin γ, and a one‑pass run yields expected error ≤ D^2/(γ^2 N); repeated passes plus leave‑one‑out give the final separator the same rate. Tools are the elementary telescoping norm proof, online updates, and empirical‑process supremum bounds (sup over loss class). Assumptions are IID data, bounded inputs and a nonzero margin; overparameterization and zero training error still generalize under these conditions.

AI-written summary · about

" chapters (5)

1. 0:00Introduction
2. 2:20Generalization
3. 28:11Perceptron
4. 48:04Remarks
5. 56:30Questions

" related talks

• 41mGeneralization Bounds for Uniformly Stable AlgorithmsVitaly Feldman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 07mTheory of Computation IIChristos Papadimitriou · The Brain and Computation Boot Camp
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 01h 20mThe elusive generalization: classical bounds to double descent to grokkingMisha Belkin · Modern Paradigms in Generalization Boot Camp 2024
• 46mSketching for Proving Generalization of Support Vector MachinesKasper Larsen · Sketching and Algorithm Design 2023
• 45mFollow the Leader with Dropout PerturbationsManfred Warmuth · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 54mA Curious Case Of Symmetric Binary Perceptron Model: Algorithms And BarriersDavid Gamarnik · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 42mA Primal-dual Analysis of Margin Maximization by Steepest Descent MethodsMatus Telgarsky · Frontiers of Deep Learning 2019