Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: My understanding is that this paper extends the approach from https://www-cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf to use *patches* from an image as filters 

I enjoyed this paper quite a bit and the numbers are quite impressive (88.5 for a 2 layer network on Cifar-10 is great), and its good to understand these methods fall short on ImageNet, this may make sense for a 2 layer as the spatial pooling destroys a lot of structure. It is interesting to see these methods outperform a scattering transform. I enjoyed the rigorous ablations and study of the spectrum of patches. These are very good baseline experiments that make a valuable data point for the community. I also think that doing an ImageNet experiment at the full 224 resolution may be worth it, if that reaches 60% top-1 or above it would be a very big contribution.

Few Questions/Clarifications:

1. You seem to say that the kernel from Shankar et al is an "End to End" classifier, but from my understanding from reading that paper and looking at the corresponding code is that they just train a linear classifier on the kernel matrix which is a deterministic function, it has several layers (within in the kernel function), but the only thing thats learned is the weights that multiply the kernel matrix (the last layer), so I think in your characterization is somewhat incorrect, but please do correct me if I am wrong in my understanding of Shankar et al.


2. How many patches were used to achieve 88.5? It seems this number is missing in Table 2b.

3. Do you know what accuracy you get when you only do Flip augmentation as opposed to crops + flips, the shankar et al number you compare to only does Flips as I see. CKN seems to do no augmentation.

4. In the related work, what do you mean by "well-designed linear classifier"?

5. How does SimplePatch perform without nearest neighbors or visual quantization?




review_title: A few inaccuracies but nice to see improvement on finite dimensional kernel approximations on Cifar-10

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a powerful non-learning Kernal based baseline for ImageNet classification. The proposed non-learning Kernal based baseline (which can be interpretable to a vector quantization) shows comparable results (88.5) with AlexNet (89.1) in CIFAR-10 top-1 accuracy. The ImageNet result (39.4) shows that it is still challenging to classify the images without deep features, but about 40% is an impressive baseline without any learning method (e.g., these results is almost comparable to BagNet top-5 error).

**Pros**

This paper shows that only using a shallow kernel can often be comparable to deep models, e.g., AlexNet.

**Cons and questions**

**[Motivation to the shallow method]**
I wonder about the motivation of the proposed kernel-based non-learning method. Why we need a shallow kernel method while a deep data-driven method shows a significantly better result?

**[Runtime comparison]**
I would believe that if the authors can provide the number of learnable parameters, the number of flops, and the real latency time compared to the deep models can bring a huge practicalness to the real-world applications.

**[More analysis would be expected]**
Apart from the accuracies, I would expect more analysis on the patch-side. For example, BagNet paper [1] shows that ImageNet classifiers are actually heavily relying on the local cues, e.g., fingers for Tench classes.
- [1] W. Brendel, M. Bethge, and . . Approximating cnns with bag-of-local-features models works surprisingly well on imagenet. ICLR 2019

It will be interesting to many readers if the authors can provide additional analysis on the "important" patches for the image classification tasks. Explainability analysis, as Brendel et al. could be useful for many researchers.

**[Additional questions]**
It may not be related to the original task, but I wonder a few things about the proposed method.

- Is the proposed method robust to the adversarial perturbation? I notice that it could be difficult to attack the proposed method (because there is no gradient). It is okay to test with a black-box attack, e.g., generate an attacked image with well-known architectures, e.g., ResNet, and test the attacked accuracy.
- Similarly, I wonder the proposed method is beneficial to the out-of-distributed (OOD) robustness, and other distribution shifts
  - Hendrycks, Dan, and Kevin Gimpel. "A baseline for detecting misclassified and out-of-distribution examples in neural networks." ICLR 2017.
  - Hendrycks, Dan, and Thomas Dietterich. "Benchmarking neural network robustness to common corruptions and perturbations.", ICLR 2019.
  - Hendrycks, Dan, et al. "Natural adversarial examples." arXiv preprint arXiv:1907.07174 (2019).


Please consider to add "explainability analysis", "adversarial robustness", "distribution shift robustness" and "OOD robustness" to show the effectiveness of the paper.

---

Post-rebuttal review

In my initial review, my main concern was the motivation for the patch-based classification is unclear, and I asked some questions related to the further potential usage of the proposed method, particularly focusing on robustness.

During the rebuttal process, the authors address most of my concerns well in their responses.

- Main motivation: this work more focuses on the mathematical analysis of the image classification tasks, rather than performances (accuracy, runtime, ...). It makes sense to me, and I think this motivation needs to be encouraged to explore by many researchers.
- Runtime or learnable parameters: tracking the runtime comparing to deep methods is non-trivial as the author clarified. However, the authors showed that the number of learnable parameters is much less than deep models (580k for the proposed method, a few M for AlexNet). I think this comparison fairly shows that the proposed method is efficient than deep models in terms of the number of parameters.
- Other analysis that can support the motivation of this paper: I'd expect to see more robustness analyses such as the black box adversarial attack results, but I agree that this is out-of-scope of this work. To me, the responses to the additional comments are not helpful, but I understand that my questions can be out-of-scope of this work.

Hence, I'd like to change my score from 5 to 6.
review_title: Interesting results, but still have questions for motivation

final_score: rating: 6: Marginally above acceptance threshold
review_content: Briefing:

This paper mainly investigates the patch-based pre-processing for image classification. The patch-based pre-processing is done by a simple convolutional kernel constructed in a data-driven manner. 
The paper achieved better or comparable performance to other more heavy comparisons using a much smaller kernel size.

Strongpoints:

The paper shows that the simple whitening procedure (by mean and covariance from training-set) of first layer weights enhances the performance, rather than using a deep kernel, which can be much efficient.


Weak points:

