Rethinking Convolution: Towards an Optimal Efficiency
Authors: Tao Wei
Yonghong Tian
Chang Wen Chen
Venue:  (2021)

Abstract: In this paper, we present our recent research about the computational efficiency in convolution. Convolution operation is the most critical component in recent surge of deep learning research. Conventional 2D convolution takes $O(C^{2}K^{2}HW)$ to calculate, where $C$ is the channel size, $K$ is the kernel size, while $H$ and $W$ are the output height and width. Such computation has become really costly considering that these parameters increased over the past few years to meet the needs of demanding applications. Among various implementation of the convolution, separable convolution has been proven to be more efficient in reducing the computational demand. For example, depth separable convolution reduces the complexity to $O(CHW\cdot(C+K^{2}))$ while spatial separable convolution reduces the complexity to $O(C^{2}KHW)$. However, these are considered an ad hoc design which cannot ensure that they can in general achieve optimal separation. In this research, we propose a novel operator called \emph{optimal separable convolution} which can be calculated at $O(C^{\frac{3}{2}}KHW)$ by optimal design for the internal number of groups and kernel sizes for general separable convolutions. When there is no restriction in the number of separated convolutions, an even lower complexity at $O(CHW\cdot\log(CK^{2}))$ can be achieved. Experimental results demonstrate that the proposed optimal separable convolution is able to achieve an improved accuracy-FLOPs and accuracy-#Params trade-offs over both conventional and depth/spatial separable convolutions.

Under review as a conference paper at ICLR 2021
RETHINKING CONVOLUTION: TOWARDS AN OPTIMAL EFFICIENCY
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, present recent research about the computational efficiency in convolution. Convolution operation is the most critical component in recent surge of deep learning research. Conventional 2D convolution takes O(CKK²HW calculate, where C' is the channel size, K is the kernel size, while H and W are the output height and width. Such computation has become really costly consid- ering that these parameters increased over the past few years to meet the needs of demanding applications. Among various implementations of the convolution, separable convolution has been proven to be more efficient in reducing the com- putational demand. For example, depth separable convolution reduces the com- plexity to O(CHW (C + K²)) while spatial separable convolution reduces the complexity to O K HW). However, these are considered an ad hoc design which cannot ensure that they can in general achieve optimal separation. In this research, we propose a novel operator called optimal separable convolution which can be calculated at OCC K KHW by optimal design for the internal number of groups and kernel sizes for general separable convolutions. When there is no restriction in the number of separated convolutions, O(CHW-log( Iog(C can achieved. Experimental results demonstrate that the proposed optimal separable convolution is able to achieve an improved accuracy- FL.OPs and accuracy- trade-offs over both conventional and depth/spatial separable convolutions.
even lower complexity at
INTRODUCTION
Tremendous progresses have been made in recent years towards more accurate image analysis tasks, such as image classification, with deep convolutional neural networks (DCNNs) (rrizhessyy et al.
2012 Srivastava et al. 2015 He et al., 2016) Real et al. 2019: Tan & Le 2019 Dai et al. 2020). However, the computational complexity for -fate-of-the-arr DCNN models has also become in- creasingly high and computationally expensive. This real-world applications, such as mobile platforms and robotics, where the resources are highly con- strained (Howard et al. 2017 DDai al. 2020). It is very much desired that DCNN could achieve better performance with less computation and fewer model parameters.
significantly defer their deployment to
The most time-consuming building block of a DCNN is the convolutional layer. There have been many previous works aiming at reducing the amount of computation in the convolutional layer. Historically, researchers apply Fast Fourier Transform (FFT) (Nussbaumer 1981 Quarteroni al., 2010) to implement convolution and they gain great speed up for large convolutional kernels. For small convolutional kernels, direct application is often still cheaper (Podlozhnyuk) 2007). Re- searchers also explore low rank approximation (Jaderberg et al. 2014]] Toannou et al.) (015)) to implement convolutions. However, most of the existing methods start from pre-trained model and mainly focus network pruning and compression.
In this research, we study how to design a separable convolution to achieve an optimal implemen- tation in terms of computational complexity. Enabling convolution separable has been proven to be an efficient way to reduce the computational complexity (Sifre & Mallat 2014 Howard et al, 2017 Szegedy al. 2016). Comparing to the FFT and low rank approximation approaches, well- designed separable convolution shall be efficient for both small and large kernel sizes and shall not require pre-trained model to operate on.

---

