  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.
