Parallel Deep Neural Networks Have Zero Duality Gap
This work addresses the fundamental challenge of non-convexity in deep learning optimization, providing theoretical guarantees for global optimality in training deep networks, which is incremental but impactful for the field.
The paper tackled the problem of non-convex optimization in training deep neural networks by proving that zero duality gap (strong duality) can be achieved for deep networks using a parallel architecture with modified regularization, enabling globally optimal training. It also demonstrated that weight decay encourages low-rank solutions and extended results to three-layer ReLU networks under specific conditions.
Training deep neural networks is a challenging non-convex optimization problem. Recent work has proven that the strong duality holds (which means zero duality gap) for regularized finite-width two-layer ReLU networks and consequently provided an equivalent convex training problem. However, extending this result to deeper networks remains to be an open problem. In this paper, we prove that the duality gap for deeper linear networks with vector outputs is non-zero. In contrast, we show that the zero duality gap can be obtained by stacking standard deep networks in parallel, which we call a parallel architecture, and modifying the regularization. Therefore, we prove the strong duality and existence of equivalent convex problems that enable globally optimal training of deep networks. As a by-product of our analysis, we demonstrate that the weight decay regularization on the network parameters explicitly encourages low-rank solutions via closed-form expressions. In addition, we show that strong duality holds for three-layer standard ReLU networks given rank-1 data matrices.