Acceleration in Distributed Sparse Regression
Main Conference Track
Authors: Marie Maros, Gesualdo Scutari

We study acceleration for distributed sparse regression in   {\it  high-dimensions},  which allows the parameter size  to exceed and grow faster than the sample size. When applicable, existing  distributed algorithms employing acceleration perform poorly  in this setting, theoretically and numerically.  We  propose a new accelerated distributed algorithm suitable for high-dimensions. The method couples  a suitable instance of accelerated Nesterov's proximal gradient  with consensus and gradient-tracking mechanisms, aiming at estimating locally the gradient of the empirical loss while enforcing agreement on the local estimates.  Under standard assumptions on the statistical model and tuning parameters, the proposed method is proved to  globally converge   at {\it linear} rate  to an estimate that is within the {\it statistical precision} of the model. The iteration  complexity scales as $\mathcal{O}(\sqrt{\kappa})$, while the communications per iteration are at most $\widetilde{\mathcal{O}}(\log m/(1-\rho))$,  where $\kappa$ is the restricted condition number of the empirical loss, $m$ is the number of agents, and $\rho\in (0,1)$ measures the network connectivity. As by-product of our design, we also report    an accelerated method for high-dimensional estimations over  master-worker architectures, which is of independent interest and  compares favorably with existing works.