HADAMRNN: BINARY AND SPARSE TERNARY ORTHOGONAL RNNS

Weaknesses:

At a high-level, while I appreciate the work towards making oRNNs work better and efficient, they themselves have quite a few issues including expressivity.

Limited Real-World Applicability: While the benchmarks used are common in the literature, they often do not translate well to real-world scenarios. oRNNs, in general, have not seen widespread adoption in practical applications.

We provide an answer to this issue below, where we describe the new benchmarks that we consider.

Training Time: The authors mention FastGRNN (Kusupati et al., 2018), which suggests that training oRNN models can be significantly slower (an order of magnitude or more) compared to other methods. It would be beneficial to see a comparison of training times for the proposed HadamRNN models against relevant baselines. Additionally, a discussion on the stability of training these models would be valuable

We provide an answer to this issue below.

Lack of Diverse Datasets: The evaluation primarily relies on toy datasets. To strengthen the claims and demonstrate broader applicability, it would be crucial to include more real-world datasets, even if smaller scale, such as those from the GLUE benchmark (e.g., SST-2, QQP) or SQUAD for question answering.

We provide an answer to this issue below, where we describe the new benchmarks that we consider.

Questions:

At this point I am on the border with a leaning towards rejection but the following things might help along with other reviewers comments.

The paper presents a valuable contribution to the field of oRNNs by introducing a stable and efficient binarization method. However, the lack of real-world evaluation and potential concerns regarding training time and stability hinder its immediate acceptance. I encourage the authors to address these concerns by:

Expanding the evaluation to include more diverse and realistic datasets. This would demonstrate the practical value of HadamRNN and provide a more comprehensive assessment of its capabilities.

Our primary focus was on benchmarks widely used within the RNN, ORNN, and LSTM research communities. In addition, we included the IMDB dataset, a realistic sentiment analysis task in natural language processing (NLP). To further showcase the versatility and strong performance of HadamRNN and Block-HadamRNN across diverse scenarios, we introduced several additional benchmarks, described in detail below.

From GLUE, as requested, we include at least the SST-2 benchmark. This provides also the opportunity to compare HadamRNN to binary and ternary transformers, as asked by reviewer gcYV. On SST-2, we observe that HadamRNN models with sizes of just a few kilobytes achieve an accuracy exceeding 80% (we expect to reach 82–83%). While this is lower than the performance of transformers, which achieve higher accuracy using pre-trained weights and have sizes in the tens of megabytes, it highlights the efficiency of HadamRNN in terms of model size.

Still from the GLUE benchmark, we are working on obtaining experimental results for the CoLA benchmark. However, these results will only be included in the article if they are ready for publication.

To demonstrate the applicability of HadamRNN and Block-HadamRNN, we also include comparisons on the HAR-2, DSA-19, and (hopefully) Yelp-5 benchmarks, as presented in the FastGRNN article (1). The HAR-2 and DSA-19 datasets are designed for recognizing human activity from sensor measurements, while Yelp-5 is a sentiment analysis dataset based on text.

Because of space limitation, all the new benchmarks are in Appendix.

1. Kusupati, Aditya, et al. Fastgrnn: A fast, accurate, stable and tiny kilobyte-sized gated recurrent neural network. Advances in neural information processing systems 31 (2018). https://arxiv.org/pdf/1901.02358

Providing a detailed analysis of training time and stability. This would offer valuable insights into the practical considerations of deploying HadamRNN in real-world applications.

In the Appendix, we provide a table that contains the training time of the models for each dataset.

We also provide a table for the IMDB dataset that shows, for different values of $p$ (the bit-width of $U$ and $V$) and various initial learning rates, the average performance and standard deviation across different random seeds, where the seed influences both the initial weights and the stochastic optimizer.

By addressing these points, the authors can significantly strengthen the paper and increase its impact.

We hope that these additional results will demonstrate the potential of this paper.

Summarizing: The proposal is interesting. However, the weaknesses presented in terms of state-of-the-art and comparison are not so minor. Therefore, this work needs more effort to be improved, and it is not ready for publication in this state.

Based on the above, expanding the experiments and the related work to include additional competitors from Transformer-based models would significantly strengthen the paper's relevance and situate it better within the current research landscape.

As mentioned earlier, we will expand the bibliography related to transformers.

In terms of experiments, we will include at least one additional benchmark where quantized transformers have been applied and present it in a new appendix.

