On Robust Concepts and Small Neural Nets
The universal approximation theorem for neural networks says that any reasonable function is well-approximated by a two-layer neural network with sigmoid gates but it does not provide good bounds on the number of hidden-layer nodes or the weights. However, robust concepts often have small neural networks in practice. We show an efficient analog of the universal approximation theorem on the boolean hypercube in this context. We prove that any noise-stable boolean function on n boolean-valued input variables can be well-approximated by a two-layer linear threshold circuit with a small number of hidden-layer nodes and small weights, that depend only on the noise-stability and approximation parameters, and are independent of n. We also give a polynomial time learning algorithm that outputs a small two-layer linear threshold circuit that approximates such a given function. We also show weaker generalizations of this to noise-stable polynomial threshold functions and noise-stable boolean functions in general.
SUMMARY This paper presents a study of the number of hidden units and training examples needed to learn functions from a particular class. This class is defined as those Boolean functions with an upper bound on the variability of the outputs. PROS The paper promotes interesting results from the theoretical computer science community to investigate the efficiency of representation of functions with limited variability in terms of shallow feedforward networks with linear threshold units. CONS The analysis is limited to shallow networks. The analysis is based on piecing together interesting results, however without contributing significant innovations. The presentation of the main results and conclusions is somewhat obscure, as the therein appearing terms/constants do not express a clear relation between increased robustness and decreasing number of required hidden units. COMMENTS - In the abstract one reads ``The universal approximation theorem for neural networks says that any reasonable function is well-approximated by a two-layer neural network with sigmoid gates but it does not provide good bounds on the number of hidden-layer nodes or the weights.** In page 1 the paper points the reader to a review article. It could be a good idea to include also more recent references. Given the motivation presented in the abstract of the paper it would be a good idea to also comment of works discussing the classes of Boolean functions representable by linear threshold networks. For instance the paper [Hyperplane Arrangements Separating Arbitrary Vertex Classes in n-Cubes. Wenzel, Ay, Paseman] discusses various classes of functions that can be represented by shallow linear threshold networks and provides upper and lower bounds on the number of hidden units needed for representing various types of Boolean functions. In particular that paper also provides lower bounds on the number of hidden units needed to define a universal approximator. - It certainly would be a good idea to discuss the results on the learning complexity in terms of measures such as the VC-dimension. - Thank you for the explanations regarding the constants. So if the noise sensitivity is kept constant, larger values of epsilon are associated with a smaller value of delta and of 1/epsilon. Nonetheless, the description in Theorem 2 is in terms of poly(1/epsilon, 1/delta), which still could increase? Also, in Lemma 1 reducing the sensitivity at a constant noise increases the bound on k? - The fact that the descriptions are independent of n seems to be related to the definition of the noise sensitivity as an expectation over all inputs. This certainly deserves more discussion. One good start could be to discuss examples of functions with an upper bound on the noise sensitivity (aside from the linear threshold functions discussed in Lemma 2). Also, reverse statements to Lemma 1 would be interesting, describing the noise sensitivity of juntas specifically, even if only as simple examples. - On page 3 ``...variables is polynomial in the noise-sensitivity parameters** should be inverse of? MINOR COMMENTS On page 5 Proposition 1 should be Lemma 1?
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
On Robust Concepts and Small Neural Nets
The universal approximation theorem for neural networks says that any reasonable function is well-approximated by a two-layer neural network with sigmoid gates but it does not provide good bounds on the number of hidden-layer nodes or the weights. However, robust concepts often have small neural networks in practice. We show an efficient analog of the universal approximation theorem on the boolean hypercube in this context. We prove that any noise-stable boolean function on n boolean-valued input variables can be well-approximated by a two-layer linear threshold circuit with a small number of hidden-layer nodes and small weights, that depend only on the noise-stability and approximation parameters, and are independent of n. We also give a polynomial time learning algorithm that outputs a small two-layer linear threshold circuit that approximates such a given function. We also show weaker generalizations of this to noise-stable polynomial threshold functions and noise-stable boolean functions in general.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



