Standard deep learning is built on a paradox: we optimize highly non-convex loss landscapes using simple gradient-based heuristics, yet we consistently find solutions that generalize well. For years, this success was attributed to "optimization luck" or the mysterious properties of high-dimensional spaces. However, a growing body of research suggests that neural network training is not inherently non-convex. By changing our perspective—specifically by "lifting" the problem into higher-dimensional spaces or applying convex duality—we can reformulate neural network training as a convex optimization problem with a guaranteed global optimum.
The Problem of Non-Convexity
In a traditional neural network, the loss function is non-convex with respect to the weights. This leads to several practical headaches:
- Initialization Sensitivity: A "bad" random seed can trap the model in a poor local minimum.
- Model Churn: As noted by Aaron Mishkin and Arda Sahiner in Fast Convex Optimization for Two-Layer ReLU Networks, retrained models often make different predictions even on the same data, complicating deployment.
- Hyperparameter Voodoo: Finding the right learning rate and schedule often feels more like alchemy than engineering.
The convex reformulation approach seeks to eliminate these issues by proving that for many common architectures, there exists an equivalent convex problem that shares the same global minimum as the original non-convex task.
Lifting and Infinite-Dimensional Spaces
The earliest insights into this direction came from treating neural networks as ensembles of infinite features. In Convex Neural Networks, Yoshua Bengio and colleagues demonstrated that if we allow the number of hidden units to grow and apply $L^1$ regularization, the training problem becomes convex in the space of hidden units.
Francis Bach expanded on this in Breaking the Curse of Dimensionality with Convex Neural Networks, showing that single-hidden-layer networks can be viewed as an infinite-dimensional convex problem. By treating hidden units as a continuous measure, the network can automatically adapt to low-dimensional structures in high-dimensional data, bypassing the local minima that plague standard training.
The Geometry of ReLU Activation Patterns
A breakthrough in making these theories practical for finite networks came from analyzing the "activation patterns" of Rectified Linear Units (ReLU). For any given dataset, a ReLU neuron is either "on" or "off" for each data point. This creates a set of linear partitions of the data.
Raman Arora and Amitabh Basu proved in Understanding Deep Neural Networks with Rectified Linear Units that if these activation patterns are known, the remaining weight optimization is a simple convex problem. They showed that one can theoretically iterate through all possible hyperplane arrangements to find the global optimum in polynomial time relative to the number of data points.
Tolga Ergen and Mert Pilanci formalized this into a dual optimization framework. In Convex Geometry and Duality of Over-parameterized Neural Networks, they demonstrated that training a two-layer ReLU network with weight decay is exactly equivalent to a convex program—specifically a variant of the Group Lasso problem. In this view, the "hidden neurons" are actually data-adaptive features that the convex solver selects to minimize the error.
Global Optimality for Complex Architectures
This convex lens has been extended far beyond simple two-layer MLP models:
- Convolutional Neural Networks (CNNs): In Implicit Convex Regularizers of CNN Architectures, Ergen and Pilanci showed that pooling and convolution layers act as specific convex regularizers (like nuclear norms), allowing shallow CNNs to be globally optimized.
- Batch Normalization: Demystifying Batch Normalization in ReLU Networks reveals that training with Batch Norm is equivalent to solving a convex problem over "whitened" data matrices, providing a rigorous explanation for why it stabilizes training.
- Vector Outputs: Arda Sahiner and colleagues proved in Vector-output ReLU Neural Network Problems are Copositive Programs that multi-output networks can be framed as copositive programs, a class of convex problems that can be solved via semidefinite programming (SDP) relaxations.
Why It Works: The Intuition of "Lifting"
The core intuition behind these reformulations is lifting. Imagine trying to find the lowest point in a crumpled piece of paper (a non-convex landscape). It's easy to get stuck in a fold. However, if you "lift" that paper into a higher-dimensional space where it is no longer crumpled but stretched flat, the "lowest point" becomes a simple, global target.
In neural networks, the "crumpling" is caused by the interaction between weights in different layers. By reparameterizing the network—often by focusing on the product of weights or the activation patterns—researchers like Mert Pilanci transform the problem into a space where the objective function is a "bowl" (convex). As Vivek Borkar argues in Asymptotic convexity of wide and shallow neural networks, as networks get wider, their landscapes naturally "smooth out" and resemble a convex hull, explaining why over-parameterization makes training easier rather than harder.
Practical Implications
Beyond theoretical elegance, this research direction offers practical tools:
- Interpretability: Mert Pilanci showed in Analytical Expressions of Deep Neural Network Weights that optimal weights are not random, but are analytical expressions of the training data's geometry (wedge products).
- Efficiency: Convex Distillation allows for compressing deep networks by matching activations using convex blocks, bypassing the need for expensive non-convex retraining.
- Guarantees: Frameworks like Principled Deep Neural Network Training through Linear Programming by Gonzalo Muñoz provide "optimality certificates"—mathematical proof that a specific training loss is the absolute lowest possible for that architecture.