On the Dual Problem of Convexified Convolutional Neural Networks
Authors: Site Bai
Chuyang Ke
Jean Honorio
Venue: Accepted by TMLR ()

Abstract: We study the dual problem of convexified convolutional neural networks (DCCNNs). First, we introduce a primal learning problem motivated by convexified convolutional neural networks (CCNNs), and then construct the dual convex training program through careful analysis of the Karush-Kuhn-Tucker (KKT) conditions and Fenchel conjugates. Our approach reduces the computational overhead of constructing a large kernel matrix and more importantly, eliminates the ambiguity of factorizing the matrix. Due to the low-rank structure in CCNNs and the related subdifferential of nuclear norms, there is no closed-form expression to recover the primal solution from the dual solution. To overcome this, we propose a highly novel weight recovery algorithm, which takes the dual solution and the kernel information as the input, and recovers the linear weight and the output of convolutional layer, instead of weight parameter. Furthermore, our recovery algorithm exploits the low-rank structure and imposes a small number of filters indirectly, which reduces the parameter size. As a result, DCCNNs inherit all the statistical benefits of CCNNs, while enjoying a more formal and efficient workflow.

Published in Transactions on Machine Learning Research (02/2024)
On the Dual Problem of Convexified Convolutional Neural Networks
Site Bai
bail 231120duu edu
Deportment of Computer Science Purdue Universily
Chuyang Ke
ckc @parduee edu
Deportment of Computer Science
Purdue University
Jean Honorio
Jhonori@@uummmlbbccom edu
School of Computing and Information Systems The University of Melbourne
Reviewed on OpenReview: https: openreview. net/ forum? id= OyMouNzzu11
Abstract
We study the dual problem of convexified convolutional neural networks (DCCNNs). First, we introduce primal learning problem motivated by convexified convolutional neural networks (CCNNs), and then construct the dual convex training program through careful analysis of the Marush-Kuhn-Tucee (KKT) conditions and Fenchel conjugates. Our approach reduces the computational overhead of constructing large kernel matrix and more importantly, climinates the ambiguity of factorizing the matrix. Duc to the low-rank structure in CCNNs and the related subdifferential of nuclear norms, there is no closed-form expression to recover the primal solution from the dual solution. To overcome this, we propose a highly novel weight recovery algorithm, which takes the dual solution and the kernel information the input, and recovers the linear weight and the output of convolutional layer, instead of weight parameter. herthermore, our recovery algorit hm exploits the low-rank structure and imposes a small number of filters indirectly, which reduces the parameter size. As a result, DCCNNs inherit all the statistical benefits of CCNNs, while enjoying a more formal and efficient workflow.
1 Introduction
In the past decade, convolutional neural networks (CNNs) have become the cornerstone of various deep learning architectures. The performance of CNNs so impressive, that they have become the standard methods on many tasks such as biomedical imaging (Suzuki, 2017; Yamashita al., 2018), robot perception (Han et al., 2016; Zhang et al., 2019) and signal processing (Hershey et al., 2017; Eren et al., 2019). Despite the great success in broad range of applications, the training of CNNs is in general an NP-hard problem (Blum & Rivest, 1992). While in practice gradient- baadee optimization methods are used in the training process most of the time, there is no theoretical guarantee of achieving global optimality or bounding the rate of convergence.
To tackle the limitations of nonconvex landscapes, Zhang et al. (2017) proposes class of convex relaxations of CNNs, namely the converified convolutional neural networks (CCNNs). Employing a convex optimization formulation, CCNNs can be optimized efficiently and their statistical properties can be analyzed rigorously (Zhang et al., 2017). In CCNNs, activation function is induced by kernel function K. The kernel

---

Published in Transactions on Machine Learning Research (02/2024)
function produces kernel matrix K, which needs to be approximately factorized into matrix Q such that K' R QQ" After that, the CCNN algorithm solves muclear norm constrained convex opt optimization problem, and computes a low rank approximation, which outputs the weights of the network. While stochastic gradient descent (SGD) is still the state-of-the-art, the whole convexified approach allows for efficient and optimal training of the network, and from a theoretical point of view makes precise statistical analysis viable (Zhang et al., 2017).
However on the algorithmic front, the CCNN framework, while enjoying the aforementioned benefits, does come with drawbacks and its own limitations.
The approximate factorization of the kernel matrix K QQ is not unique. One can use a tall matrix Q either from the Cholesky decomposition of K, from K1/2, ; or from UDI/2 where K = -UDU, to name a few. In the latter case, one can also use D for any orthonormal V, meaning that there exists infinitely many possible Q's! There is no guarantee that every choice of Q performs equally well in the learning task, and thus the factorization problem itself can be tricky. Furthermore, the idea of factorizing the kernel matrix is not suitable from a statistical perspective, given that for CCNNs, kernels with infinitely dimensional basis functions are used (for example, Gaussian RBF kernel).
Solving the exact kernel factorization problem itself can be compulationally expensive. Looking at Algorithm 1 in the CCNN framework (Zhang et al., 2017), the dimension of the kernel matrix is equal to the number of samples n times the number of convolution operations (patches) p. From a space complexity perspective, the factorization step alone occupies memory in the order of O(n²p"). This is hardly feasible: for a small network training on 1000 28 x 28 images with stride 1, i.e. 784 convolution operations, with 64 bit double precision, the kernel matrix takes more than 4 terabytes of memory! Similarly, the computational complexity of many factorization algorithms (for example, Cholesky) can take O(n'p"), which can be prohibitive in practice.
The CCNN algorithm heuristically cut the first r columns of the convolutional weight recovered for the final low rank approximation step, with the number of filters r as a hyperparameter. Setting the hyperparameter too large increases the parameter size with unnocessary information, and sctting it too small voids the optimality guarantee. And such impact may accumulate as the number of layers increases.
In this paper, we study the dual framework for learning CCNNs, which we call dual convezified convolutional neural network (DCCNN). We first carefully construct the DCCNN learning program by analyzing muclear norms and Fenchel conjugates. We then solve the convex training problem in the derived dual form. Unfortunately, due to the nature of the sub-differential of the nuclcar norm, there is closed-form expression for us to recover the primal solution from the dual solution. To overcome this, we design a novel weight recovering algorithm that leverages the KKT optimality conditions and the sub-differential of nuclear norm. Without getting the primal solution, our algorithm directly recovers the lincar weight and the convolution output using the dual solution and a kernel generating matrix, which applies to kernels with infinitely dimensional basis.
Our DCCNN framework enjoys many benefits top of the CCNN approach. First, compared to the CCNN approach, our method does not require any approximate factorization of the kernel matrix in the form of K R QQT. Instead, by solving the optimization problem in DCCNN, we can directly recover the proper solution without introducing any ambiguity or compromise. Next, our approsch does not construct the full matrix K for all samples in memory. Our weight recovering algorithm computes entries of the kernel matrix on the fly, greatly reducing the memory overhead. More than that, our DCCNN framework does not require specifying the low rank hyporparameter manually. Our weight recovery algorithm automatically computes the minimum necessary rank from the dual solution, which better exploits the benefits of the low-rankness introduced by the muclear norm constraint, as it encourages small number of filters indirectly and reduces the parameter size. To sum up, our DCCNN method inherits all the benefits of convexified CNNs like generalization error and sample complexity bounds, while enjoying a much more formal and efficient workflow without introducing ambiguity.
Related works. The area of convex convolutional neural networks is fairly new In Zhang et al. (2017), it is shown that a class of CNNs with reproducing kernel Hilbert space (RKHS) filters contains a low-rank matrix structure, which can be further convexified by using nuclear norm constraint and reduced to the
2

