Tropical Expressivity of Neural Networks

We thank the reviewer for their thorough reading of our work and detailed feedback. We would like to address weaknesses raised by the reviewer.

Rigor of Tropical Geometry and Group Theory

We apologize for the confusion caused: while we focus on the tropical geometric interpretation of neural networks, we are actually not working exclusively in the tropical setting, because some of the concepts would not make sense, as pointed out by the reviewer. Our results do not require us to work in $\overline{ℝ}$. We never work with tropical vector spaces, only tropical polynomials, which can be understood without reference to $\overline{ℝ}$. In (4), we are taking a maximum over a finite set of Hoffman constants, each of which lies in $ℝ$ rather than $\overline{ℝ}$ (one concern here might be that we are allowing coefficients of the tropical Puiseux rational function to be $−∞$, but we can ignore these). Similar observations can be made about (5), (6), and (7). On the matter of group actions, we never claim to be working with group actions in a tropical sense. In our submission, we are not working with tropical vector spaces and group actions, but simply with $ℝ^n$ and group actions in the usual sense.

Motivation

We have conducted a second literature review and found one citation missing from our original submission: On the Decision Boundaries of Neural Networks: A Tropical Geometry Perspective by Alfarra et al. (2022). We apologize for this oversight. This reference provides important insights that demonstrate the value of tropical geometry in deep learning. To the best of our understanding our work does not overlap with theirs in either theoretical focus or novel computational contributions.

As far as we know, all existing computational methods for finding the number of linear regions of a neural network rely on sampling which doesn’t guarantee an exact solution, or impose some restrictions such as boundedness on the input variables rather than the total number of linear regions.

1. We provide new tools for computing the size of the domain needed to count the linear regions, and we give a new method for computing the exact number of linear regions of a neural network on an unbounded domain.
2. We provide a direct way of computing a novel representation of neural networks, namely, the tropical Puiseux rational form. This opens the door to further connections with tropical geometry such as the number of (non-redundant) monomials that appear in the tropical expression of a neural network.

Effective Utility

The main goal of our paper was to present a proof of concept, not to develop highly optimized code. We believe there is room for improvement (particularly for symbolic computations), and better algorithms could greatly boost our approach’s performance, which we noted in the Discussion section as a future research direction. We focused on smaller networks for simpler analysis. However our code can handle more complex architectures than those we used. Our symbolic method can process networks with inputs of dimension 784 in a minute (Table 1 in the attachment).

Finally, the reviewer noticed that the two methods we outlined yield different results. The discrepancy is because the numerical algorithm may undercount the number of linear regions in certain cases due to not taking into account connectivity of regions. We will clarify this in the revision.

We thank the reviewer for identifying errors in Table 1–3 regarding the computed Hoffman constants. After reviewing the public code by Peña et al. (2018), we found that it was incorrect. We have since computed the values by brute force, and the updated tables show that the lower bounds are always below the true values. Regarding upper bounds, Theorem 3.9 states that the Hoffman constant is bounded by the inverse of the smallest nonzero singular value of submatrices of $A$. We used a threshold of $10^{−10}$ to determine nonzero values, but found that many small singular values ranged between $10^{−30} ∼ 10^{−14}$. This confirms that the singular values provide upper bounds. We agree that these bounds can be tightened as a direction for future research. This study could also be promising for new results concerning the Stewart–Todd condition measure of a matrix.

Improving Efficiency

Our claim of improving efficiency refers to the factorial reduction in scaling for invariant networks. We believe that the ideas we introduce in this manuscript may also lead to similar improvements for other methods, in a symmetric setting.

Lack of Attribution to Prior Work

We do not claim that this work is the first to analyze expressivity of neural networks using tropical geometry; we explicitly mention previous work in this direction in our manuscript in lines 39–41. We are not aware of work that implements algorithms to compute the exact number of linear regions of a network with unbounded inputs.

Lack of Precision

To clarify, the symbolic method for computing linear regions yields the ground truth, by converting the network to a tropical Puiseux rational function and applying Algorithm 3.

For missing assumptions, we acknowledge that Theorem 4.3 is missing the assumption that the group is finite. We believed it was implicit in the context (cardinal arithmetic would be implausible in the context of machine learning). Moreover, we disagree that our definition of $A$-surjective sets introduces any new assumptions on $m$ and $n$. The definition makes sense for any matrix $A$ and the assertion that the existence of $A$-surjective sets implies that $m<n$ is incorrect, as such sets exist for all $A≠0$.

We thank the reviewer for flagging typos and inaccuracies; these will be addressed in the revision.

References: Alfarra, M., Bibi, A., Hammoud, H., Gaafar, M., & Ghanem, B. (2022). On the decision boundaries of neural networks: A tropical geometry perspective. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21 45(4), 5027–5037

We thank the reviewer for reading our rebuttal and giving us this important opportunity to clarify our approach further.

The role of infinity

The tropical semiring is a fundamental algebraic object in tropical geometry where all other constructions are based. For the sake of completeness and correctness, we must introduce $-\infty$ to the extended real line since it is the neutral element for tropical addition. In our application to machine learning, the main way the tropical framework appears is that it gives a very convenient (and, as our work demonstrates, computable) way of representing neural networks. In other words, we are interested in tropical representations these functions. While tropical Puiseux polynomials naturally yield functions defined over the whole extended real line, this is generally not the case for neural networks, and thus we usually restrict to $\mathbb{R}$. We would also like to emphasize that while the mathematics are mostly developed over the real numbers, a large portion of our code uses OSCAR's implementation of the tropical algebra.

Connection to tropical geometry

Tropical geometry is a broad field and intersects with many other mathematical fields including polyhedral geometry, algebraic geometry, combinatorics, etc. For example, tropical Puiseux polynomials, tropical monomials are naturally related to linear regions and polyhedra in ways which are fully elaborated in our paper. The connection between neural networks and tropical geometry is crucial since it allows us to use OSCAR to develop symbolic computations. While we acknowledge that we don’t use any advanced tropical geometry for our results (and instead use techniques from other fields e.g., polyhedral geometry), we maintain that our work is nevertheless tropical geometric in nature: Firstly, our results are built on the tropical geometric interpretation of neural networks. Secondly, we principally interpret tropical Puiseux polynomials as functions over $\mathbb{R}$, which is the natural approach for studying their function-theoretic properties as we do in our work. Despite this interpretation, they still are rigorously tropical objects.

We understand that the mix of tropical and classical approaches and perspectives in our work may have inadvertently introduced confusion, which we will carefully clarify in the revision.

Responding to other concerns

We are very grateful for this opportunity to engage with the reviewer who gave us a very detailed, thoughtful, and constructive review, which we appreciated very much. We would like to ask if the reviewer has any other questions pertaining to our rebuttal of the concerns in the original report? We are aware that our rebuttal was brief, given that we were constrained to the quite strict character limit, but we would very much like to engage further and respond in greater detail to the reviewer’s observations in the original report above.

Effective Utility

Firstly, we want to clarify that the main goal of our paper was to present a proof of concept, not to develop highly optimized code for large-scale stress tests on modern deep neural networks. Our focus was on laying the theoretical groundwork and demonstrating the feasibility of our approach. Therefore, we did not prioritize optimizing certain parts of the code for performance. This was a deliberate choice to highlight the direct applicability of symbolic computation techniques to neural networks. For example, in the tropical Puiseux polynomial library, we implemented simple algorithms, rather than using more sophisticated computer algebra methods. We believe there is considerable room for improvement in this area, and more efficient algorithms could significantly boost our approach's performance, which we noted in the Discussion section as a future research direction.

Secondly, our experiments mainly focused on smaller networks to allow for clear and understandable analysis. We believe that understanding small networks is helpful for making deep learning more interpretable. However, our code is capable of handling more complex architectures than those used in our experiments. For instance, our symbolic method can process neural networks with inputs of dimension of 28 × 28 (the dimension of inputs in the MNIST dataset) in about 1 minute. This shows that our approach is scalable, contrary to what our smaller experiments might suggest. We have added new tables in the attachment to demonstrate this on various architectures with higher-dimensional inputs (see Table 1). In our revision, we will include these larger-scale results alongside the smaller-scale experiments, as we believe the smaller-scale ones provide a clearer and more accessible proof of concept, allowing us to illustrate the key insights and mechanisms of our approach more easily.

Finally, the reviewer raised an important issue regarding the two methods we outlined for computing linear regions, which yield different results for networks deeper than 4 layers. We appreciate the reviewer for pointing this out and giving us the chance to clarify. The discrepancy is because the numerical algorithm version implemented in our submission allows for disconnected linear regions, while the symbolic method accounts for connectivity. In other words, the numerical algorithm may undercount the number of linear regions for certain networks. We will address this discrepancy in the revision.

We thank the reviewer for their careful reading and for identifying errors in Table 1--3 regarding the computed Hoffman constants. The lower bounds should indeed be below the true Hoffman constants. After reviewing the public code by Peña et al. (2018), we found that it returned incorrect values, leading to the errors. We have since re-computed the values using a brute force method, and the updated tables show that the lower bounds are always below the true values, consistent with the theory.

Regarding upper bounds, Theorem 3.9 (line 214 of our original submission) states that the Hoffman constant is bounded by the inverse of the smallest nonzero singular value of submatrices of $A$. We used a threshold of $10^{-10}$ to determine nonzero values, but found that many small singular values ranged between $10^{-30} \sim 10^{-14}$. This confirms that the singular values provide upper bounds, aligning with the theory. We agree with the reviewer that these bounds can be tightened, and we will mention this as a direction for future research in our revision. This study could also be promising for new results concerning the Stewart--Todd condition measure of a matrix.

We now turn to addressing the questions asked by the reviewer. We summarize the major concerns in subtopics.

Improving efficiency

We would like to clarify that our claim of improving efficiency refers to the factorial reduction for invariant networks, when compared to naively sampling without taking the symmetry into account. In particular, we do not claim to introduce computational improvements on already existing works, although we believe that the ideas we introduce in this manuscript may also lead to similar improvements for other methods.

How our methods scale and the question of their utility in the context of modern deep learning have been addressed earlier in this response.

(continued in the next official comment)

As we approach the end of the discussion period, we would like to take this opportunity to address some additional concerns raised in the reviewer’s original report. Due to the character limit for rebuttals, our initial response had to be concise, and we regret not being able to provide the level of detail that the depth of the original report warrants.

It is important to clarify that some statements made in the review above are incorrect. Additionally, as with reviewer vnGc, we are concerned that our significant contributions of adapting symbolic computation to the study of neural networks were not fully recognized, given the lack of acknowledgment and comments.

Rigor of Tropical Geometry and Group Theory

We apologize for the confusion raised in our work, since, indeed, while we focus on the tropical geometric interpretation of neural networks, we are actually not working fully and exclusively in the tropical setting throughout our work, precisely because some of the concepts would not make sense, as pointed out by the reviewer. We now elaborate on the specific concerns raised by the reviewer.

Our results do not require us to work over $\overline{\mathbb{R}}$. In particular, the absence of $\overline{\mathbb{R}}$ is intentional: we never work with tropical vectors or vector spaces, but only with tropical (Puiseux) polynomials, which can be understood with no reference to $\overline{\mathbb{R}}$. Referring specifically to the expressions mentioned by the reviewer: in (4), we are taking a maximum over a finite set of Hoffman constants, each of which lies in $\mathbb{R}$ rather than $\overline{\mathbb{R}}$ (one concern here might be that we are in principle allowing coefficients of the tropical Puiseux rational function to be $-\infty$, but we can simply ignore such coefficients). Similar observations can be made about (5), (6), and (7), which should now clarify that these expressions are well-defined.

We respond similarly to the concern about group actions in the tropical setting: we never claim to be working with group actions in a tropical sense. In our submission, we are not working with tropical vector spaces and group actions, but simply with $\mathbb{R}^n$ and group actions in the classical sense.

