Sketching for Proving Generalization of Support Vector Machines

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=QhnqwQUOxsI


Duration: 45:57
224 views
2

Kasper Larsen (Aarhus University)
https://simons.berkeley.edu/talks/kasper-larsen-aarhus-university-2023-10-09
Sketching and Algorithm Design

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.



Other Videos By Simons Institute for the Theory of Computing


2023-10-11Streaming Euclidean k-median and k-means with o(log n) Space
2023-10-11Capacity Analysis of Vector Symbolic Architectures
2023-10-11Improved Frequency Estimation Algorithms with and without Predictions
2023-10-11Testing Positive Semidefiniteness and Eigenvalue Approximation
2023-10-11Sketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
2023-10-11Sketching and Projecting
2023-10-10Lightning Talks
2023-10-10Memory-Regret Tradeoff for Online Learning
2023-10-09Memory-Regret Tradeoff for Online Learning
2023-10-09Sketching Techniques for Kernel Density Estimation
2023-10-09Sketching for Proving Generalization of Support Vector Machines
2023-10-09Fast Attention Requires Bounded Entries
2023-10-09Randomized Embeddings and Neural Networks
2023-10-09Sublinear Time Eigenvalue Approximation via Random Sampling
2023-10-09Nikhil Srivastava and Venkatesan Guruswami | Polylogues
2023-10-06Machine-Checked Proofs and the Rise of Formal Methods in Mathematics | Theoretically Speaking
2023-10-04A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length pt.2
2023-10-04A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length
2023-10-03The Power of Graph Learning | Richard M. Karp Distinguished Lecture
2023-09-29Incremental View Maintenance: Beyond Worst-Case Analysis II
2023-09-29Incremental View Maintenance: Beyond Worst-Case Analysis I


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Sketching and Algorithm Design
Kasper Larsen