# Near-Tight Margin-Based Generalization Bounds for Support Vector Machines

arXiv: https://arxiv.org/abs/2006.02175 · HTML: https://mlsanity.com/paper/2006.02175/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

## Built on by (most cited first, 19 of 19)

- [Federated Learning with Label Distribution Skew via Logits Calibration](https://mlsanity.com/paper/2209.00189/) (2022)
- [Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency](https://mlsanity.com/paper/2402.15926/) (2024)
- [On Margins and Derandomisation in PAC-Bayes](https://mlsanity.com/paper/2107.03955/) (2021)
- [Machine Unlearning: A Survey](https://mlsanity.com/paper/2306.03558/) (2023)
- [Optimal Weak to Strong Learning](https://mlsanity.com/paper/2206.01563/) (2022)
- [Rate-Distortion Theoretic Bounds on Generalization Error for Distributed Learning](https://mlsanity.com/paper/2206.02604/) (2022)
- [Let Go of Your Labels with Unsupervised Transfer](https://mlsanity.com/paper/2406.07236/) (2024)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [WatchGuardian: Enabling User-Defined Personalized Just-in-Time Intervention on Smartwatch](https://mlsanity.com/paper/2502.05783/) (2025)
- [Sample Selection via Contrastive Fragmentation for Noisy Label Regression](https://mlsanity.com/paper/2502.17771/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Tight Generalization Bounds for Large-Margin Halfspaces](https://mlsanity.com/paper/2502.13692/) (2025)
- [Heterogeneity Matters even More in Distributed Learning: Study from Generalization Perspective](https://mlsanity.com/paper/2503.01598/) (2025)
- [Compression Implies Generalization](https://mlsanity.com/paper/2106.07989/) (2021)
- [On the Optimization of Margin Distribution](https://mlsanity.com/paper/2204.14118/) (2022)
- [A Fine-Grained Understanding of Uniform Convergence for Halfspaces](https://mlsanity.com/paper/2605.06004/) (2026)
- [Information-Theoretic Analysis of Next-Token Prediction under Markovian Data](https://mlsanity.com/paper/2609.34731/) (2026)

## Abstract (arXiv)

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 paper, we revisit and improve the classic generalization bounds in terms of margins. Furthermore, we complement our new generalization bound by a nearly matching lower bound, thus almost settling the generalization performance of SVMs in terms of margins.