Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a wavelet transformation based liner attention mechanism named Waveformer. Experiments on long-range arena benchmarks have been conducted to demonstrate the effectiveness of the proposed method.
strength_and_weaknesses: Strengths:
* The authors focussed on an important issues in sequence modeling
* The paper is organized well and easy to follow
* Technical details are presented clearly

Weakness:
* The novelty needs to be further justified
* The evaluation needs to be strengthen
clarity,_quality,_novelty_and_reproducibility: Sufficient technical details and background knowledge are presented, though the authors may need to further justify the novelty of the proposed method.
summary_of_the_review: My major concern is the novelty of the proposed method. Applying spectral-based transformation (Fourier or wavelet) for efficient computation has been widely adopted in ML (also indicated in Sec. 4.2 by the authors). The claim of non-linear transformation as a major contribution seems to be incremental. I suggest the authors to better justify the novelty of the proposed approach and the motivation of applying wavelet transformation.

For experiments, I suggest the authors explicitly indicate how many repetitions each model has been trained and also report the variance of accuracy. The authors choose random feature kernel in the paper and I wonder if the authors have considered other kernels or how different kernels may affect the model performance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper "WAVEFORMER: LINEAR-TIME ATTENTION WITH FORWARD AND BACKWARD WAVELET TRANSFORM" proposes integrating analysis- and synthesis-wavelet transforms into transformers.

The main idea is to move attention computations into the wavelet domain, by framing the attention computation with a forward and backward wavelet transform. The attention module uses the randomized mapping known from the performer architecture.
The proposed network is evaluated on the Long Range Arena and the Code Understanding benchmarks.

The authors observe competitive or improved performance.
strength_and_weaknesses: ### Strengths:
- To the best of my knowledge the fast wavelet transform has not yet been studied in attention modules.
- The theory is adequately discussed.
- The reported results are competitive.

### Weaknesses:
- The novelty of the proposed approach is limited. Wavelet transforms have previously been studied in other contexts.
- For a paper which studies the introduction of wavelet transforms, it would have been interesting to study the effect of the wavelet itself.
- It seems different wavelets have not been explored.
- Similarly, the depth of the wavelet transforms has not been studied. It would have been interesting to see if and how the level choice impacts the results. 
clarity,_quality,_novelty_and_reproducibility: ## Quality and clarity:

### Methods:
- Equation (1) previously appeared in the attention is all you need paper. A citation would be in order.
- Do equations 2, 4, 5, 7 and 8 appear in standard textbooks? Adding citations helps your readers find them. 
- Figure 2: The third plot in figure 2 titled 'Wavelet Transform,' looks like it was produced by a continuous transform. Are the wavelet-transforms in the paper discrete or continuous?
- Section 2.2: The Short-Time-Fourier-Transform (STFT) is often used instead of wavelet-transforms to conserve temporal or spatial information. While the introduction to section 2.2 is true, not mentioning the STFT could be misleading.
- Fnet [Lee-Thorp et al.] uses two-dimensional Fourier-Transforms. Are the wavelet transforms used in this work two-dimensional?
- If a two-dimensional transform was used is the implementation using two 1D-transforms or a single two-dimensional transform? 
- If 1D wavelets are used, how are these augmented to be useful in 2D?

### Experiments:
- Table 1: Are the experiments reproducible? Are seed values for all experiments known?
- Table 1: How big is the effect of different seeds? Do we know the variance on the numbers in table 1?
- Table 1: Is the performer experiment identical to the waveformer experiment if the analysis and synthesis wavelet-transforms are removed?
- Table 1: Are the results for the related work in table 1 reproductions or citations? If the values are cited a citation of the original paper should appear in the model column.
- Which wavelet was used for the experiments? How many coefficients does it have? How was it chosen?
- Which decomposition level do the transforms have? How was the level chosen?
- Table 4: Are accuracy values tabulated in table 4?

### Copy editing:
- The paper requires additional copy editing. Minor flaws are mostly related to articles and include i.e:
    - After the introduction:
        - The first line could be either "the transformer" or "transformers".
    - In the contribution section:
        - i.e. we develop the waveformer, which requires ...

## Originality:
- Wavelet transforms are well-known in machine learning. The papers-related work section addresses this fact properly. In the context of attention introducing wavelets is original.

summary_of_the_review: This paper presents an interesting application of fast wavelet transforms in attention modules.
The results are competitive. The experimental part of the paper leaves many questions open.
Wavelet choice and the number of scales for example are not investigated.
Mean, and variance are unknown for all experiments. Experimentally the paper presents the bare minimum.
I am recommending a weak reject for now, but am willing to adjust my rating depending on the rebuttal.

