BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20170101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20180119T111500
DTEND;TZID=UTC:20180119T123000
DTSTAMP:20260430T160249
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