Convex Reformulations for Global Neural Network Optimization

This direction is merged into another direction: non-convex optimization landscape (optimization landscape complexity). Its last version stays readable and citable here.

Version 1 of 118 papers18 conceptsfrozen 2026-10-04

Training a deep neural network is traditionally viewed as a high-stakes gamble in a rugged landscape. Because the loss functions of neural networks are non-convex, standard gradient descent can easily become trapped in local minima or stall on flat plateaus. This lack of convexity means we rarely know if a model has reached its best possible state or if it is simply stuck in a suboptimal "trap."

A growing body of research seeks to eliminate this uncertainty by transforming the "messy" non-convex training problem into a well-behaved convex one. By reformulating the architecture or the objective function, researchers are providing the first provable guarantees of global optimality for deep learning.

From Landscapes to Convex Cones

The core intuition behind this shift is lifting. In a standard neural network, we optimize weights that interact non-linearly (like the product of weights in different layers). This interaction creates the non-convex "jaggedness."

Researchers like Mert Pilanci and Tolga Ergen have shown that for two-layer ReLU networks, this problem can be "lifted" into a higher-dimensional space where the landscape becomes convex. In Convex Geometry and Duality of Over-parameterized Neural Networks, they demonstrate that training is equivalent to solving a convex problem. This transformation reveals that neural networks aren't just black boxes; they have an implicit bias toward "simple" solutions, effectively acting as data-adaptive splines.

Other approaches, such as those by Karthik Prakhya, Tolga Birdal, and Alp Yurtsever, use copositive programming and semidefinite programming (SDP) relaxations. As detailed in Convex Formulations for Training Two-Layer ReLU Neural Networks, these methods provide an exact global solution for sufficiently wide networks, replacing the trial-and-error of backpropagation with mathematically rigorous optimization.

The Library of Mirrors

Why does adding depth help if we are just solving a convex problem? Emi Zeger, Emmanuel J. Candès, and Mert Pilanci provide a striking geometric intuition in A Library of Mirrors: Deep Neural Nets in Low Dimensions are Convex Lasso Models with Reflection Features.

They prove that deep networks on low-dimensional data act as a "library of mirrors." Each layer systematically generates new features by reflecting training data points across one another. This perspective recasts deep learning as a convex Lasso problem. Instead of searching for weights in a dark, non-convex room, the model is simply selecting the best combination of these "reflected" features from a predefined, convex library.

Scaling to the Real World

Historically, convex reformulations were mathematically elegant but computationally expensive, often limited to tiny datasets. Recent work has broken this bottleneck.

  1. Convolutional Efficiency: Site Bai, Chuyang Ke, and Jean Honorio introduced Dual Convexified Convolutional Neural Networks (DCCNNs). In Dual Convexified Convolutional Neural Networks, they show how to move to a dual space that eliminates the massive memory overhead of previous convex methods, making global optimality feasible for CNNs.
  2. GPU Acceleration: The CRONOS framework, developed by Miria Feng, Zachary Frangella, and Mert Pilanci, leverages GPU acceleration and preconditioning to scale these ideas. As shown in CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks, it is now possible to train architectures like GPT-2 and datasets like ImageNet using convex reformulations, requiring near-zero hyperparameter tuning.

Beyond the NTK Regime

Many theoretical guarantees in deep learning rely on the "Neural Tangent Kernel" (NTK) regime, which assumes weights barely move from their initialization. Convex reformulations move beyond this. For instance, Shunta Akiyama demonstrates in Block Coordinate Descent for Neural Networks Provably Finds Global Minima that by decoupling layers using auxiliary variables, we can find global minima for networks of arbitrary depth without relying on the restrictive assumptions of the NTK.

By bridging the gap between the empirical success of deep learning and the theoretical rigor of convex optimization, this research direction is turning the "art" of neural network training into a predictable, verifiable science.

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_convex_reformulations_for_global_neural__519b5af6,
  title = {Convex Reformulations for Global Neural Network Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convex-reformulations-for-global-neural-network-optimization/rdr_519b5af625ae465a9641c073a1f821c2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_convex_reformulations_for_global_neural__519b5af6_v1,
  title = {Convex Reformulations for Global Neural Network Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/convex-reformulations-for-global-neural-network-optimization/rdr_519b5af625ae465a9641c073a1f821c2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}