---

Published in Transactions on Machine Learning Research (02/2024)
f(x) f1
((x)
du
W
LT
f(x) = 1( Σ, ag4
(xx)
(x,,)
L LT)
A: A S
Convolution Output
Convolution Output
(2r) approximated by kernel matrix Iactorization
Use K m4) without ambiguous factorization
A low-rank, enforced by nuclear coustraint
Recover weight with dual solution
W computed by low-rank approximation
Compute convolution output without 4fxx) or W
(a) The Primal Framework
(b) The Dual Framework
Figure 1: (a): In the primal framework, the basis function matrix ((x) Q from the approximate factorization of kernel matrix such that K ~ QQT. The convolutional weight W and linear weight L are multiplied together as matrix A with low-rankness enforced by nuclear norm constraint. W is recovered by low-rank approximation from optimized A. (b): The dual framework uses ((x,,;)) without ambiguous factorization, and recovers the weights with the optimized dual variable a. The primal solution A cannot be directly recovered because has no closed-form expression of a. Therefore, the dual framework recovers linear weight. L and computes the convolution output ((x) directly without W or ((x).
class of CCNNs. This provides basis for our work. Other convex neural network researches are more tangential. Mairal et al. (2014) proposed to approximate the CNNs with a Zhong et al. (2017) analyzed the convergence propertics of CNNs. Gunasckar et al. (2018) analyzes a lincar version of convolutional networks. Amos et al. (2017) and Makkuva al. (2020) study the so-called input. convex neural networks, where the output convex function of the inputs. Arora et al. (2019) studies the exact computation of CNNs with infinite many filters. Ergen & Pilanci (2020) proposes equivalent convex regularizers to the CNN architectures. See Appendix H for further discussion.
kernel.
Summary of our contribution. We provide the following series of novel results in this paper:
We provide a dual convexified convolutional neural network (DCCNN) framework for learning class of CNNs. We rigorously construct dual convex training program through careful analysis of the KKT conditions and Fenchel conjugates. With the dual solution, we also propose linear weight and implicit convolutional weight recovery algorithm.
Our DCCNN framework is theoretically formal. Compared to prior literature, our method does not require any ambiguous factorization the kernel matrix. Through the novel weight recovery algorithms, we directly recover the proper solution. In addition, our approach implicitly encourages a small number of filters, reducing the number of weight parameters without enforcing the low-rankness by heuristics.
Our DCCNN framework is efficient. It operates without loading the full kernel matrix for all samples in memory, or introducing any unnecessary memory overhead of factorization. As result, DCCNN inherits all the statistical benefits of convexified CNNs (Theorem in Zhang et al. (2017)), while enjoying more efficient workflow (See Appendix G.4).
Our analysis in the DCCNN framework novel. To derive the dual training program, the muclear norm in the primal problem requires careful construction of the Lagrangian through Fenchel conjugates. Furthermore, there no closed-form expression that can be used to recover the primal solution from the dual solution directly because of the sub-differential of the nuclear norm. Without getting the primal solution, our algorithm directly recovers the linear weight and the convolution out using the dual solution and a kernel generating matrix, which applies to kernels with infinite-dimensional basis.
3

---

Published in Transactions on Machine Learning Research (02/2024)
2 Preliminaries
2.1 Notation
Vn E N, we use [n] to represent the set (1, n). We use regular lower-case letters (e.g., a, c) to denote constant. We use bold lower-case letters like x to represent vectors. We use capital letters (e.g., U, V) to represent matrix. We use p as the notation for activation function, as matrix singular values, and À as matrix eigenvalues. || I|- denotes the matrix nuclear norm, and || |/2 represents the spectral norm for a matrix, and the Euclidean norm of vector. We use Tr(.) to represent the trace of matrix. For matrix V, use (i) to represent the 2t column vector and Vi to represent the entry in the 7th row and jth column. For column vectors E Rd with i E [n], we denote [x.] E Rd as the concatenation of these column vectors into a matrix. For matrix U and V with the same number of rows, IU [] represents the concatenation of the matrices. We use to represent the identity matrix and 0 the zero matrix.
2.2 Formulation of Convolutional Neural Networks
Given dataset {(x1, y.., (X,: bn)), , x; E Ro, Ut, E [n], two-layer CNN, also called one-hidden-layer CNN, is function that maps the data to the targets by passing the data through convolutional layer and a linear layer.
The convolutional layer performs convolution operations, in which a subset of d1 entries in x; is multiplied element-wise with one of the r convolutional filters Wa E IRd,, k E [r]. We call this subset of data entries patch generated from x,, denoted as z (x,) Rd, The number of patches relies on the choice of filter width, padding type, stride, elc., and we use p denote the total number of patches generated by a sample. The p patches form the patch matrix Z = Z1. .... Zp] R and the convolutional filters form the weight matrix W = [wi,..., w,] E Rdixr. Then the convolutional operations can be represented by the matrix multiplication between the patch matrix and weight matrix, i.e., 2 W.
The result the convolutional layer is then passed into an element-wing wise activation function (-). After that, p(Z W) is passed into a lincar layer. We denote the weight of the linear layer as E Roxr, For all j E [p] and & E [r], Lyk is the coefficient multiplied with the 4 convolutional filter and the jth patch. Then the output of the two-layer CNN can be represented by Tr (p(Z) To(ZTW)) W.).T).
2.3 Convexified Convolutional Neural Networks
CCNN Formulation with Linear Activation. Consider a linear activation function, to begin with, the expression for CNN simplifies to Tr (ZTWLT). Define parameter matrix A = WLT E Rd Then we can write the two-layer CNN using the new parameter A. As the multiplication of the convolutional weight, and linear weight matrices, A intrinsically low-rank, ie., rank(A) S r. Zhang al. (2017) enforces the low-rankness by extra relaxed constraint to bound the muclcar norm of A. Therefore CCNN takes the form Tr (2T A), in which ||||| S for some constant
Activation and Reproducing Kernel Hilbert Space. As proposed by Zhang et al. (2017) (Lemmna and Lemma 2 in their paper) and later generalized by Bictti & Mairal (2019), CNNs with certain choices of activation function are contained in some reproducing kernel Hilbert space (RKHS). In other words, for some specific activation function p, there is a corresponding kernel function (C = (.) (+)) that produces similar non-linearity. The basis function (-) Rdd + RRdz could be a mapping to an infinite dimensional vector space, ie., d2 could be infinity.
CCNN Formulation with Non-linear Activation. For the basis function @ (-), define basis function matrix
① (x,) (p(z) (xx) ), (Ep (xx) E dd
4

---

Published in Transactions on Machine Learning Research (02/2024)
and with convolution weight matrix W E R the convex relaxation of non-linear activated CNN can be represented with the kernel basis function, which leads to convexified two-layer CNN function:
f(x.) = Tr (x..)) ((L.)
(1)
In other words, activating the convolution output p T W) is equivalent to passing the data through the kernel basis function, Le., ((x.) W. Define parameter matrix A = WL E Rddxx, Then we can write the two-layer CNN using the new parameter A:
f(x,) = Tr (+(x;)
Learning CCNN. In this paper consider the task of learning two-layer CNN functions for classification with some loss {(-) that is convex and non-increasing, e.g. hinge loss, logistic loss, exponential loss. Using the convexified CNN function defined in Eq. (2), the parameter matrix A can be learned by solving the following optimization problem. For binary classification,
À = arg min |||| + Σ ely Tr (A))))
(3)
A
where >> is a hyperparameter. Furthermore, in the context m-cllas classification, there is a predictor for each class, i.e, fx(x)) Tr (*(x,)" (ox)))AA)) Ax) for every & [m]] Correspondingly, the parameter [A1, ... Am] can be learned by minimizing the loss for multi-class classification:
Å == arg min ||||, + Σ> (x: fx(x,)) Angiot
(4)
It is worth noticing that the ((x,) appearing in the problem can be infinitely dimensional, and can only be represented by some heuristic finite approximation in practice, which consequently introduces ambiguity. To tackle this problem, we consider the dual formulation this paper.
Layerwise Training. The CCNN formulation corresponds to the architecture of one convolutional layer and one linear layer. To extend the framework to deeper architectures, the layerwise training technique (Zhang et al., 2017; Belilovsky et al., 2019) is applicd. The convolutional layers are trained one layer at time, taking the output of the optimized previous layer as input, concatenated with one linear layer that takes part only in the training of the one convolutional layer.
3 Main Results
We begin by introducing the primal optimization problem. Learning two-layer convexified CNN, i.e., solving the loss minimization in Eq. (3) is equivalent to solving the following optimization problem:
minimize A
||||| +
((E))
(5)
i=1
subject to ys Tr (xx; A) 2 Ei, Vie [n].
in which & is an equivalent variable of ys Tr (Φ(x,) ((xx,)))) A), and e > some by hyperparameter. E(-) some convex and non-increasing loss function. In fact, many common loss functions fall into this category, c.g. hinge loss (x)( = max 1 x),, squared hinge loss (sH(x) (max(0, = logistic loss Cr((x) log(1 + +*",, and exponential loss (x) =²
In the primal problem in Eq. (5), the computation of the basis function matrix + (x;) may be infcasible, or otherwise heuristically approximated by some kernel matrix factorization, as the basis function & (æ;) could be a mapping to infinite dimensions for many kernels. To avoid such dilemma, we first derive the dual problem, then introduce the algorithm for recovering the weight from the dual solution. An illustration of the dual framework based on the primal framework demonstrated Figure 1. For the theorems in this section, provide proof sketches and leave the detailed derivations in Appendix A.
5

---

Published in Transactions on Machine Learning Research (02/2024)
3.1 Dual Optimization Problem
In order to avoid the ambiguous approximation from kernel matrix factorization, we consider the dual form of problem (5) and compute kernel generating matrix directly with the benefits of the kernel trick (Schölkopf et al., 2002).
Thcorem 1. The dual problem of Eq. (5) is given by:
maximize
(6)
subject to Amax Σ
(a s 1,
=1
a4 120, 0, [n)
in which ag are the dual variables, (-)² is the Fenchel conjugate of the loss function E(-), K (xx, x1)
@ (xx) To 4 (x²) is kernel generating matrix, such that its entries composed of the kernel function
((,,)) o (.) (.) taking one patch from each of the two samples as input:
(xx1(x)), 21(1))
((x((x),, zx(x,)
K (x,,
(7)
(x), 2x(3) (x)x(xx),
Proof Sketch: The derivation of the dual problem follows the standard Lagrangian duality framework, with a careful construction of the Fenchel conjugate (Boyd & Vandenberghe, 2004) for the nuclear norm and the loss function. For Lagrangian variables a; 2 0, we can write the Lagrangian function of the primal problem in Eq. (5) follows, after rearranging terms and utilizing the trace definition of matrix inner product:
C (A) = |||||.
auy (x,) A) + c ((E)) Σ i=1
a.
(8)
Then by definition, get the dual function by minimizing the Lagrangian function with respect to the primal variables:
g (a)) min L (A) max Σ a.y 2 (xx) A) ||lll. max A.
((E)
agEi
i=1
in which 91 and g2 take the form the Fenchel conjugate. The conjugate function norms is their dual norm (Boyd & Vandenberghe, 2004), then for the norm fo |||A]],, we have
91 So Σ asy (x:))
0
11-112 < otherwise.
in which fo (-)
(10)
xc.
Also,
02
92 = c
8*
1=1 c
TTo have detailed illustration of 6t (+), include the Fenchel conjugate some common losses Appendix

---

Published in Transactions on Machine Learning Research (02/2024)
in which (+) sup,, (.) - {(E)) is the conjugate function of the loss function E(E.). Therefore, the dual
problem of Eq. (5) is as follows:
ai
maximize
c
subject to
Σ
4 (x:)
11 S 1,
(11)
02 2,00 E [n].
Finally, we construct the kernel function by squaring the spectral norm constraint in Eq. (11) on both sides, which leads to the form in Eq. (6).
The dual problem presents in the form of the kernel generating matrix and climinates the basis function, and consequently the ambiguily of factorizing the kernel matrix. Also, our kernel generating matrix is size O(p²), which is more computationally efficient in terms of spatial complexity.
With the dual problem constructed, solve the dual problem by coordinate-descent algorithm. The algorithm picks the coordinate entry in ascending order with respect to the maximum eigenvalues of the kernel generating matrices, and optimize the chosen coordinate by binary search. The pseudocode of the algorithm provided in Algorithm 2 in Appendix E.1.
3.2 Recovering the Parameters
In conventional machine learning dual optimization problems like the dual of Support Vector Machine (SVM), the primal solution can be exactly recovered with the stationary condition in the Maaush-KuhnTTiie (KKT) conditions (Weston & Watkins, 1998; Vapnik, 1998). Such closed form expression for the primal solution, however, no longer applies to the DCCNN formulation, because the nuclear norm is non-differentiable To tackle this problem, we propose a parameter recover algorithm that avoids recovering the primal solution Á, but directly recovers the linear weight L and the output of the convolutional layer ((x) T W without explicitly recovering W or computing ((r). Our algorithm leverages the KKT conditions and the subdifferential set of the nuclear norm.
Since there are infinite many ways to decompose the convolutional weight W and linear weight from the optimal parameter Å, we adopt the singular value dccomposition method proposed by Zhang et al. (2017), i.e., for the compact SVD Å Ū, D Vi, regard Ú, as the convolutional weight W and V, as the linear weight L. We use them interchangeably in the following context. For recovering such weight parameters, we propose an algorithm to recover the linear weight in Theorem 2, and we propose the method to implicitly recover the convolutional weight by the convolution output in Theorem 3. The complete algorithm workflow is demonstrated in Algorithm 1.
3.2.1 Recovering the Linear Weight
Our weight recovering algorithm leverages the KKT conditions, in which the subdiffcrential of the nuclear norm plays an important part. We begin by introdug two Lemmas that formalize the stationary condition of our optimization problem and the relevant definition for the muclear norm subdifferential.
Lemma 1. For the primal problem (5) and the dual variables {ar) the stationary condition with respect to variable A in the KKT conditions given by:
n
0 l|
Σ d.y (xx).
(12)
Lemma (Subdifferential of Nuclear Norm (Watson, 1992)). For matrir A Rdaxp with rank(A) r, consider compact SVD A VT in which U1 E Rdxxr, D E Rexr and Vi Roxr, and full SVD A = UDVT in which U E xdd DE Rdxxp, and V E RRxx, Denote U2 E (d2x(d2-r) Va (Px((-)) such

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm 1 Recovering the weight parameters for two-layer DCCNNs
Input: Data f(x,, u))):m: Optimized dual solution {á;)?=1 to problem (6); Kernel function K. Recover the Linear Weight:
1: Compute S Ei, drdyyuy (xs, x,). {Using ((s.) defined with Eq. (7) without ambiguous factorization)
Compute the eigendecomposition 5 VAV-1.
3: Let the eigenvectors with eigenvalue 1 form the linear weight L, ie.,
i
[()) E R for all such that Ag =.
Recover the Convolution Output (Input for the next layerwise training): (Without computing (xx) W}
4: Compute the output of the convolutional layer ((x:) W by
((x,) T Σ j=1 رز8زة (x,, x;)
Output: Linear weight L; Output of convolutional layer (x,) W y
that U [U1 U2], V [V1 V2]. Then the subdifferential set of A is given by
i ||l.. (UIVT+ + UVEV. E E (d( max (E) =1)
(13)
in which mmax (.) is the largest singular value.
Now we introduce our method of recovering the linear weight using the dual solution and the kernel generating matrix, and validate that what we recover is indeed the linear weight V/.2
Thcorem 2. Given the optimal dual solution {ā=)z to the problem in Eq. (6), let V R be the matrix of eigenvectors from the eigendecomposition VAV-1 E'= Ei= ب,رلyرy K Xxx, where A = diag(A),...., Xp) E Rexp, The linear weight Vi can be recovered by the eigenvectors in V corresponding to the eigenvalue of 1, that is,
v. - E BPxr for all i such that X 1,
(14)
in which (i) denotes the tth column of V and [] denotes the concatenation of these columns.
Proof Sketch. By the stationary condition in Lemma 1, we know that the there exists one element in the subdifferenttal of ||-l]] at value A that satisfies Σn_ & (x,) A|| Then for Å, consider its compact SVD -= Ú and the full SVD Å = DDVT in which = 1 Üz). V = [V Pzz. By Lemma 2, we know that there exists E such that Ü,V, V.T + U,EV Σ.= d. (x:). Now we construct the kernel generating matrix under the intuition to avoid the basis function matrix ((x.). Let T' 7==0; 0, + &,,VV = Σ 6,y, (x.). By computing S = T we get the kernel generating matrix K K(x;, xj) on the right side of the equation. For the left side, we know by the properties of SVD that Ún and Ü2 are semi-orthogonal matrices, i.e., ÚTū, = I, U T TŪÚ,V - UUEVT and with some simplification, we get S Pi + VV VVÉTEV Also, V 1 1/2, then p for the digendecompositions 5 = VAV-1 V V-,V- VA.V-! such that A = A, + Ae- Since V is semi-orthogonal, there
[dd--);; and also Ún 1 Ú2, i.c., ÚTú, 0
O. Therefore, by plugging in
Vi 1 LT Consequently, there exists V Rexp
and VLÊTÉV, the diagonal of A,. Meanwhile, by the Lemma 2, we know that 0max (F) < 1. For the moment, assume that max (E) < 1. That is to say, the elements on the diagonal of A. lie in the range 10. Moreover, given that Vi 1 YT we know that Ag, = for all with Ae,i > O, and Ag = 1 otherwise. Therefore, the eigenvectors [v]]] with Aa = are the cigenvectors of V VT Since Vi is from the compact SVD with rank(Vi) r, Vi = [V()] is the recovered linear weight. Finally, recall that general dmax (F) S 1.
only 0's and 1's
2Strictly speaking, we recovering solution in superset of the of vectors the linear weight.
8

---

Published in Transactions on Machine Learning Research (02/2024)
Therefore, the eigenvalues of Ez EV2 could also be 1, and thus, recovering solution in superset of the set of vectors in the linear weight.
Remark 1. One of the benefits we enjoy from our recovery algoritlom is that we do not need to set the number of filters as a hyperparameter, but can directly deduce it from the linear weight we recover. That is, we do not fir the number of convolutional filters r, but deduce r by letting r r: rAn,(A)), or equivalently, r y= rank(Vi) (Vi), i.e., r is the number of 's in the diagonal of A. Furthermore, the imposed nucleur norm constraint on A encourages a low rank which implicilly reduces the parameler size in altempl to find the minimum number of filters necessary.
3.2.2 Recovering the convolutional weight
In the case of the convolutional weight, there is no closed form expression for Un E Rd because we cannot exactly compute f(x;) Rd and d2 could be infinity. We provide an approach to compute the output of the convolutional weight directly, which implicitly contains Üj, and can be used for the purpose of layerwise training well as making new predictions.
Theorem 3. Given the optimal dual solution â;, E [n]] to the problem in Eq. (11), the convolutional weight U1 can be implicitly recovered by the convolution output, that is, vi E [n].
$ (x:)
(x:) 00 Σ dgy ((x, X,)
(15)
Proof Sketch. By Lemma and Lemma we know that VJOT = EE (x,) VGETUG For both sides of the equation, multiply with ViT on the left and (xx,) on the right, we have V $ (x) = EE= āyy, 4 (x,)² & (x,) - V V 02 4 (xx). Note that V is semi-orthogonal and V 1 V22 thus VTT; =I=I and i7 V/2 = 0. This concludes the proof.
After recovering the convolution output, one can train a multi-layer DCCNN by the layerwise training approach applied in (Zhang et. al., 2017; Belilovsky et al., 2019). That is to regard the vectorized output of the convolution weight vec (I(x,) ) (1) as the input for the next layer. Note that the vectorization automatically takes care of the case for multiple-channel input or output, as it will eventually be transformed into vector. The complete algorithm of learning D-layer DCCNN is illustrated in Algorithm in Appendix E.2.
Our way of recovering the weight output can also be adapted to other CNN techniques such as Average Pooling. To achieve average pooling, one can generate pooling matrix G and simply multiply it with the convolution output before feeding it into the next layerwise training. We refer the reader to Appendix F for the generation of average pooling matrix.
Making prediction with a new sample Xnow can also be achieved with the dual solution and the kernel generating matrix. We can make predictions with the two-layer DCCNN by firstly plugging the sample into Eq. (15), then multiplying the convolutional output with the linear weight, and finally computing f (Xnew) ) = sign "r= (yy,,((Xunn T)) The algorithm for making predictions with layerwise trained D-layer DCCNN is described in Algorithm 4 in Appendix F.3.
3.3 Extension to Multiclass Classification
Our proposed method can be easily extended to multi-class classification. In this section, we provide results for the multi-class version and leave the derivations and proofs in Appendix B, as they closely resemble the derivations for binary classification.
We start from the multiclass version of loss minimization in Eq. (4). To be consistent with the binary classification formulation, for the paramcters {m 1. we define A = [Ai,.., Am] E Rdxxmp, Similarly, for & (xx) E Rd2xp, we define & (x.) = [0,, [0,, ((k-1)p> & (x:), 0dex(m--))) E Rdxxmp, In this way have
3 Experimentally, the total number of vectors associated to eigenvalues close was very small. Thus, most likely we are recovering only V2 and not V22 and so we do not believe this is an issue practical terms.
9

---

Published in Transactions on Machine Learning Research (02/2024)
CCNN
SGD (end- (end-to-end layerwise)
Dataset
Architecture
DCCNN
UD
UDÀV
K
Cholesky
1-Conv-Layer
90.3%
90.3%
88.8%
93.7%
90.2%
--
94.8%
MNIST
L-yeerLLayer
93.7%
93.5%
93.5%
96.7%
95.2%
92.4%
96.0%
AlexNet
62.3%
62.3%
53.2%
62.0%
87.1%
86.3%
83.3%
ImageNet
VGG11
55.3%
52.5%
59.8%
57.0%
89.2%
86.7%
85.0%
(a) Test Accuracies MNIST and ImageNet Binary Classification.
CCNN
Dataset
Architecture
SGD
DCCNN
UD!
UDiV
K
Cholesky
MNIST
1-Conv-Layer
75.4%
75.4%
82.3%
85.9%
87.0%
85.3%
(b) Test Accuracies on MNIST Multiclass Classification.
Table 1: Experiment results for binary and multiclass classification. Methods compared include CCNN, CNN trained with SGD, and our proposed DCCNN. For CCNN we use 25-column matrix Q from different. ways of kernel matrix factorization:
(1) UD for K UDUT; (2) UDVV for K UDUT, and random orthonormal matrix V; (3) k²; (4) the Cholesky decomposition of K. The X-Conv-Layer in the architecture column refers to the number of convolutional layers, only one linear layer is concatenated at the end for classification. For architectures with more than one convolutional layer, we list the result of SGD trained both end-to-end and layerwise. The result of SGD only reflects its performance in our specific experiment setting, e.g. few convolutional filters, and is listed for DCCNN sanity check purposes.
Tr (+(x,) Ax) = Tr (x,, A), and the minimization in Eq. (4) is equivalent to the following optimization problem:
minimize
||||| +
Σ Σ ((E,i))
(16)
A: 1=1
subject to
Tr (T m (x:)
A) TA)
Tr (Th (x: T 2 Ex,s, Vi E [n], h: + yi
in which ((-) is convex and non- non-increasing, Ék is an equivalent variable of Tr ( (x:) TA) - Tr (xx)) AA). and c > 0 is some hyperparameter.
We can derive the dual of the optimization problem in Eq. (16) as Section 3.1. With an adaptation of the kernel generating matrix, we give out the dual problem for multi-class classification.
Theorem 4. For all dual variables one with i [n] and [m], the dual problem of Eq. (16) given by:
O.ki
maximize
(17)
k=
11
m
subject to Amax
Σ
oh K2 K((X,, $1,
Okii 2 0, Oge O, Vi [m], Ak im],
in which o/: = Em Ox, [k: anii (.) is the Fenchel conjugate of the loss function {(-), and the kernel generating matrix is constructed in K2 xx,, diag (0 (0pxp:... K(x,,x)) ...., Opxp), with
4th block diagonal
K(x;,x;) ((xx)] Tx(x))-
10

---

Published in Transactions on Machine Learning Research (02/2024)
After solving the dual problem, can recover the linear weight and the convolution output by Theorem 54 and Theorem 6 using the dual solution (( ta k=1Ji=1 and the kernel generating matrix.
Theorem 5. We can recover the linear weight V1 E TRmpxrr for multi-class classifieation by Vi [V()], for all with X; 1. Here V E mmppxmp comes from -AV-1= A = diag(Ai..... Amp) E IRmpxmp and d' -6:==a Ca.ii [k yi! Oxk.i.
= -i= E o Kg (x,,x;) where
Thcorem 6. We can implicitly recover the convolutional weight in the convolution output for multi-class classi- ficaion. That is, for all i E [n], we have & (x,) 01 Eド= Σx= (pp ( K (x1,x)) Opx (m V1.
Same as binary classification, vec (o (x.) U1) can be regarded as the input for the next layerwise training. To make new prediction for sample Xnew with the multiclass model, for every l E [m], we can extract the linear weight of each class LE E gexr from L [L] .. L E Rupxx and then make predictions with the multi-class predictor ((Xeow) = arg maxxe[m] Tr 2 L of (px((Oxx K ((Xnear
x:), (px(mm L.T))
4 Experiments
In this section, we evaluate DCCNN on real-world data as a sanity check for the proposed method. The performance is by no means state-of-the-at art for relevant tasks, and the baselines reflect only its performance in our experimental settings, which is the same for all methods. For DCCNN, we solve the dual problem by coordinate-dessent approach (Algorithm 2 in Appendix E.1). For CCNN, we used a projected gradient descent approach and r 25. We apply hinge loss for evaluation. The specifie form of the problem in Eq. (6) with hinge loss can be found in Appendix D. We briefly report results in Table 2, and leave the detailed analysis in Appendix G. In Table 2a, for the binary classification task of the MNIST data (Lecun et al., 1998), we can see the DCCNN out purfoross CNNs trained using SGD and different kernel matrix factorizations for CCNN on one-conv-layer and two-conv-layer networks with only one exception, which verifies the effectiveness of DCCNN. On the more complicated ImageNet dataset (Deng al., 2009), DCCNN also performs comparably well with the end-to-end SGD optimized CNNs under both AlexNet (Krizhevsky et al., 2012) and VGG11 (Simonyan & Zisserman, 2015) architectures, and significantly outperforms the CCNN method. From Table 2b, we see that in multiclass classification, the performance level of DCCNN is better than various factorization versions of CCNN and is comparable with SGD.
References
Brandon Amos, Lei Xu, and J Zico Kolter. Input convex neural networks. In International Conference on Machine Learning, pp. 146- 155. PMLR, 2017.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Newral Information Processing Systems, 32, 2019.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Greedy layerwise learning can scale to ImageNet. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 583-593. PMLR, 09- 15 Jun 2019.
Alberto Bietti and Julien Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. The Journal of Machine Learning Research, 20(1):876 924, 2019.
Avrim Blum and Ronald L Rivest. Training a 3-node neural network np-complete. Newral Networks, (1):117 127, 1992.
J.M. Borwein and A.S. Lewis. Conver Analysis and Nonlinear Optimization: Theory and Examples. CMS Books in Mathematics. Springer New York, 2005.
4Strictly speaking, we recovering a solution in superset of the vectors the linear weight.
11

---

Published in Transactions on Machine Learning Research (02/2024)
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Ricardo Cabral, Fernando De Torre, João P Costeira, and Alexandre Bernardino. Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition. In Proceedings of the IEEE international conference on computer vision, pp. 2488 2495, 2013.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 248 255, 2009.
Levent Eren, Turker Ince, and Serkan Kiranyaz. A generic intelligent bearing fault diagnosis system using compact adaptive 1d can classifier. Journal of Signal Processing Systems, 91(2):179 1197999999991111 2019.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of cmn architectures: Convex optimization of two-and three-layer networks in polynomial time. arXiv preprinl arxiv:2006. 198, 2020.
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31, 2018.
Shizhong Han, Zibo Meng, Ahmed-Shehab Khan, and Yan Tong. Incremental boosting convolutional neural network for facial action unit recognition. Advances in neural information processing systems, 29, 2016.
Wei He, Hongyan Zhang, Liangpei Zhang, and Huanfeng Shen. vitall low-rank matrix factorization for hyperspectral image restoration. IEEE transactions on geoscience and remote sensing, 54 (1):178-188, 2015.
André Heinrich. Fenchel duality-based algorithmss for convex oplimization problems with applications in machine learning and image restoration, PhD thesis, 03 2013.
Shawn Hershey, Sourish Chaudhuri, Daniel PW Ellis, Jort F Gemmeke, Aren Jansen, R Channing Moore, Manoj Plakal, Devin Platt, Rif Saurous, Bryan Seybold, et al. Cnn architectures for large-scale audio classification. In 2017 ieee international conference on acoustics, speech and signal processing (icassp), pp- 131-135. IEEE, 2017.
I. S. Isa, Z. Saad, S. Omar, M. K. Osman, K. A. Ahmad, and H. A. Mat Sakim. Suitable mlp network activation functions for breast cancer and thyroid disease detection. In Proceedings of the 2010 Second International Conference on Computational Intelligence, Modelling and Simulation, CIMSIM '10, pp. 39 44, USA, 2010. IEEE Computer Society.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Noural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenct classification with deop convolutional neural networks. Advances in neural information processing systems, 25, 2012.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278 22222224,77- 1998.
Sheng Li and Yun Fu. Learning robust and discriminative subspace with low-rank constraints. JEEE transactions on neural networks and learning systems, 27111):110-- 2015.
Julien Mairal, Piotr Koniusz, Zaid Harchaoui, and Cordelia Schmid. Convolutional kernel networks. Advances in neural information processing systems, 27, 2014.
Ashok Makkuva, Amirhossein Taghvaci, Sewoong Oh, and Jason Lee. Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning, pp. 6672 6681. PMLR, 2020.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-timc convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705, PMLR, 2020.
12

---

Published in Transactions on Machine Learning Research (02/2024)
Bernhard Schölkopf, Alexander J Smola, Francis Bach, et al. Learning with kernels: support vector machines, regularization, oplimizalion, and beyond. MTT press, 2002.
Shai Shalev-Shwarzz, Alon Gonen, and Ohad Shamir. Large-scale convex minimization with low-rank constraint. Xiv preprint
2011.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. The International Conference on Learning Representations (ICLR), 2015.
Josep M Sopena, Enrique Romero, and Rene Alquezar. Neural networks with periodic and monotonic activation functions: a comparative study in classification problems. Ninth International Conference on Artificial Newral Nelworks ICANN, 1999.
Kenji Suzuki. Overview of deep learning in medical imaging. Radiological physics and technology. 10(3): 257-273, 2017.
P. Tseng. Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications, 109(3):475 494, 2001.
Vladimir N. Vapnik. Statistical Learning Theory. John Wiley & Sons, 1998.
G Alistair Watson. Characterization of the subdifferential of some matrix norms. Linear algebra and its applications, 370(0):33 45, 1992.
Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
Rikiya Yamashita, Mizuho Nishio, Richard Kinh Gian Do, and Kaori Togashi. Convolutional neural networks: an overview and application in radiology. Insights into imaging, 9(4):611-68) 1e26611129,,,- 2018.
Hanbo Zhang, Xuguang Lan, Site Bai, Lipeng Wan, Chenjie Yang, and Nanning Zheng. A multi-task convolutional neural network for autonomous robotic grasping in object stacking scenes. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 6435-6442. IEEE, 2019.
Yuchen Zhang, Percy Liang, and Martin Wainwright. Convexifiod convolutional neural networks. In International Conference on Machine Learning, pp. 4044 4044-4053. PMLR, 2017.
Kai Zhong, Zhao Song, and Inderjit Dhillon. Learning non-overlapping convolutional neural networks with multiple kernels. Xie preprint Xiv:1171 151177100344 111000440, 2017.
13


Reviews:
[{"review_id": "05LK5vddUC", "reviewer": "Reviewer_HJQU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The problem formulation is clearly described, and the difference from the existing CCNN is evident.\n\nWeakness:\n\n1. The motivation is not clearly established. It's unclear how performance is affected by the hyperparameter rank.\n\n2. There are no theoretical explanations for why DCCNNs outperform CCNNs.\n\n3. While the performance is shown to be better than CCNN, which has been published for six years, it's challenging to identify its practical applications compared to state-of-the-art network architectures, such as the Transformer.\n\n4. No computational complexity comparison with CCNN.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is built upon the existing convexified convolutional neural networks to study the corresponding dual problem from an optimization perspective. The proposal algorithm reduces the computational overhead in constructing the kernel matrix. To overcome the sub-differential of nuclear norms, this paper proposed novel tools for recovering the linear weight and the output.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness:\n\n1. It would be beneficial to provide theoretical analysis or numerical justification for how the performance varies with different rank values. Additionally, it would be insightful to explain how the improved performance of DCCNNs is derived from finding an optimal rank through numerical experiments or theoretical analysis.\n\n2. We need theoretical explanations or intuitions to understand why DCCNNs outperform CCNNs.\n\n3. Highlighting real-world problems or applications where DCCNNs offer advantages over existing SOTA approaches would help clarify their practical utility and potential impact.\n\n4. Please report the computational time for each algorithm. \n\n5. (Questions.) It's worth noting that solving the nuclear norm problem can often be computationally inefficient. Therefore, it would greatly benefit the paper if the authors could provide more detailed explanations regarding the methods employed in their proposed algorithm.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W6VV8EGs8m", "reviewer": "Reviewer_BXpE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n+ This paper is well-written and nicely structured. It was relatively easy to read. \n+ The theoretical results appear mathematically sound, although I did not check every detail of their proofs. \n+ Moreover, the topic is a good match for TMLR.\n\n# Weaknesses\n+ Several changes would improve the writing and enhance its clarity. \n+ The authors overstate their contributions, as I detailed in the section below. The authors should address these comments before the paper can be accepted for publication.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the dual problem of Convexified CNNs, dubbed DCCNN. They show that considering DCCNNs has a couple of advantages over CNNs:\n+ As an intermediate step for CCNN, one needs to find a kernel matrix factorization. Such factorization is not unique (which, according to the authors, might cause problems). The DCCNN formulation works directly with the kernel matrix.\n+ The original CCNN paper obtained a low-rank solution by truncating an SVD. In this paper, the authors propose to include a nuclear norm regularizer to promote low-rankness. Further, they show that the DCCNN can automatically select the solution's rank without needing an additional hyperparameter.\n+ They propose an optimization algorithm that doesn't require explicitly forming the kernel matrix, which yields computational gains.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Major comments\n\n+ I am not sure I believe that the lack of uniqueness of the factorization $K = LL^\\top$ can cause problems. This is highlighted in the introduction as one of the paper's main contributions. However, using the QR factorization, one can easily see that any such factorization satisfies $L = RQ$ for some orthogonal $Q$ and some lower-triangular $R$. Thus, $K = RR^\\top$ is the *unique* Cholesky factorization. Thus, any factorization is the same up to an orthogonal change of coordinates. Moreover, the loss function in (3) is invariant under such a change of coordinates (if we simultaneously rotate $\\Phi(x_i)$ and $A$).\n+ I also do not buy the claim that DCCNNs bypass the need for the rank parameter $r$. The authors make this claim by finding a correspondence between the multiplicity of the eigenvalue $\\lambda = 1$ of a generic subdifferential at the solution and the rank of the solution. This correspondence is rather well-known (something similar happens with the subdifferential of the l_1 norm and the sparsity of a solution in compressed sensing). Further, to find their rank estimate, they have to compute an SVD of a dual matrix and evaluate how many singular values are equal to one, which is analogous to computing an SVD of the primal solution (3), and assess how many singular values are equal to one.\n+ The claim \"Our analysis in the DCCNN framework is novel. To derive the dual training program, the nuclear norm in the primal problem requires a careful construction of the Lagrangian through Fenchel conjugates\" is an exaggeration. Nobody has considered the dual problem before in this context, but taking the dual of a convex problem is a relatively standard and well-understood procedure. For instance, Theorem 1 follows as a corollary of Theorem 3.3.5 of Borwein and Lewis (https://carmamaths.org/resources/jon/Preprints/Books/CaNo2/cano2f.pdf).\n+ The authors claim that DCCNN is more efficient than CCNN. Their argument relies on the fact that they have an optimization algorithm that doesn't require forming the whole kernel matrix at once but only on smaller $p \\times p$ blocks. They include an algorithm to achieve this in the appendix. However, there is no proof of the correctness of their algorithm. Without such a result, the only provably correct way to solve this problem would be to use a vanilla interior point method, which would incur the same complexity as CCNN.\n+ The experiments need more details that should be in the body of the paper. For example, which solvers were used to solve the convex problems? What rank was used to truncate the SVD of CCNN? Where can readers find the code to reproduce the experiments? How much time did it take to train both CCNN and DCCNN?\n\n# Minor comments\nI use P4P3 to denote \"Page 4 Paragraph 3.\"\n+ P1P1 \"The performance of CNNs are so\" -> \"The performance of CNN is so.\"\n+ P1P1 Add citations to \"among others\".\n+ P1P2 Consider explaining what Q is used for. With the current wording, a first-time reader wouldn't understand the relevance of Q.\n+ P1P3 \"The factorization of the kernel matrix can be quite heuristic.\" This is a confusing sentence; consider changing it to \"The factorization of the kernel matrix is not unique.\"\n+ P2P1 \"catastrophic\" -> \"prohibitive.\"\n+ P3P1 About the comment: \"no closed-form expression that can be used to recover the primal solution from the dual solution directly because of the sub-differential of the nuclear norm.\" It is unclear that the cause it is truly the description of the subdifferential. I would avoid making claims that are not provable.\n+ P4P6 \"activation function can be contained\" -> \"activation function are contained.\"\n+ P4P6 \"could be a mapping to infinite dimensions\" -> \"could be a mapping to an infinite dimensional vector space.\"\n+ P6 Theorem 1 No need to include a sketch of the proof in the body of the paper (move it to the appendix if you want to keep it). Recognize that this is a standard result and cite accordingly.\n+ P6 Theorem 1 Why do you have a singular value of a scalar in (6)?\n+ P9P7 \"One can refer to Appendix F\" -> \"We refer the reader to Appendix F.\"\n+ P9P9 \"we provide the results\" -> \"we provide theoretical results.\"\n+ P11P5 \"optimized by SGD\" -> \"trained using SGD.\"", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AN77giu6wF", "reviewer": "Reviewer_1tmZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Major Strengths\n\n1. Solving the dual problem (6) is a novel idea that, as the authors point out has a number of computational benefits. This idea is possible by the introduction of the slackness $\\xi_i$  in problem (5) which is also clever. In all, this paper presents a novel and useful idea. \n2. The paper is very well written, and the concepts are introduced in a smooth way. The paper’s claims are correctly supported by both theoretical results and experiments. \n3. The proofs are correct and well-written. The appendix is easy to follow, and the notation is clear and unambiguous.\n4. The authors provide an extensive amount of analysis of their method. They analyze the computation required to run their method, and they provide training times. I would also suggest making their code available. \n\n## Major Weaknesses\n\n1. The authors claim that “The whole convexified approach allows for efficient and optimal training of the network, and from a theoretical point of view makes precise statistical analysis viable (Zhang et al., 2017).\" However, their method is an order of magnitude slower than SGD (table 2 page 28). The authors should soften this claim.\n2. The experiments show that the author's method is in the ballpark of state-of-the-art results. However, I believe that the details of the experimental setup should be given in the main body of the paper. The authors claim in the main body of the paper that their experiments were carried out in MNIST and ImageNet, but this is not entirely true:\n\n“**Data.** We use the MNIST (Lecun et al., 1998) and the ImageNet datasets (Deng et al., 2009) under the\nterms of the Creative Commons Attribution-Share Alike 3.0 license. In binary classification experiments,\nfor both the MNIST and ImageNet datasets, we randomly pick two classes, images of digit 2 versus 3 from\nMNIST, images containing tench versus bathroom tissue from ImageNet, and use 2000 images for training,\n100 images for validation, and 600 images for testing. We center crop the ImageNet images to [224,224] and\ntransfer the pixel value to [0, 1]. No other preprocessing is applied.\n”\n\nNo details on the multi-class classification are provided. How many classes do they consider? How many samples per class? \n\nA related question is, when the authors say that “We center crop the ImageNet images to [224,224] and\ntransfer the pixel value to [0, 1]. “ does this mean that the authors consider black and white images? \n\n3. A major limitation of these methods is the fact that they do not work on large datasets given that their complexity scales with the number of samples. The authors should provide a better explanation of why this work is relevant in a context where datasets have an increasing number of samples.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of solving Convexified Convolutional Neural Networks by their dual problem, the DCCNN. The paper introduces an equivalent problem for the CCNN, which can be dualized. The authors explore the computational benefits of the dual counterpart and show how to solve it and recover the primal solution. The authors provide numerical experiments that show that their method is competitive with existing methods. The paper presents a clever novel idea that leads to a more efficient way of obtaining CCNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Minor comments\n\n1. In the appendix, page 16, proof of Theorem 1, in the first line, $\\beta_i$ are introduced but never used. In the same proof, the proof \n2. Algorithm 2 in the appendix needs some rewriting. For example: add a “for all i” to line 2. Lines 11 and 14 are the same, they should be taken out of the “if”. \n3. In the experiment setting, could the authors provide an intuitive explanation on why the variance of their method is at least 3 times larger than SGD. Is this because of the initialization? “For the network structure similar to AlexNet on the ImageNet dataset, we observe a standard deviation of 2.5%, and for the architecture similar to VGG11, the standard deviation is 1.7%. For multiclass classification, the standard deviation of SGD is 0.5%. “\n4. The authors’ method considers a two-layer CNN for the theoretical results. However, in the experiments, they use AlexNet DCCNN, and VGG11 DCCNN. Given that AlexNet and VGG are not two-layer CNNs, I would suggest adding an explanation of how these are obtained. \n5. The authors claim that their method is “Our DCCNN framework is highly efficient. It operates without loading the full kernel matrix for all\nsamples in memory or introducing any unnecessary memory overhead of factorization. As a result,\nDCCNN inherits all the statistical benefits of convexified CNNs, while enjoying a much more efficient\nworkflow.” without providing numerical evidence or citations. The reader needs to go as far as Appendix G4 to find the proper comparison. I would suggest adding the values, and a reference to this section in the main body of the paper.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an interesting alternative to the method of (Zhang et al., 2017) by studying the dual problem of convexified convolutional neural networks. Most reviewers agree that this is a valuable contribution to the field, and are satisfied with the general manuscript and empirical results. One reviewer had special concerns regarding the comment, made throughout the manuscript, that the solution to the primal problem depends on chosen factorization for the kernel matrix. This has led to insightful discussions among reviewers and authors. 

Based on this discussion, I am recommending this paper be accepted with the following necessary revisions:
* The comments and suggestions made by all three reviewers should be incorporated, as the authors mentioned they would.
* Specific attention should be given to the motivation for this work based on the discussions arising from Reviewer BXpE. More precisely: the primal problem does not depend on the factorization of the kernel matrix (as the loss is invariant to it). The dependence on the factorization only appears once this factorization is truncated, which is needed for computational constraints (and thus the *algorithm* of Zhang et al does depend on the factorization chosen). The dual problem proposed in this work bypasses this limitation, thus representing a valuable alternative. 
* The manuscript should be revised for typos and format (the authors are highly encouraged to include a Concluding section that summarizes their contributions given prior work).
Decision: Accept (poster)