Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a network architecture, HANN. HANN contains a hidden layer of binary activations, and can has a VC dimension smaller than the number of network parameters. HANN can be potentially a VC theory for studying the generalization of overparameterized neural networks. HANN is competitive with sota on UCI datasets.
main_review: Strength:
- demystify the generalization puzzle of overparameterized neural networks is an important topic to study
- novelty: the first VC theory of overparameterized neural networks
- the construction is not too complicated

Weakness:
- I don't fully understand the implication of Theorem 4.2. size(rho, kappa) critically depends on r, the rank of the weight matrix W. But if we decompose W=UV, where U is d*r and V=r*k. Isn't the VC dimension of HANN still higher than the number of effective parameters, dr+rk? In this case, what benefit do HANN have over ReLU and sigmoid networks?

Post rebuttal
====

Thanks for answering my questions. I'm still confused about what role does the binary activation play here though. I think the critical assumption of Theorem 4.2 is that the weight matrix is low-rank. In this case, can't I just reformulate the layer with low-rank weight as two layers with a small bottleneck hidden layer of dimensionality r, which has much smaller number of parameters than the equivalent network? If this is the case, I think the result is only relevant to the low-rank assumption, not the HANN itself.

I'm still maintaining my score based on these concerns.
summary_of_the_review: This paper solves an important problem and is novel, though I am not fully convinced by the claims due to some potential misunderstanding.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the VC dimension and minimax properties of a subclass of partially quantized NNs they name HAC(d,r,k) where d is the input dim, r is the latent (linear map) dim and k is the boolean function dim. The authors show a bound on the VC dim of HAC of O(k^r) which is independent of the number of weights. Further, the authors show that when the conditional density p(y|x) is lipschitz, H(d, d, r) achieve minimax optimality when d is fixed and $r=n^{1/(d+2)}$. 
main_review: To the best of my knowledge the theory appears sound and the proofs are correct and the usage of the compression scheme is neat. Moreover the experimental evaluation is thorough and surprising to some extent (e.g., how does this class achieve about state of the art performance). However, I have some reservations about the paper. First, reading the title and introduction has led me to believe that a much more general class of QNNs have small VC dimension. However the model that the authors study is basically a two layer NNs, shedding doubt on whether any non-toy quantized models will have small VC dim (could be easily checked via and experiment ala Zhang et al 2017). 

Moreover, I'm doubtful about studying the VC dim of NNs in the first place. I'd love to hear the authors take of what are we aiming to learn here as in practice VC dims will give us non-meaningful bounds. 

Minor comments:
Should the following be number of samples: 
       Note that the above VC bound is useless in the overparameterized setting if VC(C) =(# of weights)
In proposition 4.5, P_I could be an empty set. (e.g., if a_1 = -a_2 and b_1 = -b_2). Then, there is no unique minimizer to P_I. 
If m < n how can the size of J be n? 

It would be helpful to further explain the second paragraph in page 8 (e.g., how did you count the weights?).  

Regarding the experiments, in my opinion, using the number of weights to measure overparameterization is not indicative. A much better way to know whether the models are overparameterized is to look at the training error/loss (if it is very close to zero we are overparameterized).

summary_of_the_review: The work is technically sound however I find the title/introduction overstating the significance of the results to some extent and not sure if the motivation is strong enough.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers VC dimension for a class of partially quantized networks referred to as hyperplane augmented neural networks (HANNs). The architecture of this class of networks consists of a first hidden layer of width r and a second hidden layer of width k with Boolean (sign) activations. The name HANNs seems to be inspired by this Boolean layer which introduces a hyperplane arrangement.
An upper bound of O(k^r) is established on the VC dimension of this network that is independent of the rest of the network (a Boolean function). In addition to this result on the VC dimension of HANNs, a result is proven on their representation power. In particular, it is shown that HANNs achieve the minimax rate for classification when the posterior probability is Lipschitz.
main_review: The paper is very well written. All the concepts and ideas are explained well. The results are supported by detailed proofs and extensive references to the existing work. Nice graphics are used to present the ideas of hyperplane arrangement and resulting classifiers

The analytical results nicely complement each other. It is shown that while useful bounds on VC dimension can be proven for HANNs, the representative power of HANNs is comparable to the full precision models.

The VC dimension is known to lead to vacuous generalization bounds in full precision overparameterized neural networks. The main contribution of this paper is providing useful bounds on VC dimension for a class of highly expressive models. The bound still seems quite large though: O(k^r). It is a power of width of the layer which seems to determine the expressive capacity of the network (through determining the hyperplane arrangement). This seems a major limitation in application of the main result of the paper. If I am right, I think the paper can significantly benefit from a discussion on this (either explaining more cases where the results are useful or clarifying this limitation). For example, if we use the numbers given in experiments (which are relatively small experiments), with a data set of size 77904 and k=100, and r=3 seems to result in vacuous bounds on generalization again.
summary_of_the_review: The paper is written very well and has nice complementary results. I am however uncertain about whether the main result would be effective in explaining generalization error using VC dimension in reasonable scenarios.
review_title: null

Meta-review: The authors analyzing the VC-dimension of a class of neural networks
with hard thresholds at the hidden nodes that include a low-rank weight
matrix and hard-thresholds at hidden units.  The bounds are independent
of the number of weights used to represent functions mapping a hidden
layer to the output.  They also provided some experiments supporting the
practicality of networks like those treated in their theoretical analysis.

There was some question about whether the VC-dimension continues to be relevant.
Also, while the upper bounds have attractive properties that were highlighted by the
authors, they also are not very strong in other respects.

The consensus view overall, though, was that this is a "nice result",
a clean illustration of a generalization affect of the type that has
been of wide interest lately.
Decision: Accept (Poster)