Global Neural Network Optimization via Convex Duality

This direction is merged into another direction: convex neural network reformulation, shallow architecture constraint. Its last version stays readable and citable here.

Version 1 of 148 papers53 conceptsfrozen 2026-10-04

Training a neural network is traditionally viewed as a high-stakes gamble in a non-convex landscape. Because the loss function of a standard multilayer perceptron is riddled with local minima and saddle points, practitioners rely on "voodoo" heuristics—specific random initializations, learning rate schedules, and batch normalization—to find a functional solution.

However, a growing body of research led by Mert Pilanci and Tolga Ergen suggests that this non-convexity is not an inherent property of the learning task, but rather a byproduct of how we parameterize the model. By applying convex duality and "lifting" the problem into a higher-dimensional space, these researchers have shown that training many common architectures can be reframed as a convex optimization problem, guaranteeing global optimality in polynomial time.

The Intuition of Lifting and Duality

The core idea behind this direction is that a non-convex problem in a low-dimensional space (the weights of the neurons) can often be mapped to a convex problem in a higher-dimensional space (the activations or "features").

In Convex Neural Networks, Yoshua Bengio and colleagues first demonstrated that if we allow the number of hidden units to be learned and apply $L^1$ regularization, the training of a shallow network becomes a convex problem. Modern work has refined this by using semi-infinite duality.

Instead of optimizing the weights directly, researchers like Tolga Ergen and Mert Pilanci show in Implicit Convex Regularizers of CNN Architectures that we can solve a dual problem where the variables represent the "patterns" the neurons pick up. This transformation reveals that neural networks are essentially performing a sophisticated form of feature selection, akin to a Group Lasso model.

ReLU Networks as Piecewise Linear Splines

The Rectified Linear Unit (ReLU) is the engine behind most modern networks. Its piecewise linear nature is what makes convex reformulations possible. Tolga Ergen and Mert Pilanci proved in Convex Geometry of Two-Layer ReLU Networks that these networks act as "data-adaptive convex autoencoders."

In this view, the optimal hidden neurons are not random; they are tied to the geometry of the input data. The convex reformulation identifies "arrangement patterns"—subsets of data points that are activated by the same ReLU unit. By optimizing over these patterns, the training process becomes a search for the best piecewise linear spline that fits the data, a task that Aaron Mishkin and Mert Pilanci have characterized as finding the optimal solution path of a constrained Lasso problem.

Extending to CNNs and Transformers

While the initial breakthroughs focused on simple two-layer networks, the framework has rapidly expanded to more complex architectures:

Why This Matters: Robustness and Efficiency

The move toward convex formulations isn't just a theoretical exercise; it solves several practical pain points in deep learning:

  1. Global Optimality: By using methods like Semidefinite Programming (SDP) relaxations or copositive programming, researchers can find the absolute best weights for a given architecture, eliminating the need for trial-and-error with random seeds.
  2. Adversarial Robustness: Standard adversarial training is a "cat-and-mouse" game of heuristics. Somayeh Sojoudi and Yatong Bai showed in Efficient Global Optimization of Two-layer ReLU Networks that convex reformulations allow for "robustness by design," where the model is mathematically guaranteed to be stable against attacks.
  3. Compression: Convex Distillation, introduced by Mert Pilanci and Prateek Varshney, allows for compressing deep networks into smaller, convex counterparts that are faster and more label-efficient.

The Challenge of Depth

The primary frontier for this research is the "depth barrier." Most exact convex reformulations currently apply to shallow architectures (two or three layers). As noted in Global Optimality Beyond Two Layers, extending these proofs to deep sequential chains of weight matrices is mathematically difficult because the nested non-linearities create increasingly complex mappings.

Current strategies involve breaking deep networks into convex sub-networks or using Gaussian relaxations to approximate the global optimum of deeper structures in polynomial time. The ultimate goal is a unified theory that treats every layer of a deep model as a single, holistic convex optimization problem.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_neural_network_optimization_via_c_c00b4a15,
  title = {Global Neural Network Optimization via Convex Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-neural-network-optimization-via-convex-duality/rdr_c00b4a15f621476997eba0274356026e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_neural_network_optimization_via_c_c00b4a15_v1,
  title = {Global Neural Network Optimization via Convex Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-neural-network-optimization-via-convex-duality/rdr_c00b4a15f621476997eba0274356026e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}