摘要: This talk introduces a decentralized algorithm for the consensus optimization problem defined over a connected network of agents. The agents collaboratively look for a common argument to minimize an aggregate cost function, which is the average of local cost functions determined by the agents' private data and objectives. During the optimization process, each agent can only communicate with its neighbors; such a computation scheme avoids a data fusion center or long-distance communication and offers better load balance to the network.We propose a novel decentralized exact first-order algorithm (abbreviated as EXTRA) to solve the consensus optimization problem. "EXACT" means that it can converge to the exact solution. EXTRA can use a fixed large step size, which is independent of the network size, and has synchronized iterations. The local iterate of every agent converges uniformly and consensually to an exact minimizer of the aggregate cost function. In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer. EXTRA and DGD have the same choice of mixing matrices and similar per-iteration complexity. EXTRA, however, uses the gradients of last two iterates, unlike DGD which uses just that of last iterate. EXTRA has the best known convergence rates among the existing first-order decentralized algorithms. If the local cost functions are convex and have Lipschitz continuous gradients, EXTRA has an O(1/k) ergodic convergence rate in terms of the first-order optimality residual. If the aggregate cost function is also (restricted) strongly convex, EXTRA converges to an optimal solution at a linear rate.

报告人简介: Qing Ling received the B.S. degree in automation and the Ph.D. degree in control theory and control engineering from University of Science and Technology of China, Hefei, Anhui, China, in 2001 and 2006, respectively. From 2006 to 2009, he was a Postdoctoral Research Fellow with Department of Electrical and Computer Engineering, Michigan Technological University, Houghton, Michigan, USA. Since 2009, he has been an Associate Professor with Department of Automation, University of Science and Technology of China. His current research focuses on decentralized network optimization and its applications.