Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
Abstract
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. The resulting formulation gives a conic representation of the nonconvexity induced by linear factorization and connects linear neural network training with copositive programming.
Related
- A Bilevel Market Equilibrium Model for Natural Gas Pipeline Network Operations: Convex Relaxations and Single-level Reformulations
- Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
- Some properties of completely convex functions
- On Completely Positive and Semidefinite Programs for Moment Bounds on Maximum of Random Quadratics
- Poisson actions of noncompact locally compact sofic groups have completely positive sofic entropy
BibTeX
@misc{prakhya2026exact,
title = {{Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting}},
author = {Karthik Prakhya and Alp Yurtsever},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.17692},
eprint = {2605.17692},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.17692},
}
RIS
TY - UNPB
TI - Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
AU - Karthik Prakhya
AU - Alp Yurtsever
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2605.17692
UR - https://arxiv.org/abs/2605.17692
AB - 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. The resulting formulation gives a conic representation of the nonconvexity induced by linear factorization and connects linear neural network training with copositive programming.
ER -