Distributed SGD in overparametrized linear regression
Mike Nguyen, Charly Kirst, Nicole Mücke · Analysis and Applications · 2023
We consider distributed learning using constant stepsize stochastic gradient descent (DSGD). The data are distributed uniformly over several devices, each sending a final model update to a central server. In a final step, the local estimates are aggregated. We prove in the setting of overparametrized linear regression general upper bounds with matching lower bounds and derive learning rates for specific data generating distributions. We show that the excess risk is of order of the variance provided the number of local nodes grows not too large with the global sample size. We further compare the sample complexity of DSGD with the sample complexity of distributed ridge regression (DRR) and show that the excess DSGD-risk is smaller than the excess DRR-risk, where both sample complexities are of the same order.