Parallel Deep Neural Networks Have Zero Duality Gap
  Training deep neural networks is a well-known highly non-convex problem. In
recent works, it is shown that there is no duality gap for regularized
two-layer neural networks with ReLU activation, which enables global
optimization via convex programs. For multi-layer linear networks with vector
outputs, we formulate convex dual problems and demonstrate that the duality gap
is non-zero for depth three and deeper networks. However, by modifying the deep
networks to more powerful parallel architectures, we show that the duality gap
is exactly zero. Therefore, strong convex duality holds, and hence there exist
equivalent convex programs that enable training deep networks to global
optimality. We also demonstrate that the weight decay regularization in the
parameters explicitly encourages low-rank solutions via closed-form
expressions. For three-layer non-parallel ReLU networks, we show that strong
duality holds for rank-1 data matrices, however, the duality gap is non-zero
for whitened data matrices. Similarly, by transforming the neural network
architecture into a corresponding parallel version, the duality gap vanishes.
