A Combinatorial Perspective on the Optimization of Shallow ReLU Networks
Authors: Michael S Matena
Colin Raffel
Venue: NeurIPS 2022 Accept (2022)
Keywords: ReLU
zonotope
combinatorial
optimization

Abstract: The NP-hard problem of optimizing a shallow ReLU network can be characterized as a combinatorial search over each training example’s activation pattern followed by a constrained convex problem given a fixed set of activation patterns. We explore the implications of this combinatorial aspect of ReLU optimization in this work. We show that it can be naturally modeled via a geometric and combinatoric object known as a zonotope with its vertex set isomorphic to the set of feasible activation patterns. This assists in analysis and provides a foundation for further research. We demonstrate its usefulness when we explore the sensitivity of the optimal loss to perturbations of the training data. Later we discuss methods of zonotope vertex selection and its relevance to optimization. Overparameterization assists in training by making a randomly chosen vertex more likely to contain a good solution. We then introduce a novel polynomial-time vertex selection procedure that provably picks a vertex containing the global optimum using only double the minimum number of parameters required to fit the data. We further introduce a local greedy search heuristic over zonotope vertices and demonstrate that it outperforms gradient descent on underparameterized problems. 

A Combinatorial Perspective on the Optimization of Shallow ReLU Networks
Michael Matena
Colin Raffel
Department of Computer Science University of North Carolina at Chapel Hill
Department of Computer Science University of North Carolina at Chapel Hill Chapel Hill, NC 27599 craffel@cs. unc.edu
Chapel Hill, NC 27599 mmatenaâcs.. unc.udu edu
Abstract
The NP-hard problem of optimizing shallow ReLU network can be characterized as combinatorial search over each training example's activation pattern followed by constrained convex problem given a fixed set of activation patterns. We explore the implications of this combinatorial aspect of ReLU optimization in this work. We show that it can be naturally modeled via a geometric and combinatoric object known zonotope with its vertex set isomorphic to the set of feasible activation patterns. This assists in analysis and provides a foundation for further research. We demonstrate its usefulness when we explore the sensitivity of the optimal loss perturbations of the training data. Later we discuss methods of zonotope vertex selection and its relevance to optimization. Overparameteriizaton assists in training by making a randomly chosen vertex more likely to contain a good solution. We then introduce novel polynomial-time vertex selection procedure that provably picks a vertex containing the global optimum using only double the minimum number of parameters required to fit the data. We further introduce local greedy search heuristic over zonotope vertices and demonstrate that it outperforms gradient descent on underparameterized problems.
Introduction
Neural networks have become commonplace in variety of applications. They are typically trained to minimize a loss on a given dataset of labeled examples using variant of stochastic gradient descent. However, our theoretical knowledge of neural networks and their training lags behind their practical developments.
Single-layer ReLU networks are an appealing subject for theoretical study. The universal approx- imation theorem guarantees their expressive power while their relative simplicity makes analysis tractable (Hornik, 1991). We restrict ourselves in this paper to studying empirical risk minimization (ERM) done in previous works (Du et al., 2018; Oymak & Soltanolkotabi, 2020), which is justified since the train set performance tends to upper bound the test set performance. Furthermore, modern neural networks achieve zero training loss but nevertheless generalize well (Kaplan al., 2020; Nakkiran et al., 2021). Minimizing the training loss of a shallow ReLU network is a nonconvex optimization problem. Finding its global minima is difficult and can in fact be shown be NP-hard in general (Goel et al., 2020). Arora et al. (2016) provide an explicit algorithm for finding the global minima by solving a set of convex optimization problems; however, the size of this set is exponential in both the input dimension d and the number of hidden units m.
In this paper, we explore the combinatorial structure implicit in the global optimization algorithm of Arora et al. (2016). We start by using tools from polyhedral geometry to characterize the set of convex optimization problems and describe the relationships between the subproblems. Notably, we are
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

