The Disconnect Between Approximation and Optimization in Deep Learning

48 concepts45 papers1 proposal

Imagine a map that proves a legendary treasure exists deep within a mountain range. The map is mathematically flawless; it guarantees the treasure's exact coordinates. However, it provides no trails, no climbing gear, and no advice on how to navigate the treacherous cliffs, sudden drop-offs, and dead ends that riddle the terrain.

This scenario illustrates the central dilemma of modern deep learning theory, often described as the existence-trainability gap. For decades, the bedrock of neural network theory has been approximation mechanics—proving that a given network architecture is a "universal approximator." This line of work guarantees that there exists some configuration of weights capable of representing a target function to arbitrary precision.

Yet, knowing a solution exists somewhere in the vast parameter space says nothing about whether standard optimization algorithms, like Stochastic Gradient Descent (SGD), can actually find it. This disconnect divides what a network can theoretically represent from what it can practically learn.

The Illusion of Mathematical Existence

To understand why this gap matters, we must look at how approximation theory operates. Mathematical proofs frequently use constructive methods to show that a specific network architecture can achieve optimal approximation rates.

For instance, Ding-Xuan Zhou provided a rigorous foundation establishing that deep Convolutional Neural Networks (CNNs) are universal approximators, demonstrating in Universality of Deep Convolutional Neural Networks that they can match any continuous function while using significantly fewer parameters than traditional networks. Similarly, Chenghao Liu et al. proved in Characterizing ResNet's Universal Approximation Capability that constant-width ResNets can reach the theoretical lower bound for optimal approximation rates.

These proofs are masterpieces of mathematical assurance. They tell us that our models are expressive enough to hold the answers to incredibly complex problems. We see this across specialized domains:

However, as noted in the foundational work of Hrushikesh N. Mhaskar et al. in How to Choose an Activation Function, approximation theory focuses strictly on the existence of a solution rather than the feasibility of finding it through iterative methods. The configurations constructed in these proofs are often highly brittle, mathematically intricate arrangements of weights that occupy a near-vanishing volume of the total parameter space.

Why Optimization Fails to Find the Ideal

If an optimal configuration exists, why can't gradient descent find it? The answer lies in the geometry of the loss landscape and the dynamics of optimization.

When we train a network, we do not hand-craft the weights; we initialize them randomly and let gradient descent navigate the loss landscape based on local error signals. Bolton Bailey et al. exposed this disconnect clearly in Size-Noise Tradeoffs in Generative Networks. They proved that while highly efficient ReLU network weights exist for complex space-filling tasks, standard gradient descent frequently fails to converge to them.

The optimization process is plagued by practical hurdles that existence proofs completely ignore: vanishing gradients, local minima, and optimization traps. While over-parameterized networks sometimes enjoy smoother landscapes—as explored by Quynh Nguyen et al. in On the loss landscape of a class of deep neural networks with no bad local valleys—we still lack formal guarantees identifying the exact architectural conditions that prevent optimization traps. When architectures are pushed to their limits of efficiency, the landscape becomes treacherous.

[ Approximation Theory ] ───> Proves a perfect solution EXISTS in the weight space.
                                      │
                                      ▼  (The Existence-Trainability Gap)
                                      │
[ Optimization Theory ]  ───> Asks if Gradient Descent can actually NAVIGATE there.

Manifestations Across Architectures

The existence-trainability gap is not a niche theoretical quirk; it manifests across several prominent domains of modern deep learning:

Narrow and Compressed Networks

Theoretical work by Chenghao Liu et al. in ReLU Network with Width $d+\mathcal{O}(1)$ Can Achieve Optimal Approximation Rate proves that a ReLU network with a width just slightly larger than the input dimension can achieve optimal approximation rates. Yet, these narrow networks are notoriously difficult to train.

The authors of A Theory for Compressibility of Graph Transformers for Transductive Learning observed a similar phenomenon in Graph Transformers: while highly compressed, thin architectures mathematically exist, training them from scratch introduces severe initialization sensitivity and optimization challenges compared to their wider counterparts.

Generative and Latent Models

In continuous-time generative models, Belinda Tzen et al. proved the existence of optimal neural drift functions to steer diffusions in Theoretical guarantees for sampling and inference in generative models with latent diffusions, but noted that this does not automatically provide a practical training algorithm. Similarly, Arnab Kumar Mondal highlighted in MaskAAE: Latent space optimization for Adversarial Auto-Encoders that theoretical gains in latent space optimization are often bottlenecked by the practical instabilities of min-max optimization.

Bridging the Gap

To close the existence-trainability gap, deep learning theory must evolve from proving what networks can represent to proving what algorithms can discover.

Some frameworks attempt to bridge this divide by analyzing training dynamics directly rather than static weight spaces. For example, Geonhui Yoo et al. introduced minimalist models in Understanding Sharpness Dynamics in NN Training with a Minimalist Example to mathematically trace sharpness dynamics and stabilization regimes during actual training. In the realm of sparse networks, Francois Malgouyres established sharp conditions that guarantee stable parameter recovery in On the stable recovery of deep structured linear networks under sparsity constraints, moving closer to optimization routines with provable convergence.

Ultimately, a complete theory of deep learning cannot rely solely on the comfort of universal approximation. True understanding requires reconciling the mathematical ideals of representation with the messy, stochastic realities of gradient-based optimization.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_existence_trainability_gap_106a252e,
  title = {existence-trainability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-trainability-gap/rdr_106a252eb469432890492380e966621b},
  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_existence_trainability_gap_106a252e_v1,
  title = {existence-trainability gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/existence-trainability-gap/rdr_106a252eb469432890492380e966621b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake