Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a notion of statistical meaningful approximation and applies it to studying how NN models can approximate Boolean circuit and Turing Machines. One aspect of their definition is using two families of functions: One family F (e.g., NN) approximating a second family (e.g., Turing machines). Various generalization bounds are given with respect to this new notion. 
strengths_and_weaknesses: Long story short I find this paper to be weak accept: I support acceptance provided the authors can demonstrate they can deal with the (many) issues in this paper. 

I'm less convinced by the SM definition. To me it feels similar to other notions of learnability and also the choice of a specific loss function as opposed to a family of loss functions (which seems to be necessary for the definition to go through) is another disadvantage. 
Rather, the strength of the paper is in the simulation results of Turing machines and Boolean circuit by NN models. These simulation results are needed and could find multiple uses.
questions: "finite width RNNs with infinite precision can simulate Turing machines,
but finite-precision, finite-width RNNs cannot, as implied by streaming lower bounds"

Can you prove this statement of back it up with a paper proving it?
limitations: With many parts of the paper the feeling is that authors are using sub optimal phrasing and references. 
"Unfortunately, a rigorous analysis of optimization is unresolved even for simple two-layer nets"
The reference for this is very strange. There are many much more relevant works I would cite. 

The discussion of infinite precision also does not mention the large body of work dealing with weight-restricted NN as well 
as results showing how to avoid large weights by increasing depth. And there are more such examples. I would probably cite
"For valid generalization the size of the weights is more important than the size of the network"

There are many other improvements: for example replace "boolean" by Boolean. I recommend a though pass improving the language and the presentation.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the approximation power of neural networks under the constraint of finite-precision weights and activations. Many classical results touting the expressive power of neural networks have a strong reliance on infinite precision weights and activations whereas the more practical finite-precision networks are nearly not as expressive. 

In this paper, authors propose a different take on how one should evaluate expressivity. Instead of focusing on whether a target function can be expressed by the class of neural networks in question, one should focus on the statistical properties exhibited by the class. To that effect, authors propose the notion of statistically meaningful (SM) approximation which looks at how well ERM can approximate a given function.   

Under this notion of approximation, authors first show  that neural networks can approximate boolean circuits where the sample complexity only depends on the polynomial of the circuit size and only have a logarithmic dependence on the parameters of the neural network. Secondly, authors show that that with the transformers can approximate turning machine that run for at most $T$ steps.

The main technical contribution of this paper is the proof technique used by the authors to derive the approximation results. 

The first main contribution is the all-layer margin loss that allows one to reason about finite precision weights. 

Second contribution is Lemma 2.4 that, at a high level, says that for any $G\in \mathcal{G}$ one can find a function $F$ in the approximating class $\mathcal{F}$ with large all-layer margin approximates , then the $\mathcal{F}$  $\epsilon$-SM approximates $\mathcal{G}$ with sample complexity depends on the margin and on $\log$ of the number of parameters.

As a high-level proof technique for both boolean circuits and Turing machines, authors first showed by construction a neural network that approximate a given boolean circuit/Turning machine. To get the appropriate sample complexity result, the approximating function needs large margin. To get large margin, authors introduce “correction” functions that needs to be added to the constructed neural network. Due to the discrete nature of operations in both TM and boolean circuits, the correction functions are implemented by $\text{round}$ operations.
strengths_and_weaknesses: **Strengths:**

- This is a well motivated paper that studies the expressivity of neural networks from a statistical lens.
- To the best of my knowledge, the technique proposed in the paper is novel and the ideas are original which can be applied to study approximation power of different neural network architecture.
- Lemma 2.4 also has implications for studying generalization properties of neural networks where all-layer margin loss depends on $\ell_2$ stability of the neural network.

**Weaknesses:**