On the SST-2 benchmark from GLUE, as suggested by reviewer wQJw, HadamRNN models with sizes of just a few kilobytes achieve an accuracy exceeding 80% (with a target of 82–83%). While this is lower than the performance of transformers, which achieve higher accuracy using pre-trained weights and have sizes in the tens of megabytes, it highlights the efficiency of HadamRNN in terms of model size.

We are also working on obtaining experimental results for the CoLA benchmark from GLUE. However, these results will only be included in the article if they are ready for publication.

Other minor considerations: I recommend that the authors carefully re-read the work; there are several typos and English errors.

We have carefully proofread the article, but if you have identified any specific typos or errors, we would greatly appreciate it if you could share them with us. Your feedback would be invaluable.

Furthermore, the plots in the Appendix do not specify what the X-axis and Y-axis represent.

We have labeled the axes of the plot.

My major concern with this paper is regarding the experimental section. Specifically, in lines 123 - 125, the authors claim: "Even with binarization, transformer models [...], making them unsuitable for tasks involving long-term dependencies on edge devices." I find this assertion to be overly restrictive, as recent literature provides a substantial body of work on optimizing Transformers for edge devices and handling long-term dependencies, which is not discussed here. For example, numerous studies have been conducted on lightweight binary Transformers [1, 2, 3, 4] and approaches specifically designed to handle long-term dependencies [5, 6, 7]. Consequently, the state-of-the-art section also appears narrow, as it overlooks several relevant studies and advancements in Transformer models that are critical to this discussion.

We acknowledge that lines 123–125 could be misinterpreted. We agree that these lines do not accurately reflect the current state of the art. We will include an expanded list of references to articles discussing binarized, ternarized, and quantized transformers for time series and Natural Language Processing (NLP). Additionally, we will provide a comprehensive list of references to works focused on improving transformers' ability to handle long-term dependencies.

Thank you very much for all the references.

The paper is well-organized and has a high level of clarity in its writing and the presentation of its proposal.

Each section flows logically, enhancing the reader's comprehension of the paper's purpose and methodology. Notably, sections 3 (+ the Appendix) stand out for its depth and precision, guiding the reader through the formality of the proposed approach and leaving little room for ambiguity regarding the study's methods and objectives.

The proposal is interesting. Although it is presented explicitly for RNN, the underlying principles and approaches have strong adaptability potential. The proposed sparse ternary orthogonal recurrent weights could be effectively applied across various domains (with necessary modifications for the new application domain).

Indeed, the article focuses on the use of Hadamard matrices for RNNs, but their potential applications extend beyond this scope.

As a perspective, we outline a list of potential applications that could also benefit from similar Hadamard matrices, accompanied by bibliographical references for each. These applications of orthogonal layers include long-term time series forcasting (the three references provided by the reviewer), provable robustness of neural networks[1,2], Normalizing Flows[3], Wassertein distance estimationfor instance for WGANs [4]. We add a sentence in the conclusion.

1. Cisse, Moustapha and Bojanowski, Piotr and Grave, Edouard and Dauphin, Yann and Usunier, Nicolas. Parseval networks: Improving robustness to adversarial examples. ICML'17.
2. Anil, Cem and Lucas, James and Grosse, Roger. Sorting out Lipschitz function approximation.ICML'19.
3. Kingma, Durk P and Dhariwal, Prafulla. Glow: Generative flow with invertible 1x1 convolutions.NeurIPS'18.
4. Brock, Andrew and Donahue, Jeff and Simonyan, Karen. Large Scale GAN Training for High Fidelity Natural Image Synthesis.ICLR'18.

1. Could you evaluate the performance of Block-HadamRNN and HadamRNN on edge devices? In particular, would you be able to provide the speedup and computational overhead that while using your techniques on these devices?

We addressed this critique in the previous post.

2. Could you maybe think about making Tables 2 and 3 simpler to improve the readability of your results? Better visual perception may also result from the inclusion of a plot that contrasts the accuracy of all the suggested and benchmark approaches.

As described in the previous post, we include new plots in a new appendix.

3. Could you maybe include a thorough example in the text that shows how a trained ORNN is subjected to the binarization or sparse ternarization algorithms? Could you also explain the Straight-Through Estimator's (STE) function in the parameterization process?

In practice, we do not binarize a pre-trained full-precision ORNN. Instead, as is standard in Quantization Aware Training (QAT), we directly optimize the quantized weights. The algorithm transitions from one quantized recurrent weight matrix to another, aiming to optimize the objective function. This process relies on the use of the Straight-Through Estimator.

