Tight Generalization Bounds for Large-Margin Halfspaces
Kasper Green Larsen, Natascha Schalburg
2025Year
1Citations
1Top-tier citations
Abstract
We prove the first generalization bound for large-margin halfspaces that is asymptotically tight in the tradeoff between the margin, the fraction of training points with the given margin, the failure probability and the number of training points.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 53be790c-aedd-44c7-94de-48f93282617cCited by top-tier papers1
Ask how each one uses itBuilds on3
- Near-Tight Margin-Based Generalization Bounds for Support Vector MachinesAllan Grønlund, Lior Kamma, Kasper Green LarsenICML 2020 · 27 citations
- Margins are Insufficient for Explaining Gradient BoostingAllan Grønlund, Lior Kamma, Kasper Green LarsenNeurIPS 2020 · 13 citations
- Faster Algorithms for Structured Linear and Kernel Support Vector MachinesYuzhou Gu, Zhao Song, Lichen ZhangICLR 2025
Related papers
- Multiclass learning with margin: exponential rates with no bias-variance trade-offStefano Vigogna, Giacomo Meanti, Ernesto De Vito, Lorenzo RosascoICML 2022 · 3 citations
- Learning general halfspaces with general Massart noise under the Gaussian distributionIlias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos et al.STOC 2022 · 5 citations
- Learning Functions of HalfspacesJosh Alman, Shyamal Patel, Rocco A. ServedioSTOC 2026 · 3 citations
- Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification NoiseIlias Diakonikolas, Jelena Diakonikolas, Daniel Kane, Puqian Wang et al.NeurIPS 2023 · 5 citations
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart NoiseIlias Diakonikolas, Nikos ZarifisNeurIPS 2024 · 8 citations
