Convex Relaxations of Convolutional Neural Nets

ABSTRACT We propose convex relaxations for convolutional neural nets with one hidden layer where the output weights are fixed. For convex activation functions such as rectified linear units, the relaxations are convex second order cone programs which can be solved very efficiently. We prove that the relaxation recovers the global minimum under a planted model assumption, given sufficiently many training samples from a Gaussian distribution. We also identify a phase transition phenomenon in recovering the global minimum for the relaxation. Index Terms -- Convolutional neural networks, convex relaxations, linear programming, deep learning 1. INTRODUCTION Convolutional neural networks (CNNs) have been extremely successful across many domains in machine learning and computer vision [14, 15].