able to create a special type of polytope called zonotope (McMullen, 1971) whose vertices have one-to-one correspondence with the convex subproblems and whose faces represent information about their relationships. We then explore the combinatorial optimization problem implicit in shallow ReI.U network empirical risk minimization using the zonotope formalism to help interpret our findings and assist in some proofs.
Since the computational complexity of optimization problems shapes our approach to solving them, we examine the reductions of NP-hard problems introduced in Goel et al. (2020). The datasets produced have examples that are not in general position (i.e. they have nontrivial affine dependencies), which differs from most real-world datasets. We prove that the global optimum of the loss of shallow ReLU network over such a dataset can have a discontinuous jump for arbitrarily small perturbations of the data, which has a very natural interpretation in our zonotope formalism. This means that proof of the NP-hardness of ReLU U optimization given training examples general position does not follow from the results Goel et al. (2020) via a simple continuity argument. We therefore present a modification of their proof that uses a dataset in general position.
In contrast to the NP-hardness of general ReLU optimization, sufficient overparameterization allows gradient descent provably converge global optimum in polynomial time, as demonstrated by (Du et al., 2018; Oymak & Soltanolkotabi, 2020). We interpret the proof methods generally used in these works as asserting that sufficient overparameterization allows gradient descent to bypass much of the combinatorial search over zonotope vertices by having a randomly chosen vertex be close to one with a good solution with high probability. We then introduce a novel algorithm that finds good zonotope vertex in polynomial time requiring only about twice the minimum number of hidden units required to fit the dataset.
Finally, we explore how gradient descent interacts with this combinatorial structure. We provide empirical evidence that it can perform some aspects of combinatorial search but present an informal argument that it is suboptimal. We reinforce this claim by showing that a greedy local search heuristic over the vertices of the zonotope outperforms gradient descent some toy synthetic problems and simplifications of real-world tasks. In contrast to the NP-hard worst case, these results suggest that the combinatorial searches encountered in practice might be relatively tractable.
We summarize our contributions as follows.
We are the first to provide an in-depth exposition of the combinatorial structure arising from the set of feasible activation patterns that is implicit in shallow ReLU network optimization. In particular, we show that this structure can be characterized exactly Cartesian power of the zonotope generated by the set of training examples.
We use this formalism to prove necessary conditions for the global optimum of a shallow ReL.U network to be discontinuous with respect to the training dataset. We show that this implies that previous NP-hardness proofs of ReLU optimization do not automatically apply to datasets satisfying realistic assumptions, which we rectify by presenting a modification that uses a dataset in general position.
We explore the role that combinatorial considerations play in the relationship between overpa- rameterization and optimization difficulty. In particular, we introduce novel polynomial-time algorithm fitting& generic dataset using twice the minimum number of parameters needed.
We introduce a novel heuristic algorithm that performs greedy search along edges of zonotope and show that it outperforms gradient descent on some toy datasets.
We hope that the tools we introduce are generally useful in furthering our understanding of ReL.U networks. Notably, they have deep connections to several well-established areas of mathematics (McMullen, 1971; fichter-Geber & Ziegler, 2017: Ziegler, 2012), which might allow researchers to quickly make new insights by drawing upon existing results in those fields.
2 Empirical Risk Minimization for ReLU Networks
single ReLU layer consists of an affine transformation followed by a coordinate-we wise application of the ReLU nonlinearity x(x) max xz, 0). We can represent
affine transformation from Rd - R. by an m x (d + 1) matrix by representing its inputs in homogeneous coordinates, i.e. by appending a (d + 1)-th coordinate to network inputs that is always equal to Hence a single ReLU layer with parameters W can be written fw (x) @(WX), where x denotes expressed
2

---