In our revision, we will explicitly state that these specific concepts should not be evaluated tropically so as to diffuse any misunderstandings.

Motivation

We thank the reviewer for this question and would like to take this opportunity to respond to concerns raised by the reviewer.

With regard to motivation and contribution, we respond by stating that to the best of our knowledge, all computational methods (that have been implemented!) for computing the number of linear regions of a neural network resort to some form of sampling that doesn't guarantee an exact solution, or impose some restrictions such as boundedness on the input variables (for instance, as our Jacobian sampling method does) rather than computing the total number of linear regions. Our work fills this void in two different ways:

1. We provide new tools for computing the size of the domain that needs to be restricted to in order to count the correct number of linear regions, and we give a new method (the so-called symbolic method) for computing the exact number of linear regions of a neural network on an unbounded domain;
2. We also provide a new avenue for understanding the expressivity of neural networks (or more generally, studying interpretability) - specifically, we provide a direct way of computing another representation of neural networks, namely, the tropical Puiseux rational form. This representation is important because it opens the door to using other theory from tropical geometry, e.g., computing other measures of complexity, such as the number of (non-redundant) monomials that appear in the tropical expression of a neural network.

(continued in the next official comment)

We appreciate the time and effort the reviewer has invested in evaluating our work. However, we were concerned by the tone of the recent exchange, which we believe deviated from the professional and respectful dialogue we value. Our intent in pointing out mathematical inaccuracies was not to discredit the review but to ensure that our work is assessed with the utmost accuracy. We hope to steer the conversation back to a constructive and respectful engagement and remain grateful for the opportunity to further clarify and discuss important aspects of our research.

We also want to clarify that our response was not limited to a single sentence/paragraph in Questions section. We noted that there were additional incorrect statements and misunderstandings other than the ones we highlighted in our previous response. Our intention is to address these comprehensively, ensuring that our work is accurately represented and understood. We appreciate your attention to detail and the opportunity to clarify these points.

Group actions

Our original reading of the section in the review about group actions was that there was some confusion about how group actions are defined in the tropical setting, to which we answered that our group actions are not tropical. Group actions are quite a basic concept, but for clarification, we think it is worth being explicit about what we mean. By a left group action of $G$ on a set $X$, we mean a map $(g, x) \mapsto g \cdot x$ that satisfies the following properties:

1. For any $x$ in $X$ and $g, h$ in $G$, we have $(g h) \cdot x = g \cdot (h \cdot x)$
2. For all $x$ in $X$, we have $1_G \cdot x = x$.

A right group action can be defined in a similar way (see, e.g., the Wikipedia page on group actions). In accordance with standard mathematical terminology, we use the term group action to refer to a map $G \times X \to X$ that is either a left or a right action. In particular, we are making no assumptions on the group $G$ beyond finiteness. The group $G$ acting on $\mathbb{R}^n$ further induces an action on the finite set of linear regions $\mathcal{U}$. In this case, for a linear region $x\in \mathcal{U}$ and a group element $g\in G$, the action of $g$ sends $x$ to another linear region $g\cdot x$. Thus we are in the case of finite groups acting on finite sets, without more complicated group representation theory involved. In particular, we do not mention group representations since they are not relevant here: in this level of generality, there is no natural way attaching a representation $\rho : G \to \mathrm{GL}(\mathbb{R}^n)$ to the group action $G \circlearrowright \mathbb{R}^n$ as the reviewer seems to be suggesting. It is of course possible to define certain group actions using representations, which gives rise to the class of linear group actions, but in our work there is no need to impose this additional restriction since it is not necessary for our results to hold. Given that this is seemingly a source of confusion, we will clarify this in the revision.

Tables

We apologise for the lack of clarity in Tables 1-6. As explained in Appendix D, we compute the Hoffman constant together with upper and lower bounds for 8 different Puiseux rational functions, and each column of Tables 1-3 corresponds to the outputs given for of these 8 samples (which are randomly generated with different structural parameters for each table). Tables 4-6 provide more detail about compute times, and again each column corresponds to a different sample. We will clarify this in the revision.

