Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting

• URL: http://arxiv.org/abs/2605.17692v1
• Date: Sun, 17 May 2026 23:20:50 GMT
• Title: Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
• Abstract summary: We show that the problem of a deep linear network under the loss admits an exact reformulation in a lifted space cone.<n>While the resulting neural representation is intractable, it connects a linear factor with copositive programming.
• Score: 7.433931244705935
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. 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.

Related papers

• Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse [16.78534503577613]
  We show that the input weights and biases align along finitely many directions, leading to an effective width collapse.<n>We establish a non-redundancy property of the learned representation by proving that each learned direction induces a unique ternary activation pattern on the training data.
  arXiv  Detail & Related papers  (2026-07-03T22:03:13Z)
• A Convex Quasilinearization Method for Solving Nonlinear PDEs with Physics-Informed Neural Networks [0.0]
  We present a numerical method for the forward solution of nonlinear partial differential equations (PDEs)<n>The method, LiL-Q, is assessed on seven benchmarks, including systems (planestrain elasticity and the incompressible Navier-Stokes equations in two and three dimensions) and steady flow with heterogeneous permeability.
  arXiv  Detail & Related papers  (2026-06-16T17:09:59Z)
• D-Convexity: A Unified Differentiable Convex Shape Prior via Quasi-Concavity for Data-driven Image Segmentation [5.445483153964301]
  Convexity is a fundamental geometric prior that underlies many natural and man-made structures.<n>We propose a unified, threshold-free convexity prior based on the quasi-concavity of the network's output mask function u.<n>Our analysis unifies a wide spectrum of previous convex shape models, from discrete 1-0-1 line constraints to curvature or signed distance Laplacian based level-set priors.
  arXiv  Detail & Related papers  (2026-05-19T00:27:41Z)
• Neural Networks as Local-to-Global Computations [0.0]
  We construct a sheaf from any ReLU neural network by encoding each computational step as a restriction map on an edge.<n>Unlike the forward pass, the heat equation propagates information bidirectionally across layers, enabling pinned neurons that impose constraints in both directions.<n>We validate the framework experimentally on small synthetic tasks, confirming the convergence theorems and demonstrating that sheaf-based training, while not yet competitive with gradient descent, obeys quantitative scaling laws predicted by the theory.
  arXiv  Detail & Related papers  (2026-03-16T05:23:31Z)
• GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent [12.409030267572243]
  We first reformulate the neural network output projection problem as an entropy-regularized linear programming problem. Based on an accelerated gradient descent algorithm with numerical performance enhancement, we present our architecture, GLinSAT, to solve the problem. This is the first general linear satisfiability layer in which all the operations are differentiable and matrix-factorization-free.
  arXiv  Detail & Related papers  (2024-09-26T03:12:53Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Error-Correcting Neural Networks for Two-Dimensional Curvature Computation in the Level-Set Method [0.0]
  We present an error-neural-modeling-based strategy for approximating two-dimensional curvature in the level-set method. Our main contribution is a redesigned hybrid solver that relies on numerical schemes to enable machine-learning operations on demand.
  arXiv  Detail & Related papers  (2022-01-22T05:14:40Z)
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines [63.011641517977644]
  We take a deep network and convert it to an equivalent (indefinite) kernel machine. We then investigate the implications of this transformation for capacity control and uniform convergence. Finally, we analyse the sparsity properties of the flat representation, showing that the flat weights are (effectively) Lp-"norm" regularised with 0p1.
  arXiv  Detail & Related papers  (2020-07-15T03:21:35Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)
• Revealing the Structure of Deep Neural Networks via Convex Duality [70.15611146583068]
  We study regularized deep neural networks (DNNs) and introduce a convex analytic framework to characterize the structure of hidden layers. We show that a set of optimal hidden layer weights for a norm regularized training problem can be explicitly found as the extreme points of a convex set. We apply the same characterization to deep ReLU networks with whitened data and prove the same weight alignment holds.
  arXiv  Detail & Related papers  (2020-02-22T21:13:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.