Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new hyperdimensional computing (HDC) methodology with low-dimensional hypervectors. The authors provide the theoretical results (for a binary classifier case) that the relatively lower dimensions can yield better performance. Furthermore, their theories suggest that the model performance asymptotically drops with respect to the hypervector dimension. Finally, the author empirically shows that their HDC method performs better than the existing methodology. 
strength_and_weaknesses: Strength

1. A theoretical framework to explain the relationship between the hypervector dimensions and model performance.
2. The author's empirical results are better than the existing methodology.

Weakness
1. Hard to read.
2. Notations are not well defined. Mainly, I could not follow the idea in the Methods section. 
3. Figures are not self-explanatory. Hard to understand what idea is conveying.
4. HDC method seems to only work on MNIST dataset. CIFAR-10 results are overall very poor. 
clarity,_quality,_novelty_and_reproducibility: I list down the questions below:

1. What numerical simulation was performed in Figures 1 and 2 to get these two plots? Also, even though Statements 3.1 and 3.2 say the asymptotical degradation with respect to the hypervector dimension, how does the dimension close to 0 get the highest accuracy? Intuitively, some relatively large dimension is required to get the representational power of hypervectors (as the authors stated in $\epsilon$-quasiorthogonality). 

2. What is the kernel-based binary encoder in Section 4? The current draft needs to explain in detail what this binary encoder is. For example, what is the weight sharing in Figure 3? What is the loss function to train the binary encoder? 

3. In equation 2, the explanation on $w_{i, j}^l$ is not self-explanatory. The authors only say, "$i$,$j$ are the index of different neurons." I suspect $j$ is the index of neurons in $l-1$ layer, and $i$ is the neuron index at $l$th layer. Then, I am confused what $w_{i, j, x_{j}^{l-1}=1}^{l}$ means. It's never explained anywhere. 

4. In equation 3, $G(x)$ is never defined anywhere, except mentioning that it's a gradient. I guess that the Jacobian is an identity matrix due to the straight-through estimator.

5. In Figure 5, the inference accuracy with the majority rule drops as the hypervector dimension goes up; however, the performance does not drop with the FC layer. Does this mean that performance degradation is not due to the dimensionality of the hypervector but due to the aggregation function, especially the majority rule?

6. The CIFAR-10 results, including the existing HDC methodology, seem to fail the learning procedure. CIFAR-10 can be achieved above 90% easily with ResNet architecture. From CIFAR-10 results, I am skeptical of MNIST results because the effective dimensionality of MNIST is less than 768 [1]; therefore, low-dimension hypervectors work well. Furthermore, the bad performances of overall HDC methods in CIFAR-10 worry me about whether the current HDC framework is a promising direction for the ML community. 

[1] Bubeck, Sébastien, and Mark Sellke. "A universal law of robustness via isoperimetry." Advances in Neural Information Processing Systems 34 (2021): 28811-28822.
summary_of_the_review: The authors provide theoretical and empirical results regarding the new hyperdimensional computing framework to accelerate the inference speed. However, overall the paper could be clearer to read and more self-explanatory. Mainly, I could not understand what methodology they used as their algorithm. The one big concern is that this HDC method works well on MNIST but not other datasets (CIFAR-10), which alerts my internal false alarm. Overall, I do not think the draft does not meet the ICLR bars.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the factors affecting accuracy in HDC and proposed a more efficient HDC method. 
strength_and_weaknesses: Strength:
* The paper is mostly well organized and is straightforward to follow.
* The study on dimension and accuracy looks very interesting. The result showing using much less dimensions looks very promising. I believe the technique proposed can be rather valuable especially for resource constrained hardware given the low dimension it can achieve.
Weaknesses:
* It would be helpful to provide more context on HDC basics, possibly some illustration figures to provide readers a more straight idea of how it works.
* Is it possible to have some more benchmarks on some other datasets other than MNIST? I understand that the authors have stated that the method needs some simple dataset, having some other datasets, maybe some simple classification datasets would be more convincing.
* Albeit having a better performance than existing methods, the performance on Cifar10 is not quite optimal from a application point of view. The author also states that HDC now mostly works on simple datasets.
clarity,_quality,_novelty_and_reproducibility: This work is of decent quality, the idea and aspects look novel to the best of my knowledge. I have not run the code myself, but the code to reproduce is available in anonymous GitHub.
summary_of_the_review: Overall, I think this is an important study to make HDC more applicable, despite having some limitations. The paper would benefit from more clarify on the background. More benchmarks, even on some other simple datasets, could make it more convincing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper uses a neural network ($k$ binary neural network layers) as an encoder to derive binary features and then plug into hyperdimensional computing framework for inference. The paper manages to arrive at satisfactory performance on MNIST with a low dimension as 32, however, the connection from the motivation and analysis to the result is not clear to me. 
strength_and_weaknesses: This paper examines the necessity for high dimension in HDC, however, the reasoning can not convince me in the following aspects:

