GT-SAGA and GT-SVRG (Decentralized Variance-Reduced Gradient Tracking)

A unified decentralized finite-sum stochastic optimization framework (GT-VR, Xin, Khan, & Kar 2020, Sections II-III, Algorithms 1-2) for minimizing F(x) = (1/n) sum_{i=1}^n (1/m_i) sum_{j=1}^{m_i} f_{i,j}(x) over a primitive doubly stochastic network W that couples local variance-reduced gradient estimators r_i^k with dynamic gradient tracking x_i^{k+1} = sum_j w_{ij} x_j^k - alpha y_i^k and y_i^{k+1} = sum_j w_{ij} y_j^k + r_i^{k+1} - r_i^k: GT-SAGA (Algorithm 1) computes g_i^k = nabla f_{i,s_i^k}(x_i^k) - nabla f_{i,s_i^k}(z_{i,s_i^k}^k) + (1/m_i) sum_j nabla f_{i,j}(z_{i,j}^k) from a local gradient table, while GT-SVRG (Algorithm 2) computes v_i^k = nabla f_{i,s_i^k}(x_i^k) - nabla f_{i,s_i^k}(tau_i^k) + nabla f_i(tau_i^k) relative to periodic local checkpoints tau_i^k = x_i^{t T}.