Sketching for Proving Generalization of Support Vector Machines

Support Vector Machines (SVMs) are among the most fundamental tools for binary classification. In its simplest formulation, an SVM produces a hyperplane separating two classes of data using the largest possible margin to the data. The focus on maximizing the margin has been well motivated through numerous generalization bounds. In this talk, we revisit and improve the classic generalization bounds in terms of margins. Surprisingly, the main tool used is sketching hyperplanes via the Johnson-Lindenstrauss transform.