Tropical geometry

The reviewer is philosophically correct in observing that the entire paper could theoretically be rewritten without reference to tropical geometry, however, in the same line of reasoning, any mathematical theory could be rephrased starting from set theory. Doing so would diminish the significance of the specific mathematical contributions that tropical geometry brings to our work. Our choice to use the language of tropical geometry was twofold: (i) it provides a unifying and systematic framework for the general study of expressivity of neural networks; and (ii) it builds upon and extends the work of Zhang et al. (2018), where the main contribution of that paper was to provide an alternative perspective to studying neural networks through the lens of tropical geometry. Furthermore, we would like to claim that the use of tropical geometry is in agreement with other well established works in the linear regions literature, and does not obscure the mathematics of our paper.

Finally, concerning the OSCAR implementation, we agree that in principle our code could be reimplemented without using tropical notions. However, one of the four cornerstones of the OSCAR library is precisely the tropical geometry library (building from polymake) and our work opens the door for researchers to apply these very powerful comptuational tools to study neural networks.

We would like to thank the reviewer for their feedback on our work. We are pleased that the reviewer found our work to be sound and would like to take this opportunity to respond to the concerns raised.

Linear Regions as an Estimate of Information Capacity

In choosing the number of linear regions in the domain of a neural network as our measure of its expressivity, we are following the precedent set by seminal existing work, such as those by Zhang et al. (2018), Montúfar et al. (2014), and Raghu et al. (2017). To briefly summarize the motivation, the idea is that by counting these linear regions, we get an estimate of how many classes a neural network could classify in theory if the weights were ‘hand-tuned,’ so to speak. It is also a measure of the model’s flexibility—the more linear pieces there are, the easier it is to approximate smooth functions, in the spirit of Riemann integration, for example.

Matrix Product Notation

We apologize for any confusion caused by our choice of notation on matrix products. In Section 3.1 on line 133 of our submission, the matrix product refers to classical matrix multiplication as opposed to tropical matrix multiplication. In general, throughout our submission, we did not work with tropical linear algebra. The inequality is used component-wise, so that we are considering the set of points such that each component satisfies the inequality. In practice, this means we are taking the intersection of a set of linear inequalities in the components of x, which is useful for defining a polyhedron.

Scalability and the Curse of Dimensionality

We now turn to addressing to the weakness of the curse of dimensionality raised by the reviewer. In our work we presented a novel algorithm for using symmetry in the domain to improve sampling efficiency to numerically estimate the linear regions. Indeed, we are aware that our technique suffers from the curse of dimensionality, which we explicitly discussed in the Limitations section. Despite the computational complexity being exponential in the number of inputs, we believe that our contribution still has academic value for two reasons: Firstly, it lays the ground for further investigation in using symmetry to accelerate difficult computations; the arguments concerning the fundamental domain are very general and can be applied to any symmetric neural network. Secondly, while the overall computational complexity may not be improved, the case we investigate in our submission does lead to a factorial improvement in complexity, as it scales with the input dimension, which is a nontrivial improvement.

For our algorithm which computes the symbolic representation of a neural network and uses it to compute the exact number of linear regions, the scaling is much better, allowing up to 784-dimensional inputs. We point out that this achieves the dimension of important and widely-used benchmarking inputs, such as MNIST. The technique already scales well enough to yield interesting results concerning the number of monomials and linear regions, and with further algorithmic improvements and better hardware utilization (which are directions for future research that we identified in our original submission), it would likely improve even further.

Thank you again for your feedback on our work and the opportunity to respond to questions and weaknesses. We hope we were able to clarify the reviewer’s concerns.

References: (cited in our original submission)

Liwen Zhang, Gregory Naitzat, and Lek-Heng Lim. Tropical geometry of deep neural networks. In International Conference on Machine Learning (2018), pages 5824–5832. PMLR (2018).

Guido F. Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in Neural Information Processing Systems (2014), 27 (2014).

Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the expressive power of deep neural networks. In International Conference on Machine Learning (2018), pages 2847–2854. PMLR (2017).

