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

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.

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.

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:

• 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.

• 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.

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.

We regret that, due to strict page limits, our background section could not fully elaborate on the rich theory of polyhedral and simplicial fans. In 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." If the reviewer has concrete suggestions for specific examples beyond the material in Appendix A, we would be delighted to incorporate them.

Can you elaborate the significance of Corollary 3.3, Theorem 3.4 and Theorem 3.5?

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 (Th. 3.4 and 3.5). These 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.

Numerical Experiments:

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.

Preliminary 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.

We 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.

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.

To me, a major weakness here is the lack of numerical experiments, which diminishes the (current) significance of the results.

We 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:

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.

Preliminary 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.

We 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.

The section and results on translations and and translated versions of the stars shaped sets, seem less impactful to me.

We 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.

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.

The 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.

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.

We thank the reviewer for this remark. We will rename it to “log-likelihood loss”.

I disagree with the comment that the log likelihood function in equation (2) penalizes false positives and false negatives differently.

Thank 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.

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?

The 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.

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$?

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.

5. Minor: definition 2.3 seems to be referring to a proper face.

Thank you for pointing this out, we will correct this in the revised version.

I appreciate the authors' response to my concerns and questions. Thank you for providing detailed answers, which helped clarify several points for me. I am glad to see that you ran some preliminary experiments and that the results are coherent with your expectations, although I do remark that the (synthetic and very small scale) experiments are currently somewhat limited. I have no further questions at this time.

EDIT: I want to add that 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.

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.

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.

As 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.

Preliminary 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.

We 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.

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?

The 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.

The 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.

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.

Our 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.

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.

We 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.

To 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.

The 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.

Numerical Experiments:

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.

Preliminary 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.

We 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.