Global Convergence Analysis of Local SGD for Two-layer Neural Network without Overparameterization

Yajie Bao, Amarda Shehu, Mingrui Liu

Introduction

In federated learning, Local Stochastic Gradient Descent (Local SGD) is a foundational algorithm. Instead of communicating with a central server at every single step, local machines perform several updates on their own data before synchronizing. While this approach is highly effective in practice, theoretical understanding of its convergence on complex, non-convex loss landscapes has remained limited.

This paper provides the first global convergence analysis for vanilla Local SGD in two-layer neural networks without relying on standard theoretical crutches like overparameterization or artificial noise injection. The authors uncover a "self-correction" mechanism that allows the algorithm to escape poor initializations and achieve linear speedup in distributed training environments.

The Challenge of Theoretical "Cheats"

Until now, most proofs of global convergence for neural networks have relied on two primary assumptions, or "cheats," to make the math work:

  1. Overparameterization (The NTK Regime): Assuming the network is infinitely wide so that it behaves like a linear model. This fails to capture how neural networks actually learn hierarchical features.
  2. Noise Injection: Explicitly adding random noise (such as Langevin dynamics) to force the algorithm out of local minima.

Vanilla Local SGD employs neither of these techniques. The core challenge addressed in this work is proving that the standard algorithm, when training a standard-sized two-layer network, can find the global optimum simply by following its own noisy gradients.

Methodology: Tracking the Weights

The authors analyze a two-layer ReLU neural network under a "teacher-student" framework using synthetic Gaussian input data ($Z \sim \mathcal{N}(0, I)$). To track the complex dynamics of the weights, they introduce two primary technical innovations:

  • Self-Correction Mechanism: The authors prove that even if the model starts in a "bad region"—where gradients initially point away from the optimal solution—the mathematical interaction between the two layers eventually pulls the parameters toward the correct direction. They achieve this by partitioning the objective landscape into several regions to strictly control how one layer's updates interfere with the other.
  • Exact Recursive Characterization: They develop a novel method to mathematically describe the evolution of the model's direction. This allows them to prove that the "signal" from the data eventually overcomes the inherent "noise" of SGD.

The analysis also incorporates weight normalization on the first layer, a practical technique that simplifies the optimization geometry.

Key Insights

Natural Self-Correction The most surprising finding is that Local SGD does not require extra noise to escape local minima. The inherent structure of the gradients in a two-layer network provides a natural self-correction path. If one layer begins drifting incorrectly, the other layer's dynamics eventually create a corrective pressure.

The Signal-to-Noise Ratio ($\alpha$) The authors identify a specific condition on the output weights, denoted as $\alpha$, that determines whether the network can self-correct. If the "mean" signal of the output weights is strong enough relative to their variance, global convergence is guaranteed from almost any initialization.

Local vs. Minibatch SGD Interestingly, experiments suggest that Local SGD can sometimes correct itself faster than standard Minibatch SGD. During the early "correction" phase, taking many small, localized steps proves more effective than taking one large, averaged step.

Comparison of Local SGD and Minibatch SGD performance across different output weight conditions ($\alpha$).

Key Results

  • Global Convergence Proof: The paper provides the first rigorous proof that vanilla Local SGD converges to the global minimum for two-layer networks without assuming infinite width.
  • Linear Speedup: The iteration complexity is shown to be $O(dk^4 / N\epsilon)$, where $N$ is the number of machines, $d$ is the dimension, and $k$ is the network width. This formally proves that training time decreases linearly as more machines are added, confirming Local SGD as a mathematically sound scaling method.
  • Communication Efficiency: The number of communication rounds required is significantly lower than the total number of iterations—specifically $O(k^4)$ or $O(k^{11/2})$ depending on the initialization.

Limitations and Future Work

While a significant step forward, the analysis relies heavily on the mathematical properties of Gaussian inputs. Extending this framework to highly structured real-world data (like images or text) remains an open challenge. Furthermore, the analysis is currently limited to two-layer networks; deeper networks introduce much more complex inter-layer interference. Finally, the assumption of a noiseless "teacher" network is an idealization, leaving room for future work to explore how label noise or model mismatch affects the self-correction mechanism.

Summary updated

Abstract

Local SGD, a cornerstone algorithm in federated learning, is widely used in training deep neural networks and shown to have strong empirical performance. A theoretical understanding of such performance on nonconvex loss landscapes is currently lacking. Analysis of the global convergence of SGD is challenging, as the noise depends on the model parameters. Indeed, many works narrow their focus to GD and rely on injecting noise to enable convergence to the local or global optimum. When expanding the focus to local SGD, existing analyses in the nonconvex case can only guarantee finding stationary points or assume the neural network is overparameterized so as to guarantee convergence to the global minimum through neural tangent kernel analysis. In this work, we provide the first global convergence analysis of the vanilla local SGD for two-layer neural networks \emph{without overparameterization} and \textit{without injecting noise}, when the input data is Gaussian. The main technical ingredients of our proof are \textit{a self-correction mechanism} and \textit{a new exact recursive characterization of the direction of global model parameters}. The self-correction mechanism guarantees the algorithm reaches a good region even if the initialization is in a bad region. A good (bad) region means updating the model by gradient descent will move closer to (away from) the optimal solution. The main difficulty in establishing a self-correction mechanism is to cope with the gradient dependency between two layers. To address this challenge, we divide the landscape of the objective into several regions to carefully control the interference of two layers during the correction process. As a result, we show that local SGD can correct the two layers and enter the good region in polynomial time. After that, we establish a new exact recursive characterization of the direction of global parameters, which is the key to showing convergence to the global minimum with linear speedup in the number of machines and reduced communication rounds. Experiments on synthetic data confirm theoretical results.
BibTeX
@inproceedings{bao2023global,
  author = {Yajie Bao and Amarda Shehu and Mingrui Liu},
  title = {{Global Convergence Analysis of Local SGD for Two-layer Neural Network without Overparameterization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=gVLKXT9JwG},
}
Figure