  We propose the framework of dual convexified convolutional neural networks
(DCCNNs). In this framework, we first 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.
