Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective

Emi Zeger; Mert Pilanci

cs.LGMar 25, 2026

Unveiling Hidden Convexity in Deep Learning: a Sparse Signal Processing Perspective

Authors: Emi Zeger, Mert Pilanci

Organizations: Department of Electrical Engineering, Stanford University

Abstract

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

\ell_{1}

regularizations, linking them to sparse representations in signal processing.

Panel of Figure 2 — Fig. 1 : Illustration of a separating hyperplane (left plot) and an activation chamber (right plot).

Panel of Figure 3 — Fig. 4 : Wedge product in geometric algebra [ 21 ] .

Panel of Figure 4 — Fig. 5 : Experimental results comparing $2$ -layer NN training with non-convex and convex formulations.

Panel of Figure 5 — 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) ).

ReLU Neural Networks

Rectified linear unit (ReLU) neural networks use piecewise-linear activations to study approximation, learning dynamics, expressivity, and verification.

See all 111 papers

SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions
Apr 24, 2026Kang Liu, Jianchen Hu, Wei PengNeural Surrogate Modeling Second-Order Cone Programming
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
Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting
May 17, 2026Karthik Prakhya, Alp YurtseverNeural Network Optimization Deep Linear Networks
Umeå University, Sweden
On the Principles of Deep Feedforward ReLU Networks
Jul 8, 2026Changcun HuangReLU Neural Networks Neural Network Interpretability
Shuitu Institute of Applied Mathematics, Chongqing 400700, P.R.C

Apr 24, 2026J/K move · Enter open · S save

SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions

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

Neural Surrogate Modeling Second-Order Cone Programming Input Convex Neural Networks Neural Network Approximation Theory

Open paper AskPDF arXiv

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/.

Abstract

ReLU Neural Networks

Explore similar work

SOC-ICNN: From Polyhedral to Conic Geometry for Learning Convex Surrogate Functions

Exact Convex Reformulations of Linear Neural Networks via Completely Positive Lifting

On the Principles of Deep Feedforward ReLU Networks