Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
For theorists studying nonconvex optimization in deep learning, this work offers an exact convex reformulation that clarifies the nature of nonconvexity in linear networks, though it is incremental as it does not yield practical algorithms.
The paper proves that training deep linear neural networks under squared loss can be exactly reformulated as a convex problem over a completely positive cone, with lifted dimension independent of depth and data size. This reformulation is computationally intractable but provides a theoretical connection between nonconvex neural network training and copositive programming.
We show that the training problem of a deep linear neural network under the squared loss admits an exact convex reformulation in a lifted space over a generalized completely positive cone. The reformulation has the same optimal value as the original nonconvex problem and is linear in the lifted variables, with all nonconvexity encoded in the cone constraint. Its ambient lifted dimension depends only on the input and output dimensions, independent of the network depth and the number of data points, and the bottleneck width enters only through scalar constraints. The construction proceeds by reducing the multilayer parameterization to a bilinear factorization, lifting it to a rank-constrained semidefinite program, expressing the rank constraint via a complementarity condition, and applying a completely positive lifting. While the resulting formulation is computationally intractable in general, it gives an exact conic representation of the nonconvexity induced by linear factorization and connects linear neural network training with copositive programming.