THIS IS A CONTINUATION OF N00014-12-1-1002 Distributed Online Optimization in Dynamic Networks
Abstract
Statement of Work:This research effort proposes a distributed online optimization framework for the operation of multi-agent networkedsystems.Objective:In this proposal, inspired by recent results in the machine learning and networked systems literature, the PI proposes a distributed online optimization framework for the operation of multi-agent networked systems, where the cost function modeling the environment is revealed over time and the spatial information and coupling geometry among the agents satisfy a graph structure or a sparsity pattern. The focus is mainly on convex problems, which are more amenable toanalysis.Approach:The proposed research addresses complementary facets of such a problem setup, including deriving bounds on social regret, capturing the dependence of achievable performance by multi-agent distributed systems on abstractions that encode temporal and spatial structures and uncertainties. The PI will also look at novel techniques for decentralized online optimization that exploits the structural features of problem in terms of hypergraphs. Online dynamic network formation is also examined in this project, both for scenarios where the agents are driven by local utility functions forrestructuring their interaction and information-exchange networks as well as when the network is envisioned to respond and restructure autonomously due to adversarial actions with cost structure that is only revealed incrementally. Online resource allocation with budget constraints over time, and performance analysis of distributed algorithms for this challenging class of problems, comprise the third component of the proposed project.Overall Merit and ONR Mission/Relevance:The research is innovative in that it includes the development of rigorous algorithmic-analysis techniques for decentralized online optimization that provides performance predictions through sound estimates of the closeness a decentralized online solution to a centralized, global offline optimal solution; such performance guarantees contribute tremendously to trust in these systems, which is critical for their deployment. The Navy is moving towards deploying large, complex systems that are beyond centralized control. A canonical example of such a system is a fleet of unmanned vehicles with limited communications operating in a dynamic environment. Important characteristics of these systems are that 1) they are decentralized (i.e., system components can take independent actions), and 2) the environment in which the system operates is not necessarily known a priori,and is revealed over time. The objective of this topic is to develop scientific principles and algorithms for solvingdecentralized, online optimization problemsProgress:1) Online distributed Convex Optimization: In the current funding period we have continued our work on extendingcertain classes of distributed optimization algorithms to the online scenario where the information is revealed to the decision-maker/algorithm over time. In particular, sharp results relating the network structure on the performance of online optimization algorithms have been obtained. This work has utilized dual averaging as a basic construct for distributed online convex optimization and has paved the way for a flexible framework for proposing and deriving performance bounds for such a setup.2) A Proximal-Gradient Homotopy Algorithm for Norm-Regularized Problems: Along the same line of developing fast convex optimization algorithms that scale to large problems, we also studied the convergence rate of proximal-gradienthomotopy algorithm for norm-regularized least squares problems. This problem comes up, for example, in estimation tasks given some prior information (e.g., sparsity, group sparsity, or low-rank structure) on the signal to be estimated. Our contribution in this work was presenting an algorithm that generalizes results on the linear convergence of homotopy algorithm for `1-regularized least squares problems, to
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 23, 2016
- Source ID
- N000141612789
Entities
People
- Maryam Fazel
Organizations
- Office of Naval Research
- United States Navy
- University of Washington