- The construction of self-attention network to simulate Turing machine is a bit hard to follow from the body of the paper. It’s still not clear to me how the reading at location $l_i$ is achieved by the transformers.
- As far as I understand, authors are able to construct correction functions due to the discrete nature of boolean circuits and TM. Constructing for other class of functions is probably more challenging thus it’ll be difficult to adapt this proof technique.
questions: I am not entirely sure how the reading operation at location $l_i(x)$ is achieved. How can one binary search over the past steps when the $l_j(x)$ for $j\leq i$ are not sorted? 
limitations: Authors have addressed limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces the novel notion of statistically meaningful approximation, which requires that a function family can be approximated with high probability based on the empirical risk minimizer obtained from $n$ samples. This notion combines both approximation and generalization and does not allow for infinite precision (as used by prior work), which can inflate the expressivity of an architecture. The paper demonstrates that feedforward neural networks can statistically meaningfully approximate boolean circuits and that transformers can statistically meaningfully approximate Turing machines.
strengths_and_weaknesses: **Strengths**

The paper introduces a novel notion of approximation and generalization for neural networks, which can potentially open up a fruitful line of future research. Indeed, the paper shows that this notion of statistically meaningful approximation allows for improved bounds over prior work for approximating boolean circuits with feedforward neural networks and for approximating bounded-time Turing machines with transformers. Concretely, the paper improves the sample complexity from exponential depth scaling and polynomial parameter scaling to scaling in the circuit size for the approximation of boolean circuits. Similarly, the paper presents an exponential scaling improvement for approximation of Turing machines with bounded computation time $T$ (sample complexity polynomial in $\log T$ instead of $T$). Importantly, statistically meaningful approximation does not allow for infinite precision, which is known to inflate the expressivity of neural network architectures. Finally, the paper is very well-written and well-placed in the literature.

**Weaknesses**

The definition of the 0-1 loss on line 181 is incorrect. Consider, e.g., $y = z = 0$, which corresponds to a loss of $0$ but yields $\mathbb{1}((0 - 0.5)0 \leq 0) = \mathbb{1}(0 \leq 0) = 1$. Similarly, the definition of the all-layer margin is incorrect (e.g., $y = 0$ and $F(x, \theta) = 0$ yields $\rho = 0$, which is not strictly positive). Since all other proofs in the paper hinge on this definition, I do not know whether they are also incorrect.


I am happy to increase my score if the above concerns are addressed.

questions: Are the sequences in $\mathcal{A}^\ast$ on line 127 of finite length?
limitations: The paper does not address limitations or potential negative societal impacts.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents an alternative to expressivity (which is muddied by issues like unbounded precision), SM-approximation, which combines both expressivity and generalization. It then shows that FFNNs SM-approximate Boolean circuits and Transformers SM-approximate bounded-time Turing machines.


strengths_and_weaknesses: # Strengths

The new definition of SM-approximation is reasonable. I think the paper makes a good case for considering expressivity and generalization together.

# Weaknesses

There are no negative results, e.g., “function class \mathcal{G} is not SM-approximable by FFNNs,” or "if function class \mathclass{G} has (some property), it is not SM-approximable by FFNNs." To me such results would be equally interesting, if not more interesting. This is mentioned in the future work section, but I don't have a good sense for how difficult it would be to obtain such results. I don't consider lack of such results a weakness in this paper, but if the definition of SM-approximation made it infeasible to obtain such results, I'd consider that a major weakness of the definition.

# Minor Comments

lines 133-159. Please state that functions in \mathcal{F}, \mathcal{G} are from \mathcal{X} to \mathbb{R}.

line 186: \min_\delta

line 326-265. There are a number of assumptions made about the Transformer, most of which are very mild.

The paper claims that the following could be dispensed with in favor of standard Transformers:
- hardmax attention (distributing attention equally among ties)
- no residual connections

The paper makes no claim about:
- positional encodings are binary representation of integer position
- no layer normalization
- FFNNs have 3 layers and the last one also has a ReLU

The only important fact is:
- the number of layers is O(log T)

questions: lines 145-149. I was troubled by the appearance of the number 0.99 in a formal definition. Would there be any negative consequence of using 1-\delta instead?

line 186: How hard is it to compute \rho_F? What would the implications be if it were very hard?

limitations: I did not see an explicit discussion of weaknesses.

There isn't a statement about potential negative societal impact, and I don't think one is needed.
review_title: null

Meta-review: metareview: Reviewers agree on the merits of sharing the paper with the community.The authors are highly encouraged to incorporate the many constructive suggestions offered.
confidence: Certain
Decision: Accept