Zhouchen Lin - Alternating Direction Method of Multipliers for Machine Learning

This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd.

The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore

Alternating direction method of multipliers (ADMM) is an important algorithm for solving constrained optimization problems. It particularly fits well for the machine learning community because the latter basically favors algorithms with low per-iteration cost and does not need high numerical precision. Due to its versatility and high usability, I would not hesitate to make it one of the top recommendations if one wants to develop a general-purpose optimization library or AI chip. So there has been renewed interest on ADMM since its successful application in solving low-rank models around 2010. Since then, ADMM has been extended significantly, going far beyond the traditional setting: deterministic, convex, two-blocks of variables, and centralized. Unfortunately, the vast literature on ADMM is scattered across various sources, making it difficult for non-experts to track the advances in this important optimization technique. This book resolves this issue in a timely manner. Its materials are quite comprehensive, covering ADMM for various situations: convex (and deterministic), nonconvex, stochastic, and distributed. It is self-contained, with detailed proofs, so that even a beginner can grasp the state-of-the-art quickly, not just the pseudo-codes but also the proof techniques. More importantly, this book has not simply compiled various papers together. It has actually completely rewritten the materials so that the notations are consistent and the deductions are smooth, removing the major obstacle of reading existing literatures. In addition, the book puts more emphasis on convergence rates rather than only convergence. This makes the theoretical analysis extremely informative to practitioners. I would say that this book is definitely a valuable reference for researchers and practitioners from multiple areas, including optimization, signal processing, and machine learning.

The authors, Zhouchen Lin, Huan Li, and Cong Fang, are experts in the intersection of optimization and machine learning. Besides contributing greatly to this field with technical papers, they have also endeavored a lot in sorting out valuable algorithms that are fit for engineers, making another kind of good contribution to the community. After their previous book, Accelerated Optimization for Machine Learning: First-Order Algorithms, which I like very much, I am happy to advocate their book once more.

With the advance of sensor, communication, and storage technologies, data acquisition has become more ubiquitous than any time in the past. This has enabled us to learn a considerable amount of valuable information from big diverse data sets for effective inference, estimation, tracking, and decision-making. Learning from data requires the proper modelling and analysis of big data sets, which are usually formulated as optimization problems. Consequently, large-scale optimization involving big data has attracted significant attention from various areas, including signal processing, machine learning, and operations research.

To minimize a cost function involving a large number of variables, the most popular approach is block coordinate descent/minimization (sometimes also called alternating optimization). However, if variables are coupled linearly, the block coordinate descent/minimization method no longer works. The alternating direction method of multipliers (ADMM) can be considered an extension of block coordinate descent/minimization method for linearly constrained optimization problems. Given the abundance of application problems that can be cast in the form of linearly constrained optimization problems (convex/nonconvex, smooth/nonsmooth), ADMM has been the method of choice for machine learning and signal processing problems involving big data. It is widely (sometimes wildly) applied in many different contexts, often times without sufficient theoretical underpinning on its convergence.

This book provides an excellent summary of the state of the art for the theoretical research on ADMM. It introduces the basic mathematical form of ADMM as well as its variations. The core material is on the convergence analysis of ADMM for different classes of linearly constrained optimization problems, including convex, nonconvex, deterministic, stochastic, and centralized/distributed. The mathematical treatment is concise, up to date, and rigorous. A nice bonus is the last chapter where the practical aspects of ADMM are discussed, which should be very valuable for practitioners or first-time users of ADMM.

The first author is a well-known researcher in optimization, particularly on optimization methods for machine learning applications. The text is written in a reader friendly manner, complete with appendices that introduce the mathematical tools and background for the convergence analysis covered in the book. It should be a valuable reference for both researchers and users on ADMM and will be a great read for graduate students in optimization, statistics, machine learning, and signal processing.