Newton Method over Networks is Fast up to the Statistical Precision

Ch. 139. P. 2398–2409.

Daneshmand A., Scutari G., Двуреченский П. Е., Гасников А. В.

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 gradienttracking 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 roughly in the same number of iterations of the centralized cubic Newton, with a communication cost per iteration of the order of Oe 1/ √ 1 − ρ
, where ρ characterizes the connectivity of the network. This represents a significant communication saving with respect to that of existing, statistically oblivious, distributed Newton-based methods over networks.

Ключевые слова: Newton method

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Анализ неопределенности в алгоритмах машинного обучения (2021)

В книге

Proceedings of the 38th International Conference on Machine Learning (ICML 2021)

Vol. 139. , PMLR, 2021.