Distributed Robust Nonconvex Optimization over Time-Varying Networks: Tradeoffs and Guarantees
Abstract
The battlefield of the future will be densely populated by a variety of numerous heterogeneous (intelligent) devices (referred to as the Internet of Battle Things (IoBT))--sensors, actuators, vehicles, robots, and human wearable devices--performing a broad range of tasks, including sensing, processing information communicating, acting, and jointly optimizing and executing. This IoBT vision, however, poses several challenges, which call for new theory, methods, and optimization algorithms. First, the IoBT will have to assist humans in making useful sense of massive, complex information, captured by several assets deployed in the battlefield; this calls for the solutions of huge scale optimization problems. Furthermore, many data-analytic tasks rely on fitting highly nonlinear and/or discrete models to data, which in general requires solving highly nonconvex problems. These nonconvex large-scale models are poorly understood. It urges rethinking the interplay between statistical optimality--globally optimal solutions of nonconvex models--and computable solutions, blending computational thinking with statistical frameworks. Second, in IoBT data-intensive applications, the sheer volume and spatial/temporal disparity of data render centralized processing and storage a formidable task. There is an urgent need, thus, of developing communication-constrained distributed optimization algorithms that operate seamless i) in-network, to offer robustness to possible failures/attacks of the central units; ii) in parallel, by exploiting multicore architectures (which may be even distributed over the Cloud), to accommodate the need of fast (realtime) processing and optimization; and iii) in asynchronous modes, where workers are not required to synchronize their updates/actions. Third, communications among large numbers of heterogeneous ``things will have to be flexible and adaptive to rapidly changing situations and military missions as well as robust with respect to time-varying topologies and network failures. This proposal aspires to tackle the above grand challenges proposing SCANET--Successive Convex Approximation methods overNETworks--an efficient, distributed algorithmic framework for (stochastic) nonconvex optimization problems and learning tasks that promises statistical and computational guarantees. The crux of the proposed framework is a novel convexification-decomposition technique for a general class of nonconvex, nonseparable (possibly stochastic) multiagent optimization, coupled with a novel tracking mechanism which aims at dynamically and locally estimating the missing global information. By unlocking for the first time block- and optimization-driven communications, this new class of algorithms is expected to address the shortcomings of current (distributed) convex approximation techniques by enabling full control of the degree of parallelism and distribution of the computation/communication among processors/network assets, as well as offering more flexible selections of convex approximants and communication protocols. Furthermore, the algorithms will be robustified gainst network failures, asynchrony, noisy/quantized communications, and time-varying/ random topologies. To the best of our knowledge, this is the first attempt to design provably distributed algorithms for nonconvex multiagent optimization and and learning with computational and statistical guarantees.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1810238
Entities
People
- Gesualdo Scutari
Organizations
- Army Contracting Command
- United States Army
- University of Virginia