Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience

The problem of saddle-point avoidance for non-convex optimization is quite\nchallenging in large scale distributed learning frameworks, such as Federated\nLearning, especially in the presence of Byzantine workers. The celebrated\ncubic-regularized Newton method of \\cite{nest} is one of the most elegant ways\nto avoid saddle-points in the standard centralized (non-distributed) setup. In\nthis paper, we extend the cubic-regularized Newton method to a distributed\nframework and simultaneously address several practical challenges like\ncommunication bottleneck and Byzantine attacks. Note that the issue of\nsaddle-point avoidance becomes more crucial in the presence of Byzantine\nmachines since rogue machines may create \\emph{fake local minima} near the\nsaddle-points of the loss function, also known as the saddle-point attack.\nBeing a second order algorithm, our iteration complexity is much lower than the\nfirst order counterparts. Furthermore we use compression (or sparsification)\ntechniques like $\\delta$-approximate compression for communication efficiency.\nWe obtain theoretical guarantees for our proposed scheme under several settings\nincluding approximate (sub-sampled) gradients and Hessians. Moreover, we\nvalidate our theoretical findings with experiments using standard datasets and\nseveral types of Byzantine attacks, and obtain an improvement of $25\\%$ with\nrespect to first order methods in iteration complexity.\n