SUMMARY This paper presents a study of the number of hidden units and training examples needed to learn functions from a particular class. This class is defined as those Boolean functions with an upper bound on the variability of the outputs. PROS The paper promotes interesting results from the theoretical computer science community to investigate the efficiency of representation of functions with limited variability in terms of shallow feedforward networks with linear threshold units. CONS The analysis is limited to shallow networks. The analysis is based on piecing together interesting results, however without contributing significant innovations. The presentation of the main results and conclusions is somewhat obscure, as the therein appearing terms/constants do not express a clear relation between increased robustness and decreasing number of required hidden units. COMMENTS - In the abstract one reads ``The universal approximation theorem for neural networks says that any reasonable function is well-approximated by a two-layer neural network with sigmoid gates but it does not provide good bounds on the number of hidden-layer nodes or the weights.** In page 1 the paper points the reader to a review article. It could be a good idea to include also more recent references. Given the motivation presented in the abstract of the paper it would be a good idea to also comment of works discussing the classes of Boolean functions representable by linear threshold networks. For instance the paper [Hyperplane Arrangements Separating Arbitrary Vertex Classes in n-Cubes. Wenzel, Ay, Paseman] discusses various classes of functions that can be represented by shallow linear threshold networks and provides upper and lower bounds on the number of hidden units needed for representing various types of Boolean functions. In particular that paper also provides lower bounds on the number of hidden units needed to define a universal approximator. - It certainly would be a good idea to discuss the results on the learning complexity in terms of measures such as the VC-dimension. - Thank you for the explanations regarding the constants. So if the noise sensitivity is kept constant, larger values of epsilon are associated with a smaller value of delta and of 1/epsilon. Nonetheless, the description in Theorem 2 is in terms of poly(1/epsilon, 1/delta), which still could increase? Also, in Lemma 1 reducing the sensitivity at a constant noise increases the bound on k? - The fact that the descriptions are independent of n seems to be related to the definition of the noise sensitivity as an expectation over all inputs. This certainly deserves more discussion. One good start could be to discuss examples of functions with an upper bound on the noise sensitivity (aside from the linear threshold functions discussed in Lemma 2). Also, reverse statements to Lemma 1 would be interesting, describing the noise sensitivity of juntas specifically, even if only as simple examples. - On page 3 ``...variables is polynomial in the noise-sensitivity parameters** should be inverse of? MINOR COMMENTS On page 5 Proposition 1 should be Lemma 1?
assistant
SUMMARY This paper presents a study of the number of hidden units and training examples needed to learn functions from a particular class. This class is defined as those Boolean functions with an upper bound on the variability of the outputs. PROS The paper promotes interesting results from the theoretical computer science community to investigate the efficiency of representation of functions with limited variability in terms of shallow feedforward networks with linear threshold units. CONS The analysis is limited to shallow networks. The analysis is based on piecing together interesting results, however without contributing significant innovations. The presentation of the main results and conclusions is somewhat obscure, as the therein appearing terms/constants do not express a clear relation between increased robustness and decreasing number of required hidden units. COMMENTS - In the abstract one reads ``The universal approximation theorem for neural networks says that any reasonable function is well-approximated by a two-layer neural network with sigmoid gates but it does not provide good bounds on the number of hidden-layer nodes or the weights. ** In page 1 the paper points the reader to a review article. It could be a good idea to include also more recent references. Given the motivation presented in the abstract of the paper it would be a good idea to also comment of works discussing the classes of Boolean functions representable by linear threshold networks. For instance the paper [Hyperplane Arrangements Separating Arbitrary Vertex Classes in n-Cubes. Wenzel, Ay, Paseman] discusses various classes of functions that can be represented by shallow linear threshold networks and provides upper and lower bounds on the number of hidden units needed for representing various types of Boolean functions. In particular that paper also provides lower bounds on the number of hidden units needed to define a universal approximator. - It certainly would be a good idea to discuss the results on the learning complexity in terms of measures such as the VC-dimension. - Thank you for the explanations regarding the constants. So if the noise sensitivity is kept constant, larger values of epsilon are associated with a smaller value of delta and of 1/epsilon. Nonetheless, the description in Theorem 2 is in terms of poly(1/epsilon, 1/delta), which still could increase? Also, in Lemma 1 reducing the sensitivity at a constant noise increases the bound on k? - The fact that the descriptions are independent of n seems to be related to the definition of the noise sensitivity as an expectation over all inputs. This certainly deserves more discussion. One good start could be to discuss examples of functions with an upper bound on the noise sensitivity (aside from the linear threshold functions discussed in Lemma 2). Also, reverse statements to Lemma 1 would be interesting, describing the noise sensitivity of juntas specifically, even if only as simple examples. - On page 3 ``...variables is polynomial in the noise-sensitivity parameters** should be inverse of? MINOR COMMENTS On page 5 Proposition 1 should be Lemma 1?