Abstract
Existing global convergence guarantees of (stochastic) gradient descent do not apply to practical deep networks in the practical regime of deep learning beyond the neural tangent kernel (NTK) regime. This paper proposes an algorithm, which is ensured to have global convergence guarantees in the practical regime beyond the NTK regime, under a verifiable condition called the expressivity condition. The expressivity condition is defined to be both data-dependent and architecture-dependent, which is the key property that makes our results applicable for practical settings beyond the NTK regime. On the one hand, the expressivity condition is theoretically proven to hold data-independently for fully-connected deep neural networks with narrow hidden layers and a single wide layer. On the other hand, the expressivity condition is numerically shown to hold data-dependently for deep (convolutional) ResNet with batch normalization with various standard image datasets. We also show that the proposed algorithm has generalization performances comparable with those of the heuristic algorithm, with the same hyper-parameters and total number of iterations. Therefore, the proposed algorithm can be viewed as a step towards providing theoretical guarantees for deep learning in the practical regime.
Introduction
In optimization theory, proving that an algorithm will definitely find the global minimum is notoriously difficult for deep neural networks. Most existing proofs rely on the Neural Tangent Kernel (NTK) or "lazy training" regime. In this regime, networks are assumed to be infinitely wide, such that their weights hardly move during training. However, this doesn't match practical reality, where deep learning's power comes from learning complex, hierarchical representations—meaning weights must change significantly. This paper bridges the gap by providing a convergence guarantee that applies to practical architectures like ResNets in a regime where they actually learn features.
The Two-Phase Modification Algorithm
The authors propose a Two-Phase Modification (Algorithm 1) that can be applied to standard first-order optimizers like SGD or Adam:
- Phase 1 (Standard Training): The network is trained normally for a set duration ($\tau$). This allows the network to learn data-dependent features.
- The Transition: A small amount of random Gaussian noise is injected into all layers except the last one. This ensures that the "feature matrix" of the hidden layers becomes full rank with probability one, utilizing the property that neural networks with analytic activations (like Softplus) have a zero set of measure zero.
- Phase 2 (Rank-Preserving Training): Training continues with a modified update rule that satisfies a rank-preserving condition. This ensures that the expressivity gained in Phase 1 is maintained until the model reaches a global minimum.
Empirical Validation and Results
The authors validated their approach using standard image classification benchmarks including MNIST, CIFAR-10, CIFAR-100, and SVHN. A key component of the theory is the Expressivity Condition, a verifiable assumption that parameters exist capable of interpolating the training data. The authors numerically confirmed that standard ResNet-18 architectures with batch normalization satisfy this condition across all tested datasets.
As shown in the training logs, the two-phase approach (denoted as $A(\text{base})$) often results in a sharper drop in training loss during the second phase compared to continuing with standard SGD. Furthermore, the algorithm achieves generalization performance comparable to standard heuristic training.
On CIFAR-10 with data augmentation, the base algorithm achieved a 7.01% error, while the "guaranteed" version achieved 6.84%, demonstrating that theoretical rigor does not come at the cost of practical performance.
Conclusion and Limitations
While the paper provides a significant step toward theoretical guarantees for practical deep learning, some limitations remain. The proof requires "real analytic" activation functions; while Softplus approximates ReLU closely, the proof does not strictly apply to the non-analytic ReLU at zero. Additionally, while the paper guarantees finding a global minimum, it does not provide a new theory for why these specific minima generalize well, though empirical results are highly promising. Future work may extend this "learned NTK" perspective to implicit deep learning and robustness research.
Summary updated