We present the Straight-Through Estimator for optimizing the binary vector $u\in\\{-1,1\\}^{d_h}$ appearing in (3) and (4) in a new appendix, Appendix C.1.

Also, in Appendix C.2, we explicitly present the recurrent weight matrix for HadamRNN when $d_h = 4$.

We hope the new appendix clarifies this point.

The binarization and ternarization algorithms of Orthogonal Vanilla RNN are explained in sections 3.3 and 3.4 in a high-level way. Maybe providing a base example by giving the dimensions of the matrices to be binarized or ternarized would make the algorithms more transparent and easy to understand.

We appreciate the reviewer’s suggestion to provide more clarity on the parameterization using Hadamard matrices. To address this, in the revised version of the manuscript, in Appendix C.2, we explicitly present the recurrent weight matrix for HadamRNN when $d_h = 4$.

The results reported in Table 2 and Table 3 are tough to read. Maybe converting some of the results into plots would make it more straightforward for the reader to assess the paper's contributions. It is unclear where the advantage of using Hadamard Matrix Theory to parameterize the binary orthogonal recurrent weights lies.

It is common practice to present results in tables, as demonstrated by the articles cited in the bibliography below. This approach offers the advantage of providing precise numerical values, which are often difficult to extract from plots, and detailed information about the experimental setup.

We have therefore decided to retain the tables while providing additional plots in a new appendix, Appendix E.3. These plots illustrate how model size is reduced without compromising performance, with each model represented as a point on the plane. The coordinates of each point correspond to the model's size and its performance as reported in Table 2.

We also illustrate, in the same appendix, the complexity reduction achieved by Block-HadamRNN compared to HadamRNN using similar plots, where the x-axis represents complexity and the y-axis continues to represent performance.

The paper does not analyze the method proposed on any edge device. Reporting the overhead and the speedup obtained on HadamardRNN and Block-HadamardRNN would help assess the paper's contribution.

Implementing HadamRNNs and Block-HadamRNNs on edge devices would indeed be valuable. However, this requires substantial effort and different skills. In general, in the literature, the binarization procedure and the implementation are presented in separate papers, particularly for binary neural networks that require specific hardware (for instance FPGA). Many research articles focus on methods for building quantized or binary neural networks and do not implement them on edge devices [1, 2, 3, 4, 5]. The article implementing a quantized neural network on an edge device often are quite different in nature [6, 7].

As demonstrated in the Appendix, inference can be efficiently carried out using only integer operations through fixed-point arithmetic, marking a significant advancement toward practical implementation. Furthermore, Tables 2 and 3 detail the sizes of the neural networks and their computational complexities (measured in terms of additions and multiplications), providing a reliable estimate of their performance on edge devices.

We consider the implementation of HadamRNNs and Block-HadamRNNs on edge devices as a future direction of research and mention it as a perspective in Section 5.

1. Joachim Ott, Zhouhan Lin, Ying Zhang, Shih-Chii Liu, and Yoshua Bengio. Recurrent neural networks with limited numerical precision. arXiv preprint arXiv :1608.06902, 2016.

2. Lu Hou, Quanming Yao, and James Tin Yau Kwok. Loss-aware binarization of deep networks. In 5th International Conference on Learning Representations, ICLR, 2017

3. Shu-Chang Zhou, Yu-Zhi Wang, He Wen, Qin-Yao He, and Yu-Heng Zou. Balanced quantization : An effective and efficient approach to quantized neural networks. Journal of Computer Science and Technology, 32 :667–682, 2017.

4. Peiqi Wang, Xinfeng Xie, Lei Deng, Guoqi Li, Dongsheng Wang, and Yuan Xie. Hit-net : Hybrid ternary recurrent neural network. Advances in Neural Information Processing Systems, 31, 2018.

5. Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-bert : Hessian based ultra low precision quantization of bert. Proceedings of the AAAI Conference on Artificial Intelligence, 34(5) :8815–8821, 2020.

6. Tommaso Pacini, Emilio Rapuano, and Luca Fanucci. Fpg-ai : A technology-independent framework for the automation of cnn deployment on fpgas. IEEE Access, 11 :32759– 32775, 2023.

7. Jeffrey Chen, Sang-Woo Jun, Sehwan Hong, Warrick He, and Jinyeong Moon. Eciton : Very low-power recurrent neural network accelerator for real-time inference at the edge. ACM Transactions on Reconfigurable Technology and Systems, 17(1) :1–25, 2024.

Dear Authors, after reviewing your work and thoroughly considering the changes you have made, I have followed up on my last comment and increased my decision score.

Increased the score! All the best.