Research summary

My research focuses on optimization methods and algorithms for large-scale problems.

Async-parallel computing

Since 2005, the single-threaded CPU speed has stopped improving; it is the number of cores in each CPU and the number of CPUs in each workstation that continue to arise. Already we can buy 8-core phones, 64-core workstations, and 2.5k-core GPUs. On the other hand, most of our algorithms are still single-threaded, and because so, their running time will stay the same in the future, say, ten or twenty years. To develop faster algorithms, especially for those large-scale problems that arise in signal processing, medical imaging, and machine learning, it is inevitable to consider parallel computing.

In parallel computing, a computational problem is solved by multiple agents (CPU cores) that concurrently solve simpler subproblems. For most, the subproblems depend on each other, so the agenets must regularly exchange information. In asynchronous computing, each agent can compute with the information it has, even if the latest information from other agents has not yet arrived. Asynchronism is extremely important to the efficiency and resilience of parallel computing. Without asynchronism, all cores have to wait for the arrival of latest information, so the speed of parallel computing is dictated by the slowest core, the most difficult subproblem, and/or the longest communication delay. Without asynchronism, the entire parallel computing must stop when an agent (or a network link) is failed and awaits a fix, and such failures will happen more often as the system gets larger. Today, most algorithms are still singled-threaded, and most of the already-parallelized algorithms are synchronous. Although challenging in both mathematical and coding perspectives, it is imperative to develop the theory and algorithms for asynchronous parallel computing, in order to release the power future computing platforms.

First-order methods and operator splitting for optimization

During the 70s–90s the optimization community focused more on second-order methods as they are more efficient for the computational problem sizes of interest at the time. First-order methods, which includes most operator splitting methods, can be described and analyzed with gradients and subgradients, while second-order methods use second-order derivatives or their approximations.

Within the past decade, however, the demand to solve ever larger problems grew. Many large problems are further complicated by non-differentiable functions and constraints. Because simple first-order and classic second-order methods are ineffective or infeasible for these problems, operator splitting methods regained their popularity.

Operators are used to analyze and develop algorithms for a wide range of problems such as optimization problems, variational inequalities, and differential equations. Operator splitting is a framework that generates algorithms through decomposing a problem into smaller and simpler subproblems: complicated structures like non-differentiable functions, constraint sets, and distributed problem structures are handled elegantly in this framework. Operator splitting provide the most effective means to handle such complicated structures for computational problem sizes of modern interest.

Sparse optimization

What is common in all l1 or l1-like minimization problems mentioned above is that the data is dense; it is the solutions that are sparse. Traditional approaches for solving these problems reduce them to standard optimization problems, which are then solved by algorithms that exploit only data structures such as matrix sparsity. Therefore, the challenge is to develop algorithms that take advantages of the structure of the solutions rather that of the data. To address this challenge, I have been recently working on first-order algorithms specifically designed for solving large-scale optimization problems involving various l1 and l1-like functions. I also worked on new total variation algorithms that yields recovered images of screen resolutions as fast as in seconds. The underlying idea also led to fast algorithms for color image processing and MR image reconstruction. In addition, for iterative thresholding based algorithms, we discovered useful properties such as quick identification of nonzero entries in sparse solutions and the q-linear global convergence. These results are potentially useful in reducing the original problem, before it is fully solved, into one that is much smaller. It was also discovered that the Basis Pursuit problem, a constrained optimization for signal recovery in compressed sensing, can be solved by the Bregmen method, which takes only a small and provably finite number of iterations. A slightly different version of it, called the linearized Bregman method, is more interesting because its intermediate solutions are mostly sparse, making the method especially suitable for certain matrix problems. In this research I expect to develop a set of strategies of exploiting solution structures that can be widely applied to many algorithms.