Deep-ICE: The first globally optimal algorithm for empirical risk minimization of two-layer maxout and ReLU networks
Authors: Xi He
Yi Miao
Max A Little
Venue: ICLR 2026 Poster (2026)
Keywords: Neural network
Global optimal
Algorithm design
Combinatorial optimization
Primary area: learning theory
TL;DR: The first globally optimal algorithm for empirical risk minimization of two-layer maxout and ReLU networks

Abstract: This paper introduces the first globally optimal algorithm for the
empirical risk minimization problem of two-layer maxout and ReLU networks,
i.e., minimizing the number of misclassifications. The algorithm has
a worst-case time complexity of $O\left(N^{DK+1}\right)$, where $K$
denotes the number of hidden neurons and $D$ represents the number
of features. It can be can be generalized to accommodate arbitrary
computable loss functions without affecting its computational complexity.
Our experiments demonstrate that the proposed algorithm provides provably
exact solutions for small-scale datasets. To handle larger datasets,
we introduce a heuristic method that reduces the data size to a manageable
scale, making it feasible for our algorithm. This extension enables
efficient processing of large-scale datasets and achieves significantly
improved performance in both training and prediction, compared to state-of-the-art approaches
(neural networks trained using gradient descent and support vector
machines), when applied to the same models (two-layer networks with
fixed hidden nodes and linear models).

Published as a conference paper at ICLR 2026
DEEP-ICE: THE FIRST GLOBALLY OPTIMAL ALGO- RITHM FOR MINIMIZING 0-1 LOSS IN TWO-LAYER RELU AND MAXOUT NETWORKS
Xi He
Yi Miao!
School of Computer Science Peking University
School of Computer Science
University of Birmingham Birmingham, B15 2TT, UK yxm2 9 stuentnt.. bham. ac. uk
Beijing, China xi xiheêpku. edu. cn
Max A. Little
School of Computer Science University of Birmingham Birmingham, B15 2TT, UK max1 @mi edd
ABSTRACT
This paper introduces the first globally optimal algorithm for the empirical risk minimization problem of two-layer maxout and ReLU networks, i.e., minimiz- ing the number of misclassifications. The algorithm has a worst-case time com- plexity of O (N:DK+1), where denotes the number of hidden neurons and represents the number of features. It can be can be generalized to accommodate arbitrary computable loss functions without affecting its computational complex- ity. Our experiments demonstrate that the proposed algorithm provides provably exact solutions for small-scale datasets. To handle larger datasets, we introduce heuristic method that reduces the data size to manageable scale, making it feasible for our algorithm. This extension enables efficient processing of large- scale datasets and achieves significantly improved performance both training and prediction, compared to state-of-the-art approaches (neural networks trained using gradient descent and support vector machines), when applied to the same models (two-layer networks with fixed hidden nodes and linear models).
INTRODUCTION
In recent years, neural networks have emerged an extremely useful supervised learning technique, developed from early origins in the perceptron learning algorithm for classification problems. This model has revolutionized nearly every scientific field involving data analysis and has become one of the most widely used machine learning techniques today. Our work focuses on developing in- terpretable models for high-stakes applications. where even minor errors lead catastrophic consequences. For example, an incorrectly denied parole may result in innocent people suffering years of imprisonment due racial bias (Kirchner et al. 2016), poor bail decisions can lead the release of dangerous criminals, and machine learning based pollution models have misclassified highly polluted air as safe breathe (McGough 2018). In such settings, is crucial deploy models that are both accurate and transparent.
Designed the core algorithms, provided theoretical proofs, conducted the main experiments, and wrote manuscript.
Implemented the CUDA version of Deep-ICE algorithm, and co-investigated the ordered generation and memory-fii techniques. Initiated the project and provided supervision and critical feedback throughout the research and writing process.

---

Published as a conference paper at ICLR 2026
One effective way achieve this is to identify the best interpretable model within given hypothesis set a task that is uniquely suited to global optimal (exact) algorithms. Two-layer networks pos- sess rich expressivity. capable of representing any continuous function (Kolmogorov 1957). while remaining interpretable since the output is a linear combination of hidden units. Consequently, the empirical risk minimization (ERM) problem for two-layer networks with ReLUU or Maxout ac- tivation functions is not only practically useful but also theoretically significant, as it provides a foundation for understanding deep networks.
However, finding the ERM solution of a neural network remains extremely challenging. Goel el al. (2020) showed that minimizing the training error of two-layer ReLU networks under squared loss is NP-hard, even in the realizable setting (i.e., determining whether zero misclassification is achiev- able). This result was later extended to I. loss with 0 S P < oc (Froese et al.. 2022 Hertrich] 2022]. In practice, this difficulty is further compounded when optimizing discrete loss functions, such as the 0-1 loss (count the number of misclassification) since the ultimate goal typically in- volves comparing classification accuracy. Even in the simplest case-lineal classification using single hyperplane-the problem of minimizing discrete losses such as the 0-1 loss is NP-hard. The best-known exact algorithm for 0-1 loss linear classification has worst-case time complexity of O (N where N is the number of data is the number of features (He & Little
2023
Nevertheless, since neural networks (NNs) have finite VC-dimension (Brtlett et al. 2019), they can, in principle, be trained exactly in polynomial time (Mohri et al.] 2012). The closest related work is that Arora al. (2016), who proposed one-by-one enumeration strategy train a two- layer ReLU NN to global optimality for convex objective functions. [Hertrich] (2022) later extended their result concave loss functions. However, both studies provide only pseudocode and a vague complexity analysis, without publicly available implementations or empirical validation. Moreover, they do not show how to enumerate the hyperplane partitions; instead, they assume these partitions are given.
Arora et al. (016)) further claim, somewhat anbiguously, that their algorithm has a complexity of (2 NDK poly (N, D, K)) for two-layer ReL.U network with K hidden neurons with respect to N data points in R... The term "poly (N, D, K)" is not explicitly defined; it refers to the complexity of solving a convex quadratic programming problem with K and D variables and N x K constraints, and is therefore polynomial in NN, which we denote as O (a). Therefore, Arora et al. (016))* 's algorithm involves not only extremely large exponents (D x K + C2) but also formidable constant factors (2k x C1).
As result of the ambiguous algorithmic description and complexity analysis, the methods proposed by Arora et al. (2016) and Hertrich (2022) appear more like a conjecture-Suggesinng the existence algorithm-rathe than practically executable solutions. The prohibitive com-
of a polynomial-time plexity in both the exponent and constant terms renders their algorithms impractical even for small- scale problems. This is further highlighted by the absence of any implementation in the eight years since their initial publication. Moreover, their algorithms are limited to convex loss functions, while the fundamental objective of classification is to minimize the number of misclassified instances, i.e., the 0-1 loss.
Interestingly. Bai et al. (0223) show that training ReLU network with L'-regularized con- vex loss objective can be reformulated as a convex program and solved using a general-purpose solver. However, major limitation of such solvers is their unpredictable computational complexity. Moreover, Bai et al. (2023) consider a much simpler problem than optimizing the 0-1 loss the original objective in classification -whoee whooe discrete nature makes it substantially more difficult to optimize. Empirical results from Xi & Little (2023) further demonstrate that even for the simplest network- the linear classifier-usinn general-purpose solver to optimize the 0-1 loss exhibits
'Interpretability is a domain-specific notion, so there cannot be an all-purpose definition. As Rudin 2019 noted "Usually, however, an interpretable machine learning model is constrained in model form so that it either useful someone, or obeys structural knowledge." We claim 2-layer ReLU/Maxout networks interpretable because: 1. Shallow architecture enables direct inspection, 2-layer neural network has a simple, transparent structure. The output is just linear combination of these hidden unit activations. 2. Geometric interpretation of ReLU/Maxout network is clear, with nonlinear activations like ReLU, each hidden neuron represents hyperplane decision boundary in the input space. The network, therefore, partitions the input space into piecewise linear regions.
2

---

Published as a conference paper at ICLR 2026
highly unpredictable behavior and can incur exponential complexity, even in situations where polynomial-tinn time solution exists.
To address these limitations, this paper introduces the first globally optimal algorithm for minimizing 0-1 loss in nwo-Layer ReLU and Maxout networks. Our contributions can be summarized as follows:
First optimal algorithm for 0-1 loss. We present the first optimal algorithm for the em- pirical risk minimization problem of two-layer maxout and ReLU networks under the 0-1 loss. In contrast, prior method Arora el al. (016); Hertrich (2022) are restricted to convex loss functions, which are comparatively easier to optimize than discrete losses such as the 0-1 loss. Our algorithm extends to any computable loss function by adapting the results of He & Little (023) without increasing worst-case complexity.
Two versions of the DeepICE algorithm. Existing methods (Arora et al., 2016 Hertrich 2022) rely on hidden assumptions. In practice, generating hyperplane predictions requires substantial computation, yet their pseudocode initializes all partitions directly without such effort. Moreover, their complexity analyses are ambiguous, hindering both understanding and reproducibility. Consequently, their publication. In contrast, by leveraging a general formalism. our algorithm admits concise and unambiguous definition in single equation (T). We further provide two variants of the DeepICE algorithm: the sequential version (Algorithm 2 which reuses hyperplane predictions via memoization, and the divide-and-conquer version (Algorithm which supports parallelization without inter-processor communication.
implementation has emerged in the eight years since
Improved computational complexity. Our algorithm achieves complexity of O (2k-11 x NDK+1 + N x D substantially better than the approaches of Arora et al. (016)) and Hertrich (2022). which require O (2* C1 x DK+))) in both the best and worst cases. In addition, our algorithm exhibits significantly smaller constant factors. This efficiency enables exact solutions for datasets with formidable combinatorial complex- ity-for example, the problem in Figure which involves 122,468, 448, 960 configurations, can be solved within minutes using our CUDA implementation.
Robustness. When combined with heuristics for large-scale problems, and training ac- curacy is significantly higher than that of SVMs DNNs trained with gradient descent, our algorithm demonstrates strong out-of-sample performance. This result challenges the widely held belief that optimal algorithms necessarily overfit the training data.
The remainder of this paper is organized as follows. Section 2 presents our main theoretical con- tributions: Section 2.1 introduces the necessary background; Section 2.2 explains how geometric insights simplify the combinatories of the problem; Section 2.3 describes the construction of an efficient recursive nested combination generator, which is the core component of the Deep-ICE al- gorithm; and Scction 2.4 presents the fusion law for the Deep-ICE algorithm. Section reports empirical results. Finally, Section summarizes contributions and outlines directions for future research.
THEORY
2.1
THEORY OF LISTS
List homomorphisms
The cons-list is defined as ListR (A) = =[] A: ListR (A); that is, a list is []]A:
either an empty list [] or pair consisting of head element A and tail ListR (A), concate- nated using the cons operator :. For example, 3] = [1, 3, This cons-list corresponds to the singly linked list data structure in imperative languages. The key difference here that we are re- ferring to the model of the data structure i.e., the datatype -raher than a specific implementation. There is a corresponding homomorphism over the cons-list datatype, which a structure- map satisfying
h ([]) algi (())
(1)
h (a : xx) = alga (a, h (z))
3

---

Published as a conference paper at ICLR 2026
where h ListR (A) - X In other words, a homomorphism that sequentially combines each element a with the accumulated result h (x) using the algebra alg.
cons- -ist is simply a recursion
Alternatively, another list model called the join-list is defined as ListJ (A) [] A ListJ/ (A) U ListJ (A). A join-list is either empty, a singleton list, or the result of joining two sublists. The join operator U is associative, i.e., for any 2; y : ListJ, we have: xU(a]Uy (x U [al)Jy = xU((a] Ut) The corresponding homomorphism over join-lists is a structure- preeeevvng map defined as
h ([)) algı (())
h ([a]) = gl ([a))
(2)
h (x) algs (h h
An example of a join-list homomorphism that computes the length of a list uses the definitions algı (l)) = 0, algz (a) = and algs (I U - h (z) + h
Fusion laws An important principle associated with both cons-list and join-list homomorphisms the fusion law, stated in the following two theorems. Its correctness can be verified either by using induction (Bird & Gibbons 2020) or universal property (Bird & De Moor 1996). For brevity, we omit the proofs here.
Theorem 1. Fusion law for the cons-list. Let ʃ be a function and let and be two cons-list homomorphisms defined by the algebras olg and alg', respectively. The fusion law states that foh
g if
f (alg (a, h (z))) alg' (a, h (x)).
(3)
Similarly, the fusion condition for the join-list defined as following.
Theorem 2. Fusion law for the join-list. Let f be a function and let h and g be two join-list homomorphisms defined by the algebras alg and alg' respectively. The fusion law states that f foh
if
f (alg ((h (c), 4 (g)))) = alg' (h (v))). In point-free style this can be expressed more succinctly as f o alg = alg' f x f. where f x g y) (f (x) .9 (v)).
(4)
Equations (3) and (4) are referred to as the fusion condition, which forms the basis for proving the correctness of the derived algorithm.
2.2 PROBLEM SPECIFICATION
Assume we are given a data list ds = [2), 22...,, : [RRP]. where the points are in gen- eral position (i.e., no d + points lie on the same (d - 1)-dimensional affine subspace of R P),,, and D 2 2. We associate each data point In with true label t, [1.-1}. We ex- tend the ReLU activation function to vectors x E IR" via an entry-wise operation a (æ) = (max x1), max (0,z2) max (0, æn)).
Now, consider a two-layer feedforward ReI.U NN with K hidden units. Each hidden node is as- sociated with an affine transformation fw, D+1 R. which corresponds to a homogeneous hyperplane hy with normal vector Wy E D+1 Vk E E (1, K). These K affine trans- formations can be represented by single affine transformation (Wi) I2 D++ + RK where Wi E K (D++1), with rows given by the vectors wk. i.e., WF = (wi, W2, wx). The output of the hidden layer is then passed through the ReLU activation, followed by linear transformation ff (W2): : R + R. where W₂ = (d1, a.,.... ., aak are the weights connecting the hidden layer to the output node. Thus, the decision function fRELU implemented by the network is given by
SREL (W1, W₂) = f (W2)= o o (W1).
(5)
Alternatively, instead of applying the ReLU activation function a followed by a linear transformation I (W2), the rank-K maxout network with a single maxout neuron, replaces both components with a maximum operator maxk K + R. The resulting decision function is given by
fmaxout (Wi) max of (W1) K
(6)
Point-free is style of defining functions without explicitly mentioning their arguments.
4

---

Published as a conference paper at ICLR 2026
Let S denote the combinatorial search space. For the ReLU and maxout networks, define the configurations as $ReLU = (W1, 1, W2) E SReLU and Smaxout = W1 E Smaxout respectively. The ERM problem for both network types can then be formulated as the following optimization
argmin (s),
sES
where Eg.1 (SRELU) = EnEN 1 [sign (FRELU (W,, (x)) for ReLU network, and Eg-1 (Amasout) = -nne 1 [sign (fmasou (W1. zx,) )) + tm] for maxout networks. In the following discussion, primarily focus the maxout network, able in this setting. Unless otherwise stated, when F is used it refers to the objective function for the maxout network by default. Although our algorithm is compatible with any computable objective function, to enable future acceleration strategies, it is beneficial to restrict the choice of objective to be monotonic linear function of the form: Eo-1 (SRalU) EnEN L (Ins tn), such that L (Zn, t,. 2 O.
efficient speed-up technique is avail-
An exhaustive search specification Due to the distributivity of the ReLU activation func- tion-that is, max (0, ab) a (0, b). for a > thehe decision function introduced by the two-layer ReLU network (5) can be rewritten as
fReLU (W1, W2, x) =
an max (0, wx = Σ KEK
2x max (0, |ase wr
(8)
kEK
where t = (x, E D+1 and žạ E [1,-1}.
Similarly, the point-wise definition of the rank-K maxout neuron are defined
fNo ( (W1, 1, x)
max (wxxz
(9)
kEK.
The decision function for two-layer maxout network are simply the linear combination of maxout neurons: Smaxoour (Wi, 22,2)) x) Σeek on (Smo 2W)
From a combinatorial perspective, the direction of the normal vector does not affect the geometric definition of its associated hyperplane. Therefore, equations (8) and (9) indicate that the decision boundary of a two-layer ReLU or a single rank-K maxout neuron are fundamentally governed by K K-combination of hyperplanes, and then combinations of hyperplanes are composed again to form deep neural network. Although the set of all possible hyperplanes in R appears to exhibit infinite combinatorial complexity- since each hyperplane is parameterized by a continuous valued normal vector W&-the finiteness of the dataset imposes crucial constraint: only finite number of distinet data partitions can be induced by these hyperplanes. This observation introduces a natural the space of hyperplanes, where two hyperplanes considered
notion of equivalence classes in the same equivalence class if they induce the same partition over the dataset.
Indeed, according to the 0-1 loss linear classification theorem given by He & Little 2023 when optimizing the 0-1 loss (i.e., minimizing the number of misclassified data points), a hyperplanes in R an be characterized as the D-combinations of data points. Specifically, each critical hyperplane
O (NP) possible corresponds to the affine span of D data points, leading to a total of INN
hyperplanes. This result implies that although the parameter space continuous, the effective com- binatorial complexity of the 0-1 loss classification problem is polynomial in N (for fixed D). Each two-layer network with hidden neurons induces up to 2 distinct partitions of the input space, determined by 2 possible directions of the normal vectors. These configurations can be encoded length- K binary assignment asgn (a1, (01,...ak, ax) {1, 1 Accordingly, a two-layer ReLU maxout network can be characterized by the pair enfg (nc, asgn): (NC, {1, (1. where denotes nested combination, representing K-combination of hyperplanes.
: .C
[[R DI]
Thus, the combinatorial search space of two-layer NN, denoted S (N, K, D) consists of the Carte- sian product of all possible possibleK-combineae -combinations of hyperplanes and the 2 binary assignments.A prov- ably correct algorithm for solving the ERM problem of the two-layer network can be constructed by exhaustively exploring all configurations S (N, K, D) and selecting the network that minimizes the 0-1 loss. This procedure is formally specified
DCe (D, K) ming.1 (K) eval (K) o ep (basgns (K)) nestedCombs (D, K) (10)
5

---

Published as a conference paper at ICLR 2026
where DeepICE (D,K): : [RP] + (NC, x Css x NCss, and NCss = [[[[=P]]]
and Cas = [[[RP]]]. represent nested combinations and combinations, respectively. For the par- allelization concerns, DeepICE K) returns not only the optimal configuration for the input dataset D but also the intermediate representations NCss and Css. In the specification above, the input list xs [R]] is left implicit. The function DeepICE (D, K, ds) generates all possi- ble K-combinations of hyperplanes (K-hidden neuron networks) by and basgus (K) produces all binary sign assignments of length K. These are combined using the Cartesian product operator cp (z. = [(a, b) a f z, b + y/- Each resulting network is then evaluated by eval (K), which computes the objective value by considering all 2 possible orientations of the hyperplanes and selecting the best. Finally, ming-1 (K) selects the configuration that minimizes the 0-1 loss.
In constructive algorithmics community (Bird & De Moor 1996), programs initially defined as provably correct specifications, such as as-(10) from which efficient implementations are derived using algebraic laws like fusion. Efficiency arises both from applying fusion transformations and from designing efficient generators. To the best of our knowledge, no prior work has explored generators for nested combinations. Moreover, fusion requires that the generator be a recursive homomorphism- -uuch as a cons-list or join-list homomorphism. This precludes the non-recursive, one-by-one generation approach of Arora et al. (2016) which offers opportunity for the application of acceleration techniques.
The key contribution of this paper is the development of an efficient recursive nested combination generator, nesbe (D, Ks), defined over a liin- homomorphism, making it amenable to fusion. The generator is tailored for efficient vectorized and parallelized implementations, making ideal for GPU execution. We further demonstrate that min0-1, eval, and cp are all fusable with this generator. Additionally, the algorithm eliminates the need for an initialization step to pre-store all hyperplanes and continuously produces candidate solutions during runtime, allowing approximate solutions to be obtained before the algorithm completes.
2.3 AN EFFICIENT NESTED COMBINATION GENERATOR JOIN-LIST
The first step for constructing an efficient nested combinations generator requires the design of an efficient K-combination generator first. Previously, He & Little (2024) proposed an efficient combination generator, kcombs, based on a join-list homomorphism, which we extend to develop a nested combination generator.
The nested combination-ccmbinaiii generator is specified as following
nestedCombs (D,K) = (setEmply kcombbs (K) o!! (D)) kcombs (D)
(1I)
(a)), and (D, us) denotes indexing into the Dth element of the list as. Equation 11) has the type nestedCombs. Int x Int x [R=" + NCss). first generates all possible D-combinations, and then all size D-combinations which are then used to construct K-combinations. Once this process is complete, the D-combinations are no longer needed and are eliminated by applying setEmpty (D). which sets the Dth element of the list to an empty value.
where (f.g) () (a)
Although the specification in I1 is correct, it requires storing the intermediate result returned by kcombs (D, ds), which has size of O (ND). Storing all these combinations is both memory- intensive and inefficient. Instead, if can fuse the function (setEmpty (D), kcombs (K) (!!D)) directly into the kcombs (D) generator, the nested combination generator can be redefined as a sin- gle recursive process. This transformation enables incremental generation of nested combinations, climinating the need to materialize all combinations in advance. According to the fusion law 2, this requires constructing an algebra nestedCombsAAlg that satisfies the following fusion condition
o AcombsAg (D) nestedCombs
o X
(12)
where f f= Empty (D), kcombs (K) (IID)), and the definition of kcombs can be found in (He & Little 2024)
The derivation of nestedCombb..lg (D,K) for the empty and singleton cases is relatively straight- forward. Since we assume 2 2, no nested combinations can be constructed in these cases. For the recursive case-i.e., the third pattern in the join-list homomorphism- we show that the fusion

---

Published as a conference paper at ICLR 2026
condition holds when this third pattern of nestedCombbsAlg (D, K) is defined as (setEmpty( D) Kcombs Algh (K)
Ffst,
(k)) o (Koombs(K)))) (K)o!! (D) (com Ffst, (combsAlg((K) Fsnd)
(13)
where Fjst ((a, b), (c, d)) = (a, Fsnd ((a, b), (c, d)) = (6, d). The proof of the fusion condition rather complex; for readability, the complete proof is provided in Appendix A.2 Therefore, we can implement mestedCombbsAIg (D, K)
nestedCombbs.lgg (d, k. []) (II) (III
nestedCombsAllg (d, k; [rm]] - (II. [+a]]] III
(14)
AestedCoombs..lg (d. k (cssi;ncssi) (css), ncsss)) (setEmply (D, css). ness),
where Alo (D, css1, cs82), and ness is defined
[[]
css!! (D)
[]
ncss
kcombsAlg (K, kcombsAlg (K, ncss1, ness2), kcombs (K, css!! (D)))
otherwise
(15)
Thus an efficient recursive program for nestedCombs is defined as the following join-list homo- morphism
netedCombs (D, K, []) = netedCombs (D, K, [])
netedCombs (D, K, [x,]) neledCoobbs (D, K, [rn])
(16)
neledCombs (D, K, 25 ys)
retedCombssAlge (D, K, netedCombs (D, K, 2s), netedCombs (D, K, ys))
Informally, the function nestedCombs (D,K) K) first takes as input ((Css, NCss), (Css, NCsss)) which is returned by f f. The combination set is updated using the compo- sition setEmpty (D) Alg (K) Ffst where the first elements of the tu- ple are updated, and the D-combinations are cleared. function (Kcombs (K) o!! (D) o KeombssAg (D) Fjst, KcombsAly (K) Fend)
At the same time, the
((Css, NCss), , (Css, NCss)) nations in the tuple, respectively. The newly generated D-combinations are then used to produce new nested combinations. Finally, the two nested combinations in the tuple are merged using KcombsAlg (K): (NCss, NCss) > NCss.
(NCss, NCss) updates the combinations and nested combi-
2.4 DEEP INCREMENTAL CELL ENUMERATION (DEEP-ICE) ALGORITHM AND SYMMETRY FUSION
As noted, working with the maxout network enables the application of an additional fusion prin- ciple- extension of the symmetric fusion theorem proposed by He & Little (203)) for linear classification.
Theorem 3. Symmetric fusion for maxout neuron. Given maxout neuron defined by K hyper- plane. If the predictions associated with these K hyperplanes are known, then the predictions for the configuration obtained by reversing the direction of all normal vectors be obtained directly.
Proof. See appendix A.1
The symmetric fusion theorem eliminates half of the computation, allowing us to enumerate all 2 possible orientations of hyperplanes using only 2 of them. Consequently, the problem 10 can be reformulated more efficiently by applying the symmetric fusion
DeepICE (D, K) minn-- (K) o eval' (K- - 1) o nestedCombs (D, K) where eval' (K 1) eval (K) cp (basgns (K 1)).
We are now ready to derive the Deep-ICE algorithm, which follows as a direct consequence of the following lemma.
7

---

Published as a conference paper at ICLR 2026
Lemma 1. Let DeepICEAlg be defined
Deep (D, K) mingo (K) o eval' (K - 1) restedCombsAlg K),
(17)
where eval' (K 1) evaluates Eo-1 for each nested combination
returned
by
CestedCombsAlg (D, K). Then the following fusion condition holds:
DeepICE K)
-) f AestedCombbslly (D, = Deep (D,K)ofxf,
(18)
where f miiii-1 (D) eval' (K 1), which defines Algorithm !
See Appendix A.3 for detailed proof. Algorithm 17 has a worst-case complexity of O (NDK+1),
which is formally established in the following theorem.
Theorem
The
DeepICE
algorithm
has
a time complexity of
N
N )) which is strictly smaller than
o
X 2K-1
D
+
N x D3 x
K
0 (NDK+1), and space complexity of O strictly smaller than O (ND(K-1))
N
D
D-1 (D"1) x N which is x K +
N
-
See Appendix A.5 for detailed proof.
In practice, we provide two implementations for (17) (see A.4) The sequential version enables two techniques that substantially improve memory efficiency and runtime performance. The D&C version, which builds upon the sequential definition, supports embarrassingly parallel execution.
Figure 2 show that the empirical wall-clock runtime of algorithm aligns with worst-case complexity analysis.
Generalization to deep neural networks Our algorithm generalizes naturally to deep neural net- works. Deeper networks can be viewed as compositions of hidden neurons from preceding layers, where linear combinations of these neurons form the predictions of the subsequent layer. Hence, each layer is essentially a function of the predictions generated in the layer before it. Suppose the i-th hidden layer contains K; hidden nodes. Computing all possible predictions for this layer has complexity O (NDxKi XKxXX,..XXK For instance, the optimal solution wested-nested combination, while four-layer network corresponds to a bested-nested-nestte combination. Solving three-layer network requires complexity O DN xx2k)) Consequently, obtaining exact solutions for deeper networks is practically infeasible due to combinatorial explo- sion.
three-layer network
One way to mitigate this challenge is train a deep network greedily, where the computation of the second hidden layer depends only the first. In this case, the complexity becomes Dx K2 + K + KKK K(K,) for network with layers. Under this scheme, regardless of depth, the overall complexity dominated by that of the first hidden layer.
3 EMPIRICAL ANALYSIS
We evaluate the performance of our Deep-ICE algorithm against two baselines: support vector ma- chines (SVMs) and an identical neural network architecture trained using Adam algorithm, referred to as MLP. The MLP is optimized with binary cross-entropy loss with logits, using the entire train- ing dataset single batch in each epoch. The evaluation is conducted across 1l datasets from the UCI Machine Learning Repository. Since we assume data are in general position, which requires affine independence of the data, we remove duplicate entries and add zero mean Gaussian noise (standard deviation 1 x 10 small enough that it does not affect the results of SVM and MLP) to each dataset. All experiments conducted on single GeForce RTX 4060 Ti GPU.
8

---

Published as a conference paper at ICLR 2026
(a) Deep-ICE (0-1 loss: 16)
(b) Gradient descent (0-1 loss: 25)
Figure 1: The global optimal solution of rank-2 maxout network with one neuron real-world dataset containing N = 704 data items in 12?.
Table 1: Five-fold cross-validation results on the UCI dataset. We compare the performance of our Deep-ICE algorithm-trained
trained either with the coreset selection method or directly by Deep-ICE algorithm (marked by against approximate methods: SVM and maxout network trained via gradient descent (denoted MLP). Results are reported mean 1 loss over training and test sets in the format: Training Error Test Error (Standard Deviation: Train Test). The best- perfforrrng algorithm in each row is highlighted in bold.
Dotaset
Deep-ICE (8) (K 1)
Deep-ICU (9)) (K = 2)
Deep-ICE (%) 3)
(V)
MLP(%) (K 1)
MLP (K 2)
(%)
(K 3)
Ai4i
10000
6
97.45/97.40
97.90/97.82
97. 97.71/97.11
96.64/96.48
97,01/96.90
97.20/97.02 02
97.56/97.55
(0)))))336)
(0.01/0.35)
(0.10/0.25)
(0.11/0.44)
(0.11/0.40)
(0.18/0.39)
(3.133/144)
Cacsr
72
5
*74.55/82.67 67
89.45/88.00
64.36/86.67 6.
72.00/57.33
71.64/62.67
76.36/56.00 6.00
81.82/60.00
(7.18/16.11)
(4.21/9.80)
(7.51/5.90) 96)
(7. (7.14/6.80)
(6.76/6.80)
(6.19/9.04)
(1.15/11.93)
VP
704
2
*96. 94/97.59
97.76/97.59
97.80 97.80997.45 445
96.77/97.02
96.63/96.74
96.77/97.02
96. 96.63/96.74
(0.44/l 466
(0.41/1.69)
(0.43/1 71)
(0.44/2.07)
(0.50/2.13)
(0.73/1 64)
(0.50/2.15 13)
Spesis
975
3
"94,47/92.88 88
96,43/9,26 26
96.24/9..66
94.46/22.33
94.46/2.43
94.46/92.55
94,46/92445
(0/10))))1)
(0.49/1.82)
(0.22/1 62)
(0.10K0.38)
(0.10/0.38)
(0.10N).51)
(0.10/0.38)
IIB
80.11/77.19
72.40/1..3
72.82/74.80
75.34/75.26
75.97/73.92
(0.45/2.448
(0.74//248)
(1.02/3.57)
(0.46/2.38)
(0.66/2.08)
(0.86/2.51)
(0.18/2.08)
BT
502
*77.13/76.36
79.59/77.98
79.36/7..0 98
75.09/70.14
76.17/73.54
76.11/73.56 54
76.29/75.45
(1.46/2.71)
(0.62/3.38)
(0.59/2.88)
(0.5110.76)
(1 (10553364)
(1.01/2.06)
(1.02/2.29)
AV
2342
7
89 89/89/8885 52
90.34/89.04 .0
89, 70/77/88.7 76
87. 1.11667.22 .26
86.92/87.22 20
87. 18/86 88
87.63/87.3 3
56)
(0.15/1.39)
(0.33/1.75)
(0.31/1.24)
(0.24/0.71)
(0.24/0.66)
(0.44/0.73)
SO
1941
27
77.77/76.03
77.13/75.3
76.66/74.95
73.67/70.80
74,81/72.13
77.0971.77
78.33/74.66 68
(0.43/0.85) 83)
(0.81/1.33)) 33))
(0.74/1.38)
(0.52/2.05)
(0.44/1.63)
66)
(0.40/2.31)
DB
1146
9
78.78/79.C0 69
33.60/81.37
83.8888 1.32
69.72/67 62
16/7777)
77.64/76. 19
77.85/75.1 II
(0.41/0.69)
(0.43/2.52)
(0.98/2.23)
(0.65/2.86)
(0.41/2.01
(0.65/1.06)
(0.89/0.72)
RC
3810
7
93. 85/92/444
93.91/93.10
93.94/92.98
93.05/91.75
93.30/22.10
93.30/92.15
23.30/9.112
(0.28/1 02)
(0.24/1 02)
(0.21/0.98)
(0.25/1.12)
(0.28/1 (.0)
(0.30/1. 15)
(0. (0.29/1.13)
51433
86.57/86.72
86.60/86.72
86.39/86.70
82.77/82.75
79.73/79.73
79.65/79.6
79.48/79.73
(0.03/0.15)
(0.04X0.16)
(0.03/0.11)
(0.06/0.22)
(0.15/0.20)
(0.18/).16)
(0.07/0.04)
Exact solution vs. gradient descent Figure 1 illustrates the ERM solution and the gradient de- scent outcome for a rank-2 maxout network with one maxout neuron. Previously, Xi & Little (2023) reported 0-1 losses of 19 and 23 for the global optimal linear model and the SVM. respectively, on this dataset. In contrast, ERM solution obtained by DeepICE, achieves only 16 misclassifications, compared 25 for the same architecture trained via gradient descent. Notably, despite rank-2
maxout neuron involves two hyperplanes, the gradient- gradient-based solution uses only one; the second hyperplane lies outside the data region and does not contribute to predictions.
Exact solution coresets Exact solutions typically require exhaustive exploration of the configuration space. Achieving exact optimality on training data is often unnecessary, as such solu- tions may not generalize well to oft-of-sample data.
Instead, generating multiple high-quality candidate solutions enables selection based on validation or test performance. For example, SVMs provide tunable hyperparameters to generate alternative

---

Published as a conference paper at ICLR 2026
models, while gradient- based MLPs yield varied solutions via different random seed initializations. However, both approaches require computationally expensive retraining to explore alternatives, of- ten without principled guidance. Attempts to automate this process frequently rely strong proba- bilistic assumptions that rarely hold in practice (Shahriari et al. 2015 Klein et al. 2017) or employ
empirical heuristics (Liao al. 2022: Wainer & Fonsecal 2021 Duan al. 2003), resulting in substantial computational waste due to redundant retraining.
A common approach to address this issue in studies of exact algorithms is use multiple random initializations. However, this approach often becomes ineffective as data scales increase. Each run typically uses manually set time limit, but this still results redundant retraining. To address these challenges, we propose coresct selection method, detailed in Algorithm 4 Instead of computing the exact solution across the entire dataset, which computationally infeasible for large K and D, our approach identifies the exact solution for the most representative subsets. By shuffling the data, the input will unlikely be the ordering that is pathological i.e., one where the optimal solution is obtained only at a late stage of the recursive process in the Deep-ICE algorithm. This method can effectively explore thousands of candidate configurations in the coresets that have lower training accuracy than SVMs and MLPs. In our experiments, trained two-layer maxout network using the algorithmic process described in 4 5-fold cross-validatie tests, our method demonstrated significantly better performance. These results consistently outperformed those of SVMs and the same maxout network trained with gradient descent.
Due to the ability generate an extensive number of candidate solutions, observed several in- teresting findings in our experiments. Although extensive prior research suggests that the maximal- margin (MM) classifier (i.e., SVM) offers theoretical guarantees for accuracy (Mohri et al., 2012), we found that the MM classifier does not always perform as expected. Specifically, we did not find clear evidence that the MM classifier consistently achieves better out-of-sample perfor- mance. A more detailed analysis is provided in Appendix A.7
Furthermore, Karbuumorr,KKapukhinn et al. (2024) proposed an interesting framework that introduces stochastic- ity into the model's output and optimizes the expected accuracy, allowing gradient-based methods to directly optimize accuracy rather than surrogate losses. However, despite being named EXACT, the method is actually short for "EXpected ACcuracy opTimization" and is therefore a stochastic ap- proach rather than a deterministic exact algorithm. We include comparison with their framework in Appendix A.6 which shows that it outperforms MLPs trained with surrogate losses.
Additionally, the wall-clock runtime comparison between EXACT and MLP is provided in A.6
DISCUSSION AND CONCLUSION
In this paper, we present the first algorithm for finding the globally minimal empirical risk of two- layer neural networks under 0-1 loss. The algorithm achieves polynomial time and space complexity for fixed and K. The DeepICE algorithm is specifically designed to optimize both efficiency and parallelizability. Even without bounding techniques to accelerate computation, our implementa- tion demonstrates strong performance: it can handle over 1 x 10t1 configurations within minutes, highlighting the intrinsic efficiency of our algorithm independent of any bounding methods. Incor- porating additional bounding techniques in future research could further enhance its scalability.
Another key contribution of this paper is the empirical evidence that optimal solutions do not nec- essarily overfit the data. Our out-of-sample tests indicate that solutions trained using our method, which achieve significantly higher training accuracy than SVMs two-layer neural networks, still perform well on unseen data when model complexity is properly controlled. This finding points to a promising avenue for applying our algorithm to problems where both interpretability and model complexity are critical.
REPRODUCIBILITY STATEMENT
To facilitate reproducibility, we provide three versions of our algorithm: a recursive version, a soride-and-conquee version, and sequential definition in Appendix A.4 The recursive version written clearly in a functional style and can be executed a functional programming language with minimal syntactic adjustments, allowing the algorithm to with no ambiguity. In addition,
10

---

Published as a conference paper at ICLR 2026
imperative implementations in both Python and CUDA included in supplementary materials, along with all datasets used in our experiments. Enabling independent verification and replication of the results reported in this paper.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. ArXiv preprint ArX4v:1111.0141, 2016.
Yatong Bai, Tanmay Gautam, and Somayeh Sojoudi. Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training. SIAM Journal on Mathematics of Data Science, (12):4464744, 2023.
Peter L Bartleut, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research. 20(63):1-17, 2019.
Richard Bird and Oege De Moor. The algebra of programming. NATO ASI DPD, 152:167-203, 1996.
Richard Bird and Jeremy Gibbons. Algorithm Design with Haskell. Cambridge University Press, 2020.
Kaibo Duan, S Sathiya Keerthi, and Aun Neow Poo. Evaluation of simple performance measures for tuning svm hyperparameters. Neurocomputing, 51:41-59, 2003.
Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Re- search, 74:1775-1790, 2022.
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training depth-2 relu networks. ArXiv preprint ArXiv:0011.13550, 2020.
Xi He and Max A Little. An efficient, provably exact algorithm for the 0-1 loss linear classification problem. ArXiv preprint ArXiv:2306. 123444 2023.
Xi He and Max A Little. EKM: an exact, polynomial-timg algorithm for the k-medoids problem. ArXiv preprint ArXiv:2405. 12237, 2024.
Christoph Hertrich. Facets of neural network complexity. Technische Universitaet Berlin (Germany), 2022.
Ivan Karpukhin, Stanislav Dereka, and Sergey Kolesnikov. Exact: How to train your accuracy. Pattern Recognition Letters, 185:23-30, 2024.
Julia Kirchner, Surya Angwin, Jeff Mattu, and Lauren Larson. Machine bias: There's 's software used across the country predict future criminals. and it's biased against blacks. Pro Publica: New York, NY, USA, 2016.
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian op- timization of machine learning hyperparameters on large datasets. In Artificial intelligence and statistics, pp. 528-536. PMLR, 2017.
Andrei Nikolaevich Kolmogorov. On the representations of continuous functions of many variables by superposition of continuous functions of one variable and addition. In Dokl. Akad. Nauk USSR, volume 1 114, pp. 953-9556 1957.
Lizhi Liao, Heng Li. Weiyi Shang, and Lei Ma. An empirical study of the impact of h hyperparameter tuning and model optimization on the performance properties of deep neural networks. ACM Transactions on Software Engineering and Methodology (TOSEM), (1)) 2022.
Michael McGough. How bad is sacramento's air, exactly? google results appear at odds with reality,
some say. Sacramento Bee, 7, 2018.
11

---

Published as a conference paper at ICLR 2026
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 165):206-215, 2019.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1): 148-175, 2015.
Jacques Wainer and Pablo Fonseca. How to tune the rbf svm hyperparameters? an empirical evalu- ation of 18 search algorithms. Artificial Intelligence Review, 54(6):471--4997 2021.
He Xi and Max Little. Exact 0-1 loss linear classification algorithms, April 2023, URL https: 7/github. com wwtteegtetttttttssste
A PROOFS
A.1 SYMMETRIC FUSION FOR MAXOUT NETWORK
Theorem 5. Symmetric fusion for maxout network. Given maxout network defined by K hyper- plane (neurons) If the predictions associated with this configuration of K hyperplanes are known, then the predictions for the configuration obtained by reversing the direction of all normal vectors can be obtained directly from the original hyperplanes, without explicitly recomputing the predic- tions for the reversed hyperplanes.
Proof. Consider a maxout network defined by K hyperplanes H - (h2 E (1,2,.... kK],
where each hyperplane hu defined by a normal vector wi : RR. Together these hyperplanes define decision function fW,,w, W. (x)). Equation (TO) implies that a data item æ is predicted to negative class by fw,.w, (x) if and only it lies in the negative sides of all hyperplanes in H. because fw,.w, (x) will return positive as long there exists a & such that wa. 2 0. Therefore, the prediction labels of the two-layer NN Ymaxout consists of the union of positive prediction labels for each hyperplane /gg and the remaining data item, which lies in the negative side with respect to all K hyperplanes will he assigned to negative class. class. other words, we denote y and y as the positive and negative prediction indexes of y respectively, then we have
U UK
Umaxout
KEK
(19)
Ymaxout
D'y
where is defined as the set difference and UKEK yt denote the union of y k E K. For instance,
V1 1,,,,11,-1111 and ys (-1, 1, -1), then y [1,2) and y 32, thus yf U Uy
(1,2,3)
For two-layer maxout NN, the data points can be classified into three categories based on their relationship to the K hyperplanes defined by the K hidden neurons:
1. Data points that lie in the region where all K hyperplanes are on the positive side.
Data points that lie in the region where all hyperplanes are on the negative side.
3. Data points that lie in the region where some hyperplanes on the positive side and others are on the negative side.
If we reverse the orientation of all K hyperplanes in H. i.e., wr - Only data points that fall into the class of the first two cases will be reversed, because the prediction labels of these data be reversed if the orientation for all hyperplanes is reversed, the classification of data points in the third category will remain unchanged. This is because (8) implies that, the prediction labels of the two-layer NN, Vmaxout: consist of the union of positive prediction labels for each hyperplane h Therefoeee reversing the direction of all hyperplanes will affect only data points æ,, that lie in the positive class for all hyperplanes, (n y Yk. K)) the negative class for all hyperplanes
12