Thank you for detailed responses. I will keep my score as is.

Linear Regions as an Estimate of Information Capacity ... by counting these linear regions, we get an estimate of how many classes a neural network could classify in theory if the weights were ‘hand-tuned,’ ...

Thank you for clarifying it. I skimmed Zhang et al. (2018), Montúfar et al. (2014), and Raghu et al. (2017), but none of the authors called it information. Is the number of linear regions equivalent to either Shannon's mutual information (aka channel capacity), the information bottleneck in the rate-distortion theory, or any other information measure? If not, I recommend the authors not to call it 'information' to avoid miscommunication.

We are grateful to the reviewer for their feedback on our work. We are happy that the reviewer found the soundness and contributions of our submission to be good; and that the reviewer appreciated the practicalities of our work in relation to existing theory at the intersection of tropical geometry and machine learning.

We now respond to the questions and concerns raised by the reviewer.

Technical Depth

Our work lies at the intersection of pure mathematics and computer science and we are pleased that all reviewers found our presentation of the background and our contributions accessible and clear. As the reviewer pointed out among the strengths of our work, indeed, a major goal of our work was to adapt an existing theoretical connection to the practical setting to strengthen the current level of understanding of information capacity of neural networks, which we believe that we have achieved. We would like to further elaborate on several aspects concerning the technical depth of our contributions.

The conciseness of our proofs should not be mistaken for a lack of technical depth, nor should it imply that our results lack utility. We strengthen existing theory by introducing powerful ideas into the established intersection of tropical geometry and neural networks. Two explicit examples are connecting the Hoffman constant and machine learning inductive biases to tropical geometry, which we have explicitly studied with symmetric group actions.

The technical depth and impact of our work is further demonstrated by its implications and applications. Our geometric characterization of linear regions, for example, not only advances theoretical understanding but also has practical implications for improving computational efficiency in neural network analysis. The integration of our methods with the OSCAR system broadens the scope of symbolic computation in neural network research. In particular, the tools we provide can be used to analyze the tropical expressions of concrete neural networks; it also paves the way for the application of other computational tools and theory from the rich field of tropical geometry. For instance, this allows for the computation of some standard measures of complexity, such as the number of non-redundant monomials.

We hope this clarifies the depth and significance of our contributions. We are confident that our work meets the high standards of technical rigor and innovation expected in the field, and we are grateful for the opportunity to further elaborate on these points.

Depth–Width Separation

The behavior of depth–width separation is not within the scope of interest of our work, so we did not explore this question of depth–width separation theoretically, though upon further reflection on this relationship in order to respond to the reviewer’s question on this relationship, we conclude that our work may be able to offer some empirical interpretation of the depth–width separation, since the number of non-redundant monomials gives a concrete limit on what functions may be represented. Empirically, from the perspective of our methods, it is 'easier' to increase width than depth, since increasing the latter can lead to a significant increase in the number of monomials that appear and thus to more complicated functions. We computed the number of monomials (after removing redundant ones from the numerator and the denominator) in the tropical expression of random neural networks with the same number of hidden units. As expected, the deeper networks have more monomials than the shallow ones; see Table 2 attached.

Optimality of Algorithms

For our sampling algorithm, we con confirm its optimality in two aspects:

1. Sampling from the fundamental domain (Algorithm 2 of our original submission) gives an estimation of the true value of number of linear regions. We further have tightness of the upper bound and lower bound of the sampling ratio (Theorem 4.3 of our original submission, line 242). In fact, in experiments, we always obtain a 100% sampling ratio (Figure 1 of our original submission), which means the sampling algorithm outputs the true value.
2. The computation of Hoffman constant gives an estimation of the smallest sampling radius (Proposition 3.4 of our original submission, line 174), which further gives the smallest (optimal) sampling box that hits all linear regions. In other words, it gives the optimal region for our Algorithm 4 to be theoretically correct.

We thank the reviewer once again for the helpful feedback provided and hope that we were able to adequately address all concerns.