in homogeneous coordinates. A single hidden layer ReLU network consists of single ReLU layer followed by an affine transformation. We focus on the case of network with scalar output, so the second layer can be represented by vector v E R Although the second layer parameters are trained jointly with the first layer in practice, we assume that they are fixed for our analysis. This parallels simplifying assumptions made in previous work (Du et al., 2018).
Let é R I + R be a convex loss function such MSE cross-entropy. Since the second layer parameters fixed, we can incorporate them into a modified loss function é Rm x R R given by f(z. v) 6(v z, y) that operates directly on the first layer's activations z. This modified loss function is convex since it is the composition of convex function with an affine function.
given D {(x, w:)) as the training dataset with x; R and y/ E RR for all i 1..,,.., ... Throughout this paper, we assume that N > d 1. Sometimes we will represent a dataset by a matrix X Rdd+1)xN with each column corresponding to an example and its labels as the vectory R.V. We say that D is in general position if there exist nontrivial affine dependencies between the columns of X. The empirical loss L(W), also known as the empirical risk, is defined as the mean per-example loss
Suppose
N
1
L(W)
Σ ((w(( N
The goal of ERM is to find a set of parameters W that minimizes this loss. Arora et al. (2016) the first to introduce algorithm for exact ERM. We adapt their algorithm for the case of fixed second layer weights in algorithm 1, which has a running time of O(N'd poly(N (N, m, d)). The algorithm works by iterating over all feasible activation patterns
A [[W > 0} {0, 1) M W e pmx((+11)
The subset of parameters corresponding to an activation pattern, which we call an activation region, can be expressed via set of linear inequalities. Within a single activation region, the map from parameter values to ReLU layer activations over the training dataset is linear. Hence we can solve a constrained convex optimization problem to get the optimal parameters each activation region. Namely for given A A, solve for W Rmx(d+1) in the following
minimize
1
Σ E(a (WX:),
N
subject to (2a, 1) ( 20
where @ denotes the Hadamard product and a, denotes the i-th column of A. The global optimum then becomes the best optimum found over the entire set of activation regions. Thus single-layer ReLU network ERM can be expressed as a combinatorial search over activation patterns with a convex optimization step per pattern.
3 Zonotope Formalism
While Arora et al. (2016) mention that A arises from a set of hyperplanes induced by the training ex- amples, they only use this connection to bound its cardinality [A] = O(Nmd)) However, hyperplane arrangements are well-studied geometric and combinatoric objects (Richter-Gebert & Ziegler, 2017; Stanley et al., 2004). As such, we will that we can use this connection better characterize the combinatorial aspects of ReLU optimization.
Our mathematical tools for describing the combinatorial structure of shallow ReLU network op- timization include oriented hyperplane arrangements, polyhedral sets, polyhedral complexes, and zonotopes. Appendix A provides approachable overview of these topics for unfamiliar readers.
Single Hidden Unit by the vector w E Rd+1, Looking its behavior as w ranges over Rd++1 on a single training example x,, we see that there are two linear regimes depending on the sign of w x. They are separated by the hyperplane in parameter space satisfying w O. We can describe such behavior mathematically as oriented hyperplane with the sign of w providing its orientation. The
We start by considering single ReLU unit fw (x) = o(w"xx) parameterized
3

---

J.Y. is known an Figure 1: Left: A set of 5 training examples in R2, Center: A two dimensional slice of parameter space R2 along the was 1 plane reflecting the polyhedral complex R. The lines correspond to the of hyperplanes ....... H/g. The different shaded chambers correspond different activation regions. Each chamber can be thought of as the base of cone whose apex is the origin. Right: The zonotope Z for this dataset. The corresponding activation region for vertex is indicated by the colored circles. Note how the edges and faces of Z capture the incidence structure of the activation regions. Each the red lines is a translation of a (homogenized) training example. Exactly these training examples are active in the yellow activation region.
collection of oriented hyperplanes associated to each training example {x, oriented hyperplane arrangement (Richter-Gebert & Ziegler, 2017).
The structure imposed on parameter space [R++1 by this oriented hyperplane arrange- ment can be described as polyhedral com- plex (Ziegler, 2012), which a collection of polyhedral sets and their faces that fit together in a "nice" way. The polyhedral complex R. induced by the training set will contain codimension sets called cham- bers. These correspond exactly to acti- vation regions. Activation patterns have one-to-one correspondence with the tu- ple hyperplane orientations associated each chamber. The center panel of fig. 1 provides an illustration R for an exam- ple dataset.
Algorithm Exact ERM (Arora et al., 2016)
Input: data D
[x;, y/ ) 2nd layer mR++1
A C {0, mm
(feasible activation patterns (2))
W* R (d+((++)
(random initialization)
for A E A do
W < solution of (3)
if L()) < L(W") then
Wa + WW+WWW
end if
end for
return W
The dual zonotope a polyhedral complex is a single polytope providing an alternate representation of its combinatorial structure (Ziegler, 2012). Each dimension l member of the polyhedral complex has a corresponding codimension & face in the dual zonotope. Incidence relations between the members of the complex dual zonotope. Generally, a zonotope can be described as the image of an N -ddimensional hypercube under a linear map whose columns are known its generators (McMullen, 1971) 1). Each vertex of the zonotope thus is a weighted sum its generators with coefficients belonging to 10,
preserved in the
The dual zonotope Z of our polyhedral complex R has the training examples {x, JM as its generators. the activation regions our network. When
The vertices of have a one-to-one correspondence vertex is expressed as weighted sum over the generators, the coefficient {0. 1) of each generator equals its corresponding example's 's value the region's is activation pattern. The right panel of fig. shows example zonotope Z and its duality with the polyhedral complex R.
These correspondences allow to assign additional structure to the set of activation patterns AA rather than just treating it as an unstructured set. For example, the I-skeleton of the zonotope Z, which is the graph formed by its vertices and edges, provides means of traversing the of activation patterns. Furthermore, we can directly make connections between the training dataset and the activation pattern structure by making use of the fact that Z is generated by the training examples.
In the multiple hidden unit setting, i.e. > 1. note that parameter space becomes an m-fold Cartesian product of single-unit parameter spaces. Furthermore, we are free to set the activation pattern for each unit independently of the others. As the combinatorial structure for
Multiple Hidden Units

---

each hidden unit can be described using the zonotope E, the combinatorial structure for a multiple hidden unit network described by the m-fold Cartesian product 2 I Z. As noted in appendix A. n is also zonotope. Each vertex of ndd corresponds to product of m vertices of 2. As in the single unit case, there is a one-to-one correspondence between the vertices of 2 and the set of activation patterns A.
4 ReLU Optimization
4.1
NP-Hardness
Given the additional structure we have imposed on the set of activation patterns in algorithm 1, is natural to ask whether we can use to develop global optimization algorithm that more efficient than a brute-force search over activation patterns. Unfortunately, several works (Goel et al., 2020; Froese et al., 2021) have demonstrated that global optimization a shallow ReLU network is NP-hard. Nevertheless, this does not preclude the existence of efficient combinatorial optimizer given certain conditions on the input dataset. Since the zonotope z" encapsulates the combinatorial structure of the optimization problem, we look to see if properties of td can be related to the difficulty of combinatorial optimization.
Nontrivial affine dependencies between training examples influence the combinatorial structure of the n Since the reductions of NP-hard problems ReIJU optimization done in Goel al. (2020); Froese et al. (2021) create datasets with such nontrivial dependencies, it is natural to ask whether it is NP-hard to optimize shallow ReLU network over a training dataset in general position.
4.1.1 Discontinuity of the Global Optimum
If the global minimum of the loss is always continuous with respect to the input dataset, then the NP-hardness of optimization over arbitrary datasets in general position would follow from continuity since every set of points is arbitrarily close to set in general position. However, we can prove that such continuity holds unconditionally for ReLU optimization only the case where the training dataset is in general position. We give sketch of the proof here along with some analysis of the failure cases that can happen when the data are not general positions. We provide a full proof in appendix C.
Theorem 4.1. Suppose we are given a dataset D = (x);, in general position and some m E N. Let (D) denote the global minimum of the loss (1) over the dataset 'D for shallow ReLU network with m units. Given any >> O, some ò >> O exists such |L* (D) L (D.)) < 5 for any
dataset D.- {(x(, y:) M satisfying ||x: x S. e.
Proof sketch. For a small enough perturbation, we can prove that the datasets' zonotopes are combi- natorially equivalent. Hence their of feasible activation patterns will be exactly the same. Using the fact that any subset of a set in general position is also in general position, we can then show that the constrained convex optimization problem associated with each vertex is continuous with respect to the input dataset. Since the global minimum of the loss is just the minimum of the optimal loss for each vertex, its continuity follows from the fact that the composition of two continuous functions continuous.
When the dataset is not in general position, there are two possible ways in which breaking of nontrivial affine dependencies between examples can cause the global minimum of the loss to become discontinuous. The first is that the globally optimal vertex in the perturbed zonotope exists in the original zonotope, but its associated constrained convex optimization problem is discontinuous with respect the dataset. This can happen when there are nontrivial affine dependencies that get broken amongst the active examples in the vertex. The second way is that the globally optimal vertex of the perturbed zonotope does not exist in the original zonotope. Geometrically, we can think of such a vertex resulting from the breakdown of parallelelppppe higher dimension face (Gover, 2014). See appendix for examples these phenomena.
Analysis of Reductions We can use this characterization of the instabilities of the global optimum to perturbations the training data to analyze the reductions of NP-hard problems used in Goel et al. (2020). We focus on the reduction of the NP-hard set cover problem to the optimization of
5

---

Synthetic Data
Fashion MNIST
100
Giaslent Descor:
Training Acc
30-7-
Final Training
20
80-
10
32
Overparamsterizziin Factor
Number Units
Figure 2: Comparison between gradient descent and optimization with fixed random activation pattern. Left: Results for MSE on synthetic data for and mgen 8. The overparameterization
factor times Mgen equals the number of units in the trained network. Right: Results for accuracy on Fashion MNIST coat/pullover binary classification for d = 16 and N 700.
single bias-free ReLU. In appendix E.2, provide an explicit example of an arbitrarily small perturbation that results in the global minimum of the loss being independent of the solution to the set cover problem.
To the best of our knowledge, existing reductions of NP-hard problems ReLU optimization all create datasets that are not in general position (Goel et al., 2020; Froese et al., 2021). Therefore, we present a modification of the set cover reduction that produces a dataset in general position. See appendix E.3 for details of this modification along with proof that it is indeed reduction of the set cover problem. We thus have the following statement.
Theorem 4.2. Optimizing a ReLU is NP-hard even when restricted datasets in general position.
4.2 Polynomial Time Optimization via Overparameterization
Even though ReLU network optimization is NP-hard in general, can be shown that overparame- terization allows for gradient descent to converge to the global minimum in polynomial time (Du al., 2018; Zou Gu, 2019; Oymak & Soltanolkotabi, 2020; Allen-Zhu al., 2019). This is not contradiction since optimization of overparameterizee ReLU networks is strict subset of the set of all ReLU optimization problems.
The general proof method of these works usually involves demonstrating that overparamettrization
results in activation patterns not changing much throughout training. This allows gradient descent to effectively bypass the combinatorial search of the outer loop in algorithm 1. The remaining optimization problem can then be shown be similar to the constrained convex optimization problem (3) by assuming that the second layer is frozen. Using the zonotope formalism, we can interpret these results as saying that sufficiently large number of hidden units m guarantees with high probability that a randomly chosen vertex corresponds to region of parameter space containing global minimum of the loss. Parameter initialization selects the random vertex in practice.
This can be justified theoretically through a connection to random feature models. Here we assume that the first layer frozen, and the second layer forms linear model over the random first layer features. As the number of units m increases past the number of training examples N, the set of first layer activations can become linearly independent. The probability of this approaches 1 as m co. Whether all of the parameters within an activation region produce linearly dependent activations can be shown to depend solely on its activation pattern when the dataset in general position.
To test this, we ran experiments comparing batch gradient descent to solving (3) for a randomly chosen vertex some toy datasets. We created synthetic datasets by first choosing the input dimension d and a positive integer mgge- To get the training examples, we sampled N = (d + 1)m points in Rd i.idd from the standard Gaussian distribution. We then sampled the weights of a shallow ReLU network with Mgen units i.i.d. from the standard Gaussian distribution. We used this network to create the labels for our synthetic dataset. See appendix 1. for details on the data generation process.
We also created toy binary classification datasets from MNIST (LeCun et al., 2010) and Fashion MNIST (Xiao et al., 2017) by choosing two classes, 5/9 and coat/pullover, respectively, to differentiate. We used the first d {8, 16) components of the PCA whitened data and selected N e (350, 700} examples for our training sets. See appendix H.2 for details.
We present some of our results in fig. 2. See appendix H for details of the training procedures and for results on more d, megn and d, N pairs. On synthetic data, we see that the random vertex method finds good solution for overparameterizzaioon factors of 4 and up. However, gradient descent tends

---

to arrive at reasonably good solutions for lower levels of overparameterrzztion while the random vertex method fails. This was a general trend that we observed across different d, Mygen pairs on the synthetic datasets and d, N pairs on the binary classification datasets. Note that the Fashion MNIST networks represented in fig. were relatively underparameterized with the maximal size of 64 units being overparameterized by only factor of about 1.5.
This demonstrates that gradient descent can perform some aspects of the combinatorial search over zonotope vertices. We hypothesize that the gradient tends to be smaller within activation regions with good optimum and thus gradient descent more likely to stay within good activation region. Conversely, the larger gradients within activation regions with poor optima make it more likely that a gradient descent step will move the parameters out of those regions. We can thus think of gradient descent as performing the likelihood of moving from one vertex to another decreases as the parameters settle into better activation regions.
process over the vertices of the zonotope since
4.2.1 Tighter Bounds
We now introduce a novel vertex selection scheme that runs in polynomial time and requires minimal overparameterization Suppose D {(x;, y is a dataset in general position. Assume that the examples are ordered by the value of their last coordinate, which we suppose is unique WLOG (i.e. ef x; e/xx, for i < j). If not provided in this format, this can be accomplished in O(N log N) time. We now split the dataset into T_ chunks containing most + examples. We write each
[[ Since each D₂ contains contiguous chunk of examples sorted along an axis in coordinate space, we see that we can always find a hyperplane separating Dz and Drr for k * k.. For each k- = 1,..., d=I 1. we add two units to our ReI.U network and assign them the activation pattern of 0 for examples belong to a Dr with k < k and 1 for the remaining examples. One of the units will be multiplied by +1 in the second layer while the other will be multiplied by -1. Hence the network contains total of 2 d+1 N hidden units. We prove in appendix F that set of weights with that activation pattern exists such that the output of the network on training examples exactly matches their labels. The key idea in the proof is that we can sequentially fit the examples in the k-th chunk without undoing our progress in fitting the chunks before it.
chunk Ds = {(x: ))) [)(d++)++))
Theorem 4.3. Given dataset in Rd containing N examples in general position, a shallow ReLU network containing 2 N hidden units can be found in polynomial time exactly fitting the dataset.
2+1
To the best of our knowledge, this is the tightest known bound on the amount of overparameterizztton needed to find the global optimum of a ReLU network in polynomial time. A simple argument comparing the number of unknowns and the number of equations demonstrates that we need at least #+1 hidden units to exactly fit an arbitrary dataset with a shallow ReLU network. Hence our method uses only about twice as many hidden units as is necessary to the data. However, we emphasize that this ReLU optimization scheme is primarily of theoretical interest since we find in practice that the resulting ReLU network tends to be a very ill-conditioned function.
_N
4.3 Relevance to Optimization in Practice
Practically all optimization of ReLU networks in practice uses some variant of gradient descent with an overparameterized network. As the degree of overparameterization goes down, gradient descent begins to arrive at increasingly suboptimal solutions (Nakkiran et al., 2021).
In section 4.2, we hypothesized how gradient descent can find activation regions containing good optima. However, the gradient of the loss is inherently local property in parameter space while the space's 's decomposition into activation regions is inherently global. Boundaries between regions correspond to discontinuities in the gradient of the loss. We hypothesize that these properties lead to little direct information about the optimization problem being used to inform gradient descent's traversal over zonotope vertices. Hence we suspect that algorithms that explicitly traverse zonotope vertices using some loss-based criteria can outperform gradient descent in the underparameterrzzed- to mndlyy-oveparrameteriiee regimes.
7

---

Synthetic Data
Final Training
10
Algorithm Greedy Local Search (GL.) Heuristic
20:1
1019
Input: data D fx,, U/ W ==1 E R=++ max steps T E N
2nd layer
Overperameterization Fashion MNIST
An for 1 E verl
Final Training (80
do
1.0
Descont
Ac+1 + At
for A'' neighbors(444) (Aa) do
if (A', L (At+1: then
A4+1
Number of Units m
end if end for
Figure 3: Comparison between gradient descent and our GLS heuristics, Top: Results for MSE on synthetic data for 4 and Mgee 2. The overpa- rameterization factor times Mgen equals the number of units in the trained network. Bottom: Results for accuracy on Fashion MNIST coat/pullover bi- nary classification for d 8 and N 350.
if A A, then
return A,
end if
end for
return Ar
4.3.1 Difficulty of Combinatorial Search
Unless N., we are unlikely to find an efficient algorithm to perform the combinatorial search in algorithm for arbitrary datasets (Goel et al., 2020). However, this does not preclude the existence of heuristics that tend to work well on problems encountered in practice. We investigated this by using a greedy local search (GLS) over the graph formed by the zonotope's I-skeleton. We start by selecting a vertex at random and find its corresponding optimal loss by solving a convex program. We iterate over its neighboring vertices and compute their optimal losses as well. We then move to the neighboring vertex with the lowest loss and repeat the process until we arrive at a vertex with lower loss than its neighbors. We then take that vertex's 's optimal parameters the global minimization problem. This algorithm defined in detail in algorithm
approximation to
We also experimented with some additional heuristics that help the GLS converge faster by reducing the number of convex problems solved each step. For example, we can greedily move the first neighboring vertex encountered with lower loss, which significantly decreases the time per step in the early stages of training. We can further improve this by using geometric information about a solution's relative location in its activation region try certain vertices first. We call the algorithm with these heuristics modified greedy local search (mGLS) and define it in detail in appendix G.
Note that these heuristics are not guaranteed to return global minimizer of the loss. Furthermore, there are an exponential number of vertices in the zonotope, so there are no immediate guarantees of them taking less than exponential time to run. However, each step takes polynomial time since each vertex has (mmN) neighbors, so each step solves a polynomial number convex optimization problems.
We ran experiments comparing these heuristics gradient descent on toy datasets generated in the same way as in section 4.2. We used GLS on the synthetic data and mGLS on the MNIST and Fashion MNIST derived data. We present some of our results in fig. 3. See appendix H for details of the training procedures and for results for more values of d, Mggen and d, N pairs. On synthetic data, the GLS heuristies significantly outperformed gradient descent. On binary classification tasks, mGLS outperformed gradient descent for networks with moderate levels of underparameterizatio and performed similarly otherwise. We observed a similar trend across the rest of the d, mgen and d, N pairs. These results support our hypothesis that gradient descent is suboptimal in the combinatorial search over activation patterns. Furthermore, they suggest that this combinatorial optimization might tend to be tractable in practice.

---

5
Related Work
Some of the concepts in this work also arise in Zhang et al. (2018). A key difference is that they analyze the activation regions in input space given a ReLU network with fixed parameters. We can, in fact, use their tropical geometric approach to derive our zonotope formalism for single ReLU unit. To do so, the roles of the weights and data must be swapped; we instead use a fixed data matrix and varying vector of weights while they a zonotope generated by the training examples, however, is novel. Misiakos et al. (2021) show that the approximation error between two shallow ReLU networks depends on the the Hausdorff distance between the zonotopes generated by the each network's units. Bach (2017) also use a Hausdorff distance between zonotopes in the context of neural network optimization.
fixed weight matrix and varying vector of data. Our use of
Goel et al. (2020) provide proofs of the NP-hardness of optimization of shallow ReLU networks and the hardness of even finding an approximate solution. Froese et al. (2021) extend these results and show that the brute force search in Arora et al. (2016) cannot avoided in the worst case. Du et al. (2018) was one of the first works to prove that overparameterization in shallow ReLU networks allows gradient descent to converge to a global optimum in polynomial time. Their bound of ( on the number of hidden units needed for convergence was improved upon by subsequent work (Ji & Telgarsky, 2019; Daniely, 2019). For example, Oymak & Soltanolkotabi (2020) proved a bound of /dN2/dd)
Pilanci & Ergen (2020) and Wang et al. (2021) represent global optimization of shallow ReLU networks with & regularization using a convex optimization problem that operates simultaneously over all activation patterns for single unit. Multiple units are handled by summing over the activations with different activation patterns. This leads to exponential complexity in the data dimension but avoids exponential complexity in the number of units m. Dey et al. (2020) provide an example of a heuristic algorithm that searches over activation patterns for single ReLU unit. Their algorithm operates on the principle that examples with large positive labels are more likely to belong to the active set in good solutions.
6 Conclusion
We introduced a novel characterization of the combinatorial structure of activation patterns implicit in the optimization of shallow ReLU networks. We showed that it can be described as Cartesian product of zonotopes generated by the training examples. We used this zonotope formalism to explore aspects of the optimization of shallow ReLU networks. It provides a natural way to describe instabilities of the global minimum to perturbations of the dataset. We then related this to work on the NP-hardness of global ReLU optimization. In particular, we demonstrated that this optimization problem still NP-hard even when restricted to datasets in general position, which commonly assumed of data in practice.
We then explored how combinatorial considerations play into the relationship between overparame- terization and polynomial-time time optimization of shallow ReLU networks. Namely we interpret known results for gradient descent as stating that a randomly chosen zonotope vertex will be close one whose activation region contains a good local optimum. We then provide empirical evidence that sufficient overparameterizatioo makes highly likely that a randomly chosen vertex has good local optimum. We also provide polynomial-time algorithm that can find a vertex containing the global optimum using approximately twice the minimum number of hidden units needed to fit the dataset exactly. Finally, we provide a GLS heuristic over zonotope vertices that outperforms gradient descent on some toy problems.
In future work we plan to theoretically and empirically explore heuristics and algorithms that perform well on real-world datasets. We hope to analyze how vertex choice impacts generalization. Further insights might be derived by exploring the connections of hyperplane arrangements to tropical geometry and oriented matroids (Stanley et al., 2004; Oxley, 2006; Maclagan & Sturmfels, 2015). One caveat of our theory is that it applies to only a shallow ReLU network. However, the concepts of activation patterns are still meaningful for deep ReLU networks but require real algebraic geometry for analysis (Basu, 2014; Bochnak et al., 2013). We hope that further research along these avenues will deepen our understanding of neural network training and enable improvements to training in practice.

---

References
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, Z. Differentiable convex optimization layers. arXiv preprint arXi::1910.12433 2019.
Allen-Zhu, Z., Li, Y., and Song, Z. A convergence theory for deep learning via over-parraeterizzaion.. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Arora, R., Basu, A., Mianjy, P., and Mukherjee, A. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv:1611.0144 2016.
Bach, F. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):6296681, 2017.
Basu, S. Algorithms in real algebraic geometry: a survey. arXiv preprint arXiv:1409.1544 2014.
Bochnak, J., Coste, M., and Roy, M.-F. Real algebraic geometry, volume 36. Springer Science Business Media, 2013.
Daniely, A. Neural networks learning and memorization with (almost) no over-paramelcriiation.. arXiv preprint arXiv:1911.0987 2019.
Dey, S. S., Wang, G., and Xie, Y. Approximation algorithms for training one-node relu neural networks. IEEE Transactions on Signal Processing, 68:6696-6706, 2020.
Diamond, S. and Boyd, Cvxpy: python-embeddeed modeling language for convex optimization. The Journal of Machine Learming Research, 211):2990-2213, 2016.
Domahidi, A., Chu, E., and Boyd, Ecos: An socp solver for embedded systems. In 2013 European Control Conference (ECC), pp. 3071-3076. IEEE, 2013.
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes over- wer-parameterized neural networks. arXiv preprint 1810.0004,, 2018.
Froese, V., Hertrich, C., and Niedermeier, R. The computational complexity relu network training parameterized by data dimensionality. arXiv preprint trXiv:2105.08677 2021.
Glorot, X. and Bengio. Y. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249 256. JMLR Workshop and Conference Proceedings, 2010.
Goel, S., Klivans, A., Manurangsi, P., and Reichman, D. Tight hardness results for training depth-2 relu networks. arXiv preprint arXiv:2011. 13550, 2020.
Gover, E. Congruence and metrical invariants of zonotopes. arXiv preprint arXiv: arXiv:1401. 1401.4749, 2014.
Hornik, K. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Ji, Z. and Telgarsky, M. Polylogarithmic width suffices for gradient descent achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv: /909. /2292, 2019.
Kaplan, J., McCandlish, S., Henighan, T., Brown, B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint 200iv:2001.08361. 2020.
LeCun, Y., Cortes, C., and Burges, C. Mnist handwritten digit database. ATT ATT Labs [Online]. Available: http://yann.eer wwwwn. cww.exdb/mnisstttt...mmmmmmm/a 2, 2010.
Maclagan, D. and Sturmfels, B. Introduction to tropical geometry, volume 161. American Mathemat- ical Soc., 2015.
McMullen, P. On zonotopes. Transactions of the American Mathematical Society, 159:91-109, 1971.
10

---

Misiakos, P., Smyriis, G., Retsinas, G., and Maragos. P. Neural network approximation based on hausdorff distance of tropical zonotopes. In International Conference on Learning Representations. 2021.
Nakkiran, P., Kaplun, G., Bansal, Y., Yang. T., Barak, B., and Sutskever, I. Deep double descent:
Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003 2021.
Oxley, G. Matroid theory, volume Oxford University Press, USA, 2006.
Oymak, S. and Soltanolkotabi, M. Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal Selected Areas in Information Theory, 1(1):84-105, 2020.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Pilanci, M. and Ergen, T. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Richter-Geberte J. and Ziegler. G. M. 6: Oriented matroids. Chapman and Hall/CRC, 2017.
Stanley, R. P. al. An introduction hyperplane arrangements. Geometric combinatorics, 13 (389-496):24, 2004.
Wang, Y., Lacotte, J., and Pilanci, M. The hidden convex optimization landscape of regularized two- layer relu networks: an exact characterization optimal solutions. International Conference on Learning Representations, 2021.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Xu, Y. and Yin, W. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM Journal on imaging 2013.
sciences,
Zhang, L., Naitzat, G., and Lim, L.-H. Tropical geometry of deep neural networks. In International Conference on Machine Learning, pp. 5824-5832. PMLR, 2018
Ziegler, G. M. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
Zou, D. and Gu, Q. An improved analysis of training weerpparameterized deep neural networks. arXiv preprint arXiv: 04688, 2019.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our contributions are primarily theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We provide proofs in the appendix.

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] We have included this in the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We include standard deviations for all results in the tables.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the datasets and software libraries used.
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] The datasets used (MNIST, Fashion MNIST) are standard in machine learning.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] They are widely used datasets with pictures of handwritten digits and items of clothing.
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "oQ_M8DLZkJK", "reviewer": "Reviewer_Akn8", "summary": "\nThis paper uses methods from polyhedral combinatorics to study the optimization landscape of Shallow ReLU networks. \nBy associating a proper combinatorial object (zenotope) with an instance of minimizing the training error of a ReLU the authors show \nthat hardness results may be non robust and might break under small perturbations. Another contribution is to use the zenotope  \nto introduce a local search algorithm and demonstrate experimentally that it can outperform local search. ", "questions": "If I recall correctly, the paper of Vu regarding the hardness of training shallow networks argues that the hardness results there should persist even if the training points are in general positions. Doesn't this indicate that the optimization problem for perturbed data sets should be hard as well? Personally I think it would be surprising (though not impossible) if the hardness results for training shallow networks would break under (small amounts of) noise. ", "limitations": "A lack of a proof of a new fact of significance. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I like the idea of analyzing hard instances arising from NP hardness proofs. However the paper falls short to prove or disprove whether \nNP hardness results are robust in the sense that they may hold for non-degenerate data sets (that can be obtained by random perturbations). Without a resolution of this I find the contribution of the paper to be below the bar of NeurIPS.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Sgp7f5COUXh", "reviewer": "Reviewer_L3JB", "summary": "This paper presents a combinatorial view of optimizing shallow (two-layer) ReLU networks. The authors show that optimizing a shallow ReLU network is an NP-hard combinatorial optimization problem, and existing optimizers such as gradient descent are performing some local combinatorial search. The authors then present a greedy search method to exploit the combinatorial optimization nature, and it outperforms gradient descent in experiments. ", "questions": "1. Is it possible to compare other optimizers like SGD?", "limitations": "The limitations are addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The combinatorial modeling perspective of the learning process of shallow ReLU networks is novel and interesting.\n2. The theoretical analysis and insights presented in this paper seem sound. For example, the authors present explains the relationship between the NP-hard difficulty found in this paper and the recent theoretical results that optimizing overparameterized deep networks is feasible in polynomial time. \n3. Empirical results are provided to ground the theoretical findings. The proposed greedy search method for shallow ReLU networks is interesting. \n\n**Weaknesses**\nSee \"Questions\"", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QKztkYbfI_n", "reviewer": "Reviewer_7Q5f", "summary": "This paper considers the problem of optimizing a shallow ReLU network. The authors characterize the combinatorial structure of this problem via a zonotope whose vertices correspond to the feasible activation patterns of the network for a given training dataset. They use this characterization to provide some new insights and results on shallow ReLU optimization. In particular, they show that a necessary condition for the global optimum of a shallow ReLu network to be discontinuous is for the training dataset to have non-trivial affine dependencies. This implies that existing NP-hardness results do not trivially apply to datasets in general positions (i.e., no non-trivial affine dependencies between training examples). They also explore the relationship between over-parameterization and optimization difficulty. They provide empirical evidence that over-parameterization increases the likelihood that a randomly chosen vertex will contain a good solution. They propose a polynomial-time vertex selection algorithm which finds the global optimum using only $\\Omega(2 N)$ parameters, which improves over existing bounds on the amount of over-parameterization needed. They further introduced a greedy local search heuristic which outperforms gradient descent on  some toy datasets.", "questions": "Questions:\n- Why no results on real-world datasets are provided? Is the proposed heuristic already too expensive for datasets like CIFAR-10?\n- Why do you use GLS on the synthetic data and mGLS on the MNIST and Fashion MNIST derived data, and not mGLS on both?\n- What is meant by \"ill-conditioned\" on line 299? it is helpful to include some empirical results to illustrate this point.\n\nSuggestions:\n- Include timing results in the comparison of gradient descent and mGLS.\n- Add a comparison with the heuristic algorithm of Dey et al. (2020).\n- Change the x-axis of the Fashion MNIST to over-parameterization factor, in both Figures 2 and 3.\n- Paragraph on lines 202-209 is not very clear. It would be good to provide further details with formal mathematical descriptions of the two cases. \n- Typo in Eq. (3): $2 (a_i - 1) \\rightarrow (2 a_i - 1)$", "limitations": "The authors discussed limitations of their work in the conclusion. There's no direct negative societal impact as this work is mostly theoretical.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Novel characterization of the optimization of shallow ReLU networks which enabled the authors to provide interesting and novel results which further our understanding of neural networks training, and can be useful for future research.\n- Paper is well written with results clearly presented overall (the clarity of some sections can be further improved, see Questions for details)\n- A helpful overview of the mathematical concepts used is provided in the appendix.\n\nWeaknesses:\n- Results only apply to shallow ReLU networks.\n- The proposed greedy local search heuristic is too expensive to be used in practice on large real-world datasets.\n- Empirical results only on toy datasets, and no comparison with other existing works.", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "H5VZevpZDLn", "reviewer": "Reviewer_6i9S", "summary": "This paper illustrate that the global optimization of a two-layer ReLU network can be characterized as a combinatorial search over the vertices of the zonotope which is isometric to all feasible activation patterns. This perspective is utilized to show that the global optimum of two-layer ReLU network is discontinuous with respect to the training data. They also interpret the overparametrization as the random sampling over the zonotope vertices. A novel heuristic algorithm of greedy local search over the zonotope vertices is introduced and numerical results show its advantage over the gradient descent method. \n", "questions": "The authors shall formalize their main results in the theorem or proposition environment. \n\nFor Figure 3, as the proposed greedy local search heuristic is a randomized algorithm and the initialization of the gradient descent is at random, the authors shall plot the heat map of multiple trials instead of showing the result for a single trial. For instance, in the lower part of the figure 3, by increasing the number of units from 16 to 32, the final training accuracy of mGLS decreases. This may result from the random seed. \n\nSome literature are missing. The concept of zonotope is utilized in the optimization of two-layer ReLU network in [1,2]. The global optimization of the training problem two-layer ReLU networks with the standard $\\ell_2$ regularization can also be formalized into the search over all possible activation patterns, see [3,4].\n\n[1] Bach, Francis. \"Breaking the curse of dimensionality with convex neural networks.\"\n[2] Misiakos, Panagiotis, et al. \"Neural Network Approximation based on Hausdorff distance of Tropical Zonotopes.\"\n[3] Pilanci, Mert, and Tolga Ergen. \"Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.”\n[4] Wang, Yifei, Jonathan Lacotte, and Mert Pilanci. \"The Hidden Convex Optimization Landscape of Two-Layer ReLU Neural Networks: an Exact Characterization of the Optimal Solutions.\"\n", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The idea of connecting the optimization of ReLU networks with vertices in the zonotope is very interesting. \n- The numerical comparison between the greedy local search heuristic and gradient descent algorithm illustrate the strength of the proposed heuristic algorithm. \n\nWeakness:\n- This is a theoretical paper but the theoretical contribution of this paper is hard to interpret. There are no formalized theorem or proposition in the paper. It will be very helpful if the author can organize their main contributions into theorems. \n- The authors show that when the training data is in general position, the global optimum of the training set is continuous with respect to the training data. But what is the implication of this result?  \n- The discussion of over-parameterization in section 4.2 only provides a heuristic that the random vertex selection can work and this is only numerically verified. Some solid analysis about why the random vertex selection works will greatly strengthen the paper. \n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept