Distributed convex optimization refers to the task of minimizing the aggregate sum of convex risk functions, each available at an agent of a connected network, subject to convex constraints that are also distributed across the agents. The risk functions at the agents are generally de fined as expectations of certain loss functions, with the expectations computed over the statistical distribution of the data. One of the key challenges in solving such optimization problems is that the agents are only subjected to streaming data realizations and they are not aware of the underlying statistical models. Accordingly, each agent is only aware of its loss function and does not have sufficient information to evaluate its risk function. Another key challenge is that each agent is only aware of its constraints. This dissertation develops and studies fully decentralized fi rst-order strategies to solve such problems.
The fi rst class of strategies considered in this work belongs to the family of primal-dual methods, which rely on propagating two sets of variables: the primal variable and a dual variable. In contrast to the traditional treatment of these algorithms in the optimization literature, this dissertation develops primal-dual methods for adaptation and learning from streaming data over networks. In this case, the optimization problem is not necessarily static since its minimizer can drift with time and the exact form of the cost function is not known beforehand. Fully-distributed and adaptive variants of the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) methods are developed by resorting to stochastic-gradient approximations. The stability range and the performance limits of the resulting strategies are analyzed. Several revealing results are discovered including the fact that primal-dual techniques tend to have a smaller stability range and a degraded performance in comparison to primal techniques, such as consensus and diff usion strategies. This conclusion suggests that AH and AL techniques are not as reliable for adaptation over networks and the advantages of AH and AL techniques in the static optimization context do not necessarily carry over to the stochastic context.
The dissertation subsequently focuses on developing primal optimization methods of the diff usion type for the distributed solution of a general class of constrained optimization problems. Most available distributed solutions for these types of problems rely on the use of projection steps in order to ensure that the successive iterates at the nodes satisfy the convex constraints. In these solutions, the constraint conditions need to be relatively simple in order for the distributed algorithm to be able to compute the necessary projections analytically (such as projecting onto the nonnegative orthant). This work proposes a new class of distributed solutions that employ constant step-sizes and that eliminate the need for projection steps. The solution technique relies instead on the use of suitably chosen penalty functions and replaces the projection step by a stochastic approximation update that run concurrently with the optimization step. The challenge is to show that the use of penalty functions in the stochastic gradient update step still leads to accurate solutions. The analysis in the dissertation establishes that this is indeed possible. Moreover, in the proposed solution, the nodes are only required to interact locally and to have access to local iterates from their neighbors; there is no need for the nodes to know any of the constraints besides their own.
Acknowledgment This work was supported in part by NSF grants CCF-1011918 and CCF-0942936. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsor.