Optimization has been the workhorse of solving machine learning problems. However, the efficiency of these methods remains far from satisfaction to meet the ever-growing demand that arises in modern applications. In this context, the present dissertation will focus on two fundamental classes of machine learning problems: 1) stochastic nested problems, where one subproblem builds upon the solution of others; and, 2) stochastic distributed problems, where the subproblems are coupled through sharing the common variables.

One key difficulty of solving stochastic nested problems is that the hierarchically coupled structure makes the computation of (stochastic) gradients, the basic element in first-order optimization machinery, prohibitively expensive or even impossible.We will develop the first stochastic optimization method, which runs in a single-loop manner and achieves the same sample complexity as the stochastic gradient descent method for non-nested problems.

One key difficulty of solving stochastic distributed problems is the resource intensity, especially when algorithms are running atresource-limited devices. In this context, we will introduce a class of communication-adaptive stochastic gradient descent (SGD) methods, which adaptively reuse the stale gradients, thus saving communication. We will show that the new algorithms have convergence rates comparable to original SGD and Adam algorithms, but enjoy impressive empirical performance in terms of total communication round reduction.

This thesis focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while xing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize.

The great performance of coordinate update methods depends on solving simple subproblems. To derive simple subproblems for several new classes of applications, this thesis systematically studies coordinate friendly operators that perform low-cost coordinate updates.

Based on the discovered coordinate friendly operators, as well as operator splitting techniques, we obtain new coordinate update algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history.

Coordinate update algorithms can be used to develop decentralized algorithms for consensus optimization, which run over a network in which the agents communicate with their neighbors and perform local computation. Decentralized algorithms have broad applications and attract interest by itself. The second part of this thesis proposes an asynchronous, decentralized algorithm.

In the proposed algorithm, each agent can compute and communicate independently at different times, for different durations, with the information it has even if the latest information from its neighbors is not yet available. Such an asynchronous algorithm reduces the time that agents would otherwise waste idle because of communication delays or because their neighbors are slower. It also eliminates the need for a global clock for synchronization.

Mathematically, the algorithm involves both primal and dual variables, uses fixed stepsize parameters, and provably converges to the exact solution under a random agent assumption and both bounded and unbounded delay assumptions. When running synchronously, the algorithm performs just as well as existing competitive synchronous algorithms such as PG-EXTRA, which diverges without synchronization. Numerical experiments confirm the theoretical findings and illustrate the performance of the proposed algorithm.

In addition to the async-parallel coordinate selection rule well studied in the rst two parts of the thesis, we analyse the cyclic coordinate selection rules, where the ordering of coordinates in each cycle is arbitrary. The corresponding algorithms are fast, but their convergence is unknown in the fixed-point setting.

When T is a nonexpansive operator and has a fixed point, we show that the sequence of coordinate-update iterates converges to a fixed point under proper step sizes. This result applies to the primal-dual coordinate-update algorithms, which have wide applications to optimization problems with nonseparable nonsmooth objectives, as well as global linear constraints.

Numerical experiments are presented to compare the cyclic coordinate selection rule with the previous discussed rules.

Incorporating machine learning techniques into optimization problems and solvers attracts increasing attention. Given a particular type of optimization problem that needs to be solved repeatedly, machine learning techniques can find some features for this category of optimization and develop algorithms with excellent performance. This thesis deals with algorithms and convergence analysis in learning-based optimization in three aspects: learning dictionaries, learning optimization solvers and learning regularizers.

Learning dictionaries for sparse coding is significant for signal processing. Convolutional sparse coding is a form of sparse coding with a structured, translation invariant dictionary. Most convolutional dictionary learning algorithms to date operate in the batch mode, requiring simultaneous access to all training images during the learning process, which results in very high memory usage, and severely limits the training data size that can be used. I proposed two online convolutional dictionary learning algorithms that offered far better scaling of memory and computational cost than batch methods and provided a rigorous theoretical analysis of these methods.

Learning fast solvers for optimization is a rising research topic. In recent years, unfolding iterative algorithms as neural networks has become an empirical success in solving sparse recovery problems. However, its theoretical understanding is still immature, which prevents us from fully utilizing the power of neural networks. I studied unfolded ISTA (Iterative Shrinkage Thresholding Algorithm) for sparse signal recovery and established its convergence. Based on the properties of parameters required by convergence, the model can be significantly simplified and, consequently, has much less training cost and better recovery performance.

