Research map / Learning theory and algorithms / Prediction and decision losses
How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies binary classification with starshaped polyhedral decision regions supported on a fixed simplicial fan, giving VC dimension bounds and loss-landscape geometry for the 0/1 loss and a concave log-likelihood loss.
Problem
Binary classification with flexible yet structured (possibly nonconvex) decision regions; understanding expressivity and the geometry/combinatorics of the loss landscape for starshaped polyhedral classifiers.
Approach
Classifiers are continuous piecewise-linear functions linear on each cone of a fixed complete simplicial fan, with the decision region being a star; the 0/1 loss is constant on chambers of a data hyperplane arrangement, and the exponential-CDF log-likelihood is concave in the parameters a, enabling convex optimization.
Key results
- On synthetic 2D data with an 8-ray fan, the star classifier reaches accuracy 0.852 at lambda approximately 0.83, versus 0.824 for a ReLU network and 0.78 for an RBF SVM.
- VC dimension of starshaped classifiers on a fixed fan with n generators equals n.
- The log-likelihood loss is concave in the parameters a, so superlevel sets are convex and the optimum is computable in polynomial time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the 8-ray starshaped classifier instead of the strongest reported baseline, the ReLU neural network | Binary classification on two-dimensional synthetic data · Two-dimensional synthetic data | accuracy: 0.824 -> 0.852 | Helped |
| refine the original 8-ray fan by adding one ray (ablation) | Starshaped classifier · Two-dimensional synthetic data | accuracy | Helped |
| coarsen the original 8-ray fan by removing one ray (ablation) | Starshaped classifier · Two-dimensional synthetic data | accuracy | Hurt |
Surprising findings
- The 0/1 loss along the line of optima a*(lambda) is not unimodal in lambda, going up and down repeatedly.
- Sublevel sets of the translational 0/1 loss can be disconnected, and the extended 0/1 loss sublevel sets are not necessarily path connected.
Limitations
- Purely theoretical; experiments only on small synthetic 2D data.
- The simplicial fan, translation vector, and rate parameter lambda must be chosen a priori with no systematic selection method.
- The 0/1 loss is hard to optimize globally due to combinatorial complexity.
Experimental setup
Datasets: synthetic 2D data (500 points sampled in unit disk, 90% label accuracy)
Benchmarks: synthetic 2D dataset
Metrics: accuracy
Baselines: SVM (linear kernel) SVM (polynomial kernel) SVM (RBF kernel) SVM (sigmoid kernel) logistic regression ReLU neural network
Builds on: polyhedral classifiers kite fans Coxeter fan of type B
Closest papers by meaning
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification (NeurIPS 2025 · similarity 0.85)
- The Star Geometry of Critic-Based Regularizer Learning (NeurIPS 2024 · similarity 0.83)
- Decomposition Polyhedra of Piecewise Linear Functions (ICLR 2025 · similarity 0.83)
- Hyperbolic Embeddings of Supervised Models (NeurIPS 2024 · similarity 0.82)
- Realizable $H$-Consistent and Bayes-Consistent Loss Functions for Learning to Defer (NeurIPS 2024 · similarity 0.82)
- A Universal Growth Rate for Learning with Smooth Surrogate Losses (NeurIPS 2024 · similarity 0.82)
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.