Edit: In response to the rebuttal, I have raised my rating from five to six.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper innovates attention block by sandwiching it into wavelet forward and backward transformations. Empirical results suggest that this approach can improve upon vanilla softmax attention, as well as other approximated and more efficient attention mechanisms.
strength_and_weaknesses: The method is simple and interesting. Empirical results (especially Tab. 4) are encouraging. It encourages reader to think "
why attention in (wavelet) transformation domain can outperform the conventional one in time domain?".

However, the answer is still unknown after reading the paper. An in-depth analysis is lacking. Section 2.2 discusses the advantage of wavelet coefficients against Fourier coefficients. The authors suggests maintaining both time and frequency resolution is helpful. But that is a signal processing perspective, whose connection to representations learning is not clear. In that sense, is short-time Fourier transform also able to outperform Fourier transform? Theorem 1 is a combination of two existing theoretical results. It still cannot provide an answer to the question above.
clarity,_quality,_novelty_and_reproducibility: Overall, the paper is well written. A few clarity questions:

1. Second to last paragraph in section 2.2: "... perform discrete wavelet transform over each spatial dimension of the input ..."--- by "spatial dimension" -- you mean each of the $d$ dimensions of the input feature?

2. The wavelet transform will keep time axis while adding another frequency axis. How is that handled? 2D input becomes 3D, or simply "flatten"/"reshape" to 2D?


summary_of_the_review: Although an in-depth analysis and theoretical justification is lacking, the paper presents a simple method and promising results, which is novel and interesting.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In the paper, the author proposed a new Transformer variant with linear complexity, which is called Waveformer. In each Waveformer layer, the input will first project to the coefficient space using a forward discrete wavelet transform. Then a linearized attention operation is applied via random features. Finally, the outputs are transformed back to the "contextual" space using a backward discrete wavelet transformer step. The authors studied the expressiveness of the architecture and conducted experimental analysis of the model on standard benchmarks.
strength_and_weaknesses: Strength:

1. The architecture is new as far as I know and studying the efficiency of the model is an important direction.
2. It is useful to show the model is a universal approximator, which is the same as the original Transformer model.

Weakness:

[Novelty]
1. Where is the linear complexity coming from?

If I understand correctly, the operation that reduces the quadratic complexity in attention is to use the random feature kernel developed in Choromanski et at., 2020, but not the proposed wavelet transform. 

In the first round of reading, I got confused as in several parts of the paper, the authors emphasize that the linear-complexity model is a major contribution. I believe the authors have overclaimed that.

2. Why you use wavelet transform?

In the work, the input will first project to the coefficient space using a forward discrete wavelet transform. Then a linearized attention operation is applied. Note that even if you don;t use the wavelet transform, the model is already a linear transformer with random features. So is the wavelet transform redundant and what is the benefit?

[Universal approximation]

Once you use the random features, your model is, in fact, a "randomized" function. How did you deal with approximating a deterministic function by a "randomized function"? I didn't find any place in the proof coping with that. That being said, the proof is incomplete and lacks sufficient details. I don't think you can simply let the random feature dimension approach infinity and say, "MSE error vanishes to 0"， since we are concern about a finite-size Transformer's approximation ability

[Experiments]

The author missed important effcient Transformer S4 ("Efficiently Modeling Long Sequences with Structured State Spaces"). In all of the LRA tasks, S4 is roughly better than the proposed model for 20 points. I have little reason to vote a paper for acceptance given the significant performance gap.


clarity,_quality,_novelty_and_reproducibility: The paper writing is generally clear. I have questions regarding the novelty and the significance of the experimental results.
summary_of_the_review: I believe proposing efficient Transformer is essential but the current quality of the work (motivation, empirical results) are not ready to publish in the venue, and I recommend rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes to use two-dimensional fast wavelet transform in the attention module, and numerical comparison to numerous baseline are reported.

Strengths: This is the first attempt to use fast wavelet transform in the attention module, with improvement (sometime significant) reported for different tasks.
 
Weaknesses: The set of tasks considered in the paper is rather specific, and although in the discussion the authors say "we should not be crucified for not beating SOTA", the other side of this medal is "not reporting anything that is better than my thing", creating a false impression that they beat the result. But this is a minor issue. Another issue is that the type of the transform is not listed in the main text, but it should be important. The authors reported additional study in the rebuttal, claiming it is not important. 
The paper is not well-written: it is not easy to recover the logic of the paper (what is applied to what, for example) by reading the text.

A more delicate issue is that the final transform they report to be using is DB2 (i.e. Haar) wavelet transform, which is very simple (half-sum, half difference) of the signal.  It is very difficult to believe that this result comes exclusively from some magic property of the wavelet transform. A simple theoretical example of sequence modeling is really needed to confirm that the method has better expressivity. 


justification_for_why_not_higher_score: The paper uses a linear transformation + kernel trick + single level of the simplest wavelet transform. 
Should be the same as the kernel trick itself, but different initialization of the weights. A simple synthetic example is needed, and the writing of the paper could be improved.N
Decision: Reject