---

Published as a conference paper at ICLR 2026
(n Ur Ak E X) will be change the label. For any other data points, there always exists least one hyperplane that classifies them as negative. After reversing the direction all hyperplanes, this same hyperplane will classify these points as positive, leaving their prediction labels unchanged. M
A.2 PROOF OF NESTED COMBINATION GENERATOR
Given nesteaCombsAlg (D, K) defined
setEmpty(DD) KcombsAAgg(K) Ffst,
KcombsAlg(K) K) (etombs(KKos (D) Alg Ffst, (lg) Fsnd) )
(20)
We need to verify the following fusion condition
f o KcombsAlg (D) = nesteddCombsAlg (D, of
(21)
where f = (setEmply (D) Kcombs (K) o!! (D)). In other words, we need to prove that the fol- lowing diagram commutes
kcombaAlg(D)
Css
(Css, Cas)
fxs
(Css, NCss)
(ested(oomssAgg(..K)) ((Css, NCss). (Css, NCss))
However, proving that the above diagram commutes is challenging. Instead, we expand the diagram by presenting all intermediate stage explicitly
Cas
(Cas, Cos)
KCsA(D)
((D(
(Css, Cs) SB(D)xU
(Cas, (Cs, Cs) (KCCA FFL, KCsA P Psnd))
(CCss, Cs) (Oss, Cs))
(dXKCs(K)
(Css, NCss)
(Css, (NCss NCss)) SE(D)x (KCsA (D) (D) Flet, (KC's (K) oll (D) KC&A (D) Fjst, KCsA (K) Fend))
Css NCss) Css, NCss))
where U (a, b) = aub, and SE, KC's and KCsA are short for setEmpty, Kcombs and KcombsAlg.
To prove the fusion condition, we first need to verify the two paths between (Cas, Css) and (Css, Cs). other words, need prove
(SE (D) (D)) o KD)
SE (D) (Uo (KCsA (D KCsA Ffst, Fsnd))) ((SE (D) .! (D), (D)))
(22)
This can be proved by following equational reasoning
13

---

Published as a conference paper at ICLR 2026
SE (D) x Uo (KCAA o Ffst, (D) KCsA(D) Ffst, Uo Fsnd)) o ((SE
x (SE (D) (D)))
x absorption law
(SE (D) o KCsA (D) o Ffst, o (!! (D) KCsA (D) Ffst, Uo Fsnd)) o
x (SE (D) !! (D)))
Product fusion
(SF (D) KCsA (D) Ffst ((SE (I) !! (D)) (SE (D) (D))),
Uo (!! (D) KCsA (D) Ffst, Uo Fend) ((SE !!! (D)) (S),
Definition of SE (D) and product fusion
(SE (D) o KCsA (D), oo (!! (D) KCsA (D) Pse (D), Uo F!! (D))
Definition of Combination
(SE (D), !! (D)) KCsA (D) where Fse (D,
(SE (D,a). SE SE (D, (I, - (!! (D,a) (.,,),,!(,,)) (D.)).
Note that, the equality between the third equation and the last equation is a assertion of fact, rather than results can be proved (verified). This equivalence comes from the fact that size K- combinations can be constructed by joining all possible combinations of size i and size K i combinations, where 0 S SiSK K.
(Css, Cs)) Next, we prove the two paths between ((Css, C
and ( (Css, NCss) are equivalent.
(SE (D) o KCsA (D) o Ffst, KesA (K) oo (KCs (K) o!! (D) KCsA(D) Ffst, KCsA (K) Fsnd))o (id KCs (K)) x (id KCs (K)) Product fusion. x g (f o F o Fsnd), FKCssnd (D, (c.b) (c,d)) = (KCs (D,b). KCs (D,
(SE (D) o KCsA (D) o Fjst, KesA (K) o (KCs (K) (D) KCsA (D) o Ffst, KCsA (K) FKCs (D)))
Definition of Kcombs
(SE (D) o KCsA (D) o Ffst, KesA (K) o (K) (K) o!! (D) KCsA (D) Ffst, KCs (K) U Fsnd))
Definition of product
(SE (D) o KCsA (D) o Fjst, KosA (K) o KCs (K) (!! (D) KCsA (D) Fjst, Uo Fendy)
Definition of KCs
(SE (D) o KCsA (D) o Ffst, KCs (K) dUo (!! (D) KCsA (D) o Ffst, o Fsnd))
A.3 PROOF OF FUSION CONDITION
Lemma 2. DeepICEAlg satisfies the following fusion condition
DeepICE (D, K) = f nestedCombs (D, DeepICEAlg (D, x where f = mino-1 (D) eval' (K 1), which defines the Deep ICE algorithm 17
(23)
Proof. For optimization problem, proving equality is often too strict that it rarely holds in practice. Instead, whenever "selector" is used, we can relax the fusion condition by replacing the eqaulity as a set memership relation (Bird & Gibbons 2020).
f nestedCombsAlg (D, K) S DeepICEAlg
(24)
In point-wiss wise style, this equivalent to fo nestedCombsAly (D, K, h (æs), h (ys)) C DeepICEAlg (D, (2s)) (h (ys))) (25)
where h (as) = nestedCombs (D, K, as).
On the left side of the set membership relation, first update the nested combinations by merging nestedCombs (D, K, ys) and nestedCombs (D, K, K,ys) using restedCombs.Ag and then select the optimal ne with respect to F by using ming. (D) eval' (K -
14

---

Published as a conference paper at ICLR 2026
On the right-hand side, recall that nestedCombs (D, K, as) [R]] ([CC)) [[NC]] returns all possible nested combinations (K commiiiatioon of hyperplanes) ncss, all possible combination of data items css (Dth inner list is empty) and ncss, and f h DeepICE (D, K) is the specifi- cation of the Deep-ICH algorithm. Functions f (h (r=)) and f (h (ys)) select the optimal nested- combination with respect Fa.1 from all possible nested combinations with respect call them optcnf01. and optenfg, with respectively. Then the nested combinations are merged to- gether and selected the new optimal configuration optenfg' by using DeepICEAlg. By definition, optenfg' is obtained by selection the optimal configurations from the newly generated combinations and compared with optenfg 1. and optenf92. thus the solutions on the left side of the set membership relation must include in the right-hand side of the nested combination.
and ys,
A.4 ALGORITTMM
Algorithm present the recursive definition of the Deep-ICE algorithm.
Algorithm DeepICE rec DeepICE recursive definition
Input:
ds: input data list; D: number of features; K: number of hyperplanes;
Output: enfg
(1, Optimal nested combination with respect to ds;
ness : NCCssAAl possible nested combinations of size less than K; css Cas-All possi- ble combinations of size less than D.
DeepICE (D, K, []] nestedCombsAlgg, (I))
DeepICE (D, K, [a]) nestedCombs ([a))
DeepICE (D, K, æs U ys) = mino- (K) eval' (K - -1)o
nestedCombss Alg DCeepTCE (D, K, xs) DeepICE (D, K,ys)),
where nestedCombsAll is defined as
nestedCCombs (d, A: (]) = (IIII.. IIII
restedCombs (d, k; [x..]) = [[.]] (IIII)
nestedCombs (d, k. (cssi, mcsss) (css,, ncss )) (setEmpty (D, css). ncss).
where C88 = kcombsAAg (D, c881, cs82), and ness is defined as
[[[[]]]
css!! (D) = [[] otherwise.
ncss
kcombsAlg (K, kcombsAlg (K, ncss1, ness2), kcombs (K, css!!D))
We also provide both the pesudocode for the sequential version and D&C versions of the Deep- ICE algorithms.
15

---

Published as a conference paper at ICLR 2026
Algorithm 2 DeeplCEssr seq' Deep-ICE sequential definition
Input: ds: input data list; D: number of features; K: number of hyperplanes;
Optimal nested combination with respect to ds; lopt' optimal 0-1 loss, hyperAsgn: All possible predictions of hyperplanes with respect to input list; css: all possible nested combinations size smaller than D ness: all possible nested combinations of size smaller than K;
Output: enfgopt (NC, (1, -1) )
1. [1]]] 0*] // initialize combinations
[[]] .0"] // /niiiiiaizze nested-combinations
2. ncss
)N)) ) initialize prediction of hyperplanes as a empty
3. hyper sgn
= empty
N
x N matrix
4. lapt = N //iitiialize optimal 0-1 loss
5. for n 4- range (0, N) do: /range (0, N) = [0, ,,.., N
6. for j - reverse (range (D, n + 1)) do:
7. updates reverse (mop (Uds [n]] css 1])) // the reverse function is used to
organize configurations in revolving door ordering
8. css [j] = css [j] updacts update css to generate combinations in revolving door
ordering,
9. hyperAsgn = genModels (css D] hyperAsgm) // generate positive/negative predic- tions for each hyperplane ess [D]
10.
[D] [] empty D-combinations after generation
n D 1 ) C2
11. C1
D
ness' kcombs (k,, C2 C1)
13. nc8s kcombsAlg (K, ness, ness''
14. enfy'. L' eval (ness [K] hyperrsgn) // evaluate to the number of misclassification for each size nested combination in ncss [K]
ness [K] = [] empty size K nested-combinations after evaluation
16.
if < lope:
17.
lope l'
18.
enfgapt cafg'
19.
return en/s Lopt, Ayp,rrAgg, ness, css
16

---

Published as a conference paper at ICLR 2026
Algorithm 3 DeeplCEpec' Deep-ICE divide-and-conquee definition
Input: ds: input data list; D: number of features; K:: number of hyperplanes;
Output: en/sopt (NC, (1,,(1,-1)
Optimal nested combination with respect to ds; logt optimal
0-1 loss
(( N .N)
1. hyperAsgn empty
// initialize prediction of hyperplanes as empty
N
x N matrix
2. lopt N //mitialize optimal 0-1 loss
3. ds;, dsj split Two (ds)/ split the data set into two half
4. parallel:
5. res; DeepICE,.. seq (D, K, ds;) Process first data list
6. resj = DeepICE seq (D, K, dsj) // Process second data list
7. sync Wait for both tasks to complete
8. // Retrieve results: configuration, loss, hyperplane assignments, combinations
9. enfy,, 4,, hyperAsgn,, css;, ncss; rES,
10. enfg,- 17 hyper c885, nC88; TES
11. css, ncss nesled (D, K, (csst, ncss;). (cs8j, ncss;)) // Merge: Combine nested combinations from both subsets
12. hyperAsgn = mergeAsgn (hyperAsgm, hyperAsgn,) // Merge hyperplane assignments
13. enfy', l' eval (ness [K] hypeer // Evaluate merged nested combinations for size K
14. enfgs [[enfg:: 4)), (cnfgg:4)) (enfg', ,t)] Collect all configurations and their losses
15. (enfyopu lops) mino- ([enfgs)) // Select configuration with minimum 0-1 loss
16. return enfg lopt
Algorithm 4 shows the structure of the coreset selection method.
17

---

Published as a conference paper at ICLR 2026
Algorithm 4 Deep-ICE with Coreset Filtering
1. Input: ds: input data list; M: Block size; number of shuffle time in each filtering
process; L: Max-heap size; Bmax: Maximum input size for the Deep-ICE algorithm;
(0, 1]: Shrinking factor for heap size
2. Output: Max-heap containing top L configurations and associated data blocks
3. Initialize coreset C' f- ds
4. while C C Bmax do:
5. Reshuffle the data, divide C into C
blocks Cn { Ci, C2,..., Cr
6. Initialize size L max-heap H.
7. for 1 R. do:
8. r=r+1
9. for C E CB do: enfg + DeepICE (D,K,))
10.
Hr.ppush (enfg, C)
12.
C unique (Hr.) II Merge blocks and remove duplicates
13. L x L ell Shrink heap size:
14. enfg + DeepICE (D, K, C) // Final refinement
15. Hyypush (cnfg, C)
16. return H.
A.5 COMPLEXITY ANALYSIS
Theorem
6. The
DeepICE
algorithm
a time complexity of D ))
has
(
N D K
O K x
+ N
D3
which is strictly smaller than
N
N
0 (NDK+1), and space complexity of O
D
D- x N which is x K +
-
strictly smaller than O (N)(
Proof. We analyze the complexity using the sequential version of the DeepICE algorithm 2 At stage n, the computation of lines 5-8 has complexity O (nP-1), since there are most
D-1 new D-combinations in each recursive step. The computation at line 9 requires
0 D-1 3 N) time. Similarly, the new nested combinations lines 12-14 has size
(
(())
n D
))
which requires computations of a complexity 2K-1, x x per nested combination, as each combination must evaluate 2 possible hyper- plane orientations.
Σ
D-
x
k
k
By Vandermonde's identity, we have
K
71
n1
((D=1 )- =
(( D
n1
-((btt)
m+1 (B-1)
-
x
D
=
+
D
s (n 1)
b
k
18

---

Published as a conference paper at ICLR 2026
Summing tton N --1, 1, the total time complexity becomes
+KxNx2 (
N
D x x (
D-1 (D"1 n
2
D-
n
k
( D K
N
)
N N x (1) .N KXXN22 =0
50(Nx D x N BNDDKKA + x NDK) =0 (NDRt)
For memory, at lines 10 and 15, we clear the size D combinations and size K nested combinations, so we only need smaller configurations in memory. The resulting space complexity is
((
( K
)
N D
N (D D
N = -NNDC--1)).
x K
(26)
A.5.1 ORDERED GENERATION OF COMBINATIONS
To generate D-combinations of data points efficiently, we employ a technique that organizes com- binations in specific order, assigning each unique "rank." To achieve this, critical but small function reverse used at line combinations to be organized in "revolving door ordering" and thus combinations by their rank rather than storing the combinations explicitly. This approach offers two key ben- efits: First, storing ranks significantly reduces memory usage, from M D x 64 bits to M x log jbits (log (M) is often representable using 32 bits in coresct selection method), where M =
the DeepICE algorithm [ makes possible. This allows represented
K-1
D
workspace in memory is preallocated before training to store predictions
sociated with these hyperplanes, thereby avoiding memory allocation overhead during runtime. Sec- ond, it enables the organization of hyperplane predictions into a
N
x N matrix, where each
D
row corresponds to a unique rank. As result, the algorithm requires only O (NND*
N
time. Moreover, storing hyperplanes in single large matrix allows exploitation of high-throughput hardware such as Nvidia GPU Tensor Cores. Without this method, predictions would need to be re-
(D)
N
computed for each hyperplane, requiring at least O N D3
time. This strat-
K
egy reduces memory usage and accelerates execution without drawbacks, and it can be extended to other problems involving nested combinatorial structures.
A.5.2 MEMORY-FRER METHOD BY USING UNRANKING FUNCTION
Building on the first technique, the second method leverages the ordered structure of D- combinations to eliminate the need to store K K-coobinatioons. An unranking function takes the rank of a combination as input and reconstructs the corresponding K-combination on demand. This supports the dynamic generation of combinations for given range of rank values, thereby circum- venting memory constraints that would otherwise limit the algorithm due to insufficient storage. However, it incurs an additional computational cost of θ (K) arithmetic operations per combina- tion due to the unranking function. Despite this, the method often improves overall efficiency by simplifying memory management, leading to more effective implementations in practice.
However, this method has a limitation: it precludes the use of bounding techniques because K- combinations combinations reconstructed demand via unranking functions rather than stored
19

---

Published as a conference paper at ICLR 2026
10
Wall cleck (4)
10
10
Wall clock
100
10
1011
(N)
stae (N)
Figure 2: Empirical analysis shows that the wall-clock runtime of the DeepICE algorithm strictly smaller than the predicted worst-case complexity O (NDK+1), The log-log wall-clock runtime (seconds) of DeepICE on synthetic datasets is plotted against dataset size N. On this log-log seale polynomial run time appears linear function of problem size N, and the slope of the line corre- sponds to the polynomial degree. In the left panel, the runtime curves (from left to right) correspond to K 2 with D 2, 4, and have slopes 3.96, 6.28, and 5.8lermaller than the predicted worst-case exponents O [N*). O (N7), O (N9). In the right panel, the curves (from left to right) correspond to D = 2 with K = 1, 2, respectively), and have slopes 1.91, 3.95, and 6.11-smalle than the predicted worst-case exponents O (N*), O (Nº), (N"), respectively.
in memory. If future research requires such techniques, this approach is unsuitable, it is chal- lenging to identify which configurations (represented by ranks) are eliminated during algorithm execution.
A.5.3 EMPIRICAL ANALYSIS
Figure shows that the empirical running time of the DeepICE algorithm aligns with the expected worst-case complexity.
A.6
ADDITIONAL EXPERIMENTS
A.6.1
COMPARISON WITH EXPECTED ACCURACY OPTIMIZATION (EXACT) FRAMEWORK
This Subsection we compared with the expected accuracy optimization (EXACT) method proposed by Karpukhin et al. (2024) the results is shown in table Karpukhin et al. 2024).
A.6.2 WALL-CLOCK TIME COMPARISON
Table 3 report the run-time comparison of between DeepICE, SVM, MLP and EXACT.
A.7 EXPERIMENTS OF EXHAUSTIVELY EXPLORING ALL SOLUTIONS
For 1 case, i.c., linear case, the Deep-ICE algorithm fully explores the solution space for datasets such as Voicepath, Caesarian, Sepsis, HB, and BT. We output all solutions whose training accuracy is lower than that of the SVM. The regularization parameter for the SVM fixed across all datasets. We deliberately avoid tuning this parameter to achieve the lowest test error, as a solution with lower test accuracy may increase training error, thereby generating more candidate solutions due to the higher training error. Adjusting the regularization parameter introduces trade- off between training and test errors, complicating the analysis. To keep our discussion focused and consistent, we fix the regularization parameter. We summarize the empirical results in Table A.7 Using the generated solutions, we construct hyperplanes and select two representative types from each equivalence class: (1) hyperplanes passing through exactly D points (direct hyperplanes), and
20

---

Published as a conference paper at ICLR 2026
Table 2: Five-fold cross-validation results on the UCI dataset. We compare the performance of our Deep-ICE algorithm, with K (number of hyperplanes) ranging from 1 to 3, trained either with the coreset selection method directly (marked by agaainstt againstKarpukkhnn Karpukhin accuracy optimization (EXACT) framework. Results are reported as mean accuracy loss over train- ing and test sets in the format: Training Error Test Error (Standard Deviation: Train Test). The best-performing algorithm in each row is highlighted in bold.
al. (2024) expected
Dataset N
Deep-ICE (%) (K
Deep-ICE
Deep-ICE (9)
EXACT (%)
EXACT (%)
EXACT (%) (K
(%) (K
(K
(K
Ai4i
10000
97.45/97.4 40 (0. (010.36)
97.90.97.82
97.71/97.71
96.61/96.61
96.63/96.60
96. 69/96.62
(0.01/0.35)
(0.10/0.25)
(0.01/0.02)
(0.04/0.03)
(0. 1000.05)
Caesr
72
5
$74.55/82.67
89.45/88.00
84.36/86.67
79.5069.24
81.94/62.38
87 17.83/64000
(7.18/16.11)
(4.21/9.80)
(7.51/5.96)
(2.44/12.59)
(2.65/10.03)
(2.74/8.72)
VP
196.94/97.59
97.76/97.59
97.8099745
92.47/92.47
92.47/92.47
92.47/92.47
(0.44/1.44)
(0.41/1.65)
(0.43/1.71)
(0.08/0.34)
(0.08/0.34)
(0.08/0.34)
Spesis
96.43/95.26
94.05/94.05
(0.10/0.61)
(0.49/1.82)
(0.22/1.62)
(0.06/0.25)
(0.06/0.25)
(0.06/0.25)
HB
283
3
177.18/75.44
80.1 19/7.1
80.85/78.53
75,70/71.39
77.74/73.45
18.71/71.36
(0:45/2.48)
(0.74/2.48)
(1.02/3.57)
(1.94/3.86)
(0.55/5.89)
(1.66/3.56)
BT
502
4
177.13/76.36
79.59/77.98
79.36/77.90 98
77.84/73.51
78.09/73.51
78. 14/73.11
(1.46/2.71)
(0.62/3.38)
(1.31/2.80)
(1.54/2.36)
(1.56/3.09)
2342
89.89/88.52
90.34/89.04
89.77/88.76
87.18/87.18
87.26/87.08
97.70/87.13
(0.33/1.56)
(0.19)/)99
(0.33/1.75)
(0.03/0.11)
(0.19/0.37)
(0.34/0.40)
SO
1941
77.77/76.03
77.13/75.33
76.667 16.66/74
76.33/73.11
78.81/75.22
79.95/75.32
(0.43/0.83)
(0.81/1.32)
(0.74/1.38)
(0.26/1.82)
(1.68/1.77)
(2.2633331)
DB
1146
9
78.78/79.69
83.60/11337
81.8881.
73.91/70.58
73.91/68.93
75. 75..9/72.442
(0.41/0.69)
(0.43/2.52)
(0 (0.98/2.23)
(1.15/3.52)
(3 (3.83/4.11)
(1.73/2.30 30)
RC
3810
93,88/2.45
93,91/93.10
93.94/92.98
93,03/9262
93.08/92.66 60
93.08/22.76
(0.28/1.02)
(0.24/1.02)
(0.21/0098)
(0.32/1
(0.29/1.16)
(0.35/l
86.57/86.72
86.57/86.53
86.55/86.53
86.56/86.53
(0.03/0.15)
(0.04/0.16)
(0.03/0
(0.0440.2)
(0.05/0.
(0. (0.05/0.17)
Table 3: Running time (seconds) of each algorithm, with "0.01 <" denotes time smaller than 0.01 seconds. In principle, allocating more computational resources to DeepICE yields better solutions. For comparison, record the wall-clock time which DeepICE first obtains solution with lower ()-1 loss than the other methods. The reported times are the medians over three runs.
Datasel
N
Deep- (K
Deep- ICE (K
Deep-
SVM (8)
MLP
MLP
MLP
EXACT EXACT
EXACT
(s)
(8)
(5)
(K
[K =
(K =
(K =
(K =
(K
=
(K
2)
3)
2)
3)
2)
3)
Ai4i
10000
450.5
622.42
505.42
0.05
18.43
18.74
16.52
22.56
21.91
26.47
Caesr
72
5
0.26
0.26
7.10
0.01
12.27
12.96
10.
23.78
22.92
29,80
VP
704
2
0.83
0.45
0.85
0.01 <
11.19
11.53
10.76
24.36
23.49
25.22
Spesis
3
8.00
0.41
0.01<
9.56
10.60
HB
283
3
0.20
0.21
0.38
0.01
12.54
14.43
17.68
22.65
23.01
25.30
BT
0.26
0.01<
13.45
12.34
15.24
25.46
24.36
27.99
AV
2342
7
132.51
294.81
356.51
0.01<
14.53
14.12
13.21
22.86
23.02
28.19
SO
1941
762.50
850.42
543.54
0.04
12.43
13.23
14.53
24.12
25.61
29.36
DB
1146
50.43
20.39
16.77
0.01
14.78
16.20
17.43
26.45
22.57
27.35
RC
3810
423.5
217.26
611.37
0.02
15.02
17.02
14.53
24.68
22.77
27.21
SS
4.21
21

---

Published as a conference paper at ICLR 2026
(2) arbitrary hyperplanes computed via linear programming (LP hyperplanes). In the table, pare the out-of-sample performance of these solutions against that the SVM. We found no strong evidence that the maximal- margin hyperplane (SVM) consistently outperforms other hyperplanes with lower training errors. For example, in the HB dataset, an average of 8,922.2 solutions outper- form the SVM in training dataset. Of these, direct hyperplanes have average of 5,448.2 solutions, and LP hyperplanes have an average of 6,165.6 solutions, outperforming the SVM in out-of-sample test.
Table 4: Comparing the average out-of-sample accuracy in a 5-fold cross-validation. All solutions with training accuracy lower than that of the SVM generated, and their total number is reported (Total number of solutions). Two representative hyperplanes from the equivalence classes are in- cluded: the direct hyperplane, which passes through exactly D points, and the LP hyperplane, computed via linear programming. For each type, the average number of hyperplanes with out-of- sample accuracy lower than that of the SVM also reported.
Datasets
Total number of solutions
Direct hyperplanes
LP hyperplanes
Caesarian Voicepath
4430.2
2379.4
2913.8
124.2
55.2
54.8
Spesis
5.8
1
4.6
HB
8922.2
5448.2
6165.6
BT
5150.4
3189.8
3580
22


Reviews:
[{"review_id": "blKalQcC9U", "reviewer": "Reviewer_Dei1", "summary": "This paper presents the first algorithm for finding the globally minimal empirical risk of two layer neural networks under 0–1 loss. The algorithm achieves polynomial complexity for fixed input feature size D and hidden feature size K, i.e. $O(2^{K-1}N^{DK+1})$ compared with previous $2^KC_1N^{DK+C_2}$. When combined with heuristics for large-scale problems, such as coreset selection, the proposed algorithm demonstrates strong out-of-sample performance.", "questions": "1.\tIn table 1, there are two numbers delimited by ‘/’. What do the two numbers denote? What is the difference?\n\n2.\tThe paper argues that study of two layer of neural network will benefit model interpretability. However, the model output is a linear combination of hidden units, which is hard to interpret. If possible, please explain more about why two layer of neural network benefit interpretability.\n\n3.\tTypo in 69,70, $C_1, C_2$ should be switched. What is $K_-$ in line 383?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper introduces the first globally optimal algorithm for the empirical risk minimization problem of two-layer maxout and ReLU networks, i.e., minimizing the 0-1 loss.\n\n2.\tExperiments demonstrate better performance than those of SVMs and the same maxout network trained with gradient descent.\n\n3.\tThe paper develops an efficient recursive nested combination generator for GPU execution.", "weaknesses": "1.\tThere are confusing statements in the paper. In line 105, the paper says ”our algorithm demonstrates strong out-of-sample performance, even when **training accuracy is lower than** that of SVMs or DNNs trained with gradient descent” and the in line 483 the paper claims that the proposed method “achieves significantly **higher training accuracy** than SVMs or two-layer neural networks, still perform well on unseen data when model complexity is properly controlled”. The two claims appear to be in conflict. Besides, there is no clear evidence or discussion in the paper to support either of them.\n\n2.\tAnother concern is about computation efficiency as the method needs to enumerate data points. Is it possible to have computation time comparison?", "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": "5707pkgdfl", "reviewer": "Reviewer_8CaP", "summary": "The paper proposes Deep-ICE, a globally optimal algorithm for minimizing 0–1 loss in two-layer ReLU and maxout networks. The method exhaustively and efficiently searches over feature splits via a recursive nested-combination generator with CUDA acceleration, enabling exact training on small datasets and heuristic coreset-based extensions for larger problems. The authors provide formal correctness claims, complexity analysis, and empirical comparisons to SVMs and MLPs.", "questions": "- What exactly makes a 2-layer ReLU/maxout model “interpretable”? Can the authors provide interpretability examples or a measure?\n- How does Deep-ICE compare to global optimization methods like [1] and EXACT [3]? Can runtime and performance comparisons be added?\n- Do the authors have plans to release a Python library interface for CUDA to improve usability?\n\nThe score can be adjusted based on the responses (especially related work).\n\n[1] Efficient global optimization of two-layer relu networks: Quadratic-time algorithms and adversarial training (2022)\n\n[2] Algorithms for direct 0–1 loss optimization in binary classification (2013)\n\n[3] EXACT: How to train your accuracy (2024)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The algorithmic description and theoretical details are well-structured and readable.\n- Constructing an efficient search over all feature splits is nontrivial and technically interesting.\n- CUDA implementation and memory optimization increase the practical relevance.\n- Addresses an important research direction: global optimization of neural networks under 0–1 loss.", "weaknesses": "- The claim that two-layer networks are interpretable (unlike linear models) needs stronger justification, especially given nonlinear thresholds.\n- Several relevant exact [1] or gradient-based [2, 3] 0–1 loss optimization methods are not cited nor discussed.\n- For example, on the dataset from Figure 1, EXACT (with Tanh activation) achieves 18 errors with 2 hiddens and 16 errors with 5 hiddens, substantially outperforming MLP’s 25 errors.\n- A Python interface to the CUDA implementation would be beneficial.", "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": "GmyX91PqZV", "reviewer": "Reviewer_fiaE", "summary": "This paper introduces a globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and Maxout networks and shows improved computational complexity. Also, for larger dataset, this paper introduces a heuristic method such that the dataset is feasible for the proposed algorithm.", "questions": "Please see above.\nThe meaning of numbers in Table 1 is not clear.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper is well structured and clearly written.\n2. The problem is well motivated, and the proposed approach is methodologically sound.\n3. The discussion of related work is comprehensive and demonstrates a strong understanding of the existing literature.", "weaknesses": "1. The presentation of the Table 1 is not clear enough.\n2. The experimental validation is not fully convincing. The experiments show that the algorithm proposed in this paper has better performance compared with baselines, but I am also curious of the running time of different approaches. Also, the proposed algorithm has improved computational complexity compared with literature. I am wondering if the improved computational complexity can be validated experimentally.\n3. The evaluation could be strengthened by including additional large datasets with more features (large $N$ and $D$).", "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)