How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets
Authors: Marie-Charlotte Brandenburg
Katharina Jochemko
Venue: NeurIPS 2025 poster ()
Keywords: binary classification
starshaped polyhedral sets
VC dimension
convex optimization
sublevel sets
polyhedral geometry
Primary area: theory
TL;DR: We describe the geometry and combinatorics of the parameters of 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.

How to Learn a Star:
Binary Classification with Starshaped Polyhedral Sets
Marie-Charlotte Brandenburg Ruhr Universität Bochum Universitätsstr, 150, 44801 Bochum, Germany marie-charlotte wtt.ecchaarlottt..brrrduuuuuuuu de
Katharina Jochemko
KTH Royal Institute of Technology 100 44 Stockholm, Sweden
jochemko@kth.se
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 fusstiunction::: the 0/1-loss (discrete loss) and a log- 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 hyperplane arrangement. For the log-likelihood loss, we give sufficient conditions for the optimum to unique, and describe the geometry of the optimum when varying the rate parameter of the underlying exponential probability distribution.
Introduction
We study the problem of binary classification from a geometric and combinatorial perspective. Given a finite laheled data-set and a prescribed loss-function, we focus on characterizing the structure of those parameters that yield perfect classification namely, the set of global minimizers of the loss function. More generally, we investigate the geometry and combinatorics of the entire loss landscape in parameter space. Understanding the geometry is central to analyze the behavior of learning algorithms, as, for example, the arrangement critical points and the connectivity of minimizers influence optimization efficiency and generalization. Combinatorial structures, such as polyhedral decompositions, provide insights into how parameter spaces partition into regions of similar behavior. Naturally, these subdivisions interact with the subdivision into of classifiers which induce the same classification on the data, and is therefore intimately related to the VC dimension (the Vapnik- Chenvii-Cerooseniss dimension) of binary classifiers [Vapnik and Chervonenkis 1971].
In order to make rigorous statements, we fix the function class used for classification to be class which is suitable for the specific learning task. Fixing a large set classifiers can lead to practical difficulties due to the complexity of the space of allowed classifiers, while small set of classifiers may not able to capture the nature of the underlying problem. A natural function class consists of those functions whose decision boundary the geometric object separating the two classes is the boundary of a convex polyhedron. Such function classes have been previously considered, for example, in Astorino and Gaudioso [2002), Manwani and Sastry (2010) and Kantchelian et al. (0014) where the optimal separating convex polyhedron is found through iteratively solving LPs, minimizing logistic loss function and finding large margin convex separator, respectively.
While polyhedral classifiers form a well-structured function class, they are also highly restrictive. In particular, the region enclosed by the decision boundary is necessarily convex, which may not always align with the structure of the underlying classification problem. Maintaining the piecewise
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Figure 1: Two identical classifications of points by different starshaped polyhedral sets, supported on the same polyhedral fan with 8 generators in RR?.
linear nature, but allowing non-convex functions, we consider a class of piecewise linear functions whose decision boundaries are (possibly nonconvex) star-shaped polyhedral sets, supported on fixed polyhedral fan. Fixing the polyhedral fan makes this tractable and learnable class of functions whose space of parameters exhibits nice geometrie structures we show. Considering these function classes generalizes the approach in [evikalp and Triggs [207]] where kites are used for solving visual object detection and multi-class discrimination.
Our family of star-shaped classifiers falls within the broader class continuous piecewise- linear functions, and such can be represented by suitably structured ReLU network. However, the powerful flexibility of ReLUU networks makes it challenging to enforce specific geometric properties, such ensuring that the decision region satisfies star-convexity. Moreover, the parameter space of general ReLU neural networks admits undesirable combinatorial and geometric properties such as disconnectedness and local non-global minima even for separable data [Bandenburg al.) (2024). In contrast, by building our classifiers directly on a fixed simplicial fan, we retain the ability to model non-convex boundaries and yet maintain high control over the shape and connectivity of the decision regions.
We focus on classification with polyhedral starshaped sets with respect to two loss functions: the 0/1-loss (or discrete loss) allows us to study the parameter space in a combinatorial fashion using polyhedral methods. Additionally, consider log-likelihood loss fanction, which is amenable to numerical optimization methods, and whose level sets carry convex-geometric structures.
1.1 Our contributions
In this article, we consider binary classification restricted to a class of continuous piecewise linear functions whose decision boundaries are (possibly nonconvex) starshaped polyhedral sets. More precisely, for a fixed simplicial polyhedral fan we consider the class of functions whose restrictions to each cone in the fan is linear.
Geometry of the parameter space. We initiate the geometric study of the space of parameters defining the classification by polyhedral starshaped sets, and show that binary classifications with this model correspond to chambers in the data arrangement, a hyperplane arrangement within the parameter space. Investigating the expressivity of such starshaped polyhedral classifiers, we show that the VC dimension equals the number of rays in the fan, quantifying how the number of linear regions of the classifier impacts sample complexity.
Geometry of sublevel sets. We examine the effect of the choice of the loss function explicitly on two concrete loss functions, and contrast how the geometry induced by these different losses governs optimization. We show that the sublevel sets of false positives and false negatives are starshaped sets

---

