Timezone: »

 
Poster
Newton Method over Networks is Fast up to the Statistical Precision
Amir Daneshmand · Gesualdo Scutari · Pavel Dvurechenskii · Alexander Gasnikov

Tue Jul 20 09:00 AM -- 11:00 AM (PDT) @
in Poster Session 1 »
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 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, 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 represents a significant improvement with respect to existing, statistically oblivious, distributed Newton-based methods over networks.
Keywords: Distributed and Parallel Optimization

Author Information

Amir Daneshmand (Purdue University)
Gesualdo Scutari (Purdue)
Pavel Dvurechenskii (Weierstrass Institute)

Graduated with honors from Moscow Institute of Physics and Technology. PhD on differential games in the same university. At the moment research associate in the area of optimization under inexact information in Berlin. Research interest include - algorithms for convex and non-convex large-scale optimization problems; - optimization under deterministic and stochastic inexact information; - randomized algorithms: random coordinate descent, random (derivative-free) directional search; - numerical aspects of Optimal Transport - Algorithms for saddle-point problems and variational inequalities

Alexander Gasnikov (Moscow Institute of Physics and Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors