An efficient, provably optimal algorithm for the 0-1 loss linear classification problem
Authors: Xi He
Max A Little
Venue: ICLR 2026 Poster (2026)
Keywords: Classification
Global optimal algorithm
Hyperplane arrangement
Interpretable machine learning
Primary area: learning theory
TL;DR: Combinatorial and incidence relations between hyperplanes and data points, and an provably optimal algorithm for the 0-1 loss linear classification problem

Abstract: Algorithms for solving the linear classification problem have a long history, dating back at least to 1936 with linear discriminant analysis.
For linearly separable data, many algorithms can obtain the exact
solution to the corresponding 0-1 loss classification problem efficiently,
but for data which is not linearly separable, it has been shown that
this problem, in full generality, is NP-hard. Alternative approaches
all involve approximations of some kind, such as the use of surrogates
for the 0-1 loss (for example, the hinge or logistic loss), none of
which can be guaranteed to solve the problem exactly. Finding an efficient,
rigorously proven algorithm for obtaining an exact (i.e., globally
optimal) solution to the 0-1 loss linear classification problem remains
an open problem. 

By analyzing the combinatorial and incidence relations between hyperplanes and data points, we derive a rigorous construction algorithm, incremental cell enumeration (ICE),
that can solve the 0-1 loss classification problem exactly in $O\left(N^{D+1}\right)$---exponential
in the data dimension $D$. To the best of our knowledge, this is
the first standalone algorithm---one that does not rely on general-purpose
solvers---with rigorously proven guarantees for this problem. Moreover,
we further generalize ICE to address the polynomial hypersurface classification
problem in $O\left(N^{G+1}\right)$ time, where $G$ is determined by both the data dimension $D$ and the polynomial degree
$K$ defining the hypersurface. The correctness of our algorithm is
proved by the use of tools from the theory of hyperplane arrangements and
oriented matroids.

We demonstrate the effectiveness of our algorithm on real-world  datasets, achieving optimal training accuracy for small-scale  datasets and higher test accuracy on most  datasets. Furthermore, our complexity analysis shows that the ICE algorithm offers superior computational efficiency compared with state-of-the-art branch-and-bound algorithm.

Published as a conference paper at ICLR 2026
AN EFFICIENT, PROVABLY OPTIMAL ALGORITHM FOR THE 0-1 LOSS LINEAR CLASSIFICATION PROBLEM
Xi He
Max A. Little
School of Computer Science
School of Computational Neuroscience
Peking University Beijing, China xiheêpku. edu. on
University of Birmingham
Birmingham, UK max1 (mitemmmiee......mm.ee edu
ABSTRACT
Algorithms for solving the linear classification problem have a long history, dat- ing back at least to 1936 with linear discriminant analysis. For linearly separable data, many algorithms can obtain the exact solution to the corresponding 0-1 loss classification problem efficiently, but for data which is not linearly separable, it has been shown that this problem, in full generality, is NP-hard. Alternative ap- proaches all involve approximations of some kind, such the use of surrogates for the 0-1 loss (for example, the hinge or logistic loss), none of which can be guaranteed solve the problem exactly. Finding an efficient, rigorously proven algorithm for obtaining an exact (i.e., globally optimal) solution to the (-1 loss linear classification problem remains an open problem.
By analyzing the combinatorial and incidence relations between hyperplanes and data points, derive rigorous construction algorithm, incremental cell enu- meration (ICE), that can solve the 0-1 loss classification problem exactly in O exxponntiaal in the data dimension D. To the best of our knowledge. this is the first standalone algorithm-one that does not rely on general-purpose Seivers-witt rigorously proven guarantees for this problem. Moreover, we fur- ther generalize ICE to address the polynomial hypersurface classification problem in O (NG+1) time, where G is determined by both the data dimension and the polynomial degree K defining the hypersurface. The correctness of our algo- rithm is proved by the use of tools from the theory of hyperplane arrangements and oriented matroids.
We demonstrate the effectiveness of our algorithm on real-world datasets, achiev- ing optimal training accuracy for small-scale datasets and higher test accuracy on most datasets. Furthermore, our complexity analysis shows that the ICE al- gorithm offers superior computational efficiency compared with -tate-of-theeart branch-ana anu-dound algorithm.
INTRODUCTION
Increasingly, machine learning (ML) is being used for high-stakes prediction applications that deeply impact human lives. Many of these ML models are "black boxes" with highly complex, inscrutable functional forms. In high-stakes applications such as healthcare and criminal justice, black box ML predictions have incorrectly denied parole (Wexler) 2017). misclassified highly polluted air as safe to breathe (MeGough) 2018), and suggested poor allocation of valuable, limited resources in medicine and energy reliability (Varshney & Alemzadeh| 2017). In such high-stakes applications of ML, we always want the best possible prediction, and we want to know how the model makes these predictions so that we can be confident the predictions are meaningful (Rudin) 2022). In short, the ideal model is simple enough to be easily understood (interpretable), and optimally accurate (exact).
Another compelling reason why simple models are preferable is because such low complexity models usually provide better statistical generality, in the sense that classifier fit to some training dataset, will work well on another dataset drawn from the same distribution to which we do not have access (works well sut-oe-sample). The VC dimension is key measure of the complexity of classification

---

Published as a conference paper at ICLR 2026
model. The simple D D-dimensional linear hyperplane classification model, which discuss in detail below, has VC dimension D + which is the lowest of other widely used models such as the decision tree model (axis-pane (axis-parallel hyper-roctangles, VC dimension 2D), the K K-degree polynomial (VC dimension O (D*) and the I.-layer, I W-weight piecewise linear deep neural networks (VC dimension O (WLlog ))) for instance (Vapnik) 1999; Blumer et al. 1989 Bartlett et al. 2019).
Assume dataset of size N is drawn i.i.d (independent and identically distributed) from the same distribution as the training dataset, according to Vapnik (1999)'s 's generalization bound theorem, for the hyperplane classifier we have, with high probability,
(V
log (N/ + (N/(D+1)) N/
Evest S Eemp + +
(I)
where Egst, Eemp are the test 0-1 loss and empirical 0-1 loss of on training dataset, respectively (Mohri et al. 2018). Equation (T) motivates finding the exact (gloablly optimal) 0-1 loss on the training data and simplest model, as the lower the training accuracy and the model complexity (defined by VC-dimension) the more likely the model will obtain a better result testing dataset. If a data set is simple enough, a linear classifier can deliver an accurate enough solution. In which case, no other model can outperform the exact linear classifier.
Training a model to global optimality on a training dataset is known as the empirical risk minimiza- tion problem. However, even for perhaps the simplest case the linear model trainiirrinngg model to global optimality is intractable. It has long been proven that empirical risk minimization for 0-1 loss (i.e., minimizing the number of miselassificationss)) in linear classification is NP-hard (Ben-David 2003 as a function of the data dimension (Mohri et al. 2018). et al.
Consequently, most algorithms proposed for this problem focus on optimizing approximate variants of the 0-1 loss, such as the logistic loss (Cox) 1958 1966), and hinge loss (Cortes & Vapnik] 1995).
By contrast, relatively little attention has been given to exact algorithms for the 0-1 loss classification problem (0-1 LCP). One approach is to formulate the problem as mixed-integer program (MIP)
and solve using ceneeral-urpood solvers, such as Gurobi (Gurobi Optimization, LLC 2024).. For
instance, Tang et al. (2014) employed a MIP formulation to obtain the maximum-marge boundary under 0-1 loss, while Brooks (201T) optimized the "ramp loss" and the hard-margin loss-bott closely related to 0-1 loss using quadratic mixed-integer program (QMIP).
Alternatively, combinatorial methods such as the branch-and bound (BnB) approach have also been applied. Nguyen & Sanner (2013) for example, proposed several BnB-based algorithms for solving the 0-1 LCP. However, a common problem in BnB research is the lack of formal proofs of exhaus- tiveness, making the correctness of such algorithms uncertain. Although Nguyen & Sanner (2013) present several interesting methods, none of them are accompanied with formal correctness proof.
Nevertheless, the well-known Cover's functional counting theorem (Cover 1965) rigorously estab- lished that there are
N (N=1)=0(N3)
Cover (N+D+1)=2)
d=0
possible linear dichotomies of N points in R.P. This result suggests that, in principle, one could solve the 0-1 LCP exactly by exhaustively enumerating these partitions. However, Cover's result is purely combinatorial and does not provide any method for performing this enumeration.
Interestingly, Nguyen Sanner (2013) observed that selecting hyperplanes formed by choosing D out of N data samples suffices to solve the 0-1 loss LCP exactly. This procedure has combinatorial
complexity of N
which appears to be smaller than the complexity derived from Cover's
analysis. At the same time, in the context of the hyperplane decision tree problem, Murthy et al.
N D
:994:; Dunn (018)) observed that all possible linear partitions can be enumerated in 2D which is larger than the bound implied by Cover's result. These three distinct combinatorial analyses yield seemingly inconsistent complexity estimates. This naturally raises the question:
2

---

