How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912741957042176 |
|---|---|
| author | Brandenburg, Marie-Charlotte Jochemko, Katharina |
| author_facet | Brandenburg, Marie-Charlotte Jochemko, Katharina |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01346 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets Brandenburg, Marie-Charlotte Jochemko, Katharina Machine Learning Discrete Mathematics Combinatorics Metric Geometry 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. |
| title | How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets |
| topic | Machine Learning Discrete Mathematics Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2505.01346 |