On the Optimal Ensemble of Distributed DNN Models

In this paper, we introduce a novel problem of ensembling deep neural network (DNN) models distributed across the network, which can be a key element for distributed inference on resource-constrained end devices. We first develop a mixed integer linear program (MILP) that selects a combination of models to maximize accuracy on a negative sample set. Building on this formulation, we develop an MILP-based approach to determine an optimal path for ensembling distributed DNN models while satisfying a given latency constraint. The problem contains elements of the classical Traveling Purchaser Problem (TPP) and submodular function maximization, both of which are NP-hard. As the problem contains doubly NP-hard subproblems, we develop heuristic algorithms (some with approximation guarantee) for each subproblem in order to construct high-accuracy ensembles while adhering to latency constraints. Through extensive simulations, we demonstrate that our approach effectively finds an ensemble of models with high accuracy and low latency in distributed settings.