Analysis of the improvement: The reviewer tried to find an explainable reason for the performance improvement, although the title includes 'unreasonable'. Figure 3 seems to analyze the dictionary by covariance spectrum and intrinsic dimension, but it wasn't easy to catch the main idea. A more precise explanation of the experiments and the analysis is required.

Comments:

(1) Table 1.a shows that the proposed method achieved good performance despite the hard-assignment. What if we apply soft-thresholding to the proposed method?

(2) Experiments or discussion for the ImageNet performance with a lower number of the dictionary would be meaningful.

(3) Ablation study (data-driven or not) in ImageNet performance would strengthen the contribution of the paper (in Table 2.a?)

(4) It might be out of scope, but the reviewer could not fully catch the dictionary encoding usage just for the classification task. Is this possible to apply it to other task s.a. retrieval or other feature matching task? Then, discussion or experiments of the tasks would be required.
Or, if not, the importance of the dictionary construction on the classification task would be required.

(5) The proposed method only uses one or two layers of depth, one of the main contributions. Then, what if we use slightly more layers s.a. 3, 4, or 5? This addition of layers does not require much burden, and it would be better to add the layers if it can enhance performance.

(6) It wasn't easy to catch how the paper constructs the kernel Phi, from the method. A clearer explanation of the procedure would be appreciated.

(7) Qualitative analysis of each element of the dictionary would help readers catch the paper's contribution.

Note: The reviewer does seem to catch the main strong-points and suggestions of the paper thoroughly. The reviewer requires a clearer explanation of the contribution with the replies for the above comment, and it would be required for the precise rating.


review_title: Reviewer 2 comments

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary

The authors propose using a data-driven dictionary of patches on CIFAR-10 and Imagenet, with a shallow classifier (linear / one hidden layer CNN) obtaining results comparable to end to end deeper architectures.
The proposed method consists in random sampling a dictionary of patches (2 * 10^3 for ImageNet) and using it to encode a binary representation (feature map), with Q nearest patches in the dictionary.

#####################

Rating motivation

The idea of using small patches for ImageNet and CIFAR classification is interesting - the effectiveness of small (3x3, 5x5) patches having been shown for textures in earlier work of Varma & Zisserman (A Statistical Approach to Material Classification Using Image Patch Exemplars, TPAMI 2009). 
Another strong point of the paper is that it achieves an impressive accuracy (88.5) on CIFAR-10, almost on par with end-to-end AlexNet and other patch based methods, using only a small fraction of the patches obtained from ImageNet.
The clarity and readability of the paper could be improved, especially to the benefit of readers less familiar with the topic.

######################

Strong aspects of the paper:

- patch-based representation; data-driven kernels (although, it seems just random sampling)
- shallow model, with good performance;
- operates at lower resolution (64) on ImageNet, and obtains comparable performance to existing methods (trained end-to-end, and deeper).

#######################

Weaker points / questions:
- please add one introduction paragraph in Section 3, describing the method. Just introducing the notation is a bit abrupt, and makes the section difficult to read. Please try to clarify from the beginning what the one layer CNN is trained on (seems d * j binary image).

-please emphasize more the differences with Coates&Ng 2011, and compare on similar parameters (Tab 1a -- does the proposed method perform better because of using 10x , resp. 600x more patches in the dictionary, hence higher feature dimension?)

- evaluation only on CIFAR-10 and ImageNet -- could improve this by comparing with the scatter transform of Sifre & Mallat, on a common benchmark, e.g. texture / material dataset). It might be interesting, in addition to CIFAR-10 to test the method on Materials in Context (MINC) dataset, or Describable Textures Dataset (~6.5K images).

- How is the dictionary augmented? There is a mention of contrast invariance, and union over {d, -d} -- is the dictionary size |D| after augmentation? 
- Please explain / clarify equation 3 - why is it necessary and what is a benefit of viewing the distance between two images as a Hamming distance? Are there computational advantages?
- Please clarify the notation in eqn. (4) - why is the step in Eq 4 necessary, and why not using a max-pooling layer in the one layer CNN? 

- Please expand the explanation of the difference between data-driven (D-D) vs Non-Data-Driven (Tab 1.c); Are the patches the same for all the methods? It would also help to have the total numbers for the data-driven column (and improvement number in brackets, e.g. 78.8 ( +13.2 ).
- How would the method perform with larger patch sizes? (e.g. P=9, to have a closer comparison with BagNet).
- In Sec. 4, please add a brief explanation of spectrum definition and intrinsic dimension.

######################

Minor (typos, editing …)
- in Sec. 3(Method), first paragraph, "squared domain of surface Q^2" --> should be P^2; and patch size should be P;
- Please use 500K, 1.2M instead of 5*10^5, 1.2 * 10^6 for the number of images in CIFAR-10 and ImageNet respectively.
- Incomplete list of authors for Convolutional Kernel Methods.


review_title: Patch based convolutional kernels - comparable results to e2e methods.

Meta-review: This paper studies the patch-based convolutional kernels for image classification, and finds that making the kernel dependent on data is necessary for designing competitive kernels for image classification. The proposed simple method shows comparable results to those end-to-end deeper architectures on CIFAR-10 and ImageNet datasets. 

All reviewers feel that the paper is interesting, important, and the performance is impressive. During the rebuttal, the authors have addressed most of the questions and concerns raised by the reviewers. In particular, authors have clarified the motivation, discussed the model size of the proposed method (requested by R1), added precise details about the spectrum definition and intrinsic dimension (requested by R4), and taken the suggestions from all reviewers to improve their paper. 

After rebuttal, all reviewers agree on accepting the paper. After checking the discussions between the authors and reviewers, I am convinced that the original concerns of the reviewers are addressed. Hence, I recommend that this paper be accepted.

Decision: Accept (Poster)