BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Computational Optimisation Group - ECPv5.16.1.1//NONSGML v1.0//EN CALSCALE:GREGORIAN METHOD:PUBLISH X-WR-CALNAME:Computational Optimisation Group X-ORIGINAL-URL:https://optimisation.doc.ic.ac.uk X-WR-CALDESC:Events for Computational Optimisation Group BEGIN:VTIMEZONE TZID:UTC BEGIN:STANDARD TZOFFSETFROM:+0000 TZOFFSETTO:+0000 TZNAME:UTC DTSTART:20180101T000000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT DTSTART;TZID=UTC:20180119T111500 DTEND;TZID=UTC:20180119T123000 DTSTAMP:20240329T083228 CREATED:20180105T143648Z LAST-MODIFIED:20180105T143707Z UID:1024-1516360500-1516365000@optimisation.doc.ic.ac.uk SUMMARY:Seminar: ADMM and Random Walks on Graphs DESCRIPTION:Title: ADMM and Random Walks on Graphs\nSpeaker: Prof. José Bento\nAffiliation: Dept. of Computer Science\, Boston College\nLocation: Room 217 Huxley Building\nTime: 11:15am – 12:30pm \nAbstract. A connection between the distributed alternating direction method of multipliers (ADMM) and lifted Markov chains was recently proposed by Franca et al. 2016 for a non-strictly-convex consensus problem parametrized by a graph G. This was followed by a conjecture that ADMM is faster than gradient descent by a square root factor in its convergence time\, in close analogy to the mixing speedup achieved by lifting several Markov chains. Nevertheless\, a proof was lacking. In this talk\, I will start by revisiting Franca’s conjecture. Afterwards\, I will fully characterize the distributed over-relaxed ADMM for this consensus problem in terms of the topology of the graph G.  To be specific\, I will relate its convergence rate with the mixing time of random walks on the graph G. A consequence of this result is a proof of the aforementioned conjecture\, which\, interestingly\, is valid for any graph\,  even those whose random walks cannot be accelerated via Markov chain lifting. \nAbout the speaker. José Bento completed his Ph.D. in Electrical Engineering at Stanford University where he worked with Professor Andrea Montanari on statistical inference and structural learning of graphical models. After his Ph.D.\, he moved to Disney Research\, Boston lab\, where he worked with Dr. Jonathan Yedidia on algorithms for distributed optimization\, robotics\, and computer vision. He is now with the Computer Science department at Boston College. His current research lies at the intersection of distributed algorithms and machine learning. In 2014 he received a Disney Inventor Award for his work on distributed optimization\, which recently lead to an approved patent. In 2016 he was awarded a $10M NIH joint grant to study the emergence of antibiotic resistance and in 2017 a $2M NSF joint grant to study measures of distance between large graphs. URL:https://optimisation.doc.ic.ac.uk/event/seminar-admm-and-random-walks-on-graphs/ END:VEVENT END:VCALENDAR