Learning regularizers or priors improves the performance of optimization solvers, especially for signal and image processing tasks.

Plug-and-play (PnP) is a non-convex framework that integrates modern priors, such as BM3D or deep learning-based denoisers, into ADMM or other proximal algorithms. Although PnP has been recently studied extensively with great empirical success, theoretical analysis addressing even the most basic question of convergence has been insufficient. In this thesis, the theoretical convergence of PnP-FBS and PnP-ADMM was established, without using diminishing stepsizes, under a certain Lipschitz condition on the denoisers. Furthermore, real spectral normalization was proposed for training deep learning-based denoisers to satisfy the proposed Lipschitz condition.

This dissertation focuses on a family of optimization methods called operator splitting methods. They solve complicated problems by decomposing the problem structure into simpler pieces and make progress on each of them separately. Over the past two decades, there has been a resurgence of interests in these methods as the demand for solving structured large-scale problems grew. One of the major challenges for splitting methods is their sensitivity to ill-conditioning, which often makes them struggle to achieve a high order of accuracy. Furthermore, their classical analyses are restricted to the nice settings where solutions do exist, and everything is convex. Much less is known when either of these assumptions breaks down.

This work aims to address the issues above. Specifically, we propose a novel acceleration technique called inexact preconditioning, which exploits second-order information at relatively low computation cost. We also show that certain splitting methods still work on problems without solutions, in the sense that their iterates provide information on what goes wrong and how to fix. Finally, for nonconvex problems with saddle points, we show that almost surely, splitting methods will only converge to the local minimums under certain assumptions.

This thesis focuses on coordinate update methods (CU), which are useful for solving problems involving large or high-dimensional datasets. Coordinate update methods decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize.

The great performance of coordinate update methods depends on solving sim- ple subproblems. To derive simple subproblems for several new classes of appli- cations, this thesis systematically studies coordinate friendly (CF) operators that perform low-cost coordinate updates. Based on the discovered coordinate friendly operators, as well as operator splitting techniques, I obtained new coordinate up- date algorithms for a variety of problems in machine learning, image processing, as well as sub-areas of optimization. Several problems are treated with coordinate update for the first time in history.

CU can be further scaled up to solve larger problems through asynchronous parallel (async-parallel) techniques. Asynchrony is crucial to parallel computing since it reduces synchronization wait, relaxes communication bottleneck, and thus speeds up computing significantly. I proposed ARock, an algorithmic framework in which multiple agents (machines, processors, or cores) update coordinates in an asynchronous parallel fashion. At each step of ARock, an agent updates a randomly selected coordinate based on possibly out-of-date information. Conver- gence results are established for solving fixed-point problems. Numerical tests on regression and equations show that ARock significantly outperforms its syn- chronous counterpart.

The other novel contribution of this thesis is the introduction of an abstract framework for implementing asynchronous parallel algorithms on shared memory platforms. The programming model adopts the thread library from C++ at its lowest level. At the highest level, the goal is to enable fast prototyping of async- parallel algorithms. I developed a multilevel approach to reduce the gap between expert to low-level programming and novice-level programming. A spectrum of applications have been implemented under this framework.

Machine learning (ML) has evolved dramatically over recent decades, from relative infancy to a practical technology with widespread commercial use. This same time period increasingly saw applications modeled as large scale optimization problems, reviving interest in first-order optimization methods (due to their low per-iteration cost and memory requirements). ML enables computers to improve automatically through experience. At first glance, this may appear to signal a pending end to hand crafted optimization modeling.Yet, optimization can provide intuition for effective ML model design. Also, some ML models cannot be considered trustworthy without guarantees (e.g. satisfaction provided constraints) and/or explanations of their behaviors. Design intuition from optimization led to experiments unrolling optimization algorithms into ML model architectures via what is now known as the "learn to optimize'' (L2O) paradigm. L2O models generalize hand-crafted optimization for use with big data and provide promising numerical results.

This work investigates L2O theory and implementations. Chiefly, we investigate L2O convergence guarantees, training of L2O models, how to interweave prior and data-driven knowledge, and how to certify L2O inferences comply with desired specifications. Thus, our core contribution is a fusion of optimization and machine learning, merging desirable properties from each field -- model intuition, guarantees, practical performance, and the ability to leverage big data. A progression of novel frameworks and theory are developed herein for L2O models, extending prior work in multiple directions.

In this thesis, we present a body of work on the performance and convergence properties of asynchronous-parallel algorithms completed over the course of my doctorate degree (Hannah, Feng, and Wotao Yin 2018; Hannah and Wotao Yin 2017b; T. Sun, Hannah, and Wotao Yin 2017; Hannah and Wotao Yin 2017a). Asynchronous algorithms eliminate the costly synchronization penalty of traditional synchronous-parallel algorithms. They do this by having computing nodes utilize the most recently available information to compute updates. However, it’s not immediately clear whether the trade-off of eliminating synchronization penalty at the cost of using outdated information is favorable.

We first give a comprehensive theoretical justification of the performance advantages of asynchronous algorithms, which we summarize as "Faster Iterations, Same Quality" (Hannah and Wotao Yin 2017a). Under a well-justified model, we show that asynchronous algorithms complete "Faster Iterations". Using renewal theory, we demonstrate how network delays, heterogeneous sub-problem difficulty and computing power greatly hinder synchronous algorithms, but have no impact on their asynchronous counterparts. We next prove the first exact convergence rate results for a variety of synchronous algorithms including synchronous ARock and synchronous randomized block coordinate descent (sync-RBCD). This allows us to make a fair comparison between these algorithms and their asynchronous counterparts. Finally, we show that a variety of asynchronous algorithms have a convergence rate that essentially matches the previously derived exact rates for synchronous counterparts so long as the delays are not too large. Hence asynchronous algorithms complete faster iteration that are of the "Same Quality" as synchronous algorithms. Therefore we conclude that a wide variety of asynchronous algorithms will always outcompete their synchronous counterparts if the delays are not too large, and especially at scale.

Next, we present the first asynchonous Nesterov-accelerated algorithm that attains a speedup: A2BCD (Hannah, Feng, and Wotao Yin 2018). We first prove that A2BCD attains NU_ACDM’s complexity to highest order. NU_ACDM is a state-of-the-art accelerated coordinate descent algorithm (Allen-Zhu, Qu, et al. 2016). Then we show that both A2BCD and NU_ACDM both have optimal complexity. Hence because A2BCD has faster iterations, and optimal complexity, it should be the fastest coordinate descent algorithm. We verify this with numerical experiments comparing A2BCD with NU_ACDM. We find that A2BCD is up to 4-5x faster than NU_ACDM, and hence conclude that our algorithm is the current fastest coordinate descent algorithm that exists. Finally, we derive a second-order ODE, which is the continuous-time limit of A2BCD. The ODE analysis motivates and clarifies our proof strategy.

Lastly, we present earlier foundational work that comprises the basis of the technical innovations that made the previous results possible (Hannah and Wotao Yin 2017b). We show that ARock and its many special cases may converge even under unbounded delays (both stochastic and deterministic). These results sidestep longstanding impossibility results derived in the 1980s by making slightly stronger assumptions. They were also an early demonstration of the power of meticulous Lyapunov-function construction techniques pioneered in this body of work.

This thesis is concerned with the design and analysis of algorithms that solve nonsmooth convex optimization problems in (possibly infinite dimensional) Hilbert spaces. There are many algorithms available to solve such problems, but the methods detailed in this thesis are particularly well-suited for solving complicated problems that are built from many simpler pieces. There are a wealth of applications for which such structure is present, and this has driven the recent resurgence of interest in so-called Operator-Splitting methods; these splitting methods completely disentangle complex problem structure and give rise to algorithms that repeatedly solve a series of simpler subproblems sequentially or in parallel. These algorithms are easy to implement, they have low per-iteration cost, and in practice, they are observed to quickly converge to solutions of modest accuracy. These qualities make splitting methods attractive options for solving large-scale problems in machine learning and signal processing.

Although splitting algorithms are known to converge, a general theoretical analysis of their convergence rates has remained elusive since their inception nearly in the 1950s. Furthermore, since 2000, no new splitting algorithms have been developed that do not reduce to one of three general methods (for solving general monotone inclusion problems). The purpose of this thesis is to address these theoretical challenges by deriving sharp convergence rates of existing splitting algorithms and developing a new splitting method that does not appear to reduce to any existing method. The analysis presented is particularly simple, and applies in many cases.