Under review as a conference paper at ICLR 2021
Table 1: comparison of computational complexity and the number parameters the proposed optimal separable convolution and existing approaches. The proposed optimal separable convolution is much more efficient. In this table, C' represents the channel size of convolution. K is the kernel size, H and W are the output height and width. is the number of groups. "Vol. RF" represents whether the corresponding convolution satisfics the proposed volumetric receptive field condition.
Conventiinal
Grouped
Depch
Point- wise
Depth Sepurable
Spotial Separable
Optiall Sepurable
Opiimal Separable
Com-2D
Conv2D
Comr2D
Com2D
Com-2D
CD
Conv2D (Optimized N)
FLOPPs
6 HWW
HW//
CK2 NW
C HW
CHW(C + k²)
2C2 X KOW
20: 1 K NW
cC log(Ck²) eC (C
#Parnass
C² x²
C² k2
CK²
C²
CiC K2)
2C² K
20 K
Vol. RF
/
x
x
x
Note
g
Depth-wise Point-ufse
K²
2.71828...
Crannel S5
3x3
3x3
1x1
3x3
1x1
Volumetric RF
Receptive Ricld (RF)
O K²)
O + K*))
o(C 2 K)
Conv2D
Depth Separable
Optimal Separable
(b)
Figure I: Volumetric receptive field and the proposed optimal separable convolution. (a) The volumetric recep- tive field (RF) of convolution is the Cartesian product of its (spatial) RF and channel RF. (b) Illustrations of the channel connections for conventional, depth separable, and the proposed optimal separable convolutions.
In the DCNN research, two most well-known separable convolutions are depth separable (Sifre & Mallai, 2014) and spatial separable (Szegedy et al., 2016) convolutions. Both are able to reduce the computational complexity of convolution. The complexity of a conventional 2D convolution is quadratic with three byper-parameters: number of channels (C", kernel size (K), and spatial di- mensions (H or W ), and its computational complexity is actually O(C² KW)) Depth separable convolution is constructed as a depth-wise convolution followed by a point-wise convolution, where depth-wise convolution is a group convolution with its number of groups g = C and point-wise convolution a x convolution. Spatial separable convolution replaces K x K kernel K x and 1 x K kernels. Different types of convolutions and their computational costs are summarized in Table I. From this table, we can easily verify that depth separable convolution has complexity of O(CHW - (C' + (2)) and spatial separable convolution has a complexity of O(C² KHW)
Both depth separable and spatial separable convolutions follow an ad hoc design. They are able to reduce the computational cost to some degree but normally will not achieve an optimal separation. separable convolution in general has three sets of parameters: the internal number of groups, channel size, and kernel size of each separated convolution. Instead of setting these parameters in an ad hoc fashion, we design scheme to achieve an optimal separation. The resulting separable convolution is called optimal separable convolution in this research.
To prevent the proposed optimal separable convolution from being degenerated, we assume that the internal channel size is in an order of O(C) and propose the following volumetric receptive field condition. As illustrated in Fig. La similar to the receptive field (RF) of a convolution which is defined the region in the input space that particular CNN's feature is looking at (or affected by) (Lindeberg, 2013), ) we define the volumetric RF of a convolution to be the volume in the input space that affects CNN's output. The volumetric RF condition requires that a properly decomposed separable convolution maintains the same volumetric RF as the original convolution before decom- position. Hence, the proposed optimal separable convolution will be equivalent to optimizing the internal number of groups and kernel sizes to achieve the computational objective (measured in FLOP while satisfying the volumetric RF condition. Formally, the objective function is defined by Equation ( under the constraints defined by Equations (3)-6)) The solution to this optimization problem will be described in detail in Section
66.
In this research, similar
(He al. 2016 FLOPs measured in number of multiply-adds.
2

---

Under review as a conference paper at ICLR 2021
We shall show that the proposed optimal separable convolution can be calculated at the order of O(C KHW). This is at least factor of vC more efficient than the depth separable and spatial separable convolutions. The proposed optimal separable convolution is able to be easily generalized into an --separable case, where the number of separated convolutions N can be optimized further. In such a generalized case, an even lower complexity at O(CHW Iog(CK²)) can be achieved.
Extensive experiments are carried out to demonstrate the effectiveness of the proposed optimal sep- arable convolution. As illustrated in Fig. B on the CIFARIO 10 dataset (Krizhevsky et al. 2009). the proposed optimal separable convolution achieves a better Pareto-frontier than both conventional and depth separable convolutions using the ResNet (He et al.] 2016) architecture. To demonstrate that the proposed optimal separable convolution generalizes well to other DCNN architectures, we adopt the DARTS (Liu et al., 2018) architecture by replacing the depth separable convolution with the proposed optimal separable convolution. The accuracy is improved from 97. 97.24% to 97.67% with fewer parameters. On the ImageNet dataset (Deng et al. 2009), the proposed optimal separa- ble convolution also achieves an improved performance. For the DARTS architecture, the proposed approach achieves 74.2% topl accuracy with only 4.5 million parameters.
2
THE PROPOSED APPROACH
2.1
CONVOLUTION AND ITS COMPUTATIONAL COMPLEXITY
A convolutional layer takes an input tensor B of shape (GL-1;1111 Wi-1) and produces an output tensor B, of shape (Ct, Hi, WT), where C., H., W. are input and output channels, feature heights and widths. The convolutional layer is parameterized with a convolutional kernel of shape (Ci, Ci-1, K," KH), where Ký are the kernel sizes, and the superscript indicates whether it is aligned with the features in height or width. In this research, we take C. = O(C), H. = O(H),
W. O(W), and K WW OK) for complexity analysis. Formally, we have
Bica,, wi) = ΣEΣ Σ
Bi-1(0-11, 110-,,,--1,,,-100 ai,, M
(1)
9-1 RM" RM
where hy = - + k/" and Wi = W1-1 + W. Hence, the number of FLOPs (multiply-adds) for convolution is C2H,Wi C2-1 KW = O(C*K²HW) and the number of parameters is CCC,,K KW = O3)
For group convolution, we have g convolutions with kernels of shape (Ci/g, C1-1/9, K," K KK") ) Hence, it has H2H/g)) FL.OPs and O(C2k2/g) parameters, where g is the number of groups. A lepth-wise convolution equivalent to group convolution with g = C. = C. A point- wise convolution is 1 Xx] 1 convolution. A depth separable convolution is composed of a depth-wise convolution and a point-wise convolution. A spatial separable convolution replaces a K x K kernel with K x1 1 and 1 x K kernels. Different types of convolutions summarized in Table From this table, their FLOPs and number of parameters can be easily verified.
2.2 RETHINKING CONVOLUTIOO AND THE VOLUMETRIC RECEPTIVE FIELD CONDITION
Separable convolution has been proven to be efficient in reducing the computational demand in convolution. However, existing approaches including both depth separable and spatial separable convolutions follow an ad hoc design. They are able to reduce the computational cost to some extent but will not normally achieve an optimal separation. In this research, we shall design an efficient convolution operator achieving the computational objective by optimal design of its internal hyper- parameters. The resulting operator is called optimal separable convolution.
One difficulty is that if we do not pose any restriction to a separable convolution, optimizing the FLOPs target will resulting in a separable convolution being equivalent to a degenerated channel scaling operato Hence, we propose the following volumetric receptive field condition.
In oulti-objeccive optimization, a Pareto-optimal An allocation is Pareto-ope aaremal if there is no alternative allocation where improvement can be made participant's well-being without sacrificing any other's. Here, Pareto-frontee represents the curve of the accuracies we able achieve for different FI. Fl.oPs/
is the set of parameterizations (allocations) that are all
From Table [ let C' and K- = 1. a convolution will have C' parameters and CHWW FLOPs. This is in fact channel scaling operator. Composition of such operators is not meaningful because the composition itself is equivalent single channel scaling operator.
3

---

Under review as a conference paper at ICLR 2021
As illustrated in Fig. la the receptive field (RF) of convolution is defined to be the region in the input space that a particular CNN's feature is affected by (Lindeberg 2013). We define the channel RF to be the channels that affect CNN's output and define the volumetric RF to be the Cartesian product of the RF and channel RF of this convolution. The volumetric RF of a convolution is actually the volume in the input space that affects CNN's output. The volumetric RF condition requires that a properly decomposed separable convolution maintains (at least) the same volumetric RF as the original convolution before decomposition. Hence, the proposed optimal separable convolution will be equivalent to optimizing its internal parameters while satisfying the volumetric RF condition.
2.3 OPTIMAL SEPARABLE CONVOLUTION
In this section, we discuss the case of two-separable convolution. We present the discussion infor- mally to gain intuition into the proposed approach. In the next section, we shall provide a formal proof. Suppose that the shape of the original convolutional kernel is (Cous, Cin. K k.W ), where Cins Cout are the input and output channels, and (K#, KW) is the kernel size. Let C₁ = Cin. and C3 Cout- For the proposed optimal separable convolution, we optimize the FL.OPs as computa- tional objective while maintaining the original convolution's 's volumetric RF. Formally, the computa- tional demand of the proposed separable convolution is
f91..92 92, C2, K. K C2 KW HW
+ C2C2KH KW HW
91 In order to satisfy the volumetric RF condition, the following three conditions need to be satisfied KF K2" 1 K
92
(Receptive Field Condition)
(3)
KW + K2" -1= -l=Kw
(4)
91 9 S C2
(Channel Condition)
(5)
min(Ci, C++1) 2 gi
(Group Convolution Condition)
(6)
We have three sets of parameters: the number of groups 91- 92. the internal channel size C2. and the internal kernel sizes K. Wi In this research, we shall assume that the internal channel size C2 is in an order of OCC) and is preset according to a given policy. Otherwise, = 92 C2 = will be trivial solution. This could lead the separable convolution to be over-simplified and not applicable in practice. Typical policies of presetting C2 include C2- = min(C], (3) (normal architecture), Co (G1 + C3)/2 (linear architecture), C2 max C3) (bottleneck architecture (He al. 2016), or C2 = 4 min(C', C3) (inverted residual architecture (Sandler et al. 2018)). ).
The proposed problem is a constrained optimization. is usually hard to solve it directly. However, we shall show that the optimal solution shall be 01.92 ~ VC. For large channel sizes, the optimal solution is usually an interior point in the solution space rather than on the boundary.
FLOPS
2000
Let K be constants, by substituting 92- C2/91 and setting f(1) = O, one can derive that
3003
2300
CICcK KW CoKf KT VC,
2g Soll 2, 70
91 =
(7)
12 10
nuster
and
32.0
min f()) 2 C.C.C.KKHHH KY KNKY HW (8) 91
Figure 2: Given channels C1 C2 = C3
64, and kemel sizes K" KW
5
in Equation 2 by setting f'(g1) 0. f'(K)) = 0. The solution 9i = 8, Ki = is saddle point.
=O(C KHW)
if we set K#E WW and K2 HW 1.
One interesting fact is that we can optimize the internal number of groups 91, 92 and internal kernel sizes K H|W simultaneously. For simplicity, we assume that kernel sizes aligned in height and
C2 2 C. means the product C. C2 needs to occupy each node in the input channel C₁ Cin to maintain the volumetric receptive field. This further explained for the channel condition general case (13) in Section 2.4
4 'The channel condition 5 gi 92 S C2 +>
'It is trivial to verify that, for any solution (01, 92) with ø1 92 < C2. (01, S2 C2/91 > 92) shall be another feasible solution with smaller FL.PPs target. Hence, the optimal solution must satisfy g1 92 = C2-
4