1. In standard HDC, hypervectors in the item memory is simply sampled from a high dimensional space, and the encoding process involves only binding and bundling, which are highly parallel and efficient operations. However, this paper extracts the hypervector for each data through training a binary neural network, thus the comparison in table 1 is not fair for some baselines which samples hypervectors, as the training/encoding cost is totally different, plus only inference complexity is given in table 1, not to say the retraining cost. 

-- 1.1 Further more, this method nearly abandons the advantage of HDC, using binary NN to derive hypervectors, why not just use a simple BNN? One can imagine, use an even complicated network to derive useful features as hypervectors, follows with the HDC framework, it would have same inference cost as the features are also binarized. Therefore, a comparison with the same BNN used should be included as a baseline to justify the improvement is not from training NNs. It's not surprising to me that this method can perform well in a low dimension. 

2. The author claims it's the orthogonality, not a high dimension, that is the determinant of HDC accuracy

-- 2.1 if that holds true, a simple experiment is that, as shown in section 3.2, you can find $n$ strictly orthogonal hyper vectors in a low dimension $2^{\lceil{\log_2(n)}\rceil}$ space by simply picking $n$ rows in the Hadamard matrix, then you can use the standard HDC encoding process for training, why suffer using a neural network to find hypervectors? Follow the author's logic, if this performs well, I would buy the claim, though I doubt it. 
-- 2.2 even with a trained BNN, did you test that the learnt low dimensional hypervectors are orthogonal to each other? I doubt it. 
-- 2.3 As the cited work Yu et al., 2022 shows, the orthogonality is not helpfully sometimes, but a related (with covariance) random sampled hypervectors help boost the HDC performance. 
-- 2.4 The analysis in section 3 looks interesting, however the conclusion holds only when the hypervectors are sampled uniformly from the ball, but not for general HDC, so is the claim that "the lower the dimension, the higher the accuracy." to be conditioned, not for HDC. Though the result is still counter intuitive to me. 
-- 2.5 The high dimension brings not only orthogonality, but also robustness, i.e., the hypervector can be recovered even a large fraction of its element perturbed, this property would lost in a low dimensional space. 

3. After checking through the code, it looks to me the (MNIST) data to you BNN is floats? If not, how do you quantize the pixel values of images to binary? 
clarity,_quality,_novelty_and_reproducibility: The work is original, well-cited, however, some claims and empirically results are not well-supported. 
summary_of_the_review: Overall, it is still an interesting submission, currently I think it's under the bar of ICLR, unless some suggested experiments can be conducted to support the claims in the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a new approach in hyperdimensional computing (HDC), which is an emerging model of efficient computation involving solely binary representations (called hypervectors) for data. Typically, these hypervectors are chosen to be _random_ and _very high-dimensional_; this paper theoretically argues that lower dimensional representations suffice, provided that the hypervectors are quasi-orthogonal. Additionally, the paper proposes using a binary neural network (BNN) to derive hypervectors of very low dimension. Results on (Fashion-)MNIST shows the benefits of the proposed approach.

Original reviews for this paper were borderline. While the reviewers acknowledged the importance of the problem and the originality of the proposed ideas, several other concerns were raised. The use of BNNs as feature encoders seemed contrary to the spirit of HDC. The primary advantage for using HDC is a dramatic reduction in computation cost compared to standard floating point arithmetic, but training BNNs incurs additional costs and negates any such advantages; in any case, an apples-to-apples comparison here would have to take into account BNN training costs, which the authors did not provide.

The theoretical results on quasi-orthogonality assumed that hypervectors were randomly sampled, but the experimental results discarded this approach and used a BNN encoder (trained offline). Finally, the fact that the only results were on (Fashion-)MNIST raised questions about broader impact. Responses by the authors did not significantly affect the reviewers' opinions.

Overall, on balance the paper falls short of the bar for acceptance. The authors might consider (for a future revision) better justifying the use of BNNs as a sound strategy, tightening the connection between theory and practice, as well as clearing any doubts about future impact by performing more challenging experiments.


justification_for_why_not_higher_score: As described in the summary and the notes from the PC meeting, far too many concerns still remain to merit acceptance at this stage.
Decision: Reject