Convex Reformulations for Neural Network Optimization

412 concepts177 papers1 proposal

Training deep neural networks often feels like navigating a rugged mountain range in a dense fog. Because the standard loss landscape is highly non-convex, optimization algorithms like Stochastic Gradient Descent (SGD) can easily get trapped in suboptimal local minima or saddle points. This forces practitioners into an "initialization lottery," where the final performance of a model depends heavily on a lucky random seed.

However, a powerful alternative paradigm has emerged: convex neural network reformulation. By changing how we represent the network's parameters or data space, we can flatten this chaotic landscape entirely, transforming non-convex training objectives into convex ones where global optimality is mathematically guaranteed.

The Intuition of Lifting: Shifting to Measure Space

To understand why standard neural network training is non-convex, consider a simple two-layer network. The output is a combination of weights multiplying non-linear activations:

$$f(x) = \sum_{i=1}^m v_i \sigma(w_i^T x)$$

Because we must optimize both the inner weights $w_i$ and the outer weights $v_i$ simultaneously, their interaction creates a highly non-linear, non-convex optimization landscape.

The core insight of convex reformulation is to change the variables we optimize over. Instead of searching for individual point weights in a low-dimensional space, we can "lift" the problem into a higher-dimensional space of functions or probability distributions.

In a foundational paper, Bengio et al. demonstrated that if we treat the hidden units as an infinite feature space and apply sparsity-inducing $L^1$ regularization to the output weights, the training problem becomes convex. Instead of optimizing individual parameters, the optimization process learns a probability measure over the space of all possible hidden units. Because the relationship between this measure and the model output is linear, minimizing a convex loss function over this space guarantees that the training process can reach a global optimum.

This strategy of lifting parameters to probability measures is exceptionally versatile. For instance, in reinforcement learning, policy optimization is notoriously non-convex when parameterized directly by neural network weights. However, Zhang et al. showed that by lifting the objective into the infinite-dimensional space of probability measures and framing it as a Wasserstein Gradient Flow, the landscape becomes convex. Similarly, when analyzing infinitely wide networks in the mean-field regime, Leahy et al. and Akiyama et al. proved that treating network training as a distribution or Radon measure over parameter space allows researchers to apply convex analysis tools to guarantee global convergence.

Duality and the Geometry of Activation Patterns

While lifting to an infinite-dimensional measure space provides beautiful theoretical guarantees, how do we make this practical for finite datasets and real-world architectures? The answer lies in the geometry of activation functions like the Rectified Linear Unit (ReLU).

A ReLU neuron splits the input space into two distinct regions: one where it fires (positive output) and one where it remains silent (zero output). For a fixed dataset of $n$ samples, a network's hidden neurons can only generate a finite, combinatorial number of "activation patterns" (vectors of signs indicating which data points activate which neurons).

Arora et al. demonstrated that finding the globally optimal weights for a two-layer ReLU network can be reframed as a combinatorial search over these activation patterns. Once the specific set of neurons activated by each data point is determined, the remaining weight optimization becomes a straightforward convex problem that can be solved to global optimality.

Standard Non-Convex Optimization:
[Weights w_i, v_i] ---> Highly chaotic landscape with local minima

Convex Dual Reformulation:
[Data Samples] ---> Determine Activation Patterns ---> [Convex Program (e.g., SOCP)] ---> Global Optimum

Building on this geometric intuition, Pilanci et al. applied semi-infinite duality to show that training a finite-width two-layer ReLU network with weight decay is mathematically equivalent to a finite-dimensional convex program—specifically, a second-order cone program (SOCP).

By mapping the original weight space into a convex dual space via these data-dependent activation patterns, the authors proved that the global optimum can be reached in polynomial time relative to the number of training samples and neurons. This framework was later extended by Ergen et al. to shallow convolutional neural networks (CNNs), proving that the non-convexity of standard CNN training objectives does not preclude finding the best possible weights through standard convex solvers.

Gated Models: Eliminating the Initialization Lottery

To bypass the combinatorial complexity of searching over all possible activation patterns, researchers introduced "gated" ReLU models. In a gated model, the activation patterns are fixed at initialization using gate vectors derived from the data or a teacher model.

As shown by Mishkin et al., fixing these gates allows the training objective of a two-layer ReLU network to be solved as a high-dimensional Group Lasso problem. Because Group Lasso is inherently convex, this transformation completely eliminates the variance caused by random initialization. A specific dataset and hyperparameter set will consistently yield the exact same globally optimal model, removing the "model churn" typical of stochastic gradient descent.

This gated convex mechanism has unlocked new capabilities across several deep learning subfields:

  • Model Compression: Pilanci et al. introduced Convex Distillation, which replaces non-convex neural network blocks with simpler convex counterparts by matching the activation gates of a teacher model, enabling highly efficient, label-free compression.
  • Implicit Neural Representations: Sivgin et al. applied fixed gating patterns to 3D coordinate-based networks, allowing implicit neural volumes to be trained with global optimality guarantees and eliminating the "initialization lottery" in 3D reconstruction.
  • Bayesian Sampling: Wang et al. reframed the non-convex task of training neural networks to approximate gradient directions in Wasserstein flows as a convex semi-definite program (SDP), eliminating sensitivity to random initialization.

By shifting our perspective from the chaotic parameter space of individual weights to the structured spaces of dual variables, activation patterns, and probability measures, convex reformulations reveal that the notorious difficulty of neural network optimization is not an insurmountable law of nature, but an artifact of how we choose to write down the problem.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 213 papers
  2. Version 1 · 2026-10-04 · 223 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_convex_neural_network_reformulation_7e4a5f0c,
  title = {convex neural network reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convex-neural-network-reformulation/rdr_7e4a5f0c09d04c739fefa255ea02a51d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_convex_neural_network_reformulation_7e4a5f0c_v2,
  title = {convex neural network reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convex-neural-network-reformulation/rdr_7e4a5f0c09d04c739fefa255ea02a51d/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake