  We propose a distributed cubic regularization of the Newton method for
solving (constrained) empirical risk minimization problems over a network of
agents, modeled as undirected graph. The algorithm employs an inexact,
preconditioned Newton step at each agent's side: the gradient of the
centralized loss is iteratively estimated via a gradient-tracking consensus
mechanism and the Hessian is subsampled over the local data sets. No Hessian
matrices are thus exchanged over the network. We derive global complexity
bounds for convex and strongly convex losses. Our analysis reveals an
interesting interplay between sample and iteration/communication complexity:
statistically accurate solutions are achievable in roughly the same number of
iterations of the centralized cubic Newton method, with a communication cost
per iteration of the order of
$\widetilde{\mathcal{O}}\big(1/\sqrt{1-\rho}\big)$, where $\rho$ characterizes
the connectivity of the network. This demonstrates a significant communication
saving with respect to that of existing, statistically oblivious, distributed
Newton-based methods over networks.
