Networks and large scale optimization
Networks and large scale optimization


Optimization is at the core of machine learning. The size and complexity of modern datasets and models now often requires us to solve optimization problems over multiple computing units, possibly distributed over a network. In this tutorial, we review a very powerful optimization method, known as the Alternating Direction Method of Multipliers (ADMM), and how it can help solve large machine learning problems in a distributed setting. ADMM it is typically applied when the objective function can be decomposed into a sum of functions over a set of shared variables. This decomposition defines a network (a bipartite graph), which, if tailored to the topology of a computing network, allow us to use ADMM to solve large problems over a computing network as a distributed message-passing scheme. After we review the ADMM, we explain how to use it to solve optimization problems in machine learning, robotics, computer vision, physics, and chemistry. We also review a variant of ADMM known as the Three Weight Algorithm (TWA), a set of rules for dynamically updating the weights in ADMM's message-passing scheme. The message-weights are restricted to three different values: infinity for absolute confidence, zero for complete lack of confidence and 1 as a default confidence level. We show how the TWA, a simple change in ADMM, can have an enormous impact on the speed with which it finds good approximate solutions for non-convex problems, e.g. constraint satisfaction problems. Finally, we discuss the networks that different problems can generate, and how their topologies might affect ADMM's convergence speed.


Sam Safavi received his B.S. degree in Electrical Engineering from University of Tehran, Iran, in 2007, M.S. degree in Automated Systems and Control, from University of Sheffield, United Kingdom, in 2011, and Ph.D. degree in Electrical and Computer Engineering from Tufts University, Medford, MA, in 2017. He is currently a postdoctoral scholar in the Computer Science department at Boston College, Chestnut Hill, MA, which he joined in January 2018. His research interests include optimization theory, machine learning, signal processing on graphs, and multi-agent networks.

Open Data Science




Open Data Science
One Broadway
Cambridge, MA 02142

Privacy Settings
We use cookies to enhance your experience while using our website. If you are using our Services via a browser you can restrict, block or remove cookies through your web browser settings. We also use content and scripts from third parties that may use tracking technologies. You can selectively provide your consent below to allow such third party embeds. For complete information about the cookies we use, data we collect and how we process them, please check our Privacy Policy
Consent to display content from Youtube
Consent to display content from Vimeo
Google Maps
Consent to display content from Google