Timezone: »
Spotlight
Newton Method over Networks is Fast up to the Statistical Precision
Amir Daneshmand · Gesualdo Scutari · Pavel Dvurechenskii · Alexander Gasnikov
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 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 Newtonbased methods over networks.
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 nonconvex largescale optimization problems;  optimization under deterministic and stochastic inexact information;  randomized algorithms: random coordinate descent, random (derivativefree) directional search;  numerical aspects of Optimal Transport  Algorithms for saddlepoint problems and variational inequalities
Alexander Gasnikov (Moscow Institute of Physics and Technology)
Related Events (a corresponding poster, oral, or spotlight)

2021 Poster: Newton Method over Networks is Fast up to the Statistical Precision »
Tue. Jul 20th 04:00  06:00 PM Room None
More from the Same Authors

2022 Poster: The power of firstorder smooth optimization for blackbox nonsmooth problems »
Alexander Gasnikov · Anton Novitskii · Vasilii Novitskii · Farshed Abdukhakimov · Dmitry Kamzolov · Aleksandr Beznosikov · Martin Takac · Pavel Dvurechenskii · Bin Gu 
2022 Spotlight: The power of firstorder smooth optimization for blackbox nonsmooth problems »
Alexander Gasnikov · Anton Novitskii · Vasilii Novitskii · Farshed Abdukhakimov · Dmitry Kamzolov · Aleksandr Beznosikov · Martin Takac · Pavel Dvurechenskii · Bin Gu 
2021 Poster: ADOM: Accelerated Decentralized Optimization Method for TimeVarying Networks »
Dmitry Kovalev · Egor Shulgin · Peter Richtarik · Alexander Rogozin · Alexander Gasnikov 
2021 Spotlight: ADOM: Accelerated Decentralized Optimization Method for TimeVarying Networks »
Dmitry Kovalev · Egor Shulgin · Peter Richtarik · Alexander Rogozin · Alexander Gasnikov 
2021 Poster: On a Combination of Alternating Minimization and Nesterov's Momentum »
Sergey Guminov · Pavel Dvurechenskii · Nazarii Tupitsa · Alexander Gasnikov 
2021 Spotlight: On a Combination of Alternating Minimization and Nesterov's Momentum »
Sergey Guminov · Pavel Dvurechenskii · Nazarii Tupitsa · Alexander Gasnikov 
2020 Poster: SelfConcordant Analysis of FrankWolfe Algorithms »
Pavel Dvurechenskii · Petr Ostroukhov · Kamil Safin · Shimrit Shtern · Mathias Staudigl 
2019 Poster: On the Complexity of Approximating Wasserstein Barycenters »
Alexey Kroshnin · Nazarii Tupitsa · Darina Dvinskikh · Pavel Dvurechenskii · Alexander Gasnikov · Cesar Uribe 
2019 Oral: On the Complexity of Approximating Wasserstein Barycenters »
Alexey Kroshnin · Nazarii Tupitsa · Darina Dvinskikh · Pavel Dvurechenskii · Alexander Gasnikov · Cesar Uribe 
2018 Poster: Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm »
Pavel Dvurechenskii · Alexander Gasnikov · Alexey Kroshnin 
2018 Oral: Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm »
Pavel Dvurechenskii · Alexander Gasnikov · Alexey Kroshnin