Averaging algorithms and distributed optimization

author: John N. Tsitsiklis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, MIT
published: Jan. 13, 2011, recorded: December 2010, views: 685

Slides

Slides
0:00	Averaging algorithms and distributed optimization
0:42	Outline
1:43	The Setting (1)
2:47	The Setting (2)
3:15	The Setting (3)
3:55	Social sciences (1)
4:23	Social sciences (2)
4:44	Social sciences (3)
5:04	Engineering
6:31	The DeGroot opinion pooling model (1)
10:02	The DeGroot opinion pooling model (2)
11:46	Part I: Distributed Optimization
12:03	Gradient-like methods (1)
14:46	Gradient-like methods (2)
15:56	Smooth f; compentwise decentralization (1)
18:08	Smooth f; compentwise decentralization (2)
21:19	Smooth f; compentwise decentralization (3)
22:17	Smooth f; overlap and cooperate (1)
24:21	Smooth f; overlap and cooperate (2)
24:53	Smooth f; overlap and cooperate (3)
25:26	Smooth f; overlap and cooperate (ctd.) (1)
27:19	Smooth f; overlap and cooperate (ctd.) (2)
27:56	Smooth f; overlap and cooperate (ctd.) (3)
28:47	Smooth f; overlap and cooperate (ctd.) (4)
31:41	Smooth f; overlap and cooperate (ctd.) (5)
33:50	Smooth f; overlap and cooperate (ctd.) (6)
34:05	Smooth, additive f; overlap and cooperate (1)
35:57	Smooth, additive f; overlap and cooperate (2)
36:21	Additive f; overlap and cooperate (ctd.) (1)
37:01	Smooth, additive f; overlap and cooperate (2)
37:03	Additive f; overlap and cooperate (ctd.) (1)
37:48	Additive f; overlap and cooperate (ctd.) (2)
40:06	Convergence times — the big picture (1)
43:17	Convergence times — the big picture (2)
44:18	Part II: Consensus and averaging
44:25	Convergence time of consensus algorithms (1)
44:36	Convergence time of consensus algorithms (2)
45:57	Convergence time of consensus algorithms (3)
46:08	Convergence time of consensus algorithms (4)
46:10	Convergence time of consensus algorithms (5)
46:13	Averaging algorithms (1)
46:14	Averaging algorithms (2)
46:17	Averaging algorithms (3)
47:30	A critique
48:28	Time-Varying/Chaotic Environments
51:01	Consensus convergence
52:46	Averaging in Time-Varying Setting (1)
52:57	Averaging in Time-Varying Setting (2)
53:52	Averaging in Time-Varying Setting (3)
54:20	Averaging in Time-Varying Setting (4)
55:56	Can we beat O(n2)? (1)
57:28	Can we beat O(n2)? (2)
58:01	A model of computation; static graphs (1)
58:09	A model of computation; static graphs (2)
58:54	Majority problem under our model (1)
59:12	Majority problem under our model (2)
60:14	Thank you!

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

In distributed averaging and consensus algorithms, processors exchange and update certain values (or "estimates", or "opinions") by forming a local average with the values of their neighbors. Under suitable conditions, such algorithms converge to consensus (every processor ends up holding the same value) or even average-consensus (consensus is achieved on the average of the initial values held by the processors). Algorithms of this type have been proposed as a subroutine of distributed optimization methods, used to combine the results of different processors while a master algorithm is running. We overview a few applications of averaging algorithms, with a focus on gradient-like optimization methods. We then proceed to highlight some results, old and new, with a focus on convergence rates. We finally discuss some open problems.