  A common approach to statistical learning with big-data is to randomly split
it among $m$ machines and learn the parameter of interest by averaging the $m$
individual estimates. In this paper, focusing on empirical risk minimization,
or equivalently M-estimation, we study the statistical error incurred by this
strategy. We consider two large-sample settings: First, a classical setting
where the number of parameters $p$ is fixed, and the number of samples per
machine $n\to\infty$. Second, a high-dimensional regime where both
$p,n\to\infty$ with $p/n \to \kappa \in (0,1)$. For both regimes and under
suitable assumptions, we present asymptotically exact expressions for this
estimation error. In the fixed-$p$ setting, under suitable assumptions, we
prove that to leading order averaging is as accurate as the centralized
solution. We also derive the second order error terms, and show that these can
be non-negligible, notably for non-linear models. The high-dimensional setting,
in contrast, exhibits a qualitatively different behavior: data splitting incurs
a first-order accuracy loss, which to leading order increases linearly with the
number of machines. The dependence of our error approximations on the number of
machines traces an interesting accuracy-complexity tradeoff, allowing the
practitioner an informed choice on the number of machines to deploy. Finally,
we confirm our theoretical analysis with several simulations.
