More Like this

1. RoADTrain: Route-Assisted Decentralized Peer Model Training among Connected Vehicles

   Zheng, Han ; Liu, Mengjing ; Ye, Fan ; Yang, Yuanyuan ( January 2023 , IEEE International Conference on Distributed Computing Systems (ICDCS))

   Fully decentralized model training for on-road vehicles can leverage crowdsourced data while not depending on central servers, infrastructure or Internet coverage. However, under unreliable wireless communication and short contact duration, model sharing among peer vehicles may suffer severe losses thus fail frequently. To address these challenges, we propose “RoADTrain”, a route-assisted decentralized peer model training approach that carefully chooses vehicles with high chances of successful model sharing. It bounds the per round communication time yet retains model performance under vehicle mobility and unreliable communication. Based on shared route information, a connected cluster of vehicles can estimate and embed the link reliability and contact duration information into the communication topology. We decompose the topology into subgraphs supporting parallel communication, and identify a subset of them with the highest algebraic connectivity that can maximize the speed of the information flow in the cluster with high model sharing successes, thus accelerating model training in the cluster. We conduct extensive evaluation on driving decision making models using the popular CARLA simulator. RoADTrain achieves comparable driving success rates and 1.2−4.5× faster convergence than representative decentralized learning methods that always succeed in model sharing (e.g., SGP), and significantly outperforms other benchmarks that consider losses by 17−27% in the hardest driving conditions. These demonstrate that route sharing enables shrewd selection of vehicles for model sharing, thus better model performance and faster convergence against wireless losses and mobility. 

   more » « less
2. DART: Adaptive Accept Reject Algorithm for Non-Linear Combinatorial Bandits

   Agarwal, Mridul ; Aggarwal, Vaneet ; Umrawal, Abhishek K. ; Quinn, Christopher J. ( May 2021 , Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider the bandit problem of selecting K out of N arms at each time step. The joint reward can be a non-linear function of the rewards of the selected individual arms. The direct use of a multi-armed bandit algorithm requires choosing among all possible combinations, making the action space large. To simplify the problem, existing works on combinatorial bandits typically assume feedback as a linear function of individual rewards. In this paper, we prove the lower bound for top-K subset selection with bandit feedback with possibly correlated rewards. We present a novel algorithm for the combinatorial setting without using individual arm feedback or requiring linearity of the reward function. Additionally, our algorithm works on correlated rewards of individual arms. Our algorithm, aDaptive Accept RejecT (DART), sequentially finds good arms and eliminates bad arms based on confidence bounds. DART is computationally efficient and uses storage linear in N. Further, DART achieves a regret bound of Õ(K√KNT) for a time horizon T, which matches the lower bound in bandit feedback up to a factor of √log 2NT. When applied to the problem of cross-selling optimization and maximizing the mean of individual rewards, the performance of the proposed algorithm surpasses that of state-of-the-art algorithms. We also show that DART significantly outperforms existing methods for both linear and non-linear joint reward environments. 

   more » « less
3. Maximum Profit Facility Location and Dynamic Resource Allocation for Instant Delivery Logistics

   https://doi.org/10.1177/03611981221082574  

   Rajesh Chauhan, Darshan ; Unnikrishnan, Avinash ; Boyles, Stephen D. ( March 2022 , Transportation Research Record: Journal of the Transportation Research Board)

   Increasing e-commerce activity, competition for shorter delivery times, and innovations in transportation technologies have pushed the industry toward instant delivery logistics. This paper studies a facility location and online demand allocation problem applicable to a logistics company expanding to offer instant delivery service using unmanned aerial vehicles or drones. The problem is decomposed into two stages. During the planning stage, the facilities are located, and product and battery capacity are allocated. During the operational stage, customers place orders dynamically and real-time demand allocation decisions are made. The paper explores a multi-armed bandit framework for maximizing the cumulative reward realized by the logistics company subject to various capacity constraints and compares it with other strategies. The multi-armed bandit framework provides about 7% more rewards than the second-best strategy when tested on standard test instances. A case study based in Portland Metro Area showed that multi-armed bandits can outperform the second-best strategy by more than 20%.

    

   more » « less
4. Job Dispatching Policies for Queueing Systems with Unknown Service Rates

   https://doi.org/10.1145/3466772.3467047  

   Choudhury, Tuhinangshu ; Joshi, Gauri ; Wang, Weina ; Shakkottai, Sanjay ( July 2021 , ACM MobiHoc: International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks)

   null (Ed.)

   In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy. 

   more » « less
5. Automating Deep Neural Network Model Selection for Edge Inference

   https://doi.org/10.1109/CogMI48466.2019.00035  

   Lu, Bingqian ; Yang, Jianyi ; Chen, Lydia Y. ; Ren, Shaolei ( December 2019 , IEEE First International Conference on Cognitive Machine Intelligence (CogMI))

   The ever increasing size of deep neural network (DNN) models once implied that they were only limited to cloud data centers for runtime inference. Nonetheless, the recent plethora of DNN model compression techniques have successfully overcome this limit, turning into a reality that DNN-based inference can be run on numerous resource-constrained edge devices including mobile phones, drones, robots, medical devices, wearables, Internet of Things devices, among many others. Naturally, edge devices are highly heterogeneous in terms of hardware specification and usage scenarios. On the other hand, compressed DNN models are so diverse that they exhibit different tradeoffs in a multi-dimension space, and not a single model can achieve optimality in terms of all important metrics such as accuracy, latency and energy consumption. Consequently, how to automatically select a compressed DNN model for an edge device to run inference with optimal quality of experience (QoE) arises as a new challenge. The state-of-the-art approaches either choose a common model for all/most devices, which is optimal for a small fraction of edge devices at best, or apply device-specific DNN model compression, which is not scalable. In this paper, by leveraging the predictive power of machine learning and keeping end users in the loop, we envision an automated device-level DNN model selection engine for QoE-optimal edge inference. To concretize our vision, we formulate the DNN model selection problem into a contextual multi-armed bandit framework, where features of edge devices and DNN models are contexts and pre-trained DNN models are arms selected online based on the history of actions and users' QoE feedback. We develop an efficient online learning algorithm to balance exploration and exploitation. Our preliminary simulation results validate our algorithm and highlight the potential of machine learning for automating DNN model selection to achieve QoE-optimal edge inference. 

   more » « less