Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 
This paper formulated higher-order CNNs into a Tucker form and provides sample complexity analysis to higher-order CNNs and compressed designs of CNNs via tensor analysis. It uses then theoretically analyzes the efficiency of four block designs from ResNet, MobileNetV1, and MobileNetV2. The paper also conducts numerical experiments to verify its theoretical results and provide some empirical studies to show that increasing the expansive ratio of a bottleneck

Pros:
1.This work provides a theoretical analysis for higher-order CNNs via analyzing its Tucker formulation using tensor methods.
2.The proposed theoretical analysis can be applied to compressed designs of CNNs.
3.This work also provides numerical experiments to verify its theoretical claims.

Cons:
1.This work lacks comparisons with many important and relevant works (e.g. [1-5]), which also formulate CNNs or higher-order CNNs using various tensor decomposition forms. Many of the works also provide theoretical analysis (e.g. generalization bound in [5]) for the proposed formulations. It would be nice for the authors to show how their formulation is different from the existing ones and what is novel about the proposed formulation. Since [3] and [4] both have formulations of higher-order CNNs/CNNs using Tucker decomposition, it seems to me that the current formulation proposed in this work lacks novelty.

2.The current presentation of this work could be much more improved via a) providing more intuitions for its theoretical analysis, b) putting more connections between the theoretical analysis and empirical experiments, and c) adopting better notations (e.g. definitions of tensor operations rather than using elementwise notations) to make the theoretical analysis cleaner and clearer.

3.The finding discovered in this work via its theoretical analysis lacks sufficient experimental supports: the finding is only shown using one particular architecture design and the room for potential improvements is very limited. For example, in Table 2, the test accuracy of even the smallest model is already very close to the state-of-the-art results on these datasets, which leaves very limited room for potential improvements of test accuracies by simply increasing the expansion ratio. 

4.As mentioned above, because a) the proposed formulation of higher-order CNNs lack proper comparisons with existing works and has limited novelty and b) the finding from theoretical analysis lack sufficient experimental supports, the contribution of this paper is limited and it would be nice for the authors to provide more justifications for its novelty and better designs of experiments to convey the message.

[1] Kossaifi, Jean, et al. "Tensor contraction layers for parsimonious deep nets." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops. 2017.

[2] Kossaifi, Jean, et al. "T-net: Parametrizing fully convolutional nets with a single high-order tensor." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.

[3] Su, Jiahao, et al. "Tensorial neural networks: Generalization of neural networks and application to model compression." arXiv preprint arXiv:1805.10352 (2018).

[4] Kossaifi, Jean, et al. "Tensor regression networks." Journal of Machine Learning Research 21.123 (2020): 1-21.

[5] Li, Jingling, et al. "Understanding Generalization in Deep Learning via Tensor Methods." arXiv preprint arXiv:2001.05070 (2020).

review_title: A theoretical analysis for higher-order CNNs using tensor methods

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper provides theoretical analysis of the estimating power of CNN (3 and 5 layers). By formulating the problem using tensors, the authors showed that the estimating error of the learned CNN weights with respect to the true weights is of the order $\sqrt{d/n}$ where $d$ measures model complexity and $n$ is the training sample size. In addition, the authors considered low rank approximation to the convolution tensor through CP and Tucker decompositions, and they derived convergence result for the CNN weights in this case. The authors then applied these results to analyze different block designs through numerical experiments and ablation studies.

The writing is generally clear. The use of tensors give a very compact representation of an CNN, however tensor notations and indices can quickly become complicated in higher dimensions. The convergence results are a nice contribution to the growing literature on neural networks' theoretical analysis. In particular, the analysis of various tensor decompositions help guide the design of blocks in CNNs. 

Although the results are interesting, I feel that important aspects of CNNs were not analyzed nor discussed in this paper. Here are some of my comments and questions.
  
One of the main uses of CNNs is to perform classification where there is a softmax layer after the fully connected layer. Hence model (2) does not reflect what is done in practice and $\boldsymbol{y}$ should be a vector of probabilities. In fact I think the authors did classification on CIFAR-10 and SVHN in the numerical experiments (although it is not mentioned) using residual networks and not the model in (2). Also, why do you add sub-Gaussian errors to CNN outputs as in (2)?

