Deep neural networks (DNNs), particularly those using Rectified Linear Unit (ReLU) activation functions, have achieved remarkable success across diverse machine learning tasks, including image recognition, audio processing, and language modeling. Despite this success, the non-convex nature of DNN loss functions complicates optimization and limits theoretical understanding. In this paper, we highlight how recently developed convex equivalences of ReLU NNs and their connections to sparse signal processing models can address the challenges of training and understanding NNs. Recent research has uncovered several hidden convexities in the loss landscapes of certain NN architectures, notably two-layer ReLU networks and other deeper or varied architectures. This paper seeks to provide an accessible and educational overview that bridges recent advances in the mathematics of deep learning with traditional signal processing, encouraging broader signal processing applications.
Figures & tables
Convexity w.r.t:
Approach
Motivation/Technique
Relation to SP
outer-layer weights [ 15 ]
column generation
boosting
matching pursuit
parameters [ 7 ]
convex duality, Lasso
hyperplane arrangements zonotopes
sparse recovery, 1-bit CS [ 9 ]
probability measures [ 23 , 24 ]
mean field integration
neural tangent kernel (NTK) [ 25 ]
kernel methods [ 26 ]
network output [ 4 ]
shift complexity to regularization
matrix factorization, nuclear norm [ 18 ]
CS: robust PCA [ 20 ] matrix completion [ 19 ]
quantized weights [ 27 ]
linear program
intersection graph analysis
graphical models [ 28 ]
TABLE I : Comparison of convex perspectives on NNs. Each approach is motivated by, or involves, techniques related to signal processing (SP). The approaches in the first two rows also involve ℓ1 regularizations, linking them to sparse representations in signal processing.
Fig. 1 : Illustration of a separating hyperplane (left plot) and an activation chamber (right plot).
Fig. 5 : Experimental results comparing 2 -layer NN training with non-convex and convex formulations.
Fig. 6 : Two-layer ReLU NN trained with SGD versus convex model on ECG data (reproduced from [ 32 ] ). Convex training achieves lower training loss ( 6(a) ) and better test performance ( 6(b) ) compared to SGD. The convex model shows that NNs are local linear models that can adapt to different data regions ( 6(c) ), ( 6(d) ).
Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.
Classical ReLU-based Input Convex Neural Networks (ICNNs) are equivalent to the optimal value functions of Linear Programming (LP). This intrinsic structural equivalence restricts their representational capacity to piecewise-linear polyhedral functions. To overcome this representational bottleneck, we propose the SOC-ICNN, an architecture that generalizes the underlying optimization class from LP to Second-Order Cone Programming (SOCP). By explicitly injecting positive semi-definite curvature and Euclidean norm-based conic primitives, our formulation introduces native smooth curvature into the representation while preserving a rigorous optimization-theoretic interpretation. We formally prove that SOC-ICNNs strictly expand the representational space of ReLU-ICNNs without increasing the asymptotic order of forward-pass complexity. Extensive experiments demonstrate that SOC-ICNN substantially improves function approximation, while delivering competitive downstream decision quality. The code is available at https://anonymous.4open.science/r/SOC-ICNN-4B18/.
Kang Liu, Jianchen Hu, Wei Peng
School of Future Technology Xi’an Jiaotong University Xi’an, China · School of Future Technology School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China · School of Automation Science and Engineering Xi’an Jiaotong University Xi’an, China
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.
The architecture of deep feedforward neural networks is ubiquitous in deep learning, either as a whole system or as a subnetwork of other architectures, and thus its mechanism is a key ingredient of the black box of neural networks. On the basis of the simplest two-layer ReLU network, this paper systematically studies the mechanism of deep feedforward ReLU networks with multiple hidden layers and successfully explains the training solution obtained by the back-propagation algorithm. The concept of a path, especially in terms of the relationships between paths, plays a central role in uncovering the mystery of the black box. It is shown that a unit of a deep ReLU network can form a piecewise linear manifold to divide the input space, instead of a hyperplane of the two-layer case. How to efficiently use the hidden-layer units to produce both linear functions and partitions of the input space is also a central problem. The principles of a two-layer ReLU network can be generalized to the deeper case to a large extent, such as multiple strict partial orders and continuity restriction. The combination of the basic and simple principles proposed can yield complicated instantiations including the training solutions, and in this sense the black box of deep feedforward ReLU networks is revealed.
Changcun Huang
Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C