Training deep neural networks is traditionally understood as a non-convex optimization problem. When we train a network using standard backpropagation, we navigate a highly complex loss landscape filled with local minima, saddle points, and sharp valleys. To find a good solution, practitioners must rely on stochastic gradient descent (SGD), careful weight initialization, and extensive hyperparameter tuning.
However, a powerful alternative perspective has emerged: under certain conditions, neural network training can be exactly reformulated as a convex optimization problem. By transforming the mathematical structure of the network, we can bypass the non-convex wilderness entirely, guaranteeing global optimality in polynomial time.
While this framework provides elegant theoretical guarantees and robust training paths, it faces a fundamental bottleneck known as the shallow architecture constraint. Convex reformulations work remarkably well for shallow, two-layer networks, but scaling them to deep, multi-layer architectures introduces severe mathematical and geometric challenges.
The Intuition: Convex Lifting and Activation Cones
To understand why a non-convex neural network can be trained via convex optimization, we must look at how non-linearities interact with data. Consider a standard two-layer Rectified Linear Unit (ReLU) network. The non-convexity arises because the network multiplies the hidden layer weights by the output layer weights, all while passing the inputs through a non-linear activation function.
The key insight, formalized by Pilanci et al. in their seminal work on convex regularizers, is that for a fixed dataset, the ReLU activation function partitions the input space into a finite number of linear regions, or activation cones. Within any single cone, the activation behavior of a neuron is fixed: it is either completely on (acting as a linear pass-through) or completely off (outputting zero).
If we can enumerate or bound these activation patterns, we can perform a maneuver called convex lifting. Instead of optimizing the weights directly in their original, non-convex space, we "lift" the problem into a higher-dimensional space defined by these activation cones.
Non-Convex Space (Low Dim) Convex Lifted Space (High Dim)
Weights interact non-linearly Separated into fixed activation cones
[W1] -> [ReLU] -> [W2] ===> Optimized globally via linear/LASSO constraints
(Trapped in local minima) (Guaranteed global optimum)
In this lifted space, the training problem can be rewritten as a single, finite-dimensional convex program—specifically, a group-sparse regularization problem similar to the LASSO. This means that finding the globally optimal weights for a two-layer ReLU network is not only possible, but can be achieved in polynomial time (Pilanci et al.).
This core mechanism has been successfully extended across several shallow modeling paradigms:
- Alternative Activations: Ergen et al. demonstrated that this framework applies to non-differentiable threshold (step) activation functions, bypassing zero-gradient issues entirely by solving an equivalent LASSO-style convex problem (Ergen et al.).
- Algorithmic Speedups: To make these high-dimensional representations practical, Sojoudi et al. introduced quadratic-time Alternating Direction Method of Multipliers (ADMM) algorithms, extending the convex formulation to robust adversarial training (Sojoudi et al.).
- Statistical Clustering: Bartan et al. applied convex lifting to statistical clustering, developing Neural Fisher Discriminant Analysis (NFDA) to find globally optimal two-layer embeddings without backpropagation (Bartan et al.).
The Shallow Architecture Constraint
If convex lifting is so powerful, why do we not use it to train state-of-the-art deep networks? The answer lies in the shallow architecture constraint.
The mathematical machinery of convex reformulations relies entirely on the fact that the input data matrix $X$ is fixed and known. Because $X$ is static, the hyperplane arrangements that dictate the activation cones are also static. We can pre-compute or systematically sample the regions where neurons turn on and off.
In a deep, multi-layer network, this property breaks down completely due to nested non-linearities.
$$\text{Layer 1:} \quad H_1 = \sigma(X W_1)$$ $$\text{Layer 2:} \quad H_2 = \sigma(H_1 W_2) = \sigma(\sigma(X W_1) W_2)$$
The input to the second hidden layer is no longer the static data matrix $X$; it is the output of the first hidden layer, $H_1$, which changes dynamically as the weights $W_1$ are optimized. Because the inputs to deeper layers are parameterized by the weights of preceding layers, the activation cones are no longer fixed. They shift, warp, and interact non-linearly during optimization.
As Kim et al. note, this compounding complexity makes establishing strong duality for standard sequential architectures mathematically intractable (Kim et al.). The moment a network possesses more than one hidden layer, the optimization geometry becomes significantly more complex, preventing a straightforward convex dual representation (Sahiner et al.).
Architectural Workarounds and Frontiers
To push past the shallow architecture constraint, researchers have developed specialized strategies that either modify the network's structure or isolate the convex optimization to specific blocks.
Multi-Path vs. Sequential Architectures
One way to achieve a tractable convex dual in deeper models is to abandon traditional sequential chains. Ergen et al. showed that while standard deep sequential networks resist exact convex dualization, modifying the architecture into multi-path parallel structures allows researchers to maintain strong duality and characterize optimal weights as extreme points of a convex set (Ergen et al.).
Copositive Programming for Vector Outputs
Early convex reformulations were restricted to scalar-output models, such as binary classification. Scaling to multi-class classification requires vector outputs, which fundamentally alters the optimization geometry. To address this, Sahiner et al. leveraged copositive programming, providing a convex framework for vector-output two-layer networks, though extending this to deep multi-layer structures remains an open challenge (Sahiner et al.).
Block-Wise Convex Distillation
Because end-to-end convex training of deep networks is currently blocked by nested non-linearities, some approaches apply convex optimization locally. Pilanci et al. introduced Convex Distillation, a framework that compresses deep networks by breaking them into smaller, manageable blocks and replacing those blocks with convex counterparts (Pilanci et al.). By matching intermediate activations rather than final labels, they achieve efficient, label-free distillation within the bounds of shallow convex theory.
Final-Layer Optimization
Other methods accept the non-convexity of intermediate layers and focus purely on the final layer, where the optimization remains linear. For instance, the "Optimum Shifting" method introduced by Zhou et al. minimizes sharpness and improves generalization by treating the final fully-connected layer as an under-determined linear system (Zhou et al.). Like exact reformulations, extending these closed-form mathematical mechanisms to intermediate convolutional layers remains an unsolved challenge.
Summary
Convex reformulations prove that neural network training does not have to be a non-convex guessing game. By lifting parameters into a higher-dimensional space structured by activation cones, we can achieve guaranteed global optimality. However, the shallow architecture constraint remains the defining boundary of the field: until optimization theory finds a way to elegantly dualize the nested dependencies of sequential layers, the full power of exact convex training remains concentrated in shallow architectures.
Key Foundational Work
Convex Neural Networks (2005) — contributed 1 concept elements to this direction.
Inductive Two-layer Modeling with Parametric Bregman Transfer (2018) — contributed 1 concept elements to this direction.