Lune

NeurIPS2025Top-tier venue

How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets

Marie-Charlotte Brandenburg, Katharina Jochemko

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Pure and Spurious Critical Points: a Geometric Study of Linear NetworksMatthew Trager, Kathlén Kohn, Joan BrunaICLR 2020 · 41 citations
  2. On the Complexity of PAC Learning in Hilbert SpacesSergei ChubanovAAAI 2023 · 1 citation
  3. Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable ClassificationMatan Schliserman, Tomer KorenNeurIPS 2025 · 1 citation
  4. Structure of universal formulasDmitry YarotskyNeurIPS 2023 · 2 citations
  5. Towards Lower Bounds on the Depth of ReLU Neural NetworksChristoph Hertrich, Amitabh Basu, Marco Di Summa, Martin SkutellaNeurIPS 2021 · 70 citations
Dusk over the sea between two cliffs drawn in fine vertical lines