Global Optimization of ReLU Networks via Semi-Infinite Duality

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

Version 1 of 122 papers23 conceptsfrozen 2026-10-04

Training a neural network is traditionally viewed as a "dark art." Because the loss landscape of a deep network is non-convex, practitioners rely on stochastic gradient descent (SGD), careful initialization, and extensive hyperparameter tuning to avoid getting stuck in poor local minima. We know it works, but we often don't know if we've found the best possible model or what specific "simplicity" the network is biased toward.

A growing body of research, led largely by Mert Pilancı and his collaborators, has revealed that this non-convexity is not an inherent property of the learning task, but rather a consequence of how we parameterize the model. By applying tools from semi-infinite duality, these researchers have shown that training ReLU networks can be transformed into exact convex optimization problems, providing a path to global optimality and a clearer understanding of neural network geometry.

The Core Insight: Lifting to Convexity

The fundamental difficulty in training a ReLU network lies in the product of weights across layers (e.g., $W_2 \sigma(W_1 x)$). This interaction makes the objective function non-convex. However, Tolga Ergen and Mert Pilancı demonstrated in Convex Geometry and Duality of Over-parameterized Neural Networks that we can "lift" this problem into a higher-dimensional space where it becomes convex.

The trick involves looking at the dual problem. By using the dual of the neural network training objective, the researchers found that the optimal weights are actually solutions to a constrained convex program. In this view, the network isn't just a black box; it is a machine that finds the "simplest" function (often a linear spline) that fits the data under a specific regularizer.

Hyperplane Arrangements and the Geometry of ReLU

Why does this transformation work? The intuition lies in how ReLU activations partition the input space. A ReLU function $\max(0, wx)$ is either "on" or "off" depending on which side of a hyperplane the input $x$ falls.

For a fixed dataset, there are only a finite number of ways to partition the data points using these hyperplanes. These are known as hyperplane arrangements. Ergen and Pilancı showed that if we fix these activation patterns, the training problem becomes linear. By considering all possible valid patterns, the entire training process for two- and three-layer CNNs can be rewritten as a sum of convex problems, each corresponding to a different arrangement of the data.

This perspective reveals that architectural choices are actually implicit convex regularizers. For example:

  • Convolutional layers act as a form of group sparsity ($\ell_1/\ell_2$) regularization.
  • Pooling layers impose specific structural constraints on the convex dual.
  • Batch Normalization, as explored by Ergen et al. in Demystifying Batch Normalization in ReLU Networks, can be understood as a mechanism that enforces specific scaling properties in the convex objective, explaining its ability to stabilize training.

From Theory to Scalable Algorithms

While the theoretical existence of a convex reformulation is powerful, early versions suffered from a "curse of dimensionality." The number of variables in the convex problem scales with the number of possible hyperplane arrangements, which can be massive for high-dimensional data.

Recent work has focused on making these global guarantees practical:

  1. Fast Solvers: Aaron Mishkin, Arda Sahiner, and Mert Pilancı developed cone decomposition methods in Fast Convex Optimization for Two-Layer ReLU Networks to speed up the identification of optimal activation patterns.
  2. Adversarial Robustness: Somayeh Sojoudi and Yatong Bai extended this framework to robust optimization. In Practical Convex Formulation of Robust One-hidden-layer Neural Network Training, they showed that one can train networks to be "adversarially robust" by solving a convex problem, bypassing the instability of standard adversarial training (like PGD).
  3. GPU Acceleration: The framework reached a milestone with CRONOS, introduced by Miria Feng et al. in CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks. By using clever preconditioning and GPU-optimized solvers, they demonstrated that convex reformulations can scale to industry-standard tasks like ImageNet and GPT-2 architectures.

Why It Matters

The shift toward convex reformulations changes the fundamental questions we ask about deep learning. Instead of asking "How do we initialize weights to avoid local minima?", we can ask "What is the optimal convex regularizer for this data distribution?"

By proving that we can approximate the global optimum of ReLU networks in polynomial time—as shown by Sungyoon Kim and Mert Pilancı in Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time—this research provides a rigorous mathematical foundation for why deep learning works and offers a more reliable, transparent way to build future models.

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_optimization_of_relu_networks_via_194e9fd3,
  title = {Global Optimization of ReLU Networks via Semi-Infinite Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-optimization-of-relu-networks-via-semi-infinite-duality/rdr_194e9fd3b34d44a9a26de96d9eb80dde},
  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_optimization_of_relu_networks_via_194e9fd3_v1,
  title = {Global Optimization of ReLU Networks via Semi-Infinite Duality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-optimization-of-relu-networks-via-semi-infinite-duality/rdr_194e9fd3b34d44a9a26de96d9eb80dde/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}