---

Under review as a conference paper at ICLR 2021
width are equal. By setting ((() 0 and ((()) 0. can derive that 91 is the same as
Equation (7) and K1 K2
R+1 substituting them into Equation (8) one can get f((1, K1)
2
O HW). This results in a higher complexity than OC HHW). In fact, the solution to (9 0 and ('() 0 is saddle point. As illustrated in Fig. 2 given the input channel C1
64 and output channel C3 = 64, kernel size (K" KK) = (5, 5). we take C2 = min Main C3) = 64.
By setting (1)) = 0, ( = 0, the solution f1 = /64 = 8, K = 5+1
2 = =3 is a saddle point.
2.4 OPTIMAL SEPARABLE CONVOLUTION (GENERAL CASE)
In this section, we shall generalize the proposed optimal separable convolution from N = 2 to an optimal N and shall provide formal proof. Suppose that the shape of the original convolutional kernel is (Cout, Cin, K" KW). Let C₁ Cin. and CN+1 Cot (Cn+1 = C3 for N = 2). The computational demand of an N -sseparable convolution is
f(o-) {K. (K, }) C2 HW
KN HW
91
9N
For ease of analysis, we first introduce the notation channels per group n4 gi
G.
which simply
means: channels per group x number of groups the number of channels. Then, we have
f((n)), [K. }) C2n1 K, KI" HW +CN+INNKN K HW
(10)
satisfying the volumetric RF condition
KB + K2 + ... K" (N - 1)
(Receptive Field Condition)
(11)
kW KWW +... KW + +NN- -1)
(12)
n1 ... nN 20 + .N S C2....C Cn
(Channel Condition)
(13)
Ci+1 + 9: S min(Ci, Ci-1) 9
n 2 max(1,
(Group Convolution Condition)
(14)
We keep both notations Ii and nu This is because, for the channel condition, it is intuitive that M1 ....777 2 C₁ means that the product of nn.... needs occupy each node in the input channel C1 = C.n This is equivalent to the less intuitive condition 91 9N I C22 CC..... Cy- Similarly, for the group convolution condition, gi S min(C,, C(+1) means the number of groups can not exceed the input and output channels of this group convolution, while nı 2 max(1, CL+1 is less intuitive.
C,
For Equation
I0 apply an arithmetic arithmetic-eoometric mean incquality, we can get
I((n.), ((m.),(K!"" ( 20)2 C.C3 CRCN+IKI K KW KW
HW
(15)
91 91...N IN
2 C. ... CN+ KW KW KW HW
(16)
The equality holds if and only if Can KH KW"
-O-NINNN KH KW Let ny Bm, where
St C2K, KW Let 3 = 113 we can solve 11 = C. VUC.KK KF
and
CIINI KIIN KW
71
CLIK K.
Nc.
(17)
Note that the inequality (66) holds for arbitrary K. #WW We need to further optimize K. H|W From
the arithmetic -geomtrrceeeemetrie mean inequality again, we can get KH KN < K +K yN =
""+ -N-+ ) and the equality holds if and only if K = ... KW -"+ However, we want the inequality reversed, instead of finding the maximum of this product, we expect to find
.V
N
its minimum. This still gives us a hint, the maximum is achieved when the internal kernel sizes are the minimum should be achieved when the internal kernel sizes are as diverse as possible. In the extreme case, one of the internal kernel sizes should take K H and all the rest takes
as even as possible,
1. A formal proof of this claim can be derived. Hence, we have
f((n.), (K#!))) )) 2 N Ca Cn+1 KH KW HW O(NCI+ & K HW). (18)
5

---

Under review as a conference paper at ICLR 2021
94-
110
100 m2.3
130 m22t
66
93-
add
(32,m275
/10
92-
92-
Tops (16)
91-
dRestett
152
89-
d'Bastle (w multiplee)
89-
(20
d.Rasheet (w/ multipler)
o-Restet
ResNet
63-10)
o-ResNes Dw muttiplerr
OW multlienn
0.00
0.05
0.10
0.15
0.20
0.25
0.00
0.25
0.50
0.75
1.50
1.5
1.50
1.75
FLOPs (billion)
Paramms (million)
(a)
(b)
Figure 3: Experimental results on CIFARIO for the ResNet architecture (best viewed in color). The proposed optimal separable convolution (o-ResNet) achieves improved (a) accuracy-FLOPs and (b) accuracy- Paarmms Pareto-frontiers than both the conventional (ResNet) and depth separable (d-ResNet) convolutions.
Table 2: Experimental results on CIFARIO for DARTS, The proposed optimal scparable convolution (o- DARTS) generalizes well to the DARTS architecture, and achieves improved accuracy with approximately the FLOPs and fewer parameters. DARTS uses depth separable convolution and optional d- is prefixed.
FLOPs
#Params
Accuracy
Error Rate
Net Arch
(billion)
(million)
(%)
(%)
(d-)DARTS (Liu et al.
2018)
0.528
3.35
97.24%
2.76%
o-DARTS
0.572
3.25
97.67%
2.33%
P-DARTS (Chen al. 2019
0.532
3.43
97.50%
2.50%
PC-DARTS Xu et al. 2019)
0.557
3.63
97.43%
2.57%
GOLD-DARTS Bi ct al.
2020
0.546
3.67
97.47%
2.53%
be verified that, for N Equation 8 and Equation (18 match with the same complexity. By setting ('(N) = O, we can derive that N log(CK²)), and
min S( [[n=), (K!lW) })
eCHW log(Ck²) O(CHW log(Ck)))
(19)
where e 2.71828.. is the natural logarithm constant.
The proposed optimal separable convolution can have spatial separable configuration: single kernel takes (K H KW) or two kernels take (K 1) and (1, K.). Besides, the proposed optimal separable convolution allows using a mask of the internal number of groups and solve for an M- separable sub-problem (M < N). Details are discussed in Appendix A where the implementation of the proposed optimal separable convolution is also presented in Algorithm
EXPERIMENTAL RESULTS
In this section, we carry out extensive experiments on benchmark datasets to demonstrate the effec- tiveness of the proposed optimal separable convolution scheme. In the proposed experiments, use a prefix d- or o- to indicate that the conventional or depth separable convolutions in the baseline networks are replaced with depth separable (dsep) the proposed optimal separable (osep) convo- lutions. In this research, we set the number of separated convolutions N = 2. The details of the training settings for the proposed experiments are described in Appendix B
3.1 EXPERIMENTAL RESULTS ON CIFAR10
CIFARIO Krizhevsky et al. 2009) is a dataset consist of 50,000 training images and 10,000 testing images. These images are with a resolution of 32 x 32 and are categorized into 10 object classes. In the proposed experiments,
ResNet (He al. 2016) baselines and replace the conventional convolutions in ResNet with dsep and osep convolutions resulting in d-ResNet and o-ResNet.
The proposed osep scheme can significantly reduce FLOP//PPrams.. In Section 2 we proved that this reduction factor be VCK in theory the orange solid curve lies in region with significantly smaller v-values than the blue solid curve.
[ As illustrated by the solid lines in Fig. 3 (a) and (b),
For optimal separable, VCK-
C² Hw For depth separable, 1/K GH/"KWW
C CHWIC+K*)
K?

---

Under review as a conference paper at ICLR 2021
This indicates that o- o-ResNet shall have significantly smaller FLOPs and fewer parameters than the ResNet baseline. For example, o-ResNet/10 has even lower FLOPs (0.033 billion vs 0.041 billion) and fewer parameters (0.177 million vs 0.270 million) than ResNet20. yet with noticeable higher accuracy (92.125 12% vs 91. 91.25%) This demonstrates that the proposed osep scheme could significantly reduce both computational cost and number of parameters for conventional convolutions. For dsep, this reduction factor is 1/K*+1/0 which is bounded by K². For 3 x 3 kernels, this reduction can be at most 9. Whereas for the proposed osep scheme, no such bounds exist. The advantage of the proposed osep scheme over dsep is illustrated in Fig. 3 (a) and (b) by the orange and green solid curves. From which, we
the proposed osep scheme is more efficien(" with smaller z-values.
The proposed o-ResNets can have 8x-16x smaller FLOPs and 10x-18x fewer parameters than the ResNet baselines in the proposed experiments. For fair comparisons, we introduce the channel mul- tiplier in order to approximately match the FLOPs. We use the suffix " "-m-mmutippierrs" to in- dicate the channel multiplier. Note that FLOPs/#Params/ is proportional to charnel. wwllipllllrie for osep. As illustrated in Fig. 3 from which we can see, the proposed optimal separable convo- lution scheme is much more efficient than conventional convolutions. The orange curve, including both solid and dashed parts, achieved better accuracy-FLOP; Pareto-frontier than the blue curve. is worth noting that even under the same FLOPs, the number of o-ResNet parameters is also smaller than that of ResNet by large margin. This could result in more regularized network with fewer parameters to prevent over-fitting and possibly contribute to the final performance. In Fig. 3. we also present the d-ResNNet curves in dashed green by replacing the conventional convolutions with depth separable convolutions. As can be seen, d-ResNet achieves good accuracy-FLOPs bal- ances for small networks (e.g. d-ResNet20 and d' (-ResNet32), but performs comparable or no better than conventional convolutions for large ones (e.g. d-ResNet56 and d-ResNett 10). In summary, the proposed optimal separable convolution achieves better securacy-FL.OP and accuracy-ffPrram Pareto-frone frontiers than both conventional and depth separable convolutions.
To demonstrate that the proposed osep scheme generalizes well to other DCNN architectures, we adopt the DARTS (V2) (Liu et al. 2018) network as the baseline. The DARTS evaluation network has 20 cells and 36 initial channels, we increase the initial channels to 42 to match the FLOPs. By replacing the dsep convolutions in DARTS with the proposed osep convolutions,
illustrated in Table the resulting o-DARTS improved the accuracy from 97. 97.24% to 97.67% with fewer parame- ters (3.25 million vs 3.35 million). It is worth noting that it is very hard to significantly improve the DARTS search space. In Table _ we also include three variants of DARTS, i.e. P-DARTS (Chen) et al. 2019, PC-DARTS (Xu et al., 2019), and GOLD-DARTS (Bi al. 2020), with more advanced search strategies for comparison. As can be seen, o-DARTS even achieved higher accuracies than these advanced network architectures.
Ablation Studies We carry out ablation studies on the effects of the internal BatchNorms and non- linearities, and the spatial separable configuration. We conclude that internal BatchNorms and non- linearities have no effects on the results yet introduce extra computation and parameters, while the spatial separable configuration leads to slightly worse performance. Hence, they are not adopted in this research. Details are presented in Table with discussion in Appendix C
3.2
EXPERIMENTAL RESULTS ON IMAGENET
We evaluate the proposed optimal separable convolution scheme on the benchmark ImageNet (Deng
ct al. 2009) dataset, which contains 1.28 million training images and 50,000 testing images.
3.2.
IMAGENET40
Because carrying out experiments directly on the ImageNet dataset can be resource- and time- consuming, we resized all the images into 40 x 40 pixels. A 32 x 32 patch is randomly cropped and random horizontal flip with a probability of 0.5 is applied before feeding into the network. No extra data augmentation strategies are used. The baseline ResNet architecture is modified version of that used on the CIFARIO dataset, except that the channel sizes are set to be 4x larger, the features are
Because there is an overhead and the channels are relatively small (e.g. 16) for CIFAR10 models, the ad- vantage margin is noticeable hut is not remarkable. This margin of advantage can be higger for larger channels. 'We usually omit this channel multiplier suffix for simplicity when it is clear from the context that we are comparing different schemes under the same FT.OP//PParmms and there are no confusions.
7

---

Under review as a conference paper at ICLR 2021
Table 3: Experimental results on ImageNet40 for the ResNet architecture. The proposed optimal separable convolution (o-ResNet) achieves 4-5% performance gain over ResNet baseline.
Channel Multiplier
FLOPs (billion)
#Params (million)
Accuracy (%)
Error Rate
Net Arch
(%)
ResNer20
0.162
4.58
40.28
59.72
o-ResNet20
5.375
0.160
5.13
44.94
55.06
ResNer32
0.275
7.68
42.98
57.02
o-ResNet32
5.75
0.278
7.78
47.88
52.12
ResNet56
0.502
13.88
44.93
55.07
o-ResNer56
6.0
0.497
12.55
49.97
50.03
ResNet110
1.012
27.83
46.74
53.26
o-ResNet1 10
6.25
1.027
23.79
50.72
49.28
Table 4: Experimental results on full ImageNet for the DARTS architecture. The proposed o- D-DARTS achieves
74.2% top1 accuracy with only 4.5 million parameters.
FLOPs (billion)
#Params (million)
Top1 (%)
Topl Error
TopS (%)
Top5 Error (%)
Net Arch
(%)
(d-)DARTS Liu 2018
0.530
4.72
73.3%
26.7%
91.3%
8.7%
o-DARTS
0.554
4.50
74.2%
25.8%
91.9%
8.1 %
calculated on scales of [16, 4], and the last fully-connectedd (FC) layer outputs 1000 categories for classification. We make this modification because the ImageNet dataset has significantly more training samples than the CIFARIO dataset. Experimental results are illustrated in Table as can be seen, by substituting conventional convolutions with the proposed optimal separable convolutions, resulting o-ResNet achieved 4-5% (e.g. 49.97% vs 44.93% for 56-layer and 50.72% vs 46.74% for 1 110-layer) performance gains comparing against the ResNet baselines. This demonstrates that the proposed optimal separable convolution scheme is much more efficient. For o-ResNet56 and o- ResNetl 10, they also have fewer parameters that could contribute to more regularized model. For o-ResNet20 and oeResNet32, they have slightly more parameters because the last FC layer accounts for great portion of overhead for 1000 classes.
3.2.2 FULL IMAGENET
Similar to the experiments CIFAR10, we replace the dsep convolutions in the DARTS (V2) network with the proposed osep convolutions to demonstrate that the proposed approach able to generalize other network architectures. The experiment is carried out on the full ImageNet dataset. The DARTS evaluation network has cells and 48 initial channels, we increase the initial channel size to 56 to match the FI.OPs. The resulting network is called o-DARTS. Experimental results are illustrated in Table It can be seen that, with fewer parameters (4.50 million vs 4.72 million), the proposed o- o-DARTS network achieved higher accuracies in both topl (74.2% vs 73.3%) and top5 (91.9% vs 91.3%) accuracies than the DARTS baseline. This indicates that the proposed osep is able to achieve better accuracy-FLan FLOPs and Cecuracy-tParamm balances than dsep convolutions.
is worth noting that in the proposed experiments, we adopt ResNet and DARTS as the base- lines because these two most well-known architectures. In practice, one may simply replace the conventional or depth separable convolutions with the proposed optimal separable convolutions in a DCNN reduce the computation and model parameters. By increasing the channel sizes, better-performing models can be expected. The proposed optimal separable convolution achieved improved accuracy-FLOPs and accuracy-#Parant
frrete-frontier than both conventional and depth separable convolutions. Hence, one can either match the accuracy to get smaller model with reduced computation and model parameters, or match the FLOPs get a better serter-performing model.
4 CONCLUSIONS
In this paper, we have presented novel scheme called optimal separable convolution to im- prove the computational efficiency in convolution. Conventional convolution took a costly com- plexity O( HW). The proposed optimal separable convolution scheme is able achieve
8

---

Under review as a conference paper at ICLR 2021
its complexity O KHW), which is even lower than that of depth separable convolution O(CHW (C+Kk)) Hence, the proposed optimal separable convolution has the full potential to replace the usage of depth separable convolutions in DCNN. Examples include but are not limited to the ResNet and DART'S architectures. The proposed optimal separable convolution also has a spatial separable configuration. A generalized N-separable case can achieve better performance O(CHW log(CK²)).
Another potential impact of the proposed optimal separable convolution for the AutoML com- munity. The proposed novel operator is able to increase the neural architecture search space. In a nulti--bjecttiv optimization formulation, where both accuracy and FLOPs are optimized. we ex- pect more efficient network architecture can be discovered in the future using the proposed optimal separable convolution operator.
REFERENCES
Kaifeng Bi, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian. Gold-nas: Gradual, one-level, differ- entiable. arXiv preprint rrXi:22007.03331, 2020. 3.1
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Confer-
ence on Computer Vision, pp. 1294-1303. 2019.
2 3.1
B
Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Bichen Wu, Zijian He, Zhen Wei, Kan Chen, Yuandong Tian, Matthew Yu, Peter Vajda, et al. Fbnetv3: Joint architecture-recipe search using neural acquisition function. arXiv preprint arXiv:2006.02049, 2020. [
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. leee, 2009.
1 3.2
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016. [
3.1
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Pro- ceedings of the IEEE International Conference on Computer Vision, pp. 1314-1324, 2019.
Andrew Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 2017.
Yani loannou, Duncan Robertson, Jamie Shotton, Roberto Cipolla, and Antonio Criminisi. Training cnns with low-rank filters for efficient image classification. arXiv preprint arXiv:1511.0674 2015.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 2015. C
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint arXiv:1405.3866 2014. TE
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. 3.1
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105,
2012. I
Tony Lindeberg. A computational theory of visual receptive fields. Biological cybernetics, 107(6): 589-635, 2013. I 2.2
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 1806. 09055, 2018.
9

---

Under review as a conference paper at ICLR 2021
Henri J Nussbaumer. The fast fourier transform. In Fast Fourier Transform and Convolution Algo- rithms, pp. 80-111. Springer, 1981.
Victor Podlozhnyuk. Fft-based 2d convolution. NVIDIA white paper, 32, 2007.
E
Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri. Numerical mathematics, volume 37. Springer
Science & Business Media, 2010.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference artificial intelligence, volume 33, pp. 4780-4789, 2019. !
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510-4520, 2018 2.3
Laurent Sifre and Stéphane Mallat. Rigid-moting scattering for image classification. Ph. D. thesis,
2014. 0
Rupesh K Srivastava, Klaus Greff, and Jürgen Schmidhuber. Training very deep networks. In Advances in neural information processing systems, pp. 2377-2385, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1-9, 2015.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2826, 2016.
Mingxing Tan and Quoc V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv: 1946, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi. Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-effiiiet architecture search. In International Conference on Learning Representations, 2019.
3.1
10

---

Under review as a conference paper at ICLR 2021
Algorithm 1 The Algorithm for Optimal Separable Convolution
Input:
Input channel C₁ Cin, output channel Cx+1 Cout. kernel size (K* K."). number of sepa-
rated convolutions
Optional Input: internal kernel sizes (optional, preset), internal number of groups (optional, masked values), spatial separable (Truc or False)
Output: internal channel sizes C2 ,C, internal kernel sizes KJ ( ,-. ,N K-WW internal number of
groups 91 .... : .N
Calculate internal channel sizes C2, Cw min(Cin, Cous), max Cous) / 4, mnin(Cin, Cour), etc. according to a preset policy. if internal kernel sizes #r| K 1'.1, N are not given then
spatial separable then
Sct K [N/2]= K" K-W
[N/2+1] = K and all other internal kernel sizes to 1.
else
Set K HIW WW and all other internal kernel sizes 1. [N/2]
end if
end if
Calculate internal channels per group according to 14 VIA C. K , k!W
C4. K""
Let gi = min([[i (. Cr. C.+1). If Ci/ny < 1 or Ci/ng > min(Ci, C++1) for certain I, re-optimize g with a masked number of groups by pre-setting gi = 1 for l E (1: Ci/mg < 13, gi = min Ct+1) for I E (T: Ct/T4 > min(Ci, C(+1)).
D Because ny ~ VC, for large channel sizes, we rarely need to re-optimize. , KHWW, 11 1
Return C2,"",CMy K K!IW
A ALGORITHMIC DETAILS OF THE PROPOSED OPTIMAL SEPARABLE CONVOLUTION
For the proposed optimal separable convolution, of the internal kernel sizes can take K"l W while the rest takes 1. In this research, we simply select the middle kernel size as (K" KW) In spatial separable configuration, we select the middle two to have their kernel sizes as (K 11 and (1, KW)). is worth noting that all these configurations have the same FLOPs. Unlike the spatial separable convolution where the spatial separable configuration is able to reduce the com- plexity from K2 to 2K. This is because the complexity has already been reduced to O(K) for the proposed optimal separable convolution. Another interesting property of the proposed optimal separable convolution is that it prefers large kernel sizes over small ones.
For the proposed optimal separable convolution, we are able preset the internal convolutional kernel sizes according to custom policy, and optimize the internal number of groups only. Further- more, we are able to preset a portion of the internal number of groups to certain values, and optimize only the remaining internal number of groups Suppose that the internal channel and kernel sizes are given. Without loss of generality, we assume that I, .9N are preset. The proposed optimal separable problem will be an M-separable convolution sub-problem (M < N):
[((n.), (K#WW }) C2n, K"" K HW + ..... CM41IM K... K W satisfying the volumetric RF condition
M HW + const
(20)
KM + K H
K + const
(Receptive Field Condition)
M
(21)
KW W
+
KW kw W const
(22)
C
$ gM < C ...... ON
-1. 2
(Channel Condition)
BM+1
9M+1 9N
(23)
C+1 Ci
n 2 ma
gh < min(Cr, Cr-) (Group Convolution Condition)
(24)
This M --separable sub- problem can be solved by the same algorithm. A detailed implementation of the proposed optimal separable convolution is described by Algorithm
11

---

Under review as a conference paper at ICLR 2021
Table 5: Experimental results on CIFARIO for the ResNet architecture with ablation studies of internal BN and non-linearity and spatial separable configuration.
Channel Multiplier
FLOPs (billion)
#Params (million)
Accuracy (%)
Internal BN and Non-linearity (%)
Spatial Separable (%)
Net Arch
ResNet20
0.04055
0.270
91.25
o<ResNe120
3.875
0.04054
0.206
92.89
92.74
92.32
ResNet32
0.06886
0.464
92.49
o-ResNec32
3.875
0.06760
0.352
93.18
93.22
92.88
ResNet56
0.12548
0,853
93.03
0- ReRsNet56
3,875
0.12180
0.643
93.32
93.42
92.93
ResNet110
0.25289
1.728
93.39
o-ResNet110 10
3.875
0.24370
1.298
94.35
94.21
93.96
B TRAINING SETTINGS
Experiments CIFARIO for the ResNet architecture The images are padded with 4 pixels and randomly cropped into 32 x 32 to feed into the network. A random horizontal flip with a probability of 0.5 is also applied. All the networks are trained with standard SGD optimizer for 200 epochs. The initial learning rate is set to 0.1, with decay of 0.1 at the 100 and 150 epochs. The batch size is 128. A weight decay of 0.0001 and momentum of 0.9 used.
Experiments on CIFARIO for the DARTS architecture We follow the same training settings in (Liu et al. 2018): the network is trained with standard SGD optimizer for 600 epochs with a batch size of 96. The initial learning rate is set to 0.025 with a cosine learning rate scheduler. weight decay of 0.0003 and a momentum of 0.9 are used. Additional enhancements include cutout, path dropout of probability 0.2, and auxiliary towers with weight 0.4.
Experiments ImageNet40 for the ResNet architecture Each network is trained with stan- dard SGD optimizer for 20 epochs with the initial learning rate set to 0.1, and a decay of 0.1 at the 10 and 15 epochs. The batch size is 256, the weight decay is 0.0001 and the momentum is 0.9.
Experiments on full ImageNet for the DARTS architecture We follow the training settings in (Chen et al., 2019) for multi-GPU training: the images are random resized crop into 224 x 224 patches with a random scale in [0.08, 1.0] and random aspect ratio in [0.75, 1.33]. Random horizontal flip and color jitter also applied. The network is trained from scratch for 250 epochs with batch size 1024 on 8 GPUs. An SGD optimizer with an initial learning rate of 0.5, a momentum of 0.9, and weight decay of 3e-5. The learning rate is decayed linearly after each epoch. Additional enhancements include label smoothing with weight 0. and auxiliary towers with weight 0.4.
C ABLATION STUDIES
Internal BatchNorm and Non-linearity For a DCNN, it is generally a good practice to add BatchNorm (BN) (Loffe Szegedy 2015) and non-liny after each convolution. For the pro- posed optimal separable convolution, we wonder if it is still necessary to add such BN and non-linearity after each of the internal separated convolutions. Experimental results are illustrated in Table 5 Comparing the "Internal BN and Non- Von-lincarity" column against the "Accuracy" col- umn, we are able to conclude that with or without internal BN and non-linearity, similar results be generated. This is reasonable because the network has already been regularized by outer BN and non-linearity layers from the macro architecture. Internal ones shall offer little no additional improvements. Because internal BN and non non-linearity could intro- duce extra computation and parameters, in the proposed research, we shall not use internal BN and non-linearity.
with only statistical variances
Spatial Separable Another variation of the proposed optimal separable convolution scheme is the spatial separable configuration. For Equation (16). the optimal solution is achieved when one of
12

---

Under review as a conference paper at ICLR 2021
Table 6: i5-8250.
Experimental results on CIFARIO for the ResNet with inference time on Windows 10 Intel CPU
Channel Multiplier
FLOPs (billion)
#Params (million)
Accuracy (%)
Inference
Net Arch
Time
ResNet20
0.04055
0.270
91.25
0.0310
o-ResNe120
0.00567
0.028
87.76
0.0276
o-ResNet20
3.875
0.04054
0.206
92.89
0.0468
d-ResNet20
0.00639
0.039
88,90
0.0312
d-ResNet20
2.75
0.0400
0.250
92.66
0.0468
ResNet32
0.06886
0.464
92.49
0.0469
o-ResNe132
0.00931
0.048
89.37
0.0624
0- o-ResNet32
3.875
0.06760
0.352
93.18
0.0937
d d-ResNet32
0.01057
0.066
89.26
0.0625
d-ResNet32
2.75
0.06565
0.429
92.98
0.1154
ResNet56
0.12548
0.853
93.03
0.0938
o-ResNe156
0.01660
0.088
90.53
0.0948
o-ResNe156
3.875
0.12180
0.643
93.32
0.1562
d-ResNet56
0.01893
0.121
90.22
0.1094
d-ResNet56
2.75
0.1 0.10890
0.786
92.69
0.1875
ResNet110
0.25289
1.728
93.39
0.1563
o-ResNet110
0.03300
0.177
92.12
0.1885
ResNeet110
3.875
0.24370
1.298
94.35
0.3216
d-ResNet110
0.03770
0.244
91.90
0.1910
d-ResNet110
2.75
0.23870
1.590
93.40
0.3462
the internal kernel sizes takes K H|W and all the rest takes 1. It does not matter which one of the internal kernel sizes takes K K#W Hence, we have this spatial separable variant: a single kernel takes (K#, K W two kernels take (K" 1) and (1, KW). The detailed implementation is illus- trated in Algorithm|] [ While spatial separable or not affects neither the FLOPs nor the number of parameters for the proposed optimal separable convolution, the results could be slightly different. As illustrated by the column "Spatial Separable" in T5 the spatial separable configuration leads to slightly worse performances. The reason might be that spatial separation fuses horizontal and vertical features separately, which could be less efficient than fusing them simultancously.
D INFERENCE TIME FOR THE PROPOSED OPTIMAL SEPARABLE CONVOLUTION
FLOPs measures the best possible theoretical speed further report the wall-clock inference time of the proposed optimal separable convolution scheme. The inference time is measured on a laptop computer with Windows 10 operating system and Intel i5 5-8250 CPU, which we use to simulate a mobile platform. The results are illustrated in Table 6 As can be seen, for ResNet20, o-ResNet20 m3.875, and d-ResNet20 m2.75, they have similar FL.PPs and deResNer20 _m2.75 take slightly longer inference
able achieve. In this Section,
(=x0.0055 billion), yet o- o-ResNer20_m3 time (0.0468s vs 0.03 This because current implementation grouped convolution Py- Torch is not optimized. From Table 6 we can also conclude that under the same FLOPs, o-ResNet has slightly better performance than d-ResNet (e.g. o-ResNet32 takes 0.0937s while d-ResNet32 takes 0.1 154s). This might because the proposed optimal separable convolution scheme usually has smaller "groups" hyper-paramene parameters than depth separable convolution. Similar conclusions can also be drawn for deeper ResNer32, ResNet56, and ResNetl 10 networks.
13

---

Under review as a conference paper at ICLR 2021
E RELATED WORK
There have been many previous works aiming reducing the amount of computation in convolution. Historically, researchers apply Fast Fourier Transform (FFT) [Nussbaumer 1981 Quarteroni et al.) 2010) implement convolution. For ID convolution, FFT reduces the number of computations for points from O to O(H log H). For 2D convolution, FFT-2D reduces the computational complexity from (HW K²) to OHHW (log H +og W)) (Podlozhnyuk 2007). Hence, can be easily concluded that FFT gains great speed up for large convolutional kernels. For small convolu- tional kernels (K << H or W), direct application often still cheaper. Researchers also explore low rank approximation (Jaderberg et al. 2014, Toannou et al., 2015) to implement convolutions. However, most of the existing methods obtain moderate efficiency improvements, and they usu- ally require a pre-trained model and mainly focus network pruning and compression. In recent state-of-the-art deep CNN models, several heuristics are adopted to reduce the heavy computation in convolution. For example, in (He et al. 2016). the authors bottleneck structure. Yet in (Sandler jet al. 2018), the authors adopt an inverted bottleneck structure. Such heuristics may require further ad hoc design to work in practice, however, they
solid and shall become less convincing.
Among various implementations of convolution, separable convolution has been proven to be more efficient in reducing the computational demand. Depth separable convolution is explored exten- sively in modern DCNNs (Howard et al., [2017] Sandler et al., 2018 Howard et al., 2019 Liu al. 2018 Tan & Le 2019). reduces the computational cost of conventional convolution from D(=K==WW) to OCCHW (C++ + K²)). However, the proposed optimal separable convolu- tion is even more efficient than depth separable convolution. It can be calculated O KHW) and has the full potential to replace the usage of depth separable convolutions. A second advantage of the proposed optimal separable convolution is that it can be applied to fully connected layers if we view them as 1 x convolutional layers, whereas depth separable convolution cannot. Further, depth separable convolution requires the middle channel size to be equal to the input channel size, whereas for the proposed optimal separable convolution, the middle channel size can be freely set.
Spatial separable convolution For example, a Sobel kernel is a x 3 kernel and can be written as (1, 1) (-1,0, 1). Spatial separable will require instead convolution is also adopted in the design of modern DCNNs. For example, in (Szegedy et al. 2016), the authors introduce spatial separation to the GoogLeNet (Szegedy et al. 2015) architecture. For the proposed optimal separable convolution, there is also a spatial separable configuration.
originally developed to speed up image processing operations.
parameters while doing the same operation. Spatial separable
In the body of literature, separable convolution also referred to factorized convolution or convo- lution decomposition. In this research, the proposed scheme is called optimal separable convolution following the naming conventions of depth and spatial separable convolutions.
14


Reviews:
[{"review_id": "rJ2zSBlGJgc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe paper presents a new convolution structure which tries to achieve a better balance between the efficiency and accuracy. The proposed approach is well motivated and theoretically proved. Reasonable experiments have been provided to validate the proposed algorithm. \n\n## Pros\n1. The paper is well presented and the motivation of the paper is clear.\n2. The proposed convolution structure has theoretical small FLOPs and well justified based on the proof. \n3. Reasonable experiments have been reported to valiate the the performance gain over the baselines.\n\n## Cons\n1. Besides from the FLOPs, is it possible to provide the computational cost for the proposed algorithm, e.g., including the inference speed in the experiments like Table 3. From the engineering implementation, the proposed structure may not be hardware-friendly. \n2. For the experiments on Full Imagenet, what about the experiments for the comparison with the resnet baseline. Also, I would suggest to include the comparison with the baseline with depthwise convolution. \n\n## Reasons for the rating\nThe exploration of the structure of the convolution is challenging but important to the community. The discussion of the convolution based on balance of the efficiency and effectiveness is meaningful. Although the experiments do not cover all of my concerns, I would rate it as marginally above the acceptance threshold.\n\n## Suggestions\nPlease provde the the comparison of inference speed for the proposed structure. Also, it would be better to report the baseline with depthwise convolution. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "OgTkK67XBzK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\n\nThis paper proposes a novel type of convolution called optimal separable convolution. Compared with existing separable convolutions like depth separable and spatial separable convolutions, the authors design a scheme to achieve an optimal separation. To prevent the proposed convolution from being degenerated, the authors define the volumetric receptive field to be the volume in the input space that affects CNN’s output. The volumetric RF condition requires that a properly decomposed separable convolution maintains the same volumetric RF as the original convolution before decomposition.\n\n**Strengths**\n\n- Contributions clearly stated and validated.\n- Comprehensive mathematical proof seems reasonable.\n- Ablation experimental results to show the effectiveness of their method.\n\n**Weaknesses**\n\n- The idea seems a little bit incremental in that it is a straightforward combination of group convolution and depthwise separable convolution.\n- Some crucial ablation study/experimental results are missing.\n\n**Clarity**\n\n- The paper is well organized and easy to read.\n\n**Comments**\n\n- To show the efficiency of the proposed convolution, the authors are suggested to present a runtime comparison with existing separable convolutions. I understand the FLOPS results have shown the efficiency of the proposed optimal separable convolution, but it's still necessary to show the actual running times.\n- The volumetric receptive field (RF) condition seems reasonable. However, the authors don't provide any ablation study on the volumetric RF condition. Say, what if removing this condition?\n- The author obtains the optimal value of three sets of parameters like the number of groups, the internal channel size, and the internal kernel size.  It’s better to present some ablation studies on these parameters. These comparisons will be more powerful to demonstrate that the obtained optimal values can lead to the best result.\n- This work seems an incremental version of group convolution and depthwise separable convolution. Could the authors give more discussion on this concern?\n- The authors only provide experimental results on the classification task. It's interesting to see if this proposed convolution can be applied to other tasks, like segmentation.\n\n**After Rebuttal**\nI appreciate that the authors partly answered my questions and conducted experiments to show the runtime. After reading through their rebuttal and the other reviews, I will keep my original rating. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "KiwKCZcH-D0", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new type of separable convolution to improve ConvNet efficiency. Based on a few assumptions (receptive field condition, channel condition, group conv condition), it mathematically calculate the “optimal” configurations for separable convolutions. Experiments are mostly done on CIFAR and ImageNet.\n\n======== Strengths\n\n1). Comprehensive study on important separable conv building blocks (e.g. Table 1 is quite informative)\n2). The idea of split the groups in both stages of separable convs is somewhat new and interesting.\n\n\n======== Weaknesses\n\n1). My first concern is about the unrealistic assumptions. For example, Eq (5) “channel condition” requires g1 * g2 = C2, which doesn’t make sense to me: there is no intuition, and most existing convs doesn’t satisfy this assumption: (1) regular conv g1=g2=1 != C2 doesn’t satisfy this; (2) spatial separable conv g1=g2=1 != C2. This assumption is critical to arrive equation (7) and (8), but is unclear where this assumption comes from.  Due to these unrealistic assumptions, the term “optimal” is also questionable.\n\n2). Second, the CIFAR results show the new layers are not much better than others. As shown in Figure 3, the largest gain is <1%, and sometimes the o-ResNet (~88%) is slightly worse than d-ResNet (which indicates the propose layers might be not \"optimal\"?) The improvements on ImageNet in Table 4 seem to be promising, but as discussed in DARTS+ and other recent works, the search process of DARTS is often unstable and could potentially have high variance.\n\n3). My another main concern is about the weak baseline. As this paper is study separable convs, it should compare to separable conv based models like MobileNet/FBNet/EfficientNet, rather than the full conv based ResNet. For example, by leveraging depthwise and seprable convs, MobileNetV3 achieves 75.2% ImageNet top-1 accuracy with 219 FLOPs, which is a much stronger baseline than the on in Table4. I highly recommend the authors to conduct their experiments on these baselines.\n\n\n======== Suggestions\n\n1). Instead of formulating it as a mathematically optimal solution based on unrealistic assumptions, I recommend the authors to conduct more empirical studies on these design choices. For example, the paper only shows the performance results of “optimal” (g1, g2) computed by equation (7), but it would be helpful to show the performance for different (g1, g2) values, and compare them with the “optimal” (g1, g2).\n\n2). I recommend the authors to use the latest MobileNet or EfficientNet (or other separable conv based models) as baselines, and replace their separable convs with the proposed “optimal separable convs”, and compare the performance gains. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Lsn4k1lM7O", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThis paper proposes a novel analysis for optimal separable convolution considering the number of parameters and FLOPs. The idea is to constraint the input information consumed stationery throughout the optimization of the parameters for separable convolutions. More specifically, this paper proposes the notion of volumetric receptive field and by holding it constant throughout optimization, one can arrive at a constrained optimization problem for solving the parameters for the optimal separable convolution. Empirical results of replacing common convolution with optimal convolution in various modern CNNs have demonstrated the effectiveness of the proposed optimal separable convolution.\n\n### Reasons for score\n\nI like the idea a lot. This paper provides a principled way of designing convolution to minimize FLOPs or parameter counts without resorting to black-box optimization or algorithms of sorts. The key insight brought by the paper is to keep the volumetric receptive field constant, which seems reasonable for me. With such an observation, solving for optimal separable convolution now becomes an optimization problem that can be solved efficiently. Empirical results on modern CNNs have shown the effectiveness of this approach.\n\n### Strengths\n\n- A novel and principled approach to design separable convolution, which is of critical importance. In contrast to existing efforts in designing efficient CNNs (e.g., NAS, pruning, quantization), this paper explores a complimentary yet relative under-explored direction, i.e., optimally design the convolutional operator. I can imagine how NAS and the proposed work be combined to lead to even better results in future work.\n\n- Good empirical results by simply replacing old convolution operators with the proposed one.\n\n- The analysis is easy to follow and generally agreeable to read.\n\n\n### Weaknesses\n\n- It would be interesting to see results on wall-clock time in addition to FLOPs and # Params. With that said, this is not a deal-breaker. While it might be the case that the proposed convolution operator falls short compared to the existing ones given the hardware and software implementation we have now, I still think this work would be a great motivation for hardware and software research to look into.\n\n- It would be interesting to see results for commonly adopted CNNs on ImageNet, e.g., ResNet-50 and/or MobileNetV2. Again, this is good to have, but not a deal-breaker from my perspective.\n\n\n### Post rebuttal\n\nI appreciate the authors' efforts in conducting experiments to show the latency results. After reading through the rebuttal and the reviews from other reviewers, I would like to down-grade my score by 1.\nSpecifically, I agree with R3 and R4 that it would be better if experimental results are done for MobileNets/EfficientNets to empirically demonstrate the effectiveness of the optimal convolution. Those networks present strong baselines and it would be more convincing if optimal convolution indeed outperforms those. With that said, I agree with the authors that the DARTS experiments have shown that the optimal convolution can be better than depth-wise separable convolutions. As a result, I still recommend acceptance for this paper.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel convolution-like operator called "optimal separable convolution" which is based on minimizing number of operations given a fixed receptive field.  Authors provide further empirical results to show the effectiveness of their proposed operator.

Overall, this is a very interesting work. There is a consensus among reviewers that this work is well-motivated, novel and principled. However, reviewers have pointed to several issues that makes this a borderline paper and consequently none of the reviewers were willing to argue for the acceptance. After reading the paper, reviewers' comments and authors' response, I would summarize the main areas of improvements as follows:

1- The "optimal separable convolution" is derived theoretically using "volumetric receptive field condition". However, this condition is not discussed and motivated enough in the paper. For example, different parametrization with the same volumetric receptive field could impose very different expressive power or implicit bias. Why is this not important? Adding discussions/experiments to motivate this condition would improve the paper.

2- The derivations in Sections 2.3 and 2.4 are not well-presented and are hard to follow. I suggest authors to use the convention of having a formal Theorem statement followed by the proof. This is important since one of the main contributions of the paper is a principled derivation.

3- All reviewers were concerned with the wall-clock time. Authors responded that theoretical #FLOPs is more important because wall-clock time is hardware dependent. However, authors reported the wall-clock time using CPUs. I understand that wall-clock time is hardware dependent but that only means algorithms that can have better wall-clock time on the current hardware are more likely to be useful because there is no guarantee that the hardware would be adjusted based on one algorithm especially if the promised improvement is not large enough. Therefore, I think reporting Wall-clock time on GPUs is important which was not done here.

4- Even though authors mention several operators in Table 1, they only compare against depth separable conv in the experiments. Even based on FLOPs, the current empirical results are not very promising. For example: 

a) The gap between o-ResNet (the proposed method) and d-ResNet is not significant in Fig 3. In particular when #FLOPs is low, d-ResNet and o-ResNet have similar performance. 

b) In Tables 2 and 4, o-ResNet shows small improvements but uses more FLOPs. Even if authors can't exactly match #FLOPs, they should make sure that the proposed method uses less FLOPs than others not the other way around.

c) In Table 3, authors only compare to ResNet and d-ResNet is removed.

Considering the above issues, I think the paper is marginally below acceptance threshold. Given the novelty of the work, I want to encourage the authors to improve the paper by taking Reviewers' comments into account and resubmit their work.


Decision: Reject