Abstract: In this paper, we study decentralized empirical risk minimization problems, where the goal is to minimize a finite-sum of smooth and strongly-convex functions available over a network of nodes. We propose GT-SAGA, a decentralized stochastic first-order algorithm based on gradient tracking and a variance-reduction technique called SAGA. We develop the convergence analysis and the iteration complexity of this algorithm. We further demonstrate various trade-offs and discuss scenarios in which GT-SAGA achieves superior performance (in terms of the number of local gradient computations required) with respect to existing decentralized schemes.
Introduction
In modern machine learning, datasets are often too massive to be stored or processed on a single machine. Instead, data is distributed across a network of nodes, such as a cluster of servers or a fleet of mobile devices. The challenge is to minimize the Empirical Risk—the average loss across all data points in the entire network—without centralizing the data. This paper, a collaboration between researchers at Carnegie Mellon and Tufts University, introduces GT-SAGA, a powerful new algorithm designed to address the unique bottlenecks of decentralized optimization.
The Challenges of Decentralized Optimization
Decentralized optimization faces three primary hurdles:
- Communication Bottlenecks: Moving all data to a central server is often impossible due to privacy concerns or bandwidth limits. Algorithms must rely on local communication between neighbors.
- Data Heterogeneity: Data at one node might differ significantly from data at another. This "drift" or local bias often prevents simple decentralized algorithms from finding the true global optimum.
- Stochastic Noise: Calculating the "full gradient" (the slope for every data point) is computationally prohibitive. While using a "stochastic gradient" (one random point at a time) is faster, it introduces noise that typically forces algorithms to use decaying step sizes, slowing down convergence.
The GT-SAGA Algorithm
GT-SAGA addresses these challenges by merging two key mechanisms: Gradient Tracking (GT) and SAGA (Variance Reduction).
- Gradient Tracking: Each node maintains a "tracker" variable that estimates the average gradient of the entire network. By communicating this tracker with neighbors, nodes can correct for local data bias, allowing the algorithm to use a constant step size and converge to the exact solution.
- SAGA: Locally, each node maintains a "gradient table" of the most recent gradients calculated for every local data point. When a new sample is picked, SAGA uses this table to create an unbiased estimate of the local gradient with significantly lower variance than standard Stochastic Gradient Descent (SGD).
As shown in Algorithm 1, GT-SAGA operates iteratively. Each node updates its local estimate (Step 2), samples from its local data (Step 3), performs a local SAGA update (Step 4), and then updates its gradient tracker (Step 5) to maintain network-wide alignment. This combination allows for topological flexibility, as it only requires the network weights to be doubly-stochastic, supporting a broad class of directed network topologies.
Convergence and Complexity
The primary contribution of this work is the rigorous proof of GT-SAGA's iteration complexity. For smooth and strongly-convex problems, GT-SAGA achieves exact linear convergence. This means it approaches the true global optimum at a consistent rate, rather than plateauing like many other stochastic methods.
As illustrated in the table above, GT-SAGA's complexity is $\mathcal{O} \left( \max \left\{ \tilde{m}, \frac{Q^2}{(1-\sigma)^2} \right\} \log \frac{1}{\epsilon} \right)$, where $\tilde{m}$ is the number of local data points, $Q$ is the condition number, and $\sigma$ represents network connectivity.
In "big data" scenarios where $\tilde{m}$ is large, GT-SAGA scales better than non-variance-reduced methods like standard Gradient Tracking [17]. By decoupling the dependence on the number of data points from the network connectivity terms in the complexity bound, GT-SAGA effectively "hides" the cost of large datasets, making it highly efficient for high-dimensional, large-scale problems.
Limitations and Future Work
While GT-SAGA offers significant performance gains, it has certain trade-offs:
- Memory Overhead: The SAGA component requires storing a gradient table for every local data point. For memory-constrained devices with massive datasets, this storage requirement could be a limitation.
- Convexity Assumptions: The current theoretical guarantees apply to smooth and strongly-convex functions. Extending these results to non-convex landscapes, common in deep learning, remains an area for future research.
In Part II of this research, the authors introduce GT-SVRG, which utilizes the SVRG variance-reduction technique to offer a different trade-off between computational speed and memory efficiency.
Summary updated