In the experiments, the authors used ReLU instead of linear activation, and there is batch normalization between convolution layers. In addition, there are residual connections in the ResNet (block) architecture. All these factors that affect convergence rates were not considered in the theoretical analysis. Although I understand that these issues were omitted to simplify the proofs, I feel that there should be consistency between the theory and implementation parts. Hence Table 2 and Figure 3 do not necessarily provide empirical evidence to the theoretical results derived, as these networks have different architectures than the ones considered in Section 2. Consequently, the results hold true for a special type of CNN and it is not clear to me whether these results will still hold for CNNs used in practice (with non-linear activation, batch norm, max pooling etc.), or when the true weight tensor does not have the same tensor product structure as the learned weight tensor.

Equation (5) seems to assume that you can optimize the weights for the full connected layer and the convolution kernel perfectly. However in the numerical experiments and in practice, stochastic gradient descent with momentum is used for training and this will contribute an error term to the right hand side of Theorem 1.

In Theorem 1, can you give more explanation as to the meaning of model complexity $d_{\mathcal{M}}$? Is this the effective number of parameters? Also what are $P$ and $L$ here? In addition, is $d_{\mathcal{M}}$ always larger than $\delta$? As there is no restriction on $\delta$, it is possible that $\delta$ is much larger than $d_{\mathcal{M}}$. The same comment also applies to Theorem 2.

Some other comments:
1.  In (2), state that $1\leq i\leq n$
2.  In the paragraph after Assumption 1, what do you mean by $\lambda_{\mathrm{min}}(f_X(\theta))$ as $f_X(\theta)$ is not a matrix.
3.  On Page 5 the 2nd line after the first display, mode-$3$ multiplication between two tensors does not seem to be introduced in the notations

review_title: Interesting theoretical results on CNN but some important aspects not analyzed nor discussed

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper formulates CNNs with high-order inputs into an explicit Tucker model, and provides sample complexity analysis to CNNs as well as compressed CNNs via tensor decomposition. Experiments support their theoretical results. Sample complexity analysis of CNNs and compressed CNNs is an interesting topic. This paper is well written and is easy to follow.

Cons: 

1. Technical novelty is limited. It has been well understood that CNNs can be formulated as a tensor model, see Lebedev et al. (2015); Hayashi et al. (2019);  Kossaifi et al. (2019). By assuming a realization model, the sample complexity analysis of CNNs and compressed CNNs was transferred to the sample complexity analysis of tensor regression model and low-rank tensor regression model. The latter analysis is not new given a rich literature on this topic, see e.g., Bahadori et al. (2014); Yu and Liu (2016); Kossaifi et al. (2020). 

Lebedev, V., et al. "Speeding-up convolutional neural networks using fine-tuned CP-decomposition." 3rd International Conference on Learning Representations, ICLR 2015-Conference Track Proceedings. 2015.

Hayashi, Kohei, et al. "Exploring Unexplored Tensor Network Decompositions for Convolutional Neural Networks." Advances in Neural Information Processing Systems. 2019.

Kossaifi, Jean, et al. "T-net: Parametrizing fully convolutional nets with a single high-order tensor." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.

Bahadori, Mohammad Taha, Qi Rose Yu, and Yan Liu. "Fast multivariate spatio-temporal analysis via low rank tensor learning." Advances in neural information processing systems. 2014.

Yu, Rose, and Yan Liu. "Learning from multiway data: Simple and efficient tensor regression." International Conference on Machine Learning. 2016.

Kossaifi, Jean, et al. "Tensor regression networks." Journal of Machine Learning Research 21.123 (2020): 1-21.


2. The sample complexity analysis is for the global minimizer from a non-convex optimization, see (5).  It would be more interesting to study the sample complexity analysis for the estimator from some polynomial algorithm.  



review_title: review

Meta-review: This paper presents a theoretical analysis of CNN compression using tensor methods. None of the three reviewers have strong opinion; there scores are 5, 6, and 5.

The attempt to understand the mechanism of how tensor decomposition compresses CNNs is meaningful and interesting. However, the main contribution of this work is not sufficiently distinct compared to the existing approaches and the analysis and proof is conduected only for simplified models as mentioned by reviewers. The practical benefit of this paper is not clear and the experimental validation is weak because only a small number of model architectures were tested on a few small datasets.

This is a borderline paper. However, this paper needs to extend its contribution by performing more comprehensive analysis for general CNNs. 
Decision: Reject