Research map / Learning theory and algorithms / Combinatorial and search optimization
An efficient, provably optimal, practical algorithm for the 0-1 loss linear classification problem
Xi He, Max A Little
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| exact 0-1 loss solver (ICE) instead of SVM | linear classifier · UCI HA | training accuracy (%): 72.08 -> 77.03 | Improved |
| exact 0-1 loss solver (ICE) instead of SVM | linear classifier · UCI SP | training accuracy (%): 94.05 -> 94.46 | Improved |
| exact solution instead of approximate | linear classifier · UCI HA, 5-fold test | test accuracy (%): 71.23 -> 74.39 | Improved |
| exact solution instead of SVM | linear classifier · UCI CR, 5-fold test | test accuracy (%): 85.56 -> 83.33 | Hurt |
| exact solution instead of approximate | linear classifier · UCI datasets (5-fold test) | test accuracy | Mixed |
| ICE instead of BnB for 0-1 LCP | exact solver · synthetic N=150, D=3 | wall-clock time: 1.2 seconds vs 10^10 seconds | Improved |
| exact quadratic ICE instead of degree-2 SVM | quadratic classifier · synthetic quadratic data | 0-1 loss: 17 -> 9 | Improved |
| MIP solver (GLPK) vs ICE and BnB | exact solver · synthetic 3D data | run time | Hurt |
Closest papers by meaning
- Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction (ICML 2026 · similarity 0.85)
- Unified Binary and Multiclass Margin-Based Classification (JMLR 2024 · similarity 0.85)
- von Mises-Fisher Loss: An Exploration of Embedding Geometries for Supervised Learning (ICCV 2021 · similarity 0.85)
- Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View (NeurIPS 2020 · similarity 0.85)
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.84)
- Improved Balanced Classification with Theoretically Grounded Loss Functions (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
