Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: You have talked about small neural networks but there is an exponential dependence on 1/eps . How is this more interesting (or tighter) than the dependence on the dimension? Is it possible to combine this with the results that only depends on the dimension to get something tighter?
review_title: Exponential dependence on epsilon

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work finds a connection between Bourgain's junta problem, the existing results in circuit complexity, and the approximation of a boolean function using two-layer neural net. I think that finding connections between different fields and applying the insights gained is a valid contribution. For this reason, I recommend acceptance.

But my current major concern is that this work is only constrained to the domain of boolean hypercube, which is far from what is done in practice (continuous domain). Indeed, the authors could argue that understanding the former is a first step, but if the connection is only suitable for this case and not adaptable to more general scenarios, then it probably would have limited interest.
review_title: A work that finds connections between existing theoretical results and the universal approximation theorem

final_score: rating: null
review_content: The constants appear to grow with smaller \delta and \epsilon. 
Are the presented results not contradictory when smaller sensitivity to noise goes with larger number of units? 
Are the presented results not contradictory when the same sensitivity at larger noise goes with a larger number of units? 
How different is Theorem 3 from what could be obtained using Theorem 1 alone and not Theorem 2? 
review_title: Sensitivity vs size

final_score: rating: 5: Marginally below acceptance threshold
review_content: The approximation capabilities of neural networks have been studied before for approximating different classes of functions. The goal of this paper is to provide an analog of the approximation theorem for the class of noise-stable functions. The class of functions that are noise-stable and their output does not significantly depend on an individual input seems an interesting class and therefore I find the problem definition interesting.  The paper is well-written and it is easy to follow the proofs and arguments. 

I have two major comments:

1- Presentation: The way I understand this arguments is that the noise-stability measures the "true" dimensionality of the data based on the dependence of the function on different dimensions. Therefore, it is possible to restate and prove an analog to the approximation theorems based on "true" dimensionality of data. It is also unclear when the stability based bounds are tighter than dimension based bounds as both of them grow exponentially. I find these discussions interesting but unfortunately, the authors present the result as some bound that does not depend on the dimension and a constant (!??) that grows exponentially with (1/eps). This is not entirely the right picture because the epsilon in the stability could itself depend on the dimension. I believe in most problems (1/epsilon) grows with the dimension. 

2- Contribution: Even though the connection is new and interesting, the contribution of the paper is not significant enough. The presented results are direct applications of previous works and most of the lemmas in the paper are restating the known results. I believe more discussions and results need to be added to make this a complete work.
review_title: This paper provides an analog of the universal approximation theorem where the size of the network depends on a notion of noise-stability instead of the dimension.

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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? 

review_title: review of ``ON ROBUST CONCEPTS AND SMALL NEURAL NETS''

final_score: rating: null
review_content: The results of the paper seem to be a straightforward application of results of previous work. Besides being able to connect results from different domains (the Junta problem, circuit complexity) to the two-layer neural net, can the authors justify their own contributions in their analysis?
review_title: Application of previous results?

Meta-review: The paper makes a solid technical contribution in establishing a universal approximation theorem for the boolean hypercube. They characterize the class of boolean functions that can be efficiently approximated by a two-layer network.
 
 We like the idea of noise stability, and it could explain why in practice, perturbation techniques such as dropout are effective. Moreover, humans can identify images, despite corruptions, and hence, intuitively the concepts we aim to learn should be robust.
 
 However, the framework of the paper deviated from the networks and data structures that are the norm in practice. In practice, we rarely have boolean functions. And it is well known that boolean functions can behave quite differently from continuous functions. 
 
 We recommend that the authors widen the scope of their work, and attempt to connect their findings to practical networks and functions. Moreover, we recommend that they do a more thorough literature survey. For instance, the idea of robust concepts has appeared before
 http://www.pnas.org/content/113/48/E7655.full
 And nice connections to elastic learning have been made in the above paper.
 
 We recommend a workshop presentation since this will enable more interaction with people in the area, and people who are working on practical networks.
Decision: Invite to Workshop Track