THIS IS A CONTINUATION OF N00014-12-1-0997 New Paradigms For Scalable Online Decentralized Optimization
Abstract
Statement of Work:The proposed effort will center on developing new theoretical and algorithmic tools that change the paradigm of decentralized optimization.Objective:The proposed effort will center on developing new theoretical and algorithmic tools that change the paradigm of decentralized optimization along threemajor directions: First, the proposed methods move away from current first-order, (sub)gradient-based decomposition methods which can be traced back to the seminal Dantzig-Wolfe decomposition results developed in the middle of last century. These methods gained popularity in the networking and optimizationliteratures because they involve simple computations and lead to distributed implementations in network settings.However, these methods suffer from slow rate of convergence. The PI proposes to build upon our promising recent results and focus on fast, second order Newton-type methods that exhibit super-linear convergence rate without any centralized coordination. When all the information is stored at a central location, using second order methods is quite standard: one can store and compute the Hessian and solve theoptimization centrally. The basic research challenge here is to be able to use second order methods in a distributedfashion without requiring additional information exchangecompared to existing distributed first order methods.The second point of departure from state of the art is to focus on principled approaches to online convex optimization and regret minimization, whereinformation is revealed incrementally and in real-time, and there is no batch processing.Approach:The proposed research will focus on three thrusts:[T1] Scalable decentralized optimization for canonical network problems. [T2] Online distributed convex optimization and regret-based methods.[T3] Algorithmic innovations in distributed optimization.In Thrust 1, the PI will address various canonical network optimization problems including single and multi-commodityflow, dynamic Network Utility Maximization (NUM), and multi-agent optimization with non-separable local objectivefunctions (capturing settings where utility of cost function not only depends on the resource allocated to a particular agent but also depends on the externalities created by the decisions of other agents).In Thrust 2, the PI will develop a theory of online convex optimization and regret minimization. First, we will develop a second order, fast-converging analogue of real-time stochastic multi-commodity flow problems.In the Thrust 3, the PI will investigate algorithmic innovations that could make such algorithms even faster and more scalable. In particular, the research will focus on two directions: utilize the exciting recent algorithmic innovations for solving diagonally dominant linear system of equations (which happen to be the same set of equations that need to be solved for computing the Newton direction) in sublinear time, and a new approach for performing inexact line search, the process of finding the step-size without actually solving an optimization problem. A key challenge in implementing Newton-type methods is stepsize selection for generating solution estimates iteratively, which require global information and coordination.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 canonicalexample 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)
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 26, 2018
- Source ID
- N000141612145
Entities
People
- Ali Jadbabaie
Organizations
- Office of Naval Research
- United States Navy
- University of Pennsylvania