How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
This work addresses theoretical understanding of classification models with nonconvex decision boundaries, offering incremental insights into combinatorial and geometric properties for researchers in machine learning theory.
The paper tackles binary classification using continuous piecewise linear functions with starshaped polyhedral decision boundaries, analyzing their expressivity and loss landscape structure for 0/1-loss and exponential loss functions. It provides explicit bounds on VC dimension, describes sublevel sets as chambers in hyperplane arrangements, and gives conditions for uniqueness and geometry of optima in the exponential loss case.
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 an exponential 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 exponential 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.