in the parameter space, and. in case of perfect separability, sublevel sets with respect to the discrete loss are starconvex sets, For the log-likelihood loss we show concavity, and consequently convexity holds for its superlevel sets, implying that an optimum can be found in polynomial time. 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.
Extended parameter spaces. While most of our results focus on starshaped sets with fixed origin, we also consider starshaped classifiers where we allow translation of the origin, and consider the translation vector as an extra parameter. For fixed starshaped set and varying translation vectors, we show that the discrete loss constant on chambers in an arrangement of stars, but the sublevel sets are generally no longer starconvex. While this setup combined with the log- rggliiklihood loss does in general not lead to convex program, we show that the log-likelihood function is piecewise concave on the underlying data fan arrangement.
Finally, we allow to simultaneously vary the shape of the and the position of the origin. In this case, the sublevel sets of the discrete loss are semialgebraic sets, i.e., finite unions and intersections of solutions to polynomial inequalities, and we show that they are not necessarily path connected. We also explore the expressivity of this larger family of translated starshaped classifiers and show that the VC dimension (d log2(d) logz (k)) if d the dimension of the ambient space and the number of maximal cells in the fan.
1.2 Limitations
Throughout the article. we assume a fixed simplicial fan as given. In practical applications, an appropriate fan suitable for the specific task needs to be chosen prior to the analysis. We emphasize that this paper is purely theoretical contribution. The presented framework has not been tested on large-scale synthetic or real-works data, only small-scale experiments as presented in the end of this article have been conducted. Developing a systematic or heuristic approach for selecting parameters such as the simplicial fan, a translation vector the rate parameter, is beyond the scope of this work.
2 Description of the model
2.1 Polyhedral geometry and stars
We begin by introducing essential notions from polyhedral geometry, and the class of classifiers consider. For a thorough background on polyhedral geometry we refer the reader to [Ziegler 2012 Chapters 1-2]. Examples and visualizations of polyhedral fans are given in Appendix A
Definition 2.1.
S Rd is star-convex with respect a center line segment [o, s) = {uo + (1 4)s 0 S < 1} is contained in S. In particular, set is conver it star-convex with respect every S.
S for every s S, the
Definition 2.2. set C nd is a polyhedral cone if
C =
MI.:M...... 1C E Rgo
for vectors Vi...., Vv E IR, k The vectors (vilsvss are called generators of C. We use the notation C cone(V1..... Vk. for cone with these generators. If C is generated by linearly independent vectors then is called simplicial.
Definition 2.3. A hyperplane {x E Rd (h. x) = a} is a supporting hyperplane of the cone C' (h, v) for all points v C. A subset F C C is called (proper) face if F C' n H for some supporting hyperplane H.
Definition 2.4. collection of polyhedral cones called a polyhedral fan the following two conditions are both satisfied.
(i) If C' E A then also every face of C' is in A.
iii If C1, C2 e A then C1 in C22 is face of C₁ and C2-
3

---

Moreover, A is called simplicial fan if it contains only simplicial cones. It is further called complete if the union of all cones it contains is R". cull-dimensional cone of complete fan is maximal cone. The collection of generators of all cones in the fan are called the generators of the fan.
Intuitively speaking, fan is collection of cones that fit together nicely. Examples of two well-knnwn classes of simplicial fans, namely kite fans and Coxeter fans of type B, are given Appendix [AI]
In the following, let A always be complete, simplicial fan with generators {V: Further below we will also consider affine translates of A consisting of translated cones of the form C + where C' is a cone and E IRd is fixed translation vector.
Proposition 2.5. For every vector (aq..... ... .o,) E IR there is a unique function f RR such that A (v:)= = for 1 S i S and the restriction fa lc is linear for any cone C' C.A.A
Indeed, for any x E Red there is a unique cone E with generators Vi....; Via such that x = Mi Vi, +
Mix Vi, E C and Mig > O for all 1 S S k. If C is full-dimensional cone, then == and Vc = (Vi,... ...) is an invertible square matrix such that Ve (Hi,... .ia) = x, so Vo'x= (Ki, ... Mia)² ( Defin μ4j == O for j (1..... n) fdi...., it We write [x] E I for the vector (J11,... (2)) expressing x as positive linear combination of the generators of the cone of A that it lies in. We will sometimes simply write x] when the fan A is clear. For exemplifying computations of [x]= when A is the kite fan or the Coxeter fan of type B, we refer to Appendix A. Since f (v:,) di, for 1 S S ki the linearity of f lc implies
fa (x) = [[x] a) = u4, 0, +... + Uig Oic
Let X = ((x(1, b HO c Rd x {0, 1} be a binary labeled dataset. Define the (m x 1) -mtrrxx Ax to be such that the ith row is [=. Then evaluating Ax a results in a vector whose ith entry is fA (x))). Observe that since A is simplicial, the matrix Ax is sparse in the sense that there are at most d non-zero entries in every row.
We consider the task of finding a classifier e: Rd + {0, 1} that predicts y well given x(0 Given a complete, simplicial fan A, consider the of functions
s
U/=: Rd + a E 1R
Each function L a 0, defines a classifier IRd + 10 by setting
0 if fx) 11
cx(x)
[1
otherwise.
The classification according to Ca is the vector (ca (c=(x())...... .....
(x((x)))) (x.,'))"". we also denote the set of all classifiers ca. a 2 0 by SA, The 0-class c, (0)) is enclosed in a star- shaped set. Indeed, it is the union of simplices with vertex sets of the form {0, asg Via...., 1 via asg where Vi....... Vie are the generators of a cone of A. We call this a star and denote as (D).See
By slight abuse of notation
star(a) ca (D). See Figure for examples.
A data point (x()), ()) has positive label if y( = 1 and negative label if (()) = 0. A point (f) is a false positive with respect to a if fa (x(+) ) > 1 and y( = O. Similarly, the data point x is false negative with respect to a if fá (x(+) < 1 and ( = 1. We denote the number of false positives and false negatives by (P( and FN(a), respectively.
2.2 Loss functions
In this article, we consider minimization with respect to two distinct loss functions: the 0/1 0/1-loss and log- likeliood loss function. For the 0/1-loss (or discrete loss), seek to minimize the number of misclassifications, counting both the false positives and false negatives, i.e.
err( (a) = FP + FN(a).
For the log-likelihodd loss function, let y be the random variable giving the class label of the random vector x E IRd. We approximate the probability that x is not in the star with the cumulative distribution function of the exponential probability distribution.
P(y = 1 1 A, a) 1-e 21

---

where À > 0 is the rate parameter of the exponential distribution. The task is to find a E Rşo that maximizes the log- likelihood function
m III Ply 1/x(0) A, a) (1 (1- P(v 1/x/=1/>0)/ A. 1100)12100 1-0
((a) log
(2)
Σ (( log (1 - -1---122(x(()) + (1-1)))()
1=1
We observe that Ply 1|x, A. a) approaches 0 when approaches 0, i.c. is in the set star defined by Ca. and when x approaches infinity, i.c. is outside the star.
Note that, in principle, one can choose to approximate P(y 1|x, A, a) with any function F(fa (x)) were is cumulative distributive function on Rzo. The choice above will be justified by its desirable properties shown in the following sections.
Geometry of the parameter space
In this section we study the set of optimal parameters R as well as the sublevel sets of the 0/1-loss (1) and the loss function given by the log-likelihood function (2) from combinatorial and geometric point of view. We begin by analyzing the expressivity of the classifier, i.e., we determine the VC dimension of the set of classifiers S Recall that a dataset is shattered by a class of binary classifiers if for any possible labeling of the data there classifier in the class that produces the same labeling. The VC dimension of the class of classifiers is the maximal size of a dataset that can be shattered by the class of functions.
Theorem 3.1. Let A be a simplicial fan with n generators. Then the VC dimension of the set of classifiers S equal n.
3.1
Geometry of the 0/1-loss
We seek to understand the geometry inside the parameter space Ry (a 03. For example which illustrates all definitions and results stated in this and the following subsection (Sections 3.] and 3.2 we refer Example A.3 in Appendix A.2
Given unlabeled data point x (1) we associate the classification hyperplane
x {a E R5o S (x())) = 1) (a ([x()),,a 1),
which separates parameters a inducing a classifier ca with ca (x(()) = 0 from the ones with ca (x(
1. These hyperplanes define the data arrangement
Hx =
U
Hx
(x(().g()))
13
0.
04-
03-
02
00
0.4
(a) A star and points in IR.
Level err(a)
(c) Level sets of C(a)
Figure 2: An example of 1-dimensional dataset, perfectly classified by star supported on fan with rays, and the level sets of the two loss functions parameter space R3 This example explained in detail in Appendix[A.. A.2
5

---

The data arrangement subdivides the ambient space 1500 into (possibly empty) half-open chambers ie., subsets of the form
C(X (')x
n {a E 1250 (x 1 n n {a R5 f2 (x
(x0
(x00)
where X X is any partition of X. By construction, the data arrangement has the following properties.
Proposition 3.2. The half-open chambers of the data arrangement are in bijection with classifications of the dataset. More precisely, each half-open chamber is the set of vectors whose induced classifiers agree on the dataset.
A direct consequence of Proposition 2 is that the false positives, the false negatives and thus also the discrete loss is constant on the half-open chambers. In general, since every chamber is convex and corresponds
unique classification, the set of all parameters that perfectly separate the data points is convex.
Corollary 3.3.
The discrete loss function crr(a) is constant on the half-open chambers of the data arrangement. The purameters for which ca perfectly separate X form convex set.
For any function g: RR"" - Zzo and Zzu. the k-th level set of g, denoted L(g. k), consists of all parameters a E R" with g(a) k. Further, the k-th sublevel set, denoted Sig. k) is defined as ((g, k) U L(g. i). In particular, all the (sub)level sets of the discrete loss function, L(err, k), are unions of half-open chambers. Distinguishing further between false positive and false negatives, we obtain the following geometric structure of their sublevel sets.
Theorem 3.4. The sublevel sets of FP and FN are star-convex sets with star center 0 and co, respectively. That for all a, E 8
(i) FP(a)= & FP(a +
(ii) FN(a) 2 FN
Corollary 3.3 implies that if the dataset separable, i.e., if L(err, 0) A 0, then the set of perfect classifiers L err, 0) is a convex set. Under the same assumption, we can make similar statement as Theorem B about the sublevel sets of the discrete loss function.
Theorem 3.5. Let Ca be classifier that perfectly separates the dataset X, i.e. let Ca L(err, 0), and let ab E ((er,kk). Then for every E |a, b) holds ca E S(erI, k). In particular, the sublevel sets S(err, k) are star-convex and connected through walls of co-dimension for every k.
Theorem 3.5 shows that if the data separable, then the sublevel sets of err are star-convex, but not AA33In
necessarily convex in the usual sense (see also Example A.3 in Appendix (A.)). A the case of non-separable data, sublevel sets and even the set of minimizers of the discrete loss can be disconnected. One example for this scenario is the point configuration from Example A.3 with labeling 0, 0, 1, 1, 1, 1, O, O. Here, the minimum of the discrete loss-function is 4, attained in four non-neighboring half-open chambers.
Much stronger, in
To summarize the results this subsection, our geometric analysis reveals that sublevel sets under the 0/1-loss decompose into convex chambers within a hyperplane arrangement (Corollary 3.3) while simultaneously exhibiting star-convexity with respect to any optimal point in the chamber which minimizes the loss (Theorems 3.4 and 3.5). These theorems establish that while global optimization over the 1 loss is hard due to the combinatorial complexity of the overall non-convex landscape, the local landscape is well vell-connected. In particular, for separable data these results show that local optimization methods can between neighboring chambers along straight lines, improving in each step without getting stuck at local minima. For non-separable data, similar behavior is still exhibited by false positives and false negatives.
3.2 Log-likelihood loss
In Section 3.1
we have observed that the 0/1-loss discrete loss admits discrete geometric structures in the parameter space which are governed by an affine hyperplane arrangement. However, the discrete loss function is difficult to compute in practice. We thus propose alternative loss- function

---

for practical purposes. The log- log-likelihood loss function turns out to be well- for optimization procedures due to concavity. The definitions and results stated in this subsection are exemplified in Example A.3 in Appendix A.2
Theorem 3.6. The log- ge-llikliihod C(a) is concave. In particular. any local maximum is global maximum.
The computation of the maximum likelihood estimator, the maximizer of the log-likelihood loss- function, can be summarized by the following algorithm.
Algorithm 1 Computation of the maximum likelihood estimator
Input: A, X = ((x(1) )))
Output: a
1: determine Ax
2: solve argmaxa>0 E y log (1 e E-Axxaaa) + +11 (1- (1-))))(-A)(Ax))))
Convex (and thus also concave) functions can be optimized in polynomial time. Moreover, the description in Section [ implies that Ax can be determined in polynomial time. This implies the following.
Corollary 3.7. Algorithm can be computed in polynomial time in the size of the input data.
Strictly speaking, for Algorithm D to be a convex program, we need to consider the closed positive orthant. Any solution on the boundary corresponds to degenerate star, where star-defining points on rays move to infinity. This degenerate case will be treated in Theorem 3.9
Similarly to Section 3.1 we now consider the superlevel sets of the log- ligelikelihood loss. For given I IR the superlevel (c) of C is defined as
Sc(t) (a E RRo: L(a)= 2 21}.
The following a direct consequence of the fact that concave. Corollary 3.8. The superlevel sets Sz(l) are convex sets for all R.
We now analyze cases in which the maximum of the log- ligeliieddoood loss is unique. For this, consider the positively labeled subdataset X, (x(*) y =)
) C X and let Ax, be the submatrix Ax composed of all rows [x( corresponding to ()) E X1; similarly we define Axo for Xo = X X1. Then we have the following sufficient condition for a unique maximum of L(a).
Theorem 3.9. The log- ligeelkod loss function L(a) is strictly concave if the matrix Ax, has rank n. Furthermore, if also the rank of Ax, equals n, then C(a) has a unique (possibly degenerate) maximum in the closed positive orthant R2
Matrices of the form Ax also appear in the study of reconstruction of polytopes with fixed facet directions from support function evaluations. Dostertt and Jochemko [2023] showed that such reconstruction of polytope is unique if and only if rank Ax = In other words, Ax E (Rexm)) where V the algebraic variety encoding that rank Ax < n. In partieular, it is sufficient that each interior of maximal cell of A contains a data point, possibly after adding minimal noise. From Theorem 3.9 together with Dostert and Jochemko [2023] Corollary 14] we obtain the following sufficient condition the uniqueness of the maximum of L(a).
Theorem 3.10. Let Xo and X, be sets of noisy data labeled with 0 and respectively, and such that for every maximal cell E è there is at least one data point from X, and X₂ in the interior of a. Then L(a) has a unique (possibly degenerate) maximum in the closed positive orthant 20
Observe that the assumptions in the preceding statement can be considered mild: Given enough data points in generic position it is reasonable assume that the center of the star can always be chosen way such that the condition is satisfied.
Note that the maximizer of C, as well as the number of false positives and false negatives also depends on the choice of the rate parameter X. We now treat as an additional variable and consider the log-li lideelod function C(), a).
7

---

Theorem 3.11. Let X be dataset and Xo > O be rate parameter such that [()o: a) has unique
maximum a" (Aq). Then ((),a) a) has a unique maximum for all > O, denoted a (X), and the
function À -+ a" (X) is straight line inside B² approaching the origin.
Corollary 3.12. Let X be a dataset such that [(), a) has a unique maximum a" for all X
Then
(i) FP (A)) is monotone decreasing in X, and
(ii) FN((" (A)) is monotone increasing
Given the monotonicity of the number of false positives and false negatives in the optimal solution, it is natural to ask if the 0/1-loss, which is given by their sum, is convex in the sense that first decreases and then increases with varying A, without any "ups" and "downs". However, this is in general not the case. A counterexample is given by ExampleA...
4 Geometry of the generalized parameter space
In the previous section, we have considered polyhedral fans whose cones have their apex at the origin, and varied the shapes of the stars defined on this fixed fan. In this section, we extend this framework by allowing translations. Section 4.1 we first fix the shape the star and only vary it by translation, whereas in Section 4.2
we investigate the space of both operations at the same time.
4.1 Translations of a fixed star
Recall that the star of 180o is defined star(a) fx Rd fx( 1}, where fa [[x]*, a). Given translation vector t Rd, we have
star(a) t (x + A 1} fxx t: [[x] a) - 1) fx ([x t 5 (3)
where [x - t] captures the nonzero coefficients f4; such that x = + (4;, Vi, +... Mss Vi, E C'+t, and C A + is the unique cone of the translated fan containing On the other hand, we have
x C +t = xEx-C. C,
where - C fx c C C} is the reflected cone -C translated by the vector x. We first analyze the behavior of |x t] when varying t..
Proposition 4.1. For any x6,, the function + [x(0) - -t}² is piecewise-linead with linear pieces supported on the closed cones of the fan x(6) A. For a fixed a E TR% holds
{t E L.RR. ([x()) ) - t] a) S 1) = star(a) + x()
Given fixed classifier R we can ask about the nature of the translational 0/1-loss function
etra(t) = li fA t) 1,y 1} + Ki fa t) 1, ()) 0}}-
For this, we define an arrangement of stars S1, Si...., Sn C Rd to be the union of all (possibly non-convex) polyhedral sets of the form S n... n S where S E {S Rd {
Definition 4.2. Given a fixed E R8 the data star arrangement of a dataset X = ())) is the arrangement of stars star(a) + x() for i 1,..., m.
An example of the data star arrangement of 2- d-dimensional dataset, together with the level sets of the translational 0/1-loss is given in Example A.4 in Appendix A.3]
Theorem 4.3. The translational 0/1 0/1-loss etr,(t) is constant on half-open cells of the data star arrangement of X.
For fixed classifier a E Pyo we may also consider maximizing the translational log-likelihood function
m (0
Ca(t) = Σ y
log (1-c-
(1 -1--
t)
To describe the behavior of this function, we define an arrangement of (translated) polyhedral fans
A +t....., A + t to be the polyhedral complex consisting of all (necessarily convex) intersections of the form (Cr + t1) (C2 + +2t) ..... (C2+ tx) where C, t, is cone in A; + t.,
8

---

Definition 4.4. Given a fixed a 1250 the data fan arrangement of a dataset X = {(x(()) ())
is the arrangement of fans x()) A for i
Theorem 4.5. The translational log-likelihood function concave on any maximal cell of the data fan arrangement. In particular, t La(t) is piecewise concave function R
4.2 Translations and transformations of the star together
In Section we have considered classification by starshaped polyhedral which E R is fixed (and assumed to be the origin), and varied E R2 In Section 4.1 we have fixed E R5 and varied t E Rd. As final step, we will now vary the tuple (a, t) E IR IR i.e., both parameters simultaneously. and consider the classifiers
5o
-x 11
(x)
11
otherwise.
For fixed cone C A and data point x1),, we consider the sets which contain those tuples (a, t) such that (+) C t, and such that x lies inside or outside star(a) + t, respectively:
(C, {(a, t) eC+t, x (0) Esarr(a) +t}.
x'(C,x0) = ((a.t) x00 EC+t, (() @ star(a)+ +
Proposition 4.6. The sets (C, and (C, x)) are basic semialgebraic sets, iee, finite intersections of solutions polynomial inequalities. More precisely, each of them is the intersection of polyhedral cone with a single quadratic inequality.
We extend the O/1-loss to be viewed a function err t) in variables (a, t) R x Rd In contrast to Theorem 3.5)amm and Theorem 4.3 the (sub)level sets in this extended product of both parameter spaces neither polyhedral nor do they have piecewise-lings
boundary, but they are semialgebraic.
Theorem 4.7. The level sets and sublevel sets of the extended 0/1 O/1-loss on R x RRd are semialge- braic sets, ie., finite unions and intersections of solutions polynomial inequalities. The defining polynomials have degree at most
In the previous sections, the shape of the (sub)level sets immediately implied path-connectedness. However, in this more general framework. this property does not necessary hold.
Theorem 4.8. The level sets of the extended 0/1 llos are in general not path-connected.
end this section by considering the expressivity of our starshaped classifiers, when translation allowed. We give the following upper bound.
Theorem 4.9. For a fixed simplicial polyhedral fan in dimension with maximal cones, the VC dimension of the class of functions {Ca,t: (a, t) R Rdy is in ( loga logz(k)).
5 Experiments
We conducted small-scale experiments where we tested Algorithm I implemented in SageMath 50.5 (The Sage Developers) [024], on two-dimensional synthetic data. The compu- tations were done on MacBook Pro equipped with an M2 Pro chip and 32 GB of RAM. For comparison, also applied several standard binary classification methods leading to convex opti- mization problems on the same dataset, as well as a ReLU neural network. The computation running time ranged from few seconds to one hour.
5.1 Data
Figure Baj iqillusstrtts 500 data points sampled from a given star-shaped region (in green) defined on eight rays. The data was generated as follows: we randomly selected the and y-coordinates of all points from the interval 11, 1) using a uniform distribution and discarded any resulting points (x, v) lying outside the unit circle. This was done to achieve near rotational symmetry of the data set. For each remaining point, we then checked whether it lies inside or outside the star-shaped region. The corresponding label was assigned accordingly, with 90% probability of being correct.

---

Model
Accuracy
SVM sigmoid
0.534
SVM linear
0.718
SVM poly
0.718
Logistic reg
0.718
SVM RBF
0.78
Neural net
0.824
Algorithm
0.852
(a) Synthetic data.
(b) Results.
Figure 3: Synthetic data and accuracy of classification for tested models.
5.2 Results
In the first experiment, we used Algorithm| together with the same eight-ray fan structure to predict the labels of the synthetic data described above. We compared binary classification of our algorithm with multiple standard classification models. In the following we give a description of our results. Illustrations can be found in Appendix
Running Algorithm D on the synthetic data set, the optimal value of the regularization parameter was found to be approximately À 0.83, yielding accuracy of 0.852. The resulting optimal star classifier shown in Figure 10a For comparison, we also tested standard implementations of SVMs (with linear, polynomial, RBF, and sigmoid kernels), logistic regression, and a ReLU neural network with two hidden layers of sizes and 2, respectively. The SVMs with linear and polynomial kemells, well logistic regression, performed poorly, assigning all points the same class, thereby achieving an accuracy of 0.718. The SVM with a sigmoid kernel performed even worse. In contrast, the SVM with RBF kernel and the neural network achieved better results, with accuracies of 0.78 and 0.824, respectively. See Figure for a summary of the results.
In further experiment, we Algorithm D on the same dataset but with different underlying fans as input. Specifically, we considered both refinement and a coarsening of the original fan with eight rays, depicted in Figure 11] In the case of the refined fan, the decision boundary remained almost unchanged and the accuracy improved marginally. For the coarsened fan, the shape of the decision boundary changed considerably and the accuracy became significantly which ray was removed; see Figure 12 for an illustration if the starshaped sets. These results support the following heuristic for fan selection in two dimensions: start with small number of rays and iteratively refine the fan by adding more rays. If the additional rays do not produce significant new dents in the boundary, they can be safely discarded.
depending
6 Conclusion
This article demonstrates that polyhedral starshaped sets constitute promising family of classifiers, striking a balance between convex polyhedral classifiers and general piecewise linear functions - the latter corresponding to the class of functions representable by ReLU neural networks. The results on VC dimensions highlight that this family remains tractable from a statistical learning perspective. This is further supported by the properties of the proposed loss functions, notably convexity and star-convexity of their (sub)level sets. Moreover, the presented framework provides high level of flexibility, particularly due to the ability to freely choose the rate parameter X, which enables manual adjustment of the trade-off between false positives and false negatives as needed.
The presented framework has been tested only very few example data sets in two dimensions. remains an open question how to optimally select the parameters, such the underlying fan, the translation vector and the rate parameter, in manner tailored to the specific problem at hand.
10

---

Acknowledgements
We would like thank Maria Dostert and Mariel Supina for many fruitful discussions. We also want to thank Roland Púček for insightful conversations. MB and KJ were supported by the Wallenberg AI, Autonomous Systems and Software Program funded by the Knut and Alice Wallenberg Foundation. KJ was furthermore supported by grant nr 2018-03968 and nr 2023-04063 of the Swedish Research Council as well as Göran Gustafsson Foundation. MB was furthermore supported by the SPP 2458 "Combinatorial Synergies", funded by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation).
References
A. Astorino and M. Gaudioso. Polyhedral separability through successive LP. Journal of Optimization Theory and Applications, 1 112(2):265-2) 293, Feb. 2002. doi 10.1023/: 1013649221153
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Chenik-Chervonennis dimension. Journal of the ACM (JACM), 36(4):929-96) 965,, 1989.
M.-C. Brandenburg, G. Loho, and G. Montúfar. The real tropical geometry of neural networks for binary classification. Transactions on Machine Learning Research, 2024. URL https //openreview
H. Cevikalp and Triggs. Polyhedral conic classifiers for visual object detection and classification. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4114-4122, 2017. doi 109/CVPR.2017.4.
M. Dostert and K. Jochemko. Learning polytopes with fixed facet directions. SIAM Journal on Applied Algebra and Geometry, 7(2):4004666 2023. doi T0..137/22M1481662
A. Kantchelian, M. C. Tschantz, L. Huang. P. L. Bartlett, A. D. Joseph, and J. D. Tygar. Large- margin convex polytope machine. Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, Cur- ran Associates, Inc., 2014. URL pttttpee//proceiiiggss neurips hwtphippp.cpppp...pcp htcc/paape_ffllesppppeepeee 2001///hhe2222130ccc622222832222
pdf
A. Kupavskii. The VC-dimension of k-vertex d-polytopes. Combinatorica, 40(6))869-874, Nov.
2020. 0001:00:0077/000443-0000--111111
N. Manwani and P. S. Sastry. Learning polyhedral classifiers using logistic function. In M. Sugiyama and Q. Yang, editors. Proceedings of 2nd Asian Conference on Machine Learning, volume 13 of Proceedings of Machine Learning Research, pages 17-30, Tokyo, Japan, 08-10 Nov 2010. PMLR. mlr wwwpprressssse URL htttps:/ http:////pppoooooogoooooe/eee/ap wttps//ee////mmmaaaanna00
html
The Sage Developers, SageMath, the Sage Mathematics Software System (Version 10.5), 2024. URL https://ww..tt. www.:www.wg......c...ooamm.. org
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264 280, 1971. 1 16025
G. M. Ziegler. Lectures on Polytopes. Springer New York, May 2012. ISBN 038794365X.
d0. 1007/978 4613--431111

---

A Examples
A.1 Examples of polyhedral fans (Section 2
Example A.1 (Kites). For S I d, let e; E RRd be the vector with 1 in coordinate and 0 in all other coordinates. The coordinate hyperplanes (x R (e,, x) = 0} divide 12 into chambers, and these chambers along with all of their faces form a simplicial fan & with generators hisica Every star arising from this fan is necessarily convex, and such stars are called kites. Consider the (d 2d) mmarixi Ag (01 as
ca). Given X E Rd, the vector [x] is obtained
C2
C2
x max (0,x*A) AA)
where the maximum is taken coordinatewise. The 2-dimensional fan o and the function [x] restricted each maximal cone depicted in Figure 4a
02
F2
11
22
01
04
05
0
03
372
202
(11 12
V3
0
V4
V3
V2
82
3/2
06
03
V1
V5
04
11 + 12 06
21
+ .72
Vo
VV
0
422
0
02
422
-22
22
05
0g
-I
-T
82 + 21
0
221
(a) The kite fan o.
(b) The Coxeter fan of type B.
Figure 4: The functions
[x] and [x] restricted to the full-dimensional cones of the 2-dimensional
fans from Examples A. and A.2 O denotes the k-dimensional O-vector.
Example A.2 (Type B stars). The coordinate hyperplanes along with the hyperplanes x; Ery for pairs 5 iiis < divide I into chambers, which along with their faces form simplicial fan B with generators {0, #1 {0}. The fan B is known as the Coxeter fan of type B. Let E Rd and let a (1.....d) (1....,d) d} be a permutation such that ( S
x =
[ S ... [d)) Then we have that
x [ + (|zo(2)) (R)())))))
([=a(a)) (xo(d-1)l)vd
(4)
where Vi...., Va generate a cone of B containing x and
V;
sgn (gn(Zza))) (Za())
The vector 8 be recovered from 44 The 2 dimensional fan B and the function [x]
restricted
to each maximal cone depicted in Figure 4b
A.2 Examples of the geometry of the parameter space (Section 3
Example A.3 (Classifications of I-dimensional dataset). Consider the 1-dimensional polyhedral fan with generators Vı = -1, V2 e1, and the 1-dimensional labeled dataset consisting distinct points
12

---

(x ,(t)) (-4.0),
(x y(2)) = (-3, 1), (x(() yy = (-2,1), (x))) (-1,1),
(x (1()) = (1,
(x(6) yy))) = (2, 1),
(x (7) y (3, 0), (x ())) = (4,0).
For R20 we have
1 = (6) and
[z]
The associated data arrangement is depicted in Figure dataset together with the stars associated to the points
5a and Figure
5b
shows the 1-dimensional
2
a2
T4
1
H
Hx
a1
22
Hx
H (0)
32
(1) (2) (3) (4)
x
(0) x()) (()
H (8)
a3
21
4
(b) The dataset and the stars (thick black line) associ- ated a1, ag (top bottom).
(a) Data arrangement Hx.
Figure 5: The data arrangement and dataset from Example A.3
By Proposition 3.2 each half-open chamber of the data arrangement is the set of classification vectors a whose induced classifiers agree on the dataset. Thus, the number of false positives FP(a), the number of false negatives FN(() and the discrete loss function err(a) are constant each of the half-open chambers (cf. Corollary 3.3). Figure 6 shows the values of these functioos and it can be verified that the sublevel sets of FP and (a star-convex with centers 0 and co, respectively (cf. Theorem 3.4). As the data is perfectly separable, Theorem 3.5 implies that the sublevel sets of crr(a) star-convex and connected through walls of codimension as depicted in Figure 6cc
Figure 7 shows the level sets the log-likelihood loss function for the same example, for two choices of the rate parameter X. In accordance to Corollary 3.8 the plots illustrate that the superlevel sets of
2
2
3
4
0
0
3
3
4
5
0
0
2
2
3
4
0
2
0
0
1
2
3
10
2
2
4
2
2
2
3
3
4
5
(a) Number of false positives.
Number of false negatives.
(c) 0/1-loss.
Figure 6: The values of (a(a), FN(() and err(a) on the half-open chambers of the data arrangement for the 1 i-dimensional dataset from Example A.3 The diagonal lines in all three images show the function À + a" (X) defined in Section 3.2
13

---

these functions are convex. Moreover, the rate parameter has an influence on the (unique) maximizer of these functions, but they lie on a line À a* (A), shown in Theorem 3.11
The same line is drawn in Figures 6a 6bb illustrating that the numbers of false positives and false negative monotone increasing and decreasing, respectively (cf. Corollary 3.12). In Figure (6c] the line crosses regions where the 1llsloss has values 3, 2, 3, 2, 3, 2, 3, 4, respectively. This shows that the 0/ 0/1-soss is not "convex" in the sense that the sequence of values of the 0/ 1-loss along this line is unimodal, but goes and down repeatedly.
12
-7.84
1.2
-7.95
-9.36
-10.05
10:
1.0
-00.88
-12.15
0.8
-1.40
0.8
-14.25
13.92
-16.35
0.6
15.44
0.6
-18.45
16.96
20..55
-1848
22.05
-20.00
-24.75
-21.52
-26.85
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.0
0.2
0.4
0.6
1.0
1.2
(a) Level sets C(), a) for 0.5. The maxi-
(b) Level sets of [(A, a) for 2. The maximum
mum is attained at a (0.93, 0.48).
is attained at a = (0.23, 0.12).
Figure 7: Level sets of log-likelihooni loss functions for different choices of on the dataset from Example A.3 The black dot depicts the minimum a' (A), lying on the line of maxima when varying the choice X.
A.3 Examples of the geometry of the generalized parameter space (Section
Example A.4 (Star arrangement). Consider the 2-dimensional labeled dataset X consisting of distinct points
(x ( 1,0,, (x(2), y (2) = (2,2, (x(*), ()) ) = (3, 3,,3300 0),
and let be the 2-dimensional Coxeter fan of type B (cf. Example A.2). which has 8 rays. We fix the star through values
1
a
3, 3,
3
3
3
x33
x(1)
(3)
x
x(1
(a) (2.9.
(b) (0.9,3.05)
Figure 8: The data points from Example A.4 with fixed and two perfect classifiers.
14

---

Figure 8 shows two different translations star(a) + t that are perfect classifiers. Figure 9 shows the associated star arrangement in R and the sublevel sets of the translational 0/1-loss. In particular, in contrast to Theorem 3.5 it can be observed that the 0 level set [eerr,, 0) consists of two full- dimensional connected components. The translated stars Figure X show one example from each of the connected components.
4-
2-
-2-
-2
2
Figure 9: The star arrangement from Example A.4 and the level sets of the translational 0/1 llsss function.
B Experiments
In this section we collect illustrations of the results of our experiments described in Section
(a) Algorithm !
(b) Neural network.
(c) SVM with RBF kerne..
Figure 10: Decision boundaries for Algorithm 1 a neural network and SVM with RBF kernel.
15

---

01
Regular fan rays.
(h) Fan refinement.
Fan coarsening.
Figure 11: Left: Fan on 8 rays (blue) and the supported star (green) used in the generation of the synthetic data; Center: Refinement of the fan with one extra ray, and an example supported star; Right: Coarsening of the fan with one ray removed, and an example of supported star.
(a) Regular on rays.
(b) Fan refinement.
(c) Fan coarsening.
Figure 12: Optimal starshaped decision boundaries for Algorithm 1 with the same underlying fan as the synthetic data (left), refinement of the fan (center) and a coarsening of the fan (right). The underlying fans depicted in Figure II
C Proofs
C.1 Proof of Theorem 3.1
Proof. Let Vi.... v, be the generators of A and let l E f0,1). be arbitrary assignment of 0/1-labels to these generators. Then there exists a classifier Ca E S that assigns the same labels to Viy Vn than E, namely, for O, we
[1 11- (f a; l1t if = 1.
Then (v.) = a; 2 if and only if ((v:) 1, and thus Ca (v:) = ((v:) as claimed, It follows that the set of classifiers shatters the of generators and thus the VC dimension of SA is at least n.
To see that the VC dimension is at most n, we assume that there is set (1). n + 1, ca (x(1))
(n+1) E Rd of
points that can be shattered by SA. By construction, for all In particular, if x(1) ..... (*+1) can be shattered by S then
and only if ([x a)
[ ..... x 1111 can be shattered by the set of half-spaces of the form {x R aTx <
b. 0, ...a...... On 2 0}. This is subset of the set of halfspaces considered in Proposition C.1 below, and
thus we obtain a contradiction by Proposition C.T This completes the proof.
Proposition C.1. Let H. be the set of halfspaces in R of the form
{x
R"
a x b. on 2 0).
16

---

Then the VC dimension of H. equals n.
Proof. We need to show that there is no set of + 1 that can be shattered by H. Let . Nn+1 be points in R and let yi...., . yn+1 their projections on the first n 1 coordinates. Then y1..... -n... are affinely dependent, that is, there exist -1.-.. Mus not all equal zero, such that E, 145 = and E; p4 = 0. Let
Σ 1420
14 Σ (-ri).
K:
Then A and we have that
1
Σ
Σ (-4:);
w =
P.Y:
A
i: P420
pISi
lies in the convex hull of both the sets (yr: n4 > 0} and (y:: ue < <O. We consider the vectors
1
Σ MLY,,
Σ (-Mi)yr.
W A
É: 14:0
Then both w+ and w agree with w on the first (w )n S (w+),. that is, the last coordinate of w is not bigger than the last coordinate of w+. Then we claim that there exists no half-space {x R a² x S b, On 0} in such that a y; S b for all i such that μ4 > 0 and a a"y; for all i such that μ < O. To see this, we assume to the contrary that such hyperplane exists. We then have
coordinates. W.l.o.g we may assume that
a² a W+
Σ 4120
uaa u y:
S
Σ 1: P:20
pab
A
A
and similarly a² a=w_ > b. In particular, a² w'w_>> a² w.. Since W4 and w agree on the first 1 coordinates it therefore follows that (n(w+)) )n < a, (w-) and thus W+ < w since a, 0, contradiction. Thus, no hyperplane in H satisfies the claim and thus H does not shatter any set of 1 points. The VC dimension is thus at most n. To see that it is fact equal to observe that the set of unit vectors eI,..., ep can be shattered.
C.2 Proof of Theorem
Proof. For any labeled data point (x(+), (0) and 2 0.
(x (xx(*) ) s ( (x+
In particular, ( is in the 1-class of ca then it is also in the 1-class of Catts so any false positive of ca also false positive of ca This shows the first claim. The second claim follows analogously. O
C.3 Proof of Theorem 3.5
Proof. Let Ca E L(err, cn E L(err, k) and d(() lb (1 ()a for 1 E [0, 1]. Let further
Xo = (x(() (()) = 0} and X = X Xo. Since for fixed x the function fá (x) = [[x]A d())) is linear in I, for E Xo holds cx() (x) < cx(x) E 10, and therefore 0 FP(c.) < FP(ca(o) & FP(()). For E X, holds 1 cx(x) cate) (x) 2 (x(x) E (0, and therefore 0 = FN(ca) FN(car)) < (NN()).. Since err(Ca()) = FP (C((a))) + FN((a))) it follows that Care) S(erT, ke) for all t [0. 1]. This implies that the sublevel sets are star-convex. Furthermore, observe that star-convexity holds with respect to any a for which e, perfectly separates the data. The set of all such is a full-dimensional cell in the data arrangement. It thus follows that S(err, k) must consist of cells in the hyperplane arrangement that are connected through walls of codimension 1, and L(err, k) and L(err, k 1) are connected through walls of codimension 1.
17

---

C.4 Proof of Theorem 3.6
Proof. It is sufficient to show that summands of L(a) in the expression above are concave. To that end, we observe that for given training data (x(*), y)0)) each summand (-A) (x()))
->([x a) is linear in and thus concave. To that log (1 (1-e-A/a is concave
calculate
0 - - (x
0 0 log Dag dae
1 (1-6-A((((1))
dak 1 - e- N12 (-1)(x(0
- (x
1² (x
(1- -1-
In particular, the Hessian of log (1--
- -Xee 12
(Nel))a)² T 1x
(1 e1- -12
(x(0))22 (x(()))
is negative semi-definite and thus the likelihood function L(a)) is concave.
C.5 Proof if Theorem 3.9
Proof. From the proof of Theorem 3.6 see that the Hessian of L(a) is negative linear combination of the rank-1 matrices (Ix))))) [x for x66 X1, that is, Hess L(a) Σ. ([x( ) [x( for some A; 0 where the sum is over all such that x(0) E X1, Now let be an eigenvector of Hess ((A) with eigenvalue μ. Since Ax, has rank n, there exists an x(fo) X1
with (6) v) * Then
M |||v|| vJ Hess [(A)V= = Σ 2a((bx(01) (((())))),v)))) s Aio ((xx660))) v))² < O.
follows that μ * 0 and thus μ < O. Thus, Hess [(A) is negative definite and thus C(A) is strictly concave. Since the parameter space R {a > 0} is convex, Hess L(A) has a unique maximum on the extended positive orthant (R2o U (xo))² If furthermore the rank of Ax, n then for each j E {I,...,,7, n there exists an ((1) Xo such that [x > O. Therefore, we see that C(a) -o whenever aj - Thus, the unique maximum must be attained in the closed positive orthant (Rzo)"
C.6 Proof of Theorem 3.11
Proof. We observe that for all >> 0 holds C(tAo a) = L(A,, ta). Therefore, for fixed > 0 holds L(t),, a) L()o, la) L(>,, a* (Mo)) L(t>,, 1/t a" aAoo)
for all a E Rg Thus, an = 1/t a" (Ao) ) is the unique maximum of Ct a), and all maxima lie on the ray {a" (A*())= >> 0} = (tAp) > 0} = f aAu) :t 03.
C.7 Proof of Corollary 3.12
Proof. From the proof of Theorem 3.11 we see that for any 0 < À < X holds a a²() = A/X
a* (A) (A). Since a" (A) R% both claims follow from Theorem 3.4
C.8 Proof of Proposition 4.1
Proof. We begin with the first statement. First, let C = cone Viy Vi.) be a full-dimensional
cone of A such that is contained in the interior of the cone ( - C of the fan (1) - A. Equivalently,
( t C. With Ve = .v..... Vs.)) we can thus compute [x( - + = Vo (x(+) - t), which
is linear function in t. The statement for lower-dimensional cones follows by taking limits. The
second statement follows from substitution of the variables x -t and t + x() in 3
D
18

---

C.9 Proof of Theorem 4.3
Proof. Proposition 4.1 implies that
(t) = ff t E x starr())3) 800 = 13l + :i::::::: : star(a), y =03/,
and is thus constant on each cell of the data star arrangement.
C.10 Proof of Theorem 4.5
Proof. By Proposition 4.1, for any + f (x() - -t (a, [x(1) tl) is linear in on every
maximal cell of the fan arrangement of (1) A. L...., m. Let gF (t) (a, [x(0) t|) be this linear function. Then the Hessian of (t) is the sum of matrices of the form
① Ø log(1 - - Öt, 0t,
δ gr (1 (1- - (t=())ar())) ot." dt, gr()).
-22e-
Since these are negative semi-definite, this proofs the claim.
C.11 Proof of Proposition 4.6
Proof. First note that
(C,x((1) {(a, t) x01 CCttnn(aatt (A(x(() -
-t) 13.
The first set equals 1550 x (-C x() Restricted to (a, t) such that t E x() -C, the function t. ++ [x(() -t] t]] is a linear map by Proposition 4.1 so the expression f -t) -t)= ([x(() - a) is quadratic polynomial in variables f1.... tu ........ On. Therefore, S (C,x((() it the intersection of
solutions to the linear inequalities defining the polyhedral cone R500 x (-C+ + xx(() ()) and the quadratic
inequality ([x(1) t a) I 1. Similarly, S (C, (C,xx(1) ()) is the intersection of R5 X (-C + xx(1) with
the set of solutions to the inequality ([x(1) | 1.
C.12 Proof of Theorem 4.7
Proof. We consider the subdivision of 1 x IRd into sets
n n S (C,( CEN s=1
where we range over all possible b(C, E 10, for all C A,i (l..,,,, By Proposition 4.6 each gb(C,)) x(0) is basic semialgebraic with defining polynomials of degree most 2, and hence the same holds for the above finite intersection. By construction, the extended 0/1-loss is constant on each Ncea n (C x)) Fix k E Zzo. Then the hthh level set L(err, k) of the extended 0/ 1-loss is the (finite) union over all sets Nces n (C, x()) on which the extended 0/1 1/1-loss l-loss is equal to k. Thus, the level set is a semialgebraic set. Since sublevel sets are finite unions of level sets, the same holds for sublevel sets.
C.13 Proof of Theorem 4.8
Proof. We show this statement by giving example of a data-set with disconnected level set (err, 0). For this, we continue with Example A.4 a configuration of 3 data points in IR? The 2-dimensional Coxeter fan of type B has 8 rays and 8 maximal cones. Thus, the parameter space RSS I is subdivided into cells of the form Ncea N SbIC,i) x()). many of these are empty or lower dimensional. The extended 0/1-loss attains the value 0 on 16 maximal cells. To describe them, we use the indexing the rays as depicted in Figure 4b and denote C, = cone(v,, Vi+1) for
1, l...., 7, Cs cone(vs, v1). One example of valid configuration is tuple (a, t) such that (2) E (star(a) + n + t), (2) E (R² (star(a) + t)) n (C's t) and (3) E (star(a) + +t) (C2 + t), depicted in Figure 8a
The set of (a. t) satisfying these conditions
19

---

is ( x() n In'''SSs (Cs. x
(C2, x()) In total, the set of perfect classifiers, i.c. the 0th level is the union of the following 16 nonempty cells:
(C,,
(3 (
(C4,,
(3))
("(C,
x()))
(C,,,
(8)),
(" ((,
5 (C,, (n
(3))
(Cs, x (3)))
S (Cs,
(1),
(',,
S (3))
5 (Cs, 8 (C, no (C4, 5 (C3, x (3)), SO
(C2, (8)),
(Cs, x(3),
(Ca, (C1, x x3))
It can be checked that the union of the sets in each of the above columns is path connected. However, there no path from point in the left column to a point in the right column. If these sets were path connected. then there was path from the configuration depicted in Figure Sa to the configuration in Figure 8b) by continuous translation the star and by shifting the points o, v; along the rays
continuously. But since (2) lies in the convex hull of (2) and (3) and the line segment through any of these point is parallel to the rays V2, Vo, any such continuous transformation necessarily increases
the number of mistakes certain point.
C.14 Proof of Theorem 4.9
Proof. By Kupavskii 2020]. the of simplices has VC dimension Od log)(d). Any star- shaped classifier Ca a union of & simplices. Thus, the result follows from Blumer et al. 1989
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract briefly summarizes the content of the article. The introduction positions the results of the paper within the literature to our best knowledge, and gives more detailed overview over the results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
discussion the limitations given in the introduction under "I "Limitations""
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
21

---

Answer: [Yes]
Justification: All assumptions are either clearly stated in the description of the model, or explicitly stated in the theorems. Rigorous proofs are given in Appendix B. Due to the amount of theoretical results we have not included informal proofs for the statements in the core of the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides all necessary information to reproduce the experiments. The experimental results are independent of the main claims and main results of the article, which theoretical in nature.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
22

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: The small experiments in this article not central to the contribution and easily reproducible with the description provided in the article.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
Codeeubmieie is onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Ye]]
Justification: The paper specifies all necessary details to fully understand and reproduce the experiments conducted for this article.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[No]
Justification: Statistical significance is not relevant for the conducted experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for caleulating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yss]
Justification:
All of this information is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpp::////urriiee /t/.rieurp...// wwwpurrps.ccpuulcc//eeeeccee hccpppblic/tthiccciiide........l
Answer: [Yes]
Justification: The research conducted in this article fully complies with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since this is purely theoretical work, there is immediate societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not involve the release of any data or models, so the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
25

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
26

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
27


Reviews:
[{"review_id": "HWqaFC60Vs", "reviewer": "Reviewer_EcQ6", "summary": "The authors consider the optimization of star-shaped sets. To do so, they are given a set of simplicial cones which are a set of cones than span $\\mathbb{R}^d} whose intersection is itself a facet of the cones). As a result, for every point $x$ one can decompose it as a combination of the basis vectors for some cone denoted $[x]$. Assuming that such a simplicial fan has $n$ vectors in $\\mathbb{R}^d$, we can write each vector  $x$   as  a $d$-sparse combination fo the $n$ basis vectors. For a given $a \\in \\mathbb{R}_{>0}^n$, we can define the hyperplane arangement that defines a set $[x]^T\\cdot a$ and try to learn this separation. \n\nThis motivates their first result which is that the VC dimension is $n$. Next they show that the sublevel sets for the discrete loss are star-convex and for the exponential loss, superlevel sets are concave. Lastly they consider the problem where both the offset $t$ and the parameter $a$. In this case the set of losses are semi-algebraic sets.", "questions": "Can you elaborate on how the appropriate simplicial fans will be chosen. Why this method would be better than other existing techniques?", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The paper is complete and has a thorogh set of results.\n\nThe weakeness is that the technical novelty of the paper is limited. None of the theorems or proofs are surprising and are fairly natural. I think showing that such simplicial fans are useful either theoretically for some class of problems or for some empirical datasets would make the paper much stronger. It would be useful to share any mechanisms  on how to choose appropriate simplicial fans is important.", "was_revised": true, "final_justification": "I thank the authors for their response. I appreciate their contributions and the work they have put in. However, it doesn't quite fit the bar for acceptance in my books. I feel adding some of the additional directions they mentioned in their response will make a much stronger paper.", "rebuttal": "We thank the reviewer for their careful examination of our manuscript and for the thoughtful questions and comments. We aim to address the main concerns in our response below.\n\nWe acknowledge the reviewer’s concern regarding the novelty of the individual technical results. While the mathematical tools we employ are classical, our primary contribution lies in formally establishing connections between simplicial fans and learning theory. Specifically, we analyze the VC dimension, star-convexity of discrete losses, and the concavity properties of exponential losses. To the best of our knowledge, this systematic exploration is novel within the context of optimizing star-shaped sets and contributes to a foundational understanding that can support further theoretical and practical developments.\n\nTo better support the significance of our results, we plan to expand the current version of the article with a small-scale computational study on synthetic data. This study compares our algorithm with standard approaches such as SVM, logistic regression, and neural networks; a description of our preliminary results is provided below.\n\nThe choice of an appropriate fan is indeed crucial and nontrivial. As a data-dependent heuristic in two dimensions, we suggest to incrementally increase the number of rays; see the description of our experiments below.  This strategy allows the fan to grow adaptively with observed structure, avoiding over-parameterization while still capturing complex decision regions.\n\n\n**Numerical Experiments:**\n\nWe conducted a small-scale study using synthetic two-dimensional data, comparing our algorithm with standard binary classification models that also involve convex optimization, as well as simple neural network architectures. We focused on the case without translation.\n\nPreliminary results suggest that our algorithm achieves slightly better accuracy than SVM with a radial basis function kernel and comparable or slightly better performance than neural networks with ReLU activation. Logistic regression and SVM with polynomial kernels performed poorly on our star-convex data.\n\nWe also investigated the impact of fan selection. Specifically, we tested data sampled from stars with fewer rays than the underlying fan of our model. The \"dents\" introduced by these new rays were, unsurprisingly, not very significant in magnitude. This observation supports the following heuristic in two dimensions: begin with a small number of rays and iteratively refine the fan by adding more rays. If additional rays do not yield significant new dents, they may be safely discarded."}, {"review_id": "O0wwOsKsJQ", "reviewer": "Reviewer_jMmD", "summary": "This paper introduces and analyzes a novel class of binary classifiers whose decision boundaries are star-shaped polyhedral sets. The model is built upon a pre-defined simplicial polyhedral fan, and the shape of the star is determined by a vector of positive parameters,\n. The authors provide a thorough theoretical investigation of this model from a geometric and combinatorial perspective.\n\nSome of the key contributions that I could mention are:\n\nExpressivity Analysis: The paper establishes that the Vapnik-Chervonenkis (VC) dimension of the classifier class (with a fixed origin) is equal to the number of generators in the underlying fan.\n\nLoss Landscape Geometry: It characterizes the parameter space for two different loss functions. For the 0/1-loss, the sublevel sets are described as unions of chambers in a hyperplane arrangement, with the sublevel sets exhibiting star-convexity. For a proposed exponential loss function, the log-likelihood is proven to be concave, guaranteeing that local optima are global and enabling efficient optimization.\n\nExtended Model: The framework is extended to allow for translations of the star's origin, which are treated as additional parameters. The paper analyzes the geometry of this larger parameter space, showing that the sublevel sets of the 0/1-loss become semi-algebraic and can be disconnected. It also provides an upper bound for the VC dimension of this more expressive classifier family.\n\nThe work is purely theoretical, providing a foundation for this class of classifiers.", "questions": "1. The framework relies on a given simplicial fan. While determining the optimal fan is out of scope, could you provide more intuition on the practical implications of this choice? For example, how does the complexity of the fan (e.g., number of generators n) relate to the model's sample complexity (via the VC dimension) and its ability to fit complex decision boundaries? Are there any data-dependent heuristics one might consider for fan selection in a practical setting?\n\n2. The introduction compellingly positions this work as an alternative to general ReLU networks. Could you elaborate on this connection? Clarifying this could make the work's relationship to the broader deep learning literature more explicit.", "limitations": "I included some questions in the weaknesses and questions section. It would be great to hear responses on those.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\n1. The paper proposes a novel and interesting family of classifiers that elegantly bridges the gap between simple linear/convex models and highly complex, non-convex models like general ReLU neural networks. By fixing the underlying combinatorial structure (the fan), the authors introduce a controllable and analyzable form of non-convexity. This is a strong and original theoretical contribution to the geometric understanding of machine learning models.\n\n2. Although not an expert in this area, I like the technical quality of this work. The analysis skillfully combines concepts from polyhedral geometry, convex analysis, and statistical learning theory. The characterization of the loss landscapes, particularly the concavity result for the exponential loss is very interesting.\n\n3. The paper is exceptionally well-written and organized. The authors take care to define all necessary geometric concepts before using them.\n\n\n*Weakness*\nThe primary weakness, as acknowledged by the authors, is the absence of any experiments. While this is a theoretical paper, the ultimate motivation is classification. Even a small-scale experimental study on synthetic data could have provided valuable insights.", "was_revised": true, "final_justification": "My concerns are addressed and I shall maintain the score.", "rebuttal": "We thank the reviewer for their careful examination of our manuscript and for the thoughtful questions and comments. We aim to address the main concerns in our response below, and also conducted a small-scale experimental study as suggested, see below.\n\n> *The primary weakness, as acknowledged by the authors, is the absence of any experiments. While this is a theoretical paper, the ultimate motivation is classification. Even a small-scale experimental study on synthetic data could have provided valuable insights.*\n\nAs suggested by the reviewer, we conducted a small-scale study using synthetic two-dimensional data, comparing our algorithm with standard binary classification models that also involve convex optimization, as well as simple neural network architectures. We focused on the case without translation. We plan to include these results into the camera-ready version.\n\nPreliminary results suggest that our algorithm achieves slightly better accuracy than SVM with a radial basis function kernel and comparable or slightly better performance than neural networks with ReLU activation. Logistic regression and SVM with polynomial kernels performed poorly on our star-convex data.\n\nWe also investigated the impact of fan selection. Specifically, we tested data sampled from stars with fewer rays than the underlying fan of our model. The \"dents\" introduced by these new rays were, unsurprisingly, not very significant in magnitude. This observation supports the following heuristic in two dimensions: begin with a small number of rays and iteratively refine the fan by adding more rays. If additional rays do not yield significant new dents, they may be safely discarded.\n\n> *The framework relies on a given simplicial fan. While determining the optimal fan is out of scope, could you provide more intuition on the practical implications of this choice? For example, how does the complexity of the fan (e.g., number of generators n) relate to the model's sample complexity (via the VC dimension) and its ability to fit complex decision boundaries? Are there any data-dependent heuristics one might consider for fan selection in a practical setting?*\n\nThe number of rays has a direct impact on the model's complexity: by a result of Stanley (1975), the number of maximal cones (and thus linear pieces in the decision boundary) in a simplicial fan with n rays is $n^{d/2}$. Thus, given a model with n rays, the models complexity is bounded by $n^{d/2}$. In practical terms this means that adding more rays gives you finer decision boundaries, but also raises the sample complexity and computational burden.\n\nThe choice of an appropriate fan is indeed crucial and nontrivial. As a data-dependent heuristic in two dimensions, we suggest to incrementally increase the number of rays; see the description of our experiments above.  This strategy allows the fan to grow adaptively with observed structure, avoiding over-parameterization while still capturing complex decision regions.\n\n\n> *The introduction compellingly positions this work as an alternative to general ReLU networks. Could you elaborate on this connection? Clarifying this could make the work's relationship to the broader deep learning literature more explicit.*\n\n\nOur family of star-shaped classifiers falls within the broader class of continuous piecewise-linear functions, and as such can be represented by a suitably structured ReLU network. However, the powerful flexibility of ReLU networks makes it challenging to enforce specific geometric properties, such as ensuring that the decision region satisfies star-convexity. In contrast, by building our classifiers directly on a fixed simplicial fan, we retain the ability to model non-convex boundaries yet maintain high control over the shape and connectivity of the decision regions. In other words, whereas a generic ReLU network may approximate virtually any decision boundary but offers little transparency or guarantees on its geometry, our approach imposes a disciplined piecewise-linear structure that both captures rich non-convex phenomena and admits a precise theoretical analysis."}, {"review_id": "MMrwSGPl7X", "reviewer": "Reviewer_nJxy", "summary": "This paper studies the combinatorial and geometric properties of binary classifiers whose decision boundaries are defined by star shape sets, i.e., and non-convex piecewise linear functions supported on a fixed polyhedral simplical fan of cones. The authors present bounds on the VC dimension, demonstrating learn ability, as well as other geometric/convexity/partial convexity properties of a zero-one loss function as well as an exponential type loss function. The further study related properties of an extension that allows for choosing a translation of the star-shaped set as well.", "questions": "1. If it is possible for the authors to include a numerical experiment in their camera ready version of the paper, which compares their proposed model to standard binary classification models that result in convex optimization problems, for example linear models, SVMs, logistic regression, kernel methods etc. this may help to improve my score. Critically the experiment needs to be comprehensive and sound enough, and include comparisons along the dimensions of performance of the models as well as computational difficulty. In my mind, an adequate experiment only needs to be performed on a simple tabular dataset(s), although comparisons with neural networks (which also yield nonlinear decision boundaries) might be interesting as well.\n\n2. Why is the restriction $a > 0$ needed on the vectors defining the classifiers? Is it related to my comment above about the threshold being at 1 instead of 0? If you redefined the threshold to zero, could $a$ be unrestricted?\n\n3. I disagree with the comment that the log likelihood function in equation (2) penalizes false positives and false negatives differently. As I mentioned, this is really a binary cross entropy type function, and it should be symmetric with respect to the two classes. Note that the reason for the different logarithmic versus linear forms of the two terms arises from the form of the exponential distribution, which does not favor one class more than the other. Furthermore, the comment on the different rates of decay between the two terms is not totally sound because $f_a$ is bounded below by zero but is unbounded above. To properly have a difference in how false positives and false negatives are treated, one we need to introduce a reweighting on the two terms. I would suggest revising this discussion.\n\n4. Properly speaking, Problem 2 in algorithm 1 is not convex because the constraint $a > 0$ is an open set. If kept in this form, can it be made to be $a \\geq 0$?\n\n5. Minor:  definition 2.3 seems to be referring to a *proper* face.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. This is a theoretically solid paper, studying a family of binary classifiers that, the best of my knowledge, is novel and has the potential to be significant. I think this is an interesting and valuable family of classifiers, particularly because they sit in between convex piecewise linear and fully piecewise linear functions, as the authors describe. It is therefore very interesting to examine whether this non-convex yet somehow structured family of classifiers has desirable properties. \n2. The authors present a thorough and comprehensive study of various geometric and convexity properties, which I appreciate.\n3. The paper is written and organized, well and the results appear to be mathematically sound (although I did not read the appendix in full).\n4. I particularly find the following two results to be most significant and useful for ML researchers. First, the result of Theorem 3.1, the characterization of the VC dimension of the set of star shaped classifiers for a fixed simplicial fan as exactly the number of generators of the fan, is very natural to me and insightful to understanding the complexity of learning. Second, Thm 3.6, which demonstrates concavity of the exponential type loss function, is very helpful for verifying the computational tractability of learning in this setting. \n\nWeaknesses:\n1. To me, a major weakness here is the lack of numerical experiments, which diminishes the (current) significance of the results. Well I understand that this is a theoretical paper and the authors mentioned this in their limitations discussion, I still think it is critical (and would expect) to include some basic numerical experiments in a paper like this. Demonstrating the value of this novel family of binary classification models, even on a very simple synthetic or real binary classification task (i.e., with tabular data) would help to clarify to the ML community that there is some practicality to the theoretical ideas of this paper. Particularly because the exponential loss leads to a convex optimization problem, in the setting of Thm 3.6, it is quite disappointing that there is no experiment to demonstrate the solvability of this convex problem and the relative merits of this family of classifier functions, which would help to further support and justify their choice over other models.\n2. At the same time, the section and results on translations and and translated versions of the stars shaped sets, seem less impactful to me. Indeed, in neural net activation functions for example, these types of translations are often not considered, at least until the case without translations studied more carefully. I would've rather seen a more focused discussion on the case without translation, including experiments, that needs additional results that don't necessarily have as much value.\n3. The authors make some choices in the development of their model, that in my opinion from the perspective of learning theory, are not totally standard. Most notably:\n- The decision to set the threshold of the classifier for predicting positive versus negative to one, instead of to zero, which recovers the sign function and is by far the standard in binary classification (often referred to as \"margin based\" classification). It is not clear to me why the threshold needs to be set to one, and I think zero would be more standard and more elegant potentially.\n- the \"exponential loss function\" proposed here is different from the standard exponential loss of binary classification, where the loss is $e^{-yf(x)}$ and is particularly notable in the boosting algorithm literature. In fact, the exponential loss considered in this paper is really much more like a cross entropy loss. I would suggest calling it that, or a version of that, instead of the exponential loss.", "was_revised": true, "final_justification": "I have adjusted my score to a 4. After reading the rebuttal and the other reviews, I think this is a nice contribution to learning theory and its interplay with polyhedral theory. However, my reason for borderline accept is that the experiments that the authors mentioned are only on very small synthetic datasets and therefore limited, in particular on the evaluation dimension of computational work/difficulty/scalability. Also, due to the limitations of the NeurIPS OpenReview platform, the authors are not able to share their experiment results. However, despite these issues the theoretical contribution of the paper is strong and so I lean towards acceptance. With strong numerical evidence, this paper would be a definite (and not borderline) accept for me.", "rebuttal": "We thank the reviewer for their careful examination of our manuscript and for the thoughtful questions and comments. We hope to address the main concerns in our response below, and also conducted a small-scale experimental study as suggested, see below.\n\n> *To me, a major weakness here is the lack of numerical experiments, which diminishes the (current) significance of the results.*\n\nWe fully agree that empirical validation would greatly enhance the impact of our work. In the revised version of our article, we will include a small-scale study on two-dimensional data, which we now describe:\n\nWe conducted a small-scale study using synthetic two-dimensional data, comparing our algorithm with standard binary classification models that also involve convex optimization, as well as simple neural network architectures. We focused on the case without translation.\n\nPreliminary results suggest that our algorithm achieves slightly better accuracy than SVM with a radial basis function kernel and comparable or slightly better performance than neural networks with ReLU activation. Logistic regression and SVM with polynomial kernels performed poorly on our star-convex data.\n\nWe also investigated the impact of fan selection. Specifically, we tested data sampled from stars with fewer rays than the underlying fan of our model. The \"dents\" introduced by these new rays were, unsurprisingly, not very significant in magnitude. This observation supports the following heuristic for choosing an appropriate fan in two dimensions: begin with a small number of rays and iteratively refine the fan by adding more rays. If additional rays do not yield significant new dents, they may be safely discarded.\n\n> *The section and results on translations and and translated versions of the stars shaped sets, seem less impactful to me.*\n\nWe agree that the core theoretical insights center around origin-fixed fans. For this reason, we have structured the article to emphasize the case without translations first (Section 2), followed by translation as an extension (Section 3). In the camera‑ready version, our new experimental section will focus exclusively on the non‑translated model,  emphasizing the significance of Section 2.\n\n\n> *The decision to set the threshold of the classifier for predicting positive versus negative to one, instead of to zero, which recovers the sign function and is by far the standard in binary classification (often referred to as \"margin based\" classification). It is not clear to me why the threshold needs to be set to one, and I think zero would be more standard and more elegant potentially.*\n\nThe choice of threshold is without loss of generality due to positive scaling of $a$: any positive-, unit-threshold model (as in our article) can be equivalently represented by a model with threshold zero and unrestricted domain (i.e., the sign function) by applying the logarithm. The reason for our choice lies in the geometric construction and the general geometry of star bodies and their radial functions. We have chosen to keep the number of functions as minimal as possible, thus omitting the additional step of composing the classifier with a logarithmic function.\n\n\n> *The \"exponential loss function\" proposed here is different from the standard exponential loss of binary classification, where the loss is  and is particularly notable in the boosting algorithm literature. In fact, the exponential loss considered in this paper is really much more like a cross entropy loss. I would suggest calling it that, or a version of that, instead of the exponential loss.*\n\n\nWe thank the reviewer for this remark. We will rename it to “log-likelihood loss”.\n\n\n> *I disagree with the comment that the log likelihood function in equation (2) penalizes false positives and false negatives differently.*\n\nThank you very much for pointing this out, this was misconception on our side. We will revise the paragraph about the bias towards false positives and false negatives in the camera-ready version of the article.\n\n> *Why is the restriction $a>0$ needed on the vectors defining the classifiers? Is it related to my comment above about the threshold being at 1 instead of 0? If you redefined the threshold to zero, could  be unrestricted?*\n\nThe restriction lies in the nature of model -- in fact, the choice of the threshold for the classifier being 1 comes from the restriction of the $a$'s to be positive, not the other way around. The entries of the vector $a$ correspond to positive scalars of the rays of the fan, which define the stars. A negative scalar would correspond to \"flipping\" the ray direction to its negative. The associated classifier would not be star-convex (and might even have holes), thus lying outside our class of star-convex classifiers.\n\n> *Properly speaking, Problem 2 in algorithm 1 is not convex because the constraint $a> 0$ is an open set. If kept in this form, can it be made to be $a \\geq 0$?*\n\n Indeed, this is a very good point. Strictly speaking, for it to be a convex program, we need to consider the closed positive orthant. Any solution on the boundary corresponds then to a degenerate star, where one point on a ray moves to infinity. This is considered in Theorem 3.9, and we will highlight this subtlety more clearly in the revised version.\n\n> *5. Minor: definition 2.3 seems to be referring to a proper face.*\n\nThank you for pointing this out, we will correct this in the revised version."}, {"review_id": "KhEmdrFvm4", "reviewer": "Reviewer_cg74", "summary": "The paper studies a class of piecewise linear binary classifiers whose decision boundaries are starshaped polyhedral sets defined with respect to some fixed simplicial fan. \nThe authors show two main results.\nFirst, they show that the VC-dimension of the class equals the number of generators of the simplicial .\nSecond, they analyze the loss landscape of the hypothesis class under the exponential loss, i.e., the cross-entropy loss, and the 0-1 loss.\nIn particular, they show that the exponential loss is a concave function in the parameter space, enbabling efficient learning and optimization. \nThey also show that sublevel sets under the 0/1-loss are structured as chambers in a hyperplane arrangement.", "questions": "Can you elaborate the significance of Corollary 3.3, Theorem 3.4 and Theorem 3.5?\nI understand that they are interesting geometric properties of the hypothesis class. But does it have implication on the advantages or disadvantages of using the 0-1 loss function for optimizing the hypothesis class?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 4, "strengths_and_weaknesses": "**Strengths**\nThis paper presents a technically solid and mathematically rigorous study of binary classification using starshaped polyhedral sets, contributing novel insights into the combinatorial and geometric structure of hypothesis class with non-convex decision boundaries. \nThe hypothesis class constructed is an insightful example of efficiently learnable classes with significance non-convex structure. The work excels in its formal analysis: it gives explicit bounds on VC-dimension, and characterizes the geometry of sublevel sets for both 0-1 and exponential loss functions. \n\n**Weaknesses**\nThe paper seems to be only loosely connected to the broader machine learning community. It will be nice if the authors can discuss in more detail the connection to other common themes in machine learning such as the tension between expressivity and learnability, and the effect of the choice of loss function to efficient learnability. \nBesides, the definitions appearing in the paper, e.g., polyhedral fan, simplifical fan, are quite complicated and dense. It will be nice if the authors can provide pointers to the formal definition at least during the first few occurences of these definitions. It may also be helpful to provide more visual examples to help non-expert readers parse these geometric concepts.", "was_revised": true, "final_justification": "After reading the rebuttal, I think the work has important contribution to the theory explaining tradeoffs between learnability and expressivity. Moreover, the work sheds light into the role of convexity (in terms of both the loss landscape as well as the decision boundary) in such tradeoff. Therefore, I am now leaning towards accept.", "rebuttal": "We thank the reviewer for the careful examination of our manuscript and the thoughtful questions and comments. We hope to address the main concerns in our response below. To support our theoretical results, we additionally conducted a small-scale experimental study, which we describe below.\n\n\n> *It will be nice if the authors can discuss in more detail the connection to other common themes in machine learning such as the tension between expressivity and learnability, and the effect of the choice of loss function to efficient learnability.*\n\n\n We appreciate the reviewer’s suggestion to more clearly situate our work within broader machine‐learning themes. In the revised manuscript, we emphasize the following points:\n\n- Our star‐shaped hypothesis class sits between convex piecewise‐linear (limited expressivity but easy to learn) and fully piecewise‐linear (very expressive but high complexity). By proving that the VC dimension equals the number of rays, we quantify precisely how increasing the number of linear regions of the classifier (and thus expressivity) impacts sample complexity, making explicit the classic trade-off between richer decision boundaries and learnability.\n\n\n- The effect of the choice of the loss function is made explicitly on two concrete examples:  0‑1 loss (whose sublevel sets decompose into unions of chambers of a hyperplane arrangement) with an exponential loss function (whose superlevel sets are concave). This contrast illustrates how the geometry induced by different losses governs optimization: while 0‑1 loss minimization is NP‑hard in general, the star‑convex structure admits principled local‑search heuristics, and the concavity of the exponential loss admits efficient convex solvers.\n\n\n> *The definitions appearing in the paper, e.g., polyhedral fan, simplifical fan, are quite complicated and dense. It will be nice if the authors can provide pointers to the formal definition at least during the first few occurences of these definitions. It may also be helpful to provide more visual examples to help non-expert readers parse these geometric concepts.*\n\n\nWe regret that, due to strict page limits, our background section could not fully elaborate on the rich theory of polyhedral and simplicial fans. \nIn the revised version we will add clearer pointers to the examples and visualizations in Appendix A, and add explicit pointers (e.g., Ziegler’s Lectures on Polytopes, Chapters 1–2) for additional material introducing the formal definitions at the first mention of \"polyhedral fan\" and \"simplicial fan.\"\nIf the reviewer has concrete suggestions for specific examples beyond the material in Appendix A, we would be delighted to incorporate them.\n\n> *Can you elaborate the significance of Corollary 3.3, Theorem 3.4 and Theorem 3.5?*\n\nOur geometric analysis reveals that sublevel sets under the 0-1 loss decompose into convex chambers within a hyperplane arrangement (Corollary 3.3), while simultaneously exhibiting star‑convexity with respect to any optimal point in the chamber which minimizes the loss (Th. 3.4 and 3.5). \nThese theorems establish that while global optimization over the 0-1 loss is hard  due to the combinatorial complexity of the overall non‑convex landscape (Cor. 3.3), the local landscape is well-connected (Th. 3.4, Th. 3.5). In particular, for separable data these results show that local optimization methods can move from a chamber to a neighboring chamber along a straight line, improving the number of mistakes in each step and finding and terminating at the global minimum (without getting stuck at local minima (Th. 3.5). Theorem 3.4 says that also in the case of non-separable data, the landscape of false positives and false negatives behaves similarly. These results contrast with arbitrary non-convex losses, where disconnected sublevel sets can trap local methods, and highlights a key advantage of our structured non-convex setting.\n\n**Numerical Experiments:**\n\nWe conducted a small-scale study using synthetic two-dimensional data, comparing our algorithm with standard binary classification models that also involve convex optimization, as well as simple neural network architectures. We focused on the case without translation. We plan to include these results into the camera-ready version.\n\nPreliminary results suggest that our algorithm achieves slightly better accuracy than SVM with a radial basis function kernel and comparable or slightly better performance than neural networks with ReLU activation. Logistic regression and SVM with polynomial kernels performed poorly on our star-convex data.\n\nWe also investigated the impact of fan selection. Specifically, we tested data sampled from stars with fewer rays than the underlying fan of our model. The \"dents\" introduced by these new rays were, unsurprisingly, not very significant in magnitude. This observation supports the following heuristic in two dimensions: begin with a small number of rays and iteratively refine the fan by adding more rays. If additional rays do not yield significant new dents, they may be safely discarded."}]

Author rebuttal:

Meta-review: This paper presents a nice theoretical study of binary classification with star-shaped polyhedral decision boundaries, establishing VC dim bounds and characterizing the geometry of loss landscapes. The results are technically solid and novel in framing, though largely based on classical tools. Some weakenesses were identified in the rebuttal phase, which the authors addressed with preliminary experiments and a clarification of the broader significance. 

The authors should take the excellent points in the discussion into account as they craft a final version of the manuscript. Overall, this is a valuable contribution.
Decision: Accept (poster)