How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
Abstract
We consider binary classification restricted to a class of continuous piecewise linear functions whose decision boundaries are (possibly nonconvex) starshaped polyhedral sets, supported on a fixed polyhedral simplicial fan. We investigate the expressivity of these function classes and describe the combinatorial and geometric structure of the loss landscape, most prominently the sublevel sets, for two loss-functions: the 0/1-loss (discrete loss) and a log-likelihood loss function.
In particular, we give explicit bounds on the VC dimension of this model, and concretely describe the sublevel sets of the discrete loss as chambers in a hyperplane arrangement. For the log-likelihood loss, we give sufficient conditions for the optimum to be unique, and describe the geometry of the optimum when varying the rate parameter of the underlying exponential probability distribution.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Pure and Spurious Critical Points: a Geometric Study of Linear NetworksMatthew Trager, Kathlén Kohn, Joan BrunaICLR 2020 · 41 citations
- On the Complexity of PAC Learning in Hilbert SpacesSergei ChubanovAAAI 2023 · 1 citation
- Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable ClassificationMatan Schliserman, Tomer KorenNeurIPS 2025 · 1 citation
- Structure of universal formulasDmitry YarotskyNeurIPS 2023 · 2 citations
- Towards Lower Bounds on the Depth of ReLU Neural NetworksChristoph Hertrich, Amitabh Basu, Marco Di Summa, Martin SkutellaNeurIPS 2021 · 70 citations
