Introduction
Training deep neural networks is notoriously challenging due to highly non-convex loss landscapes, which can cause vanishing or exploding gradients and trap optimization in sub-optimal critical points. To isolate and study these optimization dynamics, researchers often analyze "deep linear networks"—models lacking non-linear activations but retaining the non-convexity of deep architectures.
While prior work has shown that standard deep linear networks can converge to global minima, these guarantees typically require the network's width to grow linearly with its depth ($L$). This paper investigates whether Residual Networks (ResNets), characterized by skip connections, can overcome this depth dependency. The authors provide a theoretical guarantee that both Gradient Descent (GD) and Stochastic Gradient Descent (SGD) can reach the global minimum when training deep linear ResNets, requiring a network width that is entirely independent of depth.
Methodology & Theoretical Framework
The authors analyze $L$-hidden-layer linear ResNets defined by the function: $$f_W(x) = B(I + W_L) \dots (I + W_1)Ax$$
The theoretical framework relies on a few key methodological choices:
- Fixed Input and Output Layers: The input matrix $A$ and output matrix $B$ are fixed throughout training.
- Zero Initialization: All hidden weight matrices $W_l$ are initialized to zero. In a ResNet architecture, this means the network initially acts as a simple linear transformation $BA$, effectively bypassing the hidden layers and allowing perfect gradient flow from the first iteration.
- Transformation Strategies: The study explores two types of fixed transformations for $A$ and $B$: Gaussian random matrices and a novel "modified identity" transformation.
The core of the mathematical proof establishes restricted gradient bounds—interpretable as a Polyak-Łojasiewicz (PL) condition—and demonstrates that these favorable properties hold along the entire optimization trajectory.
Key Theoretical Insights
- Depth Independence: Unlike standard deep linear networks where width requirements scale with $O(L)$, linear ResNets require a width independent of $L$. This mathematically formalizes the intuition that skip connections fundamentally simplify the optimization landscape.
- Sharper Bounds via Gaussian Transformations: When using Gaussian random matrices for the fixed layers, the required width is $O(kr\kappa^2)$, where $\kappa$ is the condition number of the data covariance matrix. This bound is sharper than those for standard networks by a factor of $O(\kappa L)$.
- Optimal Width via Modified Identity: The authors propose a specific deterministic "modified identity" choice for $A$ and $B$ that guarantees global convergence with a remarkably narrow width of just $m = d + k$ (the sum of the input and output dimensions).
Convergence Results & Empirical Validation
The paper establishes rigorous convergence rates for both GD and SGD:
- Gradient Descent: GD achieves an $\epsilon$-error in $O(\kappa \log(1/\epsilon))$ iterations.
- Stochastic Gradient Descent: The authors provide the first global convergence rate for SGD in deep linear networks, reaching an $\epsilon$-error in $\tilde{O}(\kappa^2 \epsilon^{-1} \log(1/\epsilon) \cdot n/B)$ iterations. Furthermore, in the "realizable" case (where the global minimum loss is zero), SGD achieves a linear convergence rate.
To validate these theoretical findings, the authors employ a 10-dimensional synthetic dataset ($X \in \mathbb{R}^{10 \times 1000}$ generated from a standard normal distribution, with labels $Y = -X + 0.1E$). This controlled environment isolates the effects of depth and width without the confounding noise of real-world data. The empirical results confirm that while standard deep linear networks become progressively harder to train as depth increases, ResNets maintain a consistent, fast convergence rate regardless of depth.
Limitations & Future Directions
While the theoretical guarantees are strong, the paper acknowledges several limitations. The most significant is the focus on linear networks; real-world ResNets utilize non-linear activations (like ReLU) that introduce substantially more complex landscape features. Additionally, fixing the input and output layers is a theoretical simplification, whereas practice dictates training these layers alongside the rest of the network. Finally, the width requirement for SGD still depends on the sample size $n$ and batch size $B$, indicating room to tighten these bounds for stochastic settings.
Future work will aim to extend this analysis to non-linear ResNets and explore different loss functions, such as cross-entropy for classification tasks.
Summary updated