Decentralized Optimization for High-dimensional Learning
Abstract
AbstractThe Internet of Battle Things (IoBT) encompasses numerous interconnected, heterogeneous assets such as sensors, unmanned platforms, and wearable devices. The potential of enabling autonomous swarm capabilities is unlimited. These assets gather and processinformation, support sense making, coordinate defensive actions, impact adversaries, and offer better Intelligence, Surveillance, and Reconnaissance, to name a few. Enabling autonomous swarming and machine learning capabilities call for new interdisciplinary principles and decentralized algorithms.In this proposal, we focus on decentralized (stochastic) optimization for high-dimensional inference over mesh networks, where no centralized coordination is present. High-dimensional models subsume the number of decision variables to be larger than the total sample size over the network, making the learning problems ill-conditioned. The goal is to exploit latent low-dimensional structures in the network data (e.g., sparsity, low-rank) to achieve statistical consistency in a resource-efficient manner. While statistical-computational guarantees of centralized high-dimensional learning are well studied, our understanding in the network setting is unsatisfactory, even for simple learning tasks: (i) distributed schemes, designed and performing well in the low dimensional regime, can break down dramatically in the high-dimensional case; and (ii) existing convergence studies fail to provide useful predictions; they are in fact confuted by experiments.By merging decentralized optimization and high-dimensional statistics, this project aims to address these challenges by proposing a novel stochastic distributed algorithmic framework for various high-dimensional M-estimation problems over mesh networks, accommodating both batch or streaming (stochastic) data oracles. The crux of the proposed approach is a novel statistically informed decomposition that leverages local surrogates of the centralized (unknown) loss in tandem with in-network communication protocols, to iteratively refine agents# local estimates up to statistical optimality. This framework offers unprecedented design flexibility and guarantees, engineered to meet diverse computational and communication constraints. Fundamental tradeoffs in the statistical error, computational demands, and communication costs will be uncovered, along with optimal scaling designs concerning sample size, ambient dimension, and optimization/network parameters. The proposed research will be complemented and validated using a multi-tiered experimental approach, leveraging synthetic data generation models, real-world data sets, as well as hands-on experiments using test-bed epuck robots.To our knowledge, this is the first time that such a comprehensive platform is proposed for the design of (stochastic) decentralized algorithms optimized for various high-dimensional inferential tasks, while efficiently allocating computational, data, and network resources.Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412751
Entities
People
- Gesualdo Scutari
Organizations
- Office of Naval Research
- Purdue University
- United States Navy