Sign in
Efficient Second-Order Algorithms for Decentralized Optimization with Provable Convergence Guarantees
Home - Activities
Home - ActivitiesReporter：
Dr. Jiaojiao Zhang, The Chinese University of Hong Kong
Inviter：
Xin Liu, Professor
Subject：
Efficient Second-Order Algorithms for Decentralized Optimization with Provable Convergence Guarantees
Time and place：
15:30-16:30 August 9(Tuesday), Z311
Abstract：
Big data over geographically distributed devices necessitates the development of decentralized optimization, where a group of nodes collaboratively minimizes a total objective via local computation and communication with its neighbors. Although first-order methods enjoy low per-iteration computational complexity, second-order methods are attractive due to their faster convergence rates and hence lower communication costs. Motivated by this, we aim to propose decentralized second-order algorithms inheriting the advantage of fast convergence as in the single-machine setting while avoiding high communication cost.
In the first work, we propose a novel Newton tracking algorithm, where each node updates the local variable along a local Newton direction modified with neighboring and historical information. No Hessian matrices exchange over the network. We prove that Newton tracking converges linearly to the exact optimal solution. In the single-machine setting, the Newton method has theoretically faster rate than first-order methods. However, developing a communicate-efficient decentralized variant of the Newton method with condition-number-independence property or super-linear rate is non-trivial. In the second work, we fill this gap by proposing a decentralized Newton method with multi-consensus and compression. We establish theoretically faster rate than first-order methods with novel analysis.
In the third work, we move on to the stochastic setting when each node has many samples so that even computing the local full gradients is not affordable. We develop a general algorithmic framework that incorporates stochastic quasi-Newton approximations with variance reduction and then specify two fully decentralized stochastic quasi-Newton methods to locally construct Hessian inverse approximations without extra sampling or communication. We prove that the general framework converges linearly and the local constructed Hessian inverse approximations are positive definite with bounded eigenvalues.
In the first work, we propose a novel Newton tracking algorithm, where each node updates the local variable along a local Newton direction modified with neighboring and historical information. No Hessian matrices exchange over the network. We prove that Newton tracking converges linearly to the exact optimal solution. In the single-machine setting, the Newton method has theoretically faster rate than first-order methods. However, developing a communicate-efficient decentralized variant of the Newton method with condition-number-independence property or super-linear rate is non-trivial. In the second work, we fill this gap by proposing a decentralized Newton method with multi-consensus and compression. We establish theoretically faster rate than first-order methods with novel analysis.
In the third work, we move on to the stochastic setting when each node has many samples so that even computing the local full gradients is not affordable. We develop a general algorithmic framework that incorporates stochastic quasi-Newton approximations with variance reduction and then specify two fully decentralized stochastic quasi-Newton methods to locally construct Hessian inverse approximations without extra sampling or communication. We prove that the general framework converges linearly and the local constructed Hessian inverse approximations are positive definite with bounded eigenvalues.