The reviewer appreciates the author's response. The reviewer has read their comments and reread parts of the paper but still maintains the score unchanged. The reviewer would rewrite parts of the paper to highlight the novelty of the proofs, the proofs themselves and how they were significantly different from prior works, and finally the author's suggested connections to depth-width tradeoffs.

We would like to thank the reviewer for their careful and thoughtful reading of our work. We were pleased to read that the reviewer found our work novel and interesting, and that we were able to communicate and present the concepts and our contributions clearly. We especially appreciate that important issues on existing literature was raised via the reviewer’s questions, to which we now respond.

Aim and Proof of Concept

Firstly, we would like to clarify that the primary aim of our paper was to present a proof of concept rather than to develop highly optimized code for large-scale stress tests. Our focus was on establishing the theoretical foundations and demonstrating the feasibility of our approach. Consequently, we made no significant effort to optimize certain parts of the code for perfor- mance; this choice was made in order to demonstrate the direct applicability of established symbolic computation techniques to study neural networks. For example, the tropical Puiseux polynomial library, we utilized a direct implementation and relatively straightforward algorithms. We believe that there is substantial potential for improvement in this area, and more efficient algorithms could significantly enhance the performance of our approach, which we mentioned in the Discussion section of our submission for future research directions.

Scalability and Higer-Dimensional Inputs

Secondly, our experiments primarily focused on smaller networks to facilitate clear and comprehensible analysis. Nevertheless, the code we developed is capable of handling higher-dimensional cases than those presented in our experiments. For instance, our code can process networks with input dimension 28 × 28 (MNIST dimension) in roughly 1 minute. This capability demonstrates that our approach is in fact scalable, contrary to what our illustrative experiments might have suggested. In our revision, we plan to include these larger scale results alongside the smaller scale experiments, though we believe that the smaller scale ones provide a clearer and more readily accessible proof of concept in the sense that small networks allow us to more easily illustrate the key insights and mechanisms of our approach.

We do appreciate the importance of these concerns and hope that we have addressed them adequately. We do agree with the reviewer that with further optimization and development, the techniques we proposed could be applied to more complex and larger-scale neural networks.

Hoffman Constants

We are very grateful to the reviewer for their careful reading of our work and especially for pointing out the mistakes in Table 1–3 concerning the computed Hoffman constants. Indeed, the lower bound should always be below the true Hoffman constants. Upon further careful investigations of the public code we used to compute the true Hoffman constants due to Peña et al. (2018), we find that the reviewer was indeed correct that the values we reported were erroneous because the public code does not always return correct value. To complete our experiments, we then tested examples without using the code of Peña et al. (2018), and instead implemented a brute force computation to find the maxima over all submatrices. We have provided updated tables for these experiments and these new results show that the lower bounds are always below true values, which is consistent with the theory.

With regard to upper bounds, Theorem 3.9 (line 214) in our original submission shows that the Hoffman constant of a matrix $A$ is bounded by the inverse of the smallest nonzero singular value of $A_J$ , where $J$ ranges over all rows of $A$. In our implementations, to determine a nonzero value, we set the threshold to be $10^{−10}$. However, it seems that a value of $10^{−10}$ is so strict that in fact many small singular values are ruled out. After revisiting our computations and listing all the singular values, we found that many small singular values have magnitude between $10^{−30} ∼ 10^{−14}$. Thus the singular values indeed provide upper bounds, in practice, so the theory is again consistent. In practice, however, in agreement with the reviewer, we also acknowledge that the upper bounds can be tightened and in the revision, we will mention this as a noteworthy direction of future research. We believe that such a study could also have positive implications on the Stewart–Todd condition measure of a matrix.

Minor Comments and Corrections

We appreciate the few typographical and formatting errors flagged by the reviewer and will commit to careful editing and proof-reading in our revision. Thank you once again for your valuable feedback.

References: (cited in our original submission)

Javier F. Peña, Juan C. Vera, and Luis F. Zuluaga. An algorithm to compute the Hoffman constant of a system of linear constraints. arXiv preprint arXiv:1905.06366 (2019).