Published as a conference paper at ICLR 2026
Which of these analyses is correct for solving the 0-1 loss linear classification
problem? If all are valid, how are they connected?
This paper is dedicated to addressing these questions formally. Our key contributions are as follows:
Combinatorial foundations for classification in Euclidean space: We establish the com- binatorial and incidence relationships between hyperplane arrangements and point config- urations in the ordinary vector space R.. Unlike the classical treatment in combinatorial geometry and oriented matroid theory-which is based on homogeneous coordinates we work directly in inhomogeneous (Euclidean) coordinates (Edelsbrunner 1987 Fukuda 2016).
Theorem for solving the 0-1 LCP, which rigorously proves why Nguyen & Sanner (2013)'s prioritized combi- natorial search (PCS) algorithm can exactly solve the 0-1 LCP. The supporting lemmas of Theorem 3 reveal deep connections between the three distinct combinatorial analyses
A novel 0-1 loss linear classification theorem: We present
Cover 19655) Murthy al.] (1994): Dunn (2018), and Nguyen Sanner (2013).
The first rigorously proven standalone algorithm for 0-1 linear classification problem: By combining Theorem 3 with the efficient combination generator introduced by He & Little 2025), we construct the first rigorously proven, standalone algorithm-on that does not rely on general-purpose solvers-for solving the 0-1 LCP. Empirical results (see Figure 5 show that, for example, when N 150 data size with D 3, ICE would take 1.2 seconds worst-case whereas Nguyen and Sanner (2013)'s BnB would take approximately 1010 seconds (nearly 317 years), clearly demonstrating the superiority of our approach.
Extension to polynomial hypersurface classification: We extend our theoretical frame- work to polynomial hypersurfaces, resulting in an optimal algorithm for solving the 0-1 loss hypersurface classification problem.
Empirical insights on generalization: Our experiments show that solutions with lower training accuracy often generalize better to unseen test data. This observation refutes the conventional belief that exact algorithms overfit and is consistent with Vapnik (1999)'s generalization bound thcorem.
The paper is organized as follows. In Section 2 we provide detailed geometric analysis of the linear classification problem and develop novel theorems for solving the 0-1 loss linear and hypersurface classification problems. This result leads to new class of algorithms capable of solving these problems exactly. Section presents empirical results comparing the ICE algorithm with standard approximate methods on real-worke datasets from the UCI Machine Learning Repository, evaluating both training accuracy and out-of-sample generalization performance. Finally, Section 4 discusses our contributions and the limitations of the proposed algorithm, and outlines potential directions for future research.
2
THEORY
2.1
PROBLEM DEFINITION
Assume dataset consists of N data points (or data items) Fn, Vn E (1...., N] data points In E D and D is the dimension of the feature space. Each data point has unique true label I, E 1-,1, 1}. Vn E N. All true labels in this dataset are stored in set I = (4, (,,,., The data points and their labels are packaged together into the dataset D, denoted as Dr. The 0-1 LCP can be defined as
N. where the
v = argmin Ea.1 (w, Dí) = Σ [sign (w" xn) * Ln]. WERD+1
(3)
nEN
where Ea11 (w, D1)= EmEN'' 1 [sign (w a.) # Ln] is the 0-1 loss objective function which counts
the number of misclassified data points given the parameter w, we denote E (w, Di) as Ep-1 (w)
Informally dataset in R is in inhomogencous coordinates, whereas क (a:, represents the same point in homogeneous coordinates (projective space)
3

---

Published as a conference paper at ICLR 2026
*
count: IMI 2 IM Cowret 33
Murthy's count: 2
atgorithm:
*
X
Exhoustive cnumeration solves 0-1
classification problem
Two ways to emmmerate possible cells of arringement,
(Theorem 3)
*8
exhaustive enumeration solves lincur classfication problem with arbitrary objecrive (Theorem
algorithum:
lel
Eshaustive enumeration solves
0-1 lincar classfication problem (Theorem
*
Figure I: Novel theoretical contributions enabling the ICE algorithm: identifying the necessary and sufficient dual-arrangement faces that must be enumerated to solve the 0-1 ICP. The black x marks (unbounded cells) and red X marks (bounded cells) represent all the cells of dual arrangement, with |-] denoting their size. In Theorem 2 we show that exhaustively enumerating all cells and the reversals of unbounded cells (with total size X + 2 x yields number exactly matching Cover's counting function Cover for possible linear dichotomies (as proved in Lemma D This procedure solves the linear classification problem for any objective function, filling the gap Cover's theo- rem, which provides only counting formula without specifying how to enumerate the dichotomies. Theorem 3 demonstrates that the 0-1 LCP can solved exactly by exhaustively enumerating all blue circles in the figure and their corresponding reversed sign vectors, formally proving the cor- rectness of Nguyen Sanner (2013)'s PCS algorithm, which had only been empirically observed to be optimal. Finally, Theorem 5 shows that it suffices enumerate only the blue circles, without their reversed signs, reducing the number of configurations and enabling the construction of our incremental cell enumeration (ICE) algorithm.
when Dj clear from the context. The supervised classification problem is solved by computing (3) which is a sum of 0-1 loss functions 1 []. each taking the value if the Boolean argument is truc, and 0 if false. The function sign returns +1 is the argument positive, and -1 if negative (and zero otherwise). The linear decision function w E with parameters E IR D+1 and æ = (x, 1) is data point in homogeneous coordinates. Although apparently simple, this a surprisingly challenging optimization problem. Considered mization technique, gradient descent, is not applicable (since the gradients of Ev-1 with respect to w zero everywhere they exist), and the problem is non-convex there potentially very large number local minima which gradient descent can become trapped. Nevertheless, the finiteness of the dataset implies that only a finite number of partitions cerned with those partitions that can be induced by hyperplanes linear dichotomies. The next subsection explains how to identify these linear dichotomies using a geometric dual transformation. which can then be applied to solve 3).
continuous optimization problem, the standard ML opti-
possible. In particular,
diagrammatic summary of the key geometric results presented in Figure 1
2.2 POINT CONFIGRRATION AND HYPERPLANE ARRANGEMENTS
A point configuration is synonymous with dataset and is denoted by P = (pm E RD; in A finite hyperplane arrangement is finite set of hyperplanes 7 {hi,..., h where each hyper- plane is defined as h. = { t E R², w"' x = c} for some constant E IR. A point configuration or hyperplane arrangement in general position is called simple if no of them lie (k- 2)- dimensional affine subspace of TDD and the intersection of any k hyperplanes is contained in
(D k) -dimensional flat, for 1 < k < D. For example, if D = 2 then set of lines is in gen- eral position if two are parallel and no three meet at point.
Definition 1. Faces of hyperplane arrangement. Let Fu be the set of sign vectors sign (æ)
in E for arrangement H. which is defined as
Fx {sign (x) : ERD).
(4)
4

---

Published as a conference paper at ICLR 2026
A face f (connected component) of an arrangement f C RP is maximal subset of IR such that all x E f have the same sign vector signy (a) E Fu. Given a sign vector signæ (x) = (δ1 (at) 52 (a:) ,...,,, 51 (z)). the connected region of f can be defined as f Nkez h fact, f defines an equivalence class in R... Since any point a E f has the same sign vector, then signy (f) is the sign vector for any point in f. A face is said to be k-dimensional if it is contained in a k-flat for -1 S S D + 1. Some special faces are given specific names vertices (k 0), edges (k- = 1), and cells (k- = D). A k-face and a (k- f)-face f are said to be incident if f is contained in the boundary of face g, for 1 S k I D. In that case, face g is called a superface of f. and f is called a subface of g. The cells in an arrangement can be further split into two classes, the bounded cells and unbounded cells. Informally, a cell is bounded if it is a closed region surrounded by hyperplanes (the boundaries not contained in cells), and unbounded otherwise.
k In
Superficially, a hyperplane arrangement might seem to contain more information or structure than a set of data points (a point configuration). However, a valuable approach to studying geometric ob- jects involving points and hyperplanes is to explore the transformations between these two objects. By studying the dual transformation between point configurations and hyperplane arrangements, it will later be seen that the superficial impression of the structural information contained in hyper- plane arrangement and point configuration is incorrect. Both hyperplane arrangements and point configurations possess equally rich combinatorial structure.
In the next section, we examine the geometric relationships among points, hyperplanes, and di- chotomies, with a focus on their combinatorial and incidence relations, leading to a new perspective on the linear classification problem. This enables the development of efficient and general al- gorithm capable of solving linear classification problems. Detailed proofs of all theorems and lemmas in next section are provided in the Appendix A.
2.3 LINEAR CLASSIFICATION AND VOINT-HYPERPLANT DUALITY
The geometric dual transformation é RP_ + R maps point p to a non-vertical affine hyperplane (p). defined by the equation
2 + P242 + + PD- - xp = PD,
(5)
and conversely, the function o= transforms (non-vertical) hyperplane h defined by polynomial
W + W222 +... -Un-1#n-1 - .D = wi to a point Φ (h) = (wi, W.,..., , wp'' The terms primal space, and dual space refer to the spaces before and after transformation by Φ and $-1 The dual transformation is naturally extended to a set of points é (P) and a set of hyperplanes @ (H) by applying it to all points and hyperplanes in the set. We have the following important theorem which is the foundation for analysising the incidence and combinatorial relations between data points and linear dichotomies.
Theorem 1. Incidence relations of the dual transformation. Let p be a point and a non-vertical affine hyperplane h. {a: w² x = 0} in IRP, Under the dual transformation o. and H satisfy the following properties:
1. Incidence preservation: Point p belongs to hyperplane h if and only if point o (h) belongs to hyperplane & (p) = p.
2. Order preservation: Point p lies above (below) hyperplane h if and only if point Φ-1 (h) lies above (below) hyperplane @ (p).
That the dual transformation preserves the incidence relations above can be proved by examining the relationship between the dual transformation ø and the unit paraboloid (Edelsbrunner 1987) The incidence preservation property described above implies a duality between the definiions of general position for point configurations and hyperplane arrangements. For instance, when 1) 2, three points lying in the same 1-flat I (a line) correspond to three lines in the dual space intersecting at the same point Φ (I), these three lines are mutually parallel if the line is vertical.
It can be difficult to visualize how Cover's dichotomies form equivalence classes for decision hyper- planes, but the same decision hyperplanes in the dual space & (P), Vp E RD" partition the space into different cells, where each cell corresponds to equivalence class of dichotomies (Fig. 2 More-
N
over, this explains why the prediction by Murthy et al. (1994) Dunn (2018), of 2D
D possible
5

---

Published as a conference paper at ICLR 2026
P. EER
My
de BP-2O
Figure 2: A point configuration D (left-panel) and its dual arrangement HD (right-panel). The yellow hyperplanes wA, Wi with two points lying on them in RD correspond to the yellow points in the dual space, which are the intersection of corresponding dual hyperplanes & (wa). (w;). For (blue) hyperplanes w1, W2, wy with the same prediction labels (+, -.. their corresponding dual points (wr), ). Φ (W2), & (w2) lie in the same cell of dual arrangement (D).
linear classifications is correct: the most straightforward way to enumerate all cells in hyperplane
arrangement to first enumerate the D vertices- determined by a unique combination
of D hyperplanes in general position and then consider the 2D adjacent cells associated with each vertex. This enumeration relies on the general position assumption, which guarantees that every D-combination of hyperplanes defines a distinct vertex with exactly 2n neighboring regions.
Importantly. we present the following lemma, which explains the combinatorial relationship between linear dichotomies and the cells of the dual arrangement. This lemma is the basis for an alternative approach to proving Cover's counting theorem.
Lemma 1, For set points D = {xn E R : n E VV} in general position, the total number of linear dichotomies in Cover's function counting theorem, is the same the number of cells of the dual arrangement HD, plus the number of bounded cells of Hp. In other words, denote the number of dichotomies for N data items in RD as Cover (N, D + 1) (D denote the dimension of data in homogeneous coordinates) and the number of cells and bounded cells an hyperplane arrangement in IR
BD (HD) and CpD (Hp). Then
Cover (N, D+1 BD (HD) CD (Hp)
Another, previously reported, geometric analysis on the combinatorial relations between the hyper- plane arrangement and the point configuration is based homogeneous coordinates, where all cells of the dual arrangement are unbounded [Edelsbrunner 1987 Fukuda 2016).
The equivalence between the number of dichotomies and the sum of the number of bounded cells and the number of cells may initially seem unclear. The intuition lies in the fact that not every dichotomy in the primal space corresponds to a cell in the dual space. Specifically, decision bound- aries associated with unbounded cells correspond to two dichotomies, whereas those associated with bounded cells correspond only one. This relationship is clarified by the following lemma.
Lemma 2. For dataset D in general position, each of Cover's 's dichotomies corresponds to a cell in the dual space, and dichotomies corresponding to bounded cells have no complement cell (cells with reverse sign vector). Dichotomies corresponding to the unbounded cells in the dual arrangements di (D) have complement cell.
Since each of Cover's dichotomies corresponds to cell in the dual space, and dichotomies cor- responding to bounded cells have no complement cell (cells with reverse sign vector), lemma demonstrates that all possible Cover's dichotomies of given dataset D can be obtained by enumer- ating the cells of an arrangement and the complemented cells the bounded cells. The enumeration of the complements of the bounded cells requires an additional process, as the bounded cells within the arrangement do not have complementary cells. This result leads directly to the following theo- rem.
Theorem 2. Linear classification theorem. Let a data set in general position RDD. If an O (ND+1) cell enumeration algorithm exists, then exact solutions for the linear classification problem with an arbitrary objective function can be obtained in at most O (teval DD-1) time by exhaustively enumerating the cells of the dual arrangement HD, where teval represents the time required to evaluate the classification objective.

---

Published as a conference paper at ICLR 2026
Theorem gives method for solving the linear classification problem arbitrary objective function. However, as we interested in only the LCP with 0-1 loss objective (3) the properties below helps to solve the LCP over 0-1 loss more efficiently. The next lemma explains not only that Cover's dichotomies have corresponding dual cells for the dual hyperplane arrangement, but also that hyperplanes containing 0 S k < D data points have corresponding dual faces.
Lemma 3. For a dataset DD in general position, hyperplane with & data items lying on it, 0 < k: s D correspond to a (D - k) -face in the dual arrangement Hp. Hyperplanes with D points lying on it, correspond to vertices in the dual arrangement.
Definition 2. Given hyperplane arrangement H = {hn in E W.. The separation set sep (f.g) for two faces f. g is defined by
sep (S.g) - EN: 8n (1) - 5n (g) #0},
using which, we say that the two faces f. 9 are conformal sep (f.g) g) = 0.
That two faces that are conformal is essentially the same thing saying that two faces have consis- tent classification assignments.
Lemma 4. Given hyperplane arrangement H (hn : n E M) two faces f. g are conformal and only if f and g are subfaces of common face or one face is a subface of the other.
A similar result described in oriented matroid theory (Björner 1999). The following lemma will be instrumental in the analysis, presented later, of the linear classification problem with the 0-1 loss objective. It suggests that the optimal cell, with respect to 0-1 loss, is conformal to the optimal vertex.
Lemma 5. Given a hyperplane arrangement H = {ha n E N). for arbitrary maximal face (cell) f. the sign vector of f is sign (f). For an arbitrary (D - d)-dimension face g. S D, the number of different signs of signæ (g) with respect to signy (f) is larger than or equal d, where equality holds only when g is conformal to f (g is a subface of f).
Now we have all receipts to prove the final result, for the linear classification problem over 0-1 loss, we can solve it by exhuastively searching all D-combinations of data points. The following theorem formally proves Nguyen& & Sanner (2013 observation.
Theorem 3. 0-1 loss linear classification theorem. Consider dataset D1 of N data points of dimension D in general position, along with their associated labels. Let Skcomin denote the set of all D-combinations with respect to dataset DD Then we have following relation
argmin minnEE.1(,, Di), Eo Di)) S. argmin Eo.1 D1) WER
(8)
where w, represents the normal vector of the hyperplane that pass through the D-combination of data 8, and -w is the negation of w,. The inner min on the left-hand side ensures that 8 E Skcomts (D, D) for each s, where Skcombs (D,D) denote all possible D-combinations of the set D. We take the smaller of Eo11 (w.) and E0-1 (-w.), and the outer argmin selects one of the values of that minimizes this quantity over all E Skcombs (D,D).
2.4 NON-LINEAR (POLYNOMIAL HYPERSURFACE) CLASSIFICATION
Based on the hoert-hy duality. equivalence relations for linear classifiers finite sets of data were established above. However, a linear classifier is often too restrictive in practice, as many problems require more complex decision boundaries. It is natural to ask whether it is possible tend the theory to non-linear classification. This section examines well-known concept in algebraic geometry, the K-tuple Veronese embedding, which allows the generalization of the previous strat- egy for solving classification problem with hyperplane classifier to problems involving hypersurface classifiers.
Importantly, we present the following theorem, which describes the relationship between hyperplane and hypersurface classification problems.
Theorem 4. The K-tulee Veronese embedding. Given variables To. F1. DD in projective space pd (which is isomorphic to the affine space Rº when ignoring the points at infinity (Cox et al., 1997)), let Mo, M1,... Mc be all monomials of degree K with variables æa -1,...... where
7

---

Published as a conference paper at ICLR 2026
Algorithm Incremental cell enumeration (ICE) algorithm
Input: ingut which
points g position: labal degren polynomiaa.:
Output: The optimal normal vector w R and optinnal D-1 loss Eig
I: D' PN caleniating embroded
2: w"
(Pi)
3: ds reonder(w" (w=" DD)
Cas + (0.............................. ........................... K+1 empr lint for t K-combinations
for 0 N
6: Bor k = min (K. Css(E] +- (os(k) U map(AS. 5-+ [n]] Css(k 1]) incremental combination generation
down O do
8:
aua 4- wugg(geeModel(dd)) Csa(D.) // generate nomnal vecturs from vontinations
10:
w' if Far("w)) F then
12:
ur" Fii 1o', Fia1(10")
13:
N.N- D (ar(w)) E F then
15:
ur Fb. w Follw (wo) I symmetric farion iow
16:
end for
18:
Cloa [D] 4- [] eliminnte Decoudinutions oftes
and for
20:
return u F54
G G= -D+ (see Appendix A for the formal definition of monomials and poly-
nomials and explanation of G). Define a mapping Pk PD + PG which sends the point p = (po: .PD PD to the point PK (p) the K--tupk Veronese embedding of dd in PG The hyperplane classification over the embedded
(Mo (p) M1 ....... Mc (p)). This called
datasets PK (D) is isomorphic the polynomial hypersurface classification (defined by degree K polynomial) over the original dataset D.
is now straightforward to extend Theorem to the following polynomial hypersurface classifica- tion theorem.
Corollary 1. 0-1 loss polynomial hypersurface classification theorem. Consider dataset of N data points in IR in general position, along with their associated labels. Let Px (D) be the K-tuple Veronese embedding defined by monomials of degree K, we have following relation
argmin 8E Stonni (G. (D)) min(Fo.:(ur) PK (Di)), Eoo(--w,, PK (Di))) S argmin Eo. (w. PK (Di)) (9) wERC-1
where w, E BGG denote as the normal vector determined by s (G data points).
2.5 INCREMENTAL CELL ENUMERATION (ICE) ALGORITIM
Due to the symmetry of the 0-1 loss, where data item is assigned label of either or -1, the 0-1 loss for the negative orientation of a hyperplane can be directly derived from the positive orientation of the same hyperplane without calculating it explicitly. The following theorem formalizes this relationship.
Theorem 5. Symmetry fusion theorem. Consider dataset D of data points dimension in general position, along with their associated labels. Let be hyperplane which goes through D out of data points in the dataset D, separating the dataset into two disjoint sets D+ and D- If the 0-1 loss for the positive orientation of this hyperplane is then the O)- loss for the negative orientation of this hyperplane is N -- D.
Therefore, the 0-1 loss linear classification problem can be solved by enumerating only the positive negative-oriented hyperplanes, rather than both.
We now have all the necessary components to construct our algorithm, which enumerates linear classification decision hyperplanes and thus solves 3). Theorem 3 states that all globally optimal solutions to this problem are equivalent (in terms of 0-1 loss) to the optimal solutions contained within the set of positive and negatively oriented linear classification decision hyperplanes (vertices
8

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of the accuracy of our novel ICE algorithm, against approximate methods real-world datasets. Best performing algorithm is marked bold.
datasct
N
D
ICE(%)
SVM(%)
LR(%)
LDA(%)
HA
283
77.03
72.08
73.14
73.85
CA
80.6
77.2
73.6
75.0
CR
95.51
91.10
89.89
89.89
VP
704
97.30
96.88
96.59
96.59
BT
502
78.69
74.50
75.50
74.10
SP
975
94.46
94.05
94.05
94.05
in the dual space) passing through D out of N data points in the dataset D. There exist numerous algorithms for enumerating combinations; for Seample,Ngguyee & Sanner (2013)'s PCS algorithm employed a one-by-one enumeration strategy. However, such a one-by-one approach is inefficient and unsuitable for optimization tasks, as it non-recursive and therefore precludes the use of bound- ing methods for further acceleration.
He (2025) and He Little (2025) provide an extensive discussion of various combination gener- ators defined in both sequential and divide-and-conge conqurruuer styles. We adopt the sequential generator introduced by He & Little (205). The pseudocode presented in Algorithm [ The algorithm has complexity of O (NG+T x GD), where G' is the dimension of the embedded space (with G = D if K 1). Since in line of Algorithm| we eliminate D-combinations at every recursive step, the
algorithm's 's memory usage is O (N
EMPIRICAL EXPERIMENTS
In this section, we analyze the performance of our ICE algorithm empirically. Our evaluation aims test the following hypotheses: (a) the ICE algorithm consistently achieves the highest training accuracy among competing algorithms when allowing ICE to run to termination; (b) the solutions with significantly higher training accuracy (learned using the ICE algorithm) also achieve higher accuracy the test datasets, and (c) the observed wall-clock runtime aligns with the worst-case time complexity analysis.
Exact linear (hyperplane) classification We first compare our exact algorithm, ICE, against sup- port vector machines (SVM) logistic regression (LR), and linear discriminant analysis (LDA) on linear setting, using binary classification datasets from the UCI machine learning repository (Dua & Graff, 2019). As shown in Table ! the ICE algorithm consistently finds solutions with lower 0-1 loss than approximate algorithms.
Due to space constraints, the results of the runtime complexity analysis and out-of-sample tests are presented in Appendix B Figure shows that the empirical wall-clock runtime agrees closely with the theoretical predictions. In Figure [] we compare ICE against the state-of-the -h-t---rtttttt BnB algorithm by Nguyen & Sanner (2013) for solving the 0-1 LCP. Our empirical analysis demonstrates that Nguyen & Sanner 2s algorithm exhibits exponential complexity in the worst-case.
Additionally, we also compare the performance of the ICE and BnB algorithms with that of a mixed- integer programming (MIP) solver for the 0-1 LCP, implemented in MATLAB using the GLPK solver, results shown in Figure (Figure 6) These show that while the MIP solver is more efficient than BnB on small datasets, its performance is less predictable compared with ICE and BnB.
From I we anticipate that exact solutions will not only achieve lower 0-1 loss on training datasets but are also more likely generalize better, yielding lower 0-1 loss on test datasets. To evaluate this hypothesis, reboet] the out-of-sand -f--ole performance of the ICE algorithm using 5-fold cross- validation, compared against approximate algorithms. The results indicate that training linear model with substantially lower training error than the approximate algorithms also leads to stronger generalization in out-of-sample tests, thereby refuting the notion that the optimal solution necessar- ily overfits the data.
We tuned the SVM hyperparameters using standard coarse grid search, testing set of widely spaced values (e.g., (0.01, 0.1, 1,..., 10000) on a logarithmic scale.

---

Published as a conference paper at ICLR 2026
Figure 3: Optimal quadratic classifiers learned by the ICE algorithm (top four panels) achieve 0-1 losses of 9, 16, 17, and 16, while the approximate quadratic classifiers learned by an SVM with degree-2 polynomial kernel (bottom four panels) obtain 0-1 losses of 17, 26, 21, and 22.
Exact hypersurface (quadratic hypersurface) classification To evaluate the algorithm beyond linear classification, we test the ICE algorithm on synthetic datasets whose ground truth is a noisy quadratic boundary with label noise. We compute the exact solution (leamed by ICE) four datasets of size N = 100 and D = 2 and compare it against approximate solutions (learned by SVM with degree-2 polynomial kernel). The results are shown in Figure Similarly, the out-of- sample generalization performance on real-world datasets for the quadratic classifier is reported in Table 3
SUMMARY, DISCUSSION AND FUTURE WORK
In this paper, we have presented incremental cell enumeration, ICE, the first provably correct, worst- case polynomial O (N++1), which is polynomial in N and exponential in varying D, run-time complexity algorithm for solving the 0-1 loss linear classification problem (3. Our empirical inves- tigations show that the exact solution often significantly outperforms the best approximate solutions on the training dataset and also yields lower test error. This finding is critically important because demonstrates that, contrary to widely held belief, globally optimal solutions to the 0-1 LCP can generalize well unseen data. Prior the development of ICE, provably correct exact algorithms- such as those proposed by Nguyen & Sanner (2013) were computationally intractable even for moderate N and small D, and their optimality had not been rigorously proved.
The immediate shortcoming of the algorithm is its exponential complexity in the data dimension D. This combinatorial complexity further compounded in the hypersurface case, where the embed- ding space has dimension O (DK). resulting in a final hypersurface classification algorithm with time complexity (ND*). However, since this problem is NP-hard, the exponential dependence on D and is unlikely to be eliminated unless NP=P. Notably, the ICE algorithm relies solely on matrix operations, allowing for full vectorization and parallelization. Our current implementation uses simple parallelization via the PyTorch library. More sophisticated parallel implementations can be achieved by adopting the divide-and-conquer (D&C) combination generator introduced in (He & Littl 2025). A parallel implementation based on D&C-style recursion, executed on massively parallel GPUs, is expected yield significantly better performance.
REFERENCES
Gerald L. Alexanderson and John E. Wetzel. Simple partitions of space. Mathematics Magazine, 51 (4):220-225, 1978. doi: 10. 10.1080002557XX.1988.19999 1080/0025570X. 1978.119777711
TRLLhttps:://// /ttp:::///oi...//10//
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly- ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(1):228552)) 2019.
10

---

Published as a conference paper at ICLR 2026
Shai Ben-David, Nadav Eiron, and Philip M Long. On the difficulty of approximately maximizing agreements. Journal of Computer and System Sciences, 66(3):496 -14,, 2003.
Anders Bjömerr Oriented matroids. Number 46. Cambridge University Press, 1999.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the wapnik-cherroneen dimension. Journal of the ACM (JACM), 36(4):929-96) 1989.
J Paul Brooks. Support vector machines with the ramp loss and the hard margin loss. Operations Research, 59(2):467-479 2011.
Corinna Cortes and Vladimir Vapnik. Support- networks. Machine Learning 20(3):273-297 1995.
Thomas M Cover. Geometrical and statistical properties of systems of linear inequalities with appli- cations in pattern recognition. IEEE Transactions on Flectronic Computers, (3):326-334, 1965.
David Cox, John Little, Donal O'shea, and Moss Sweedler. Ideals, varieties, and algorithms, vol- ume 3. Springer, 1997.
David R Cox. The regression analysis binary sequences. Journal of the Royal Statistical Society: Series B (Methodological), 20(2):215-233 1958.
David Roxbee Cox. Some procedures connected with the logistic qualitative response curve. Re- search Papers in Statistics: Festschrift for Neyman, pp. 55-71, 1966.
D. Dua and C. Graff. UCI Machine learning repository, 2019. URL http:://archiiie ics. uuii edu/
Jack William Dunn. Optimal trees for prediction and prescription. PhD thesis, MIT, 2018.
Herbert Edelsbrunner. Algorithms combinatorial geometry, volume 10. Springer Science & Business Media, 1987.
Herbert Edelsbrunner, Joseph O'Rourke, and Raimund Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM Journal on Computing, 15(2):341-363, 1986.
Komei Fukuda. Lecture: Polyhedral computation, spring 2016.
Institute for Opera-
fions Research and Institute of Theoretical Computer Science, ETH Zurich. https://inf. ethz.
pdf, 2016.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://wwel
gurobi... com
Xi He. Recursive optimization: exact and efficient combinatorial optimization algorithm design principles with applications to machine learning. PhD thesis, University of Birmingham, 2025.
Xi He and Max. A. Little. Combination generators with optimal cache utilization and communica- tion free parallel execution, 2025. /0/
Xi He, Yi Miao, and Max A. Little. Deep-ice: The first globally optimal algorithm for empirical risk minimization of two-layer maxout and relu networks, 2025. /ttpsttss///rri
abs/2505. 05740
Michael McGough. How bad is Sacramento's air, exactly? Google results appear at odds with reality, some say. Sacramento Bee, 7, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018.
Sreerama K Murthy, Simon Kasif, and Steven Salzberg. system for induction of oblique decision trees. Journal of Artificial Intelligence research, 2:1-32, 1994.

---

Published as a conference paper at ICLR 2026
Tan Nguyen and Scott Sanner. Algorithms for direct 0-1 loss optimization in binary classifica- tion. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pp- 1085-1093, Atlanta, Georgia, USA, 17-19 Jun 2013. Proceedings of Machine Learning Research. URL hhtttpss:/prroceeeeet
ml prw.s / / wgwp///////////nnn/e/aa 3a .html
C. Rudin. Why black box machine learning should be avoided for high-stakes decisions, in brief. Nature Reviews Methods Primers, 2(1):81, 2022.
Yufang Tang, Xueming Li, Yan Xu, Shuchang Liu, and Shuxin Ouyang. A mixed integer pro- gramming approach to maximum margin 0-1 loss classification. In 2014 International Radar Conference, pp. 1-6. IEEE, 2014.
Vladimir Vapnik. The nature of statistical learning theory. Springer Science & Business Media, 1999.
Kush R Varshney and Homa Alemzadeh. On the safety of machine learning: Cyher-physical sys- tems, decision sciences, and data products. Big Data, 5(3):246-255. 2017.
Rebecca Wexler. When a computer program keeps you in jail: How computers are harming criminal justice. New York Times, 13, 2017.
A PROOFS AND DEFINITIONS
Definition 3. Monomial. monomial with respect to a D-tuple x (21, 22)) is a product of the form
M x² x1 x2
DD
(10)
where (01, 02 ... (D)) and 01, 02 .., monomial is the sum |a| 01 + ,g. On nonnegative integers. The total degree of this On- When a = 0 = (O,..., 0), x =
Definition 4. Polynomial. polynomial combination (with coefficients in the field R)) of monomials. A polynomial P P(x), or P in short, will be given in the form
11, T2 ED with coefficients in a finite linear
((x) Σ waa E IR.
(11)
where i is finite. The set of all polynomials with variables æı, F2.22... ...,............................ and coefficients in R is denoted by [21,
or IR [z).
Let P = E, w be polynomial in R [z). Then is called the coefficient of the monomial x If Wi + O, then w called a term of P. The maximal degree of P, denoted deg (P). is the maximum |as] such that the coefficient ag is nonzero. For instance, the polynomial P P(x)) 5x7 + 32 + 2 + 21 + 32 + 3 for æ E R has six terms and maximal degree two. Note that, since |as| is defined as the sum of monomial degree, polynomial 1 (x) 5x + 1 has degree four.
The number of possible monomial terms of degree K polynomial is equivalent to the number of ways of selecting K variables from the multisets of D+1 variables This is equivalent to the size K combinations of D + elements taken with replacement. In other words, selecting K variables from the variable set (No, ..,..., ..) in homogeneous coordinates with repetition, leads to the following fact.
Fact 1. If polynomial P in R [r1, T2 ..., TDD ppp
has maximal degree K, then polynomial P has
( DD+K K
monomial terms at most.
Lemma. For set points = {z, E R. PRP:n
n e A in general position, the total number of linear dichotomies in Cover's function counting theorem, is the same as the number of cells of the dual arrangement Hp, plus the number of bounded cells of Hp. In other words, denote the number of dichotomies for N data items in RDD as Cover (N, D + 1) (D denote the dimension of data in
'There are D 1 variables considering polynomials in homogeneous coordinates, i.c. projective space PP.
12

---

Published as a conference paper at ICLR 2026
homogeneous coordinates) and the number of cells and bounded cells of an hyperplane arrangement in RR as BD (HD) and Cp (Hp). Then
Cover (N, + BD (Hb) CD (Hp)
(12)
Proof. Given set of points D fan E ERD: E } in general position. Cover 1965/s is function counting theorem states that the number of linearly separable dichotomies given by affine hyper- planes
N INd) (
Cover (N, D + 1) 2 d=0
(13)
The original Cover's function counting theorem counts the number of linearly separable dichotomies given by linear hyperplanes. However, the dual arrangement HD consists of set of affine hyper- planes. Nevertheless, the number of dichotomies given by affine hyperplanes in IP for dataset ' is equivalent to the number of dichotomies given by linear hyperplanes for dataset D in R 12+1 (where 'D is the homogeneous datasel, which is obtained by embedding 'D in homogeneous space. Recall that, x (ac 1) is the data in homogeneous coordinates).
Alexanderson & Wetzel 1978)) (and see also Edelsbrunner et al. 1986) show that shows that for a
N d
simple arrangement H. (hn N in RD, the number of cells is CD (H) Ed
N N-1
)
and the number of bounded regions is BD (H)
D
Putting these two pieces of information together, obtains
Bp (HD) CD (Hz)
N
Σ
N
D
d
d=0
NN-1) + Σ
D
N
--1
(-11 ]
+
1=0
(14)
Σ
NN-1
N
+ エ
(N
(N=1)
d
d=n
d=0
18-11
d
d=0
=Cover (N, D 1).
Lemma. For dataset D in general position, each of Cover's dichotomies corresponds to cell in the dual space, and dichotomies corresponding to bounded cells have no complement cell (cells with reverse sign vector). Dichotomies corresponding the unbounded cells in the dual arrangements é (D) have a complement cell.
Proof. The first statement true because of the order preservation property - data item æ lies above (below) hyperplane h if and only if point Φ-1 (h) lies above (below) hyperplane ó (x). For a dataset D and hyperplane h, assume h has a normal vector w (in homogeneous coordinates) and there is no data item lying on h. Then, hyperplane h will partition the set D into two subsets Dj {ar, wo x: > 0} and DJ {ar, w x 0}. and according to the Thm. [ DD has unique asso- ciated dual arrangement (D). Thus, the sign vector of the point Φ- (h) with respect arrange-
ment (D) partitions the arrangement into two subsets Φn (D) = { (xx)) v (h) 0}
and dh (D)- { { ( - (h) < =0). where vI fe..) is the normal vector the dual hyperplane (, in other words, point 6- (h) lies in cell of arrangement ø (D).
13

---

Published as a conference paper at ICLR 2026
Next, it is necessary to prove that bounded cells have no complement cell. The reverse assignment of the bounded cells of the dual arrangements & (D) cannot appear in the primal space since the transformation o can only have normal vector pointing in one direction, in other words, transfor- mation Φb: DD = 01 + P222 + PD-1 PD implies the Dth component of normal vector is 11 For unbounded cells, in dual space, every unbounded cell f associates with another cell such that has an opposite sign vector to f. This is because every hyperplane Φ (In) is cut by another N 1 hyperplanes into N + 1 pieces (since in simple arrangement no two hyperplanes are parallel), and each of the hyperplanes contains two rays, call them r2. These two rays point in opposite directions, which means that the cell incident with rı has an opposite sign vector to r2 with respect to all other N - 1 hyperplanes. Therefore, it is only necessary to take the cell f incident with rı, and in the positive direction with respect to e (.x),, take g to be the cell incident with ra. and in the negative direction with respect to Φ (. In this way, two unbounded cells f and g are obtained with opposite sign vectors. This means that, for point o 6- (h) in these unbounded cells, this hyperplane partitions the dataset to Dj," and D and it is possible to move the position of hyperplane h in the primal space. So, there exists new hyperplane h obtained by moving h. and partitions the dataseto D = D/ and D = Dj-- In other words, h' has opposite assignment compared to hyperplane h. This corresponds, the dual space, to moving a point o (h) inside the cell f. to cell g. For instance, in the simplest case, hyperplane can be moved from left-most. to the right-most to obtain an opposite assignment without changing the direction of the normal vector.
Since each of Cover's dichotomies corresponds to cell in the dual space, and dichotomies cor- responding to bounded cells have no complement cell (cells with reverse sign vector), lemma 2 demonstrates that all possible Cover's dichotomies of given dataset D can be obtained by enumer- ating the cells of an arrangement and the complemented cells of the bounded cells. The enumeration of the complements of the bounded cells requires an additional process, as the bounded cells within the arrangement do not have complementary cells. This result directly leads to the following theo- rem.
Lemma. For a dataset D in general position, a hyperplane with l data items lying on it, 0 < k < D correspond to a (D k--face in the dual arrangement Hp. Hyperplanes with D points lying on it, correspond to vertices in the dual arrangement.
Proof. According to the incidence preservation property, k data items lying on a hyperplane will intersect with l hyperplanes, and the intersection of k hyperplanes will create - (D--))-dimessitni dimensiool space, which is a (D- - face and the O-faces are the vertices of the arrangement.
Lemma. Given a hyperplane arrangement = (hn n E NV,, for an arbitrary maximal face (cell) f. the sign vector of f is sign,, (f). For an arbitrary (D dd)-dmennsion face g. 0 < d S D, the number of different signs of signy (g) with respect to sign, (f) is larger than or equal to d, where equality holds only when is conformal to (g is subface of f).
Proof. Denote the number of different signs of signy (g) with respect to sign (f) by Fa.1 (g). In a simple arrangement, the sign vector sign (f) of a cell f has no zero signs, and a (D d)- dimension face has d zero signs. Thus the number of different signs of signy (g) with respect to sign (f) must be larger than or equal to d, i.e., Eo.1 (f) 2 d. If (f g) = 0. then Ea (g) according to the definition of sep (f.g)= = G. In this case, f. g are conformal. By contrast, if f.g are not conformal, i.e. sep (f, g) + 0, and assuming |sep (ʃ. = C, then according to the definition of the objective function and conformal faces, Ea.1 (sign (J)) d+ C. Hence, Ea.1 (sign (0)) 2 d. and equality holds only when g is conformal to f.
Theorem. Consider a dataset D of N data points of dimension D in general position, along with their associated labels, denote Secembs as the set of all D-combinations with respect to dataset D. Then we have following inequality
argmin min (Eo-1 (wa). Eo-1 (-w,)) S argmin Eo-1 (w)
(15)
S
wCRD+1
where w, represents the normal vector of the hyperplane that pass through the D-combination of data s, and -w, is the negation of w.. The inner min on the left-hand side ensures that for each s e Skcombe, we take the smaller of Fa.1 (In.) and F (-wx), the outer argmin finds one of the value of
14

---

Published as a conference paper at ICLR 2026
that minimizes this quantity over all E Skcombs In other words, [5) means that all globally optimal solutions to problem (3), are equivalent (in terms of O-1 loss) to the optimal solutions contained in the set of solutions of all positive and regatively-orienteer linear classification decision hyperplanes (vertices in the dual space) which go through D out of N data points in the dataset DD
Proof. First, transform datasetD to its dual arrangement. According to Lemma 2 and Lemma 3 each dichotomy has corresponding dual cell and the sign vectors for all possible cells in the dual arrangement and their reverse signs are evaluated, the optimal solution for the 0-1 loss classification problem can be obtained. Assume the optimal cell is f. it is required to prove that, one of the adjacent vertices for this cell is also the optimal vertex. Then, finding an optimal vertex is equivalent to finding an optimal cell since the optimal cell is one of the adjacent cells of this vertex. According to Lemma 5] any vertices that non-conformal have corresponding 0-1 loss with respect to signæ (f) which is strictly greater than D. Since f is optimal, any sign vectors with larger sign difference (with respect to sign (f)) will have larger 0-1 loss value (with respect true label t). Therefore, vertices that are conformal to f will have smaller 0-1 loss value, thus one can evaluate all vertices (and the reverse sign vector for these vertices) and choose the best one, which, according to Lemma 3 is equivalent to evaluating all possible positive and negatively-orientel linear classification decision hyperplanes and choosing one linear decision boundary with the smallest 0-1 loss value.
Theorem 6. Symmetry fusion theorem. Consider dataset D of N data points of dimension D in general position, along with their associated labels. Let be hyperplane which goes through D out of N data points in the dataset D, separating the dataset into two disjoint sets D+ and D= If the 0-1 loss for the positive orientation of this hyperplane is I, then the 0-1 loss for the negative orientation of this hyperplane is N - D.
Proof. Assume there are m + and m data points misclassified D+ and D=, then the 0-1 loss for h equals| | m + m Denote the hyperplane h with negative orientation as h- In the partition introduced by / all correctly classified data by le will be misclassified in 4-. Thus the 0-1 loss of
h is D m + + [D m Since [D 1 D N N D. we obtain the 0-1 loss for h which
is N D
B ADDTIONAL EXPERIMENTS
B.I RUN-TIME COMPLEXITY ANALYSIS
We test the wall clock time of our novel ICE algorithm on four different synthetic datasets with dimension ranging from 1D to 4D. The DD-dimensional dataset has data size ranging from N = 1000 to 60000, the 2D-dimensional ranges from 150 to 2400, 3D-dimensional from 50 to 500, and dimensssia data ranging from 30 to 200. The worst-case predictions are well-matched empirically (see Figure
All decision boundaries computed by exact algorithms entail the same, globally optimal 0-1 loss. Therefore, the only meaningful comparison between ICE and any other exact algorithms is in terms of time complexity. Here, we compare the wall-clock run time of our ICE algorithm with the exact As branch-and-
branch-and-bowd bound (BnB) algorithm Nguyen & Sanner (0113). (2 in the worst case it must test all possible assignments of data points to labels which requires an ex- ponential number of computations, by comparison to ICE's s worst case polynomial time complexity arising from the enumeration of dichotomies instead. Empirical computations confirm this reasoning (see Figure 5) predicting for instance that for the N = 150 data size with D = 3, ICE would take 1.2 seconds worst-case whereas BnB would take approximately 1000 seconds (nearly 317 years), demonstrating the clear superiority of our approach.
algorithm,
Additionally, we compare the performance of the ICE and BnB algorithms with that of a mixed- integer programming (MIP) solver for the 0-1 LCP, the results is shown in Figure 6 The results show that while the MIP solver is more efficient than BnB on small datasets, its performance is less predictable compared with ICE and BnB. This is highlighted by the fact that the number of sampling points explored by the MIP solver is smaller than those of BnB and ICE, as the MIP solver had not yet terminated to obtain the exact solution within our three-hour time limit.
15

---

Published as a conference paper at ICLR 2026
datasets
N
D
ICE (%)
SVM (%)
LR (%)
LDA (%)
HA
283
3
#77.35/74.39
72.21/71.23
72.39/72.28
73.10/74.74
(0.58)((.666)
(0.58)((.000)
(0.92)((.15))
(0.85)((.666)
CA
72
5
81.75/61..3
71.93/60.00
76.49/58.67
76.14/58.69
(2.66)((.58)
(7.85)(0816 16)
(4.40V(7730)
(6.75)((730))
CR
89
6
#95.49/83.33
92.11/85.56
90.99/82.22
90.99/82.22
(1.18)((786)
(1.89)(10.09)
(2.36)(9.13)
(2.36)(12.67))
VP
704
2
*96.93/97.59 96.77/97.02
96.02/96.03
96.48/96.88
(0.44)((0.15)
(0.49)((.32)
(0.00)((0229)
(0.63)((228))
BT
502
4
#79.50/74.06
74.96/72.67
76.06/73.27
75.81/73.07
(0.82)(2.36)
(0.82)((.85)
(0.79)((3550)
(1.09)((.533)
SP
975
3
*94.49/94.15
94.13/93.74
94.13/93.74
94.13/93.74
(0.27V(1.00 .00)
(0.33)((L33)
(0.33)((013))
(0.33W(1.33)
Ai4i
10000
6
97.45/97.44
96.62/96.57
96.99/96.99 90
97.00/96.75
(0.10)(0.36)
(0.33)((.53)
(0.10)((044)
(0.13)(0.33)
AIDS
2139
23
87.75/87.61
86.84/86.49
86.56/86.58
85.71/84.90
(L.09)((.12)
(0.32)((.24))
(0.19)(1.23)
(0.25)((.30)
AL
243
14
98.45/98.36
95.77/95.10
96.18/95.51
94.53/88.57
(0.92)(2.37)
(0.89)((.005
(1.06)((..1)
(0.53)((.22))
AV
2043
7
88.94/88.31
87.14/87.33
86.94/87.0K .04
86.27/86.70
(0.25)(2.21))
(0.41)((1.64)
(0.36)((1551)
(0.42)/(1339)
RC
3810
7
93.86/92.55
92.83/92.78
92.86/92.81
93.14/92.65
(0.29V((105
(0.18)((0.78)
(0.25)(0.67)
(0.17)((059))
DB
19 1146
79.48/79.74
69.63/67.65
70.57/69.39
73.93/70.61
(1.76V(0.70)
(0.01)((0.03)
(0.01)((.03)
(0.01)(0.02)
SO
27 1941
77.70/76.04
73.03/73.62
72.78/72.96
73.81/74.81
(0.45)((.88)
(0.01)(O.01)
(0.00)((.02)
(0.01)(0.03)
SS
51433 3
86.58/86.68
82.78/82.71
79.69/79.65
80.31/80.32
(0.04)((.11) (0.00)((0000)
(0.00)((0000)
(0.00)((.00))
Table 2: Comparison of the accuracy of our novel incremental cell enumeration (ICE) algorithm, against approximate methods: SVM, logistic regression (IRR), and linear diseriminant analysis (LDA) real-world datasets. Results reported mean accuracy loss over training and test sets in the format: Training Error / Test Error (Standard Deviation: Train / Test). Exact solutions are marked with * otherwise approximate, obtained using stochastic coreset selection for tractability purposes C Best performing algorithm is marked bold.
16

---

Published as a conference paper at ICLR 2026
10
10
Wall clock time [e)
10
109
10"1
10
101
10
10a
10
10
Problem size (N)
Log-log wall-clock rum time (seconds) for the ICE algorithm in 1D 4D synthetic datasets, against dataset size N. where the approximate upper bound is disabled (by setting it to N). The run- run-time time curves from left right (corresponding to D 1, 2, 3, 4 respectively), have slopes 2.0, 3.1, 4.1, and 4.9, very good match to the predicted worst-case run-time complexity of O (N3), (N²), O (N*), and O (No) respectively.
Figure 4:
Ball
ICE
168
Ested model
107
105
105
Wall elock time (4
105
103
10
10
100
10
10
1
10
5
7
40
60
120
Probleu size (N)
Figure 5: Log-linear wall-clock run time (seconds) plot comparing the ICE algorithm against the branch-and-boun (BnB) algorithm of Nguyen & Sanner (2013) (Matlab implementation provided by the authors) on three dimensional synthetic data. On this log-linear scale exponential run time appears linear function of problem size N, whereas, polynomial run time is logarithmic func- tion of N. Fitting appropriate models (lines) to the computational experiment data (dots) provides clear evidence of this prediction.
17

---

Published as a conference paper at ICLR 2026
10
10
Bol
10²
fitted model
10
ICB fited model
3EEP Bitsed model
Wall clock time (4)
109
10"1
10
10:3
10
10
10
10"
Problem size (MV
Figure 6: Log-linear wall-clock run time (seconds) plot comparing the ICE algorithm against the branch-and- -andc--nd- (BnB) algorithm of Nguyen & Sanner (2013) (MATLAB implementation pro- vided by the authors) and the mixed-integer programming (MIP) solver (implemented in MATLAB using GLPK solver) three dimensional synthetic data. On this log-linear scale exponential run time appears as a linear function of problem size N, whereas, polynomial run time is a logarithmic function of N. Fitting appropriate models (lines) the computational experiment data (dots) pro- vides clear evidence of this prediction. The smaller sampling size of the MIP solver compared with BnB and ICE is due to the solver not terminating within the three-hour time limit, highlighting its much less predictable performance.
B.2 OUT-OF-SAMER GENERALIZATION TEST
Due to the inherent combinatorial complexity of the 0-1 loss classification problem, the ICE algo-
rithm becomes computationally intractable for high-dimensional datasets. In Table 2 except for datasets that are tractable for ICE algorithm (those datasets evaluated in Table [T]. we train all other datasets using the coreset selection method (ICE-coreset) introduced by (He et al. 2025). This method acts randomized wrapper for exact algorithms (pseudocode is provided in Appendix C). In brief, the coreset selection method reduces the dataset by eliminating subsets associated with solutions exhibiting higher (-1 loss. This process is repeated until the reduced dataset (the coreset) becomes tractable for the ICE algorithm. As predicted, the solutions obtained by the ICE-coreset algorithm not only perform well training data but also demonstrate higher test accuracy, refuting the misconception that exact algorithms necessarily overfit the training set.
B.3 HYPERSURFACE CLASSIFICATION
The out-of-sample generalization performance on real-world datasets for the quadratic classifier reported in Table
C CORESET SELECTION METHOD
Algorithm 2 shows the structure of the coreset selection method.
18

---

Published as a conference paper at ICLR 2026
datasets
N
D
ICE (%)
SVM (%)
HA
283 3
77.35/73.68
73.01/66.67
(0.20/0.00)
(0.00/0.00)
CA
72 5
78.95/86.66
70.18/46.67
(0.01/0.00)
(0.02/0.01)
CR
89 6
92.96/94.44
91.55/94.44
0.20/0.13
(0.00/0.00)
VP
704
2
97.12/96.45
96.63/95.74 74
(0.01/0.00)
(0.00/0.01)
BT
502
4
78.30/80.00
73.56/75.25
0/0.44
(0.01/0.02)
SP
975 3
95.13/91.79
94.74/91.22
(0.00/0.00)
(0.00/0.00)
Table 3: Empirical comparison of the training accuracy of our ICE algorithm against an approxi- SVM with 2 polynomial kernel real-world datasets. Results reported as mean accuracy over training and test sets in the format: Training Accuracy Test Accuracy (Standard Deviation: Train / Test). Best performing algorithm marked bold.
Algorithm ICE with coreset filtering
Input: M: block size; R: number shuffles in each filtering round; L: max-heap size; Buaxi maximum input size for ICE algorithm; e (0, 1]: heap shrinking factor Output:
Max- heap Hi containing top configurations and associated data
blocks
C ds initialize coreset with dataset
2: while [C] < Bmax do
3: Divide into
[C| M
blocks: Cp = (C1, O2,.,,,,..., Crian
O2.,,,......
4: Initialize max-heap Hr of size L
5: for = 1 to R do
6: for all C CB do
7: enfg t- ICE (Di, K)
8:
Hr.push((cnfp C*) end for
9:
10: C +- (H.L) // merge blocks and remove duplicates
L Lx l/l shrink heap size
12: end for
end while
14: enfg- + ICE(Dt, K. // final refinement
15: p..push(cnfg.
16: return Hi.
19


Reviews:
[{"review_id": "IZ3W9pUKAT", "reviewer": "Reviewer_czqw", "summary": "The paper presents a novel, provably optimal algorithm called Incremental Cell Enumeration (ICE) for exactly solving the NP-hard 0-1 loss linear classification problem. The authors derive the algorithm by analyzing combinatorial and incidence relations through the lens of hyperplane arrangements and point-hyperplane duality, resulting in a method with a worst-case complexity of $O(N^{D})$, which is polynomial in the number of data points (N) but exponential in dimension (D). The paper formally proves that the globally optimal solutions lie within the set of hyperplanes defined by D data points and demonstrates ICE's superior computational efficiency and ability to achieve better generalization compared to state-of-the-art approximate and exact Branch-and-Bound methods on real-world datasets.", "questions": "1. The reported worst-case time complexity seems to vary slightly across the paper: it is initially stated as $O(N^{D})$, later as $O(N^{D+1})$, and the general hypersurface complexity in Algorithm 1 is $O(N^{G}×G^{3})$. It would be better to standardize and clarify the exact worst-case run-time complexity for the linear case (K=1).\n\n2. The paper convincingly demonstrates superior theoretical and empirical performance for linear classification (K=1), but how does it extend to the polynomial hypersurface classification (K>1), and how does the high-dimensional results rely on an approximation wrapper? To demonstrate the practical viability of this major theoretical contribution, please provide empirical validation for small D and K>1 (e.g., quadratic boundaries, K=2, on D=2 or D=3 data).", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper introduces the Incremental Cell Enumeration (ICE) algorithm and makes significant advancements in the field of exact classification, particularly for the challenging 0-1 loss objective. The paper provides clear definitions and a structured narrative from the problem definition to the complex geometrical analysis and final algorithmic implementation. The empirical results provide a critical empirical insight on generalization, showing that achieving optimal training accuracy often leads to stronger generalization (higher test accuracy) compared to approximate methods.", "weaknesses": "1. The paper successfully generalizes the theoretical framework using the K-tuple Veronese embedding to solve the 0-1 loss polynomial hypersurface classification problem. However, the empirical section explicitly states that experiments were restricted to the linear case (K=1). To fully support the significance and utility of the theoretical extension, empirical results for low-dimensional data (D≤3) with K>1 must be included.\n\n2. The tractability is limited to low dimensions which undermines real-world applicability. It would be preferable to incorporate a formal analysis (or reference) that provides a rigorous approximation bound for the 0-1 loss achieved by the ICE-coreset relative to the true global optimum. This would bridge the gap between the theoretical exactness of ICE and the practical approximation needed for real-world data sizes and dimensions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uYhzDWGbbw", "reviewer": "Reviewer_TkkK", "summary": "This paper proposes an algorithm called incremental cell enumeration (ICE) which solves the classification problem directly with the 0-1 loss. It is claimed that the proposed algorithm is significantly faster than the existing PCS-type algorithm, and outperforms the baseline of linear classifiers such as the SVM and logistic regression in terms of classification accuracy. The proposed method is claimed to have exact optimality supported by a geometric interpretation. The implementation of the ICE algorithm is standalone and does not depend on mixed integer solvers.", "questions": "1.  As stated in Theorem 5, the 0-1 loss is calculated as $l$ and $N - l - D$. Does it mean that the $D$ points where the hyperplane goes through are counted as correctly classified? \n2. How was SVM tuned (grid over the parameter $C$) and how is the class weight set?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method has clear geometric framing. The dual view has an intuitive explanation of the candidate enumeration.\n2. The reported speedup over PCS is significant.\n3. The paper has a self-contained algorithm, so it is easy to run in practice.", "weaknesses": "1. The paper has limited practice use. The method is restricted to very low dimensions and scalability is unclear.\n2. Although the paper claims the exact optimality, it is not clearly shown that the global 0-1 minimizer must be included on some D-point hyperplane so the ICE algorithm miss still miss that.\n3. In Table 2, many rows show test accuracy better than train, which is atypical. Hence performance claims seems to be not trustworthy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MxFvh0syLb", "reviewer": "Reviewer_zBLK", "summary": "The paper presents Incremental Cell Enumeration (ICE), an algorithm that exactly solves the 0–1 loss linear classification problem. The authors build on results from combinatorial geometry and oriented matroid theory to provide a constructive, provably correct enumeration method for all linear dichotomies in $O(N^D)$ time. They also extend the approach to polynomial hypersurfaces via Veronese embeddings.\nEmpirical results on real datasets show that ICE achieves globally optimal training accuracy and often exhibits good generalization performance, while outperforming prior exact algorithms such as branch-and-bound in runtime.", "questions": "1. How does ICE scale beyond low-dimensional data (e.g., D > 10) in practice?\n2. Could the framework be extended to multi-class or structured output settings?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Theoretical rigor and clarity: The paper offers a clean, self-contained, and mathematically rigorous development of the theory behind exact 0–1 loss classification. The exposition is clear and logically structured.\n\n2. Conceptual contribution: Establishing a provably correct standalone algorithm for exact 0–1 loss optimization is intellectually meaningful and addresses a long-standing question in the theory of linear classifiers.\n\n3. Technical soundness: The results and proofs appear correct and well motivated. The connections between hyperplane arrangements, dichotomies, and duality are carefully worked out.\n\n4. Empirical validation: Experiments are convincing within the scope of small- to medium-scale datasets and demonstrate that the exact solutions generalize well.\n\n5. Overall presentation: The paper is very well written, with precise notation and a transparent link between theoretical and empirical parts.", "weaknesses": "1. Scope and scalability: The proposed method has exponential dependence on the feature dimension D. Although this is inherent to the problem, it limits practical applicability. The discussion of computational limits and possible parallelization or approximation schemes could be expanded.\n\n2. Empirical breadth: The experimental section, while solid, remains narrow. It would strengthen the work to include more challenging benchmarks or comparisons to small-scale MILP-based or neural surrogate solvers.\n\n3. Accessibility of theory: The theoretical sections are dense, and readers outside geometry or matroid theory may struggle. A concise figure or schematic illustrating the relationships between the primal and dual spaces could improve readability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Sue5TGVI3n", "reviewer": "Reviewer_iFiA", "summary": "In this paper, by analyzing the combinatorial and incidence relations between hyperplanes and data  points, the authors derive a rigorous construction algorithm, incremental cell enumeration (ICE), that can solve the 0-1 loss classification problem exactly in $O(N^D)$—exponential in the data dimension D. ICE is then generalized  to address the polynomial hypersurface classification problem.\n\nThe effectiveness of ICE is demonstrated on UCI datasets, achieving optimal training accuracy for small-scale datasets and higher test accuracy on most datasets. Furthermore, the complexity analysis shows that the ICE algorithm offers superior computational efficiency compared with state-of-the-art BnB algorithm.", "questions": "1. In Table 2, the \"training accuracy\" should be \"testing accuracy\"?\n2. The testing accuracy of harder problems, such as Ai4i etc., is given in Table 2. Why are the training accuracy of them not reported?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Sound theoretical results.\n2. Extension to polynomial hypersurface classification problem using K-tuple Veronese embedding.\n3. Better training accuracy than baselines.\n4. Much faster than BnB in the worst-case.", "weaknesses": "1. The complexity of ICE is exponential, which makes it unsuitable for large-scale or high-dimensional problems. \n2.  The sequential generator in the ICE algorithm, which is core of ICE that enumerates all liner classification decision hyperplanes, is the\n introduced by He&Little(2025).\n3. There are no experimental evaluations for nonlinear cases (K>1) for the extension to polynomial hypersurface classification problem.\n4. line 125, \"which rigorously explains why the PCS algorithm of for solving the linear classification problem\" is redundant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FgXIVgxeBn", "reviewer": "Reviewer_Fcxj", "summary": "The paper addresses the traditional NP-hard 0-1 loss linear classification problem by introducing a new algorithm called Incremental Cell Enumeration (ICE). The authors first introduce a new theorem showing that to find a globally optimal classifier, it suffices to consider hyperplanes defined by any combination of $D$ data points (where $D$ is the feature dimension).  \n\nThis result formalizes an observation by Nguyen & Sanner (2013) and explains why their combinatorial search could find the exact solution. The authors further introduce a “symmetry fusion” theorem (Theorem 5) to avoid redundant checks of both orientations. The paper also extends the theory to non-linear classification by polynomial hypersurfaces. The authors introduce a practical algorithm based on these insights. Instead of naive enumeration of all $D$-combinations of $N$ points, which is computationally inefficient, the paper improves this through an incremental combination generation strategy that efficiently traverses the space of combinations without heavy repetition.\n\nThe paper demonstrates ICE on several real-world datasets, showing that it achieves higher training accuracy than SVM, LDA, and logistic regression, and requires significantly less computational time than SOTA BnB algorithms.", "questions": "- In Algorithm 1, the input data points are reordered by an initial SVM weight vector ($w^$) and sorted by $|w^{\\top}x|$. Could the authors clarify the purpose of this step?\n\n- How does ICE compare against Nguyen & Sanner’s other proposed algorithms? How does ICE compare against MILP-based formulations?\n\n- Fixing or clarifying the rationale for these partial comparisons: runtime-only versus BnB and accuracy-only versus surrogates, would help assess whether any conclusions about performance tradeoffs are generalizable.\n\n- Empirical results on scaling with D, even in synthetic settings, would clarify the claim of its usability.\n\n- Additional insight into how ICE handles label noise or imbalance would help evaluate whether the generalization claims hold in a more realistic setting.\n\n- Experiment in ICE in polynomial feature spaces (e.g., $K = 2$) would better understand the method’s contribution and whether non-linear extensions are viable in practice.\n\n- The theoretical results assume the data has no special degeneracies like more than $D$ points exactly on one hyperplane. In practice, datasets might violate this (e.g., duplicates or correlated features). How does the ICE algorithm handle such cases?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper highlights an interesting conflict from previous works' observation and provides new theoretical insight to address such conflicts (Theorem 3), bridging the gaps between three combinatorial analysis works from past literature. This has a high potential impact on both theory and practice.\n- The paper introduces a novel Symmetry Fusion Theorem how the misclassification error of a hyperplane’s reverse orientation can be obtained analytically.\n- The majority of claims in this paper are supported with formal mathematical proof or a lemma, and the complexity analysis is transparent: the paper clearly derives the worst-case runtime and memory use.\n- The paper practical algorithmic solution based on these insights for small-to-moderate problem sizes, with experiments to demonstrate that ICE offers higher training accuracy than other surrogate optimization methods and lower computational time compared to the SOTA BnB method.", "weaknesses": "Some weaknesses in the methodology need more clarification:\n- In proof, the authors assume that increasing the sign‐difference increases the 0–1 error (line 718). However, it's unclear to me how sign differences between sign vectors of dual cells can directly translate into classification errors on true labels.  For example, a candidate $g$ differing in three signs might flip one of the errors to correct and flip two previously correct points to wrong. Thus, flipping signs could increase or decrease misclassification depending on the labels. The authors did not make an alignment between the sign and the true label. Thus, the \"non-conformal vertices must have strictly higher 0–1 loss\" is not correctly proven, which leads to a flaw in the major claim made in this paper.\n\n - Almost every result assumes the data is in \"general position\". This is a strong assumption that seems like it would often be violated in Real datasets (e.g., consider duplicate points or points that only differ by a very small epsilon). It's not clear whether ICE would still guarantee good solutions in this case.\n\n- The ICE algorithm has worst-case polynomial time in N only for fixed D, and it remains exponential in D. The paper also acknowledges that the runtime grows exponentially with D, which is a shortcoming of ICE. Therefore, framing this as a “polynomial” algorithm is misleading, since $D$ is part of the input dimension.\n\n- There is no rationale for the initial SVM ordering in Algorithm 1 is heuristic and does not guarantee any bound; it is not analyzed theoretically at all. I may have missed some part, but a better clarification can be helpful.\n\nAlso, the experimental results can be improved:\n\n- **SOTA Baseline** Nguyen & Sanner (2013) proposed multiple algorithms, not just a straightforward BnB. The paper only discusses the basic BnB worst-case. A more comprehensive benchmark against all relevant methods from Nguyen & Sanner (2013) (like prioritized combinatorial search, PCS, and other heuristics) would give a better understanding of ICE’s performance.  The release their code as a zip file I found linked on this [page](https://users.cecs.anu.edu.au/~ssanner/publications.html).\n\n- **MILP Baseline** The paper omits mixed-integer programming (MILP) baselines that were introduced in the introduction. Prior research has formulated 0-1 loss minimization as an MILP (e.g., Tang et al. 2014 for maximum-margin under 0-1 loss, Brooks 2011), and a MILP solver could serve as an exact baseline on small datasets. Including a MILP-based method in the experiments (even if only feasible for small N, D) would have been informative.\n\n- **Missing Evaluation** The paper only evaluates the runtime comparison between the SOTA BnB method, but not its accuracy. Similarly, the paper evaluates only the accuracy of other methods, but not their runtime complexity. The paper does not provide a valid reason why these aspects were excluded from the experiments.\n\n- **Generalization** Although the authors claim that optimal 0-1 loss often generalizes better than suboptimal solutions, this is only demonstrated through observations from cross-validation. In these small datasets, the optimal linear model did well on the test set, but is that always true? What if there’s label noise? The experimental evaluation does not explicitly test robustness to label noise or outliers. Also, class balance is not explicitly discussed, and while some UCI datasets may have imbalanced classes, the authors did not highlight performance under severe class imbalance.\n\n- **Dimensionality of the Data** The paper does not report empirical runtime as D grows. For the more practical usage claimed in the title, the authors should have included synthetic analyses of ICE’s performance against existing methods across different numbers of D.\n- **Non-linear** The authors claim that the ICE algorithm is generalizable to finding optimal 0-1 loss classifiers in non-linear hypothesis spaces. However, the paper does not demonstrate any experiments for $K>1$. All empirical results are for the linear case.\n\n**Reference**\n\nTang, Y. et al. (2014). Mixed-integer programming for 0-1 loss classification\n\nBrooks, J. Paul (2011). \"Support vector machines with the ramp loss and the hard margin loss.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)