*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Dynamic Optimization problems on graphs with overlapping variables: analysis, algorithms, and applications
Committee:
Dr. Justin Romberg, ECE, Chair, Advisor
Dr. Mark Davenport, ECE
Dr. Yorai Wardi, ECE
Dr. Arkadi Nemirovski, ISyE
Dr. Adam Charles, Princeton
Abstract: This dissertation studies optimization problems on graphs with overlapping variables. That is, optimization problems their objective can be expressed as the sum of overlapping (sharing) local loss functions; each loss function depends on a small subset of the optimization variables. Such problems arise in signal processing, machine learning, control, statistical inference, and many other related fields. For example, the data defining the loss functions have a significant spatial or temporal dependency. To expose the local structure of these problems, we cast them on graphs. Each node is associated with a loss function and edges whenever two loss functions share variables. The goal is to use the graph's topology to assume better ways to solve these problems. First, we consider problems with graphs with fixed topology; the emphasis is on deriving efficient decentralized algorithms to solve such large-scale problems. Our approach approximates how natural coupled-dynamical systems evolve. Each agent solves a local problem communicates its solution to agents with which it shares variables. We show how algorithms as the Jacobi method and ADMM solve these problems fully decentralized. Afterward, we move to graph problems with dynamical topologies that arise in time-varying optimization programs, where we get chain-like graphs. In particular, we are interested in how the solution for the t-th frame of variables changes in time: while adding a new functional and a new set of variables does, in general, change the solution everywhere, we give conditions under which the local estimates converge to limit points at a linear rate. Consequently, we derive theoretical guarantees for algorithms with limited memory and derive a new memory-efficient Newton online algorithm (NOA). We consider two natural extensions to the fundamental time-varying problem: convex optimization problems with local bounded constraints and the case where there is no transparent growth model of the dynamics. Through this work, we present numerous examples of various applications where these results apply, including signal reconstruction, image denoising, graph min-cut, Bayesian inference, simultaneous localization and mapping (SLAM), multi-task learning, and estimating neural rate function from spikes train.
