We study the online Generalized Magician’s Problem with Multiple Workers (GMPMW), where tasks arrive sequentially and must be assigned to one of several workers for processing, with each worker consuming a stochastic amount of resources and generating an unknown reward. The system must decide on the acceptance of each task and its assignment to a worker, in order to maximize the accumulated reward within the budget. To address this problem, we propose the Online Worker Assignment (OWA) Algorithm. It optimally solves an optimization problem to balance resource allocation across workers and maintains virtual resource utilization according to the joint evolution of different workers. The competitive ratio of OWA is lower bounded by the closed-form expression $\max${${1}/{L},c$}$\cdot(1-K^{-\frac{1}{2}})$, where $L$ is the number of workers, $K$ is the resource budget, and $c$ is a constant derived from the problem instance. We perform trace-driven experiments with real-time video analytics, demonstrating the excellent capability of OWA to accommodate multiple workers in GMPMW.

Federated unlearning (FU) algorithms offer participants in federated learning (FL) the "right to be forgotten'' for their individual data and its impact on a collaboratively trained model. Existing FU algorithms primarily focus on accelerating the retraining process and enhancing the utility of the retrained models following data removal requests. However, these approaches generally lack consideration for the robustness of FU algorithms in potential adversarial environments, where adversaries can craft malicious data removal requests to compromise the retrained model. In this work, we introduce a robust federated unlearning framework (robustFU) which notably enhances the resilience of FU algorithms against a wide range of adversarial attacks. In robustFU, we design a novel dynamic conflict sample compensation algorithm that dynamically reintroduces randomly generated samples with significant information gain to the participating clients during retraining. Additionally, robustFU employs an innovative global reweighting mechanism which adjusts the weight of each model update during the global aggregation, based on its degree of misalignment with the trained model prior to unlearning. Extensive experiments demonstrates the effectiveness and robustness of the proposed robustFU framework under adversarial environments. Furthermore, robustFU significantly accelerates the retraining process, achieving a 2.53× speed-up compared to the retrain from the scratch baseline.

IoT (Internet of Things) cameras have widely been deployed over the last few years. These cameras are often with limited hardware so that they can only capture noisy videos in low resolution. In this work, we propose the joint video denoising and super-resolution network for IoT cameras, which consists of the noise-robust moving-attention (NRMA) module and the noise-eliminated upsampling (NEU) module. In NRMA, we adopt a coarse-to-fine approach by first extracting the coarse flow and then refining through bi-directional feature propagation among adjacent frames. In NEU, we further utilize inner-frame features for noise-elimination and upsampling. Through this approach, we avoid the negative effects brought by applying denoising and super-resolution in tandem, and enhance the reconstruction of moving objects by the embedded attention layers in NRMA. We conduct our experiments on both synthetic datasets, which utilize existing data with additive white Gaussian noise (AWGN), and a realistic dataset captured using a pair of IoT and professional cameras. Our extensive experimental results demonstrate that our proposed method significantly reduces noise and enhances detail in both types of datasets. Notably, our approach outperforms the state-of-the-art benchmark (RealBasicVSR) by an average of 5.24 dB on the existing datasets (with noise level σ = 20) and by 0.95 dB on the realistic dataset in terms of PSNR.

We study a new online assignment problem, called the Online Task Assignment with Controllable Processing Time. In a bipartite graph, a set of online vertices (tasks) should be assigned to a set of offline vertices (machines) under the known adversarial distribution (KAD) assumption. We are the first to study controllable processing time in this scenario: There are multiple processing levels for each task and higher level brings larger utility but also larger processing delay. A machine can reject an assignment at the cost of a rejection penalty, taken from a pre-determined rejection budget. Different processing levels cause different penalties. We propose the Online Machine and Level Assignment (OMLA) Algorithm to simultaneously assign an offline machine and a processing level to each online task. We prove that OMLA achieves 1/2-competitive ratio if each machine has unlimited rejection budget and Δ/(3Δ-1)- competitive ratio if each machine has an initial rejection budget up to Δ. Interestingly, the competitive ratios do not change under different settings on the controllable processing time and we can conclude that OMLA is "insensitive" to the controllable processing time.

Real-time video surveillance cameras have been widely deployed over the last few years. In case of incidents such as natural disasters, it provides vital guidance in real time to aid the rescue operations. However, the quality of the captured video is far from satisfactory due to the limited camera hardware and low network bandwidth. Noise is often observed especially at night and the resolution is low. To this end, we are motivated to retrieve the nighttime surveillance video through calibrated denoising and super-resolution. We only use the preceding and current frames, but not the future frames. Thus, we avoid the additional delay of waiting for future frames, which is not suitable for real-time video applications. We design the pipeline semantically beneficial for both denoising and super-resolution, and achieve high rendering quality, especially for real-world noise. Moreover, we propose a novel calibration method for collecting paired noisy and clean observations in the real world, which provides more effective training data. We conduct experiments using the real-world dataset collected under low-light conditions, and benchmark with state-of-the-art video denoising and super-resolution methods. Results show that our method achieves significant performance gain while introducing small delay compared with the benchmarks, suitable for real-time videos.

Abstract We present a novel online decision-making solution, where the optimal path of a given decision tree is dynamically found based on the contextual bandits analysis. At each round, the learner finds a path in the decision tree by making a sequence of decisions following the tree structure and receives an outcome when a terminal node is reached. At each decision node, the environment information is observed to hint on which child node to visit, resulting in a better outcome. The objective is to learn the context-specific optimal decision for each decision node to maximize the accumulated outcome. In this paper, we propose Dynamic Path Identifier (DPI), a learning algorithm where the contextual bandit is applied to every decision node, and the observed outcome is used as the reward of the previous decisions of the same round. The technical difficulty of DPI is the high exploration challenge caused by the width (i.e., the number of paths) of the tree as well as the large context space. We mathematically prove that DPI’s regret per round approached zero as the number of the rounds approaches infinity. We also prove that the regret is not a function of the number of paths in the tree. Numerical evaluations are provided to complement the theoretical analysis.

We study the multi-machine task scheduling problem in an integrated serverless edge and cloud computing system, where tasks can be scheduled locally on edge processors or offloaded to cloud servers, with the objective of minimizing the makespan, i.e., the total time to finish all tasks. The system is semi-online, where the edge processing delays of the tasks are known as priori, but the cloud processing delays remain unknown due to the uncertainty introduced by uploading and loading delay (loading the software environment). The problem is NP-hard in nature, and therefore we resort to approximation schemes and propose a novel algorithm named multi-machine with restart scheduling (MRS). MRS utilizes task restart, where a task that is cancelled will be restarted later when its processing time exceeds the threshold, and the threshold can be adaptively adjusted. We derive an competitive ratio for MRS so that its worst-case gap from the optimal solution is bounded. We also implement the MRS scheduler in a real-world system, which schedules a diverse set of Deep Neural Network (DNN) inference tasks. It shows that MRS achieves significant reduction in makespan compared to existing benchmark schemes.

Video surveillance cameras have been extensively deployed over the last few years. In case of incidents such as natural disaster rescue, it provides vital guidance in real-time. However, due to the limited camera hardware and network bandwidth, noise are observed especially at night and the resolution is low. To tackle these two issues, we design and implement EADV, an Edge-Assisted Deep Video denoising and super-resolution system for real-time surveillance at night. We demonstrate the video quality enhancement using a camera, a displayer, and an edge server. The low-quality video captured by the camera is enhanced by the server and shown on the displayer. The enhanced real-time video is smooth and the performance uplift is observable.

We present a novel learning framework that utilizes the early exit of Deep Neural Network (DNN), a device-only solution that reduces the latency of inference by sacrificing a reasonable degree of accuracy. Choosing the optimal exit point is challenging as the delay and the accuracy of each exit point are random and cannot be known in advance. The problem is further complicated as the overall duration of the processing is also unknown. To this end, we propose Learning Early Exit (LEE), an online learning scheme based on multi-armed bandits analysis. LEE efficiently learns the optimal exit point for mobile-based DNN inference while simultaneously balancing the exploration-exploitation trade-off. LEE differs from the standard bandit analyses in two ways: the reward of choosing each exit point addresses the confidence-latency trade-off, and the time duration between each action is random (i.e., the latency of each action is random). LEE addresses the aforementioned challenges and it achieves asymptotically optimal performance. We implement a real-world system with a real-time testbed that can be deployed in a driving system. DNN models with multiple exit points are trained and deployed in the testbed so that the performance of LEE and benchmark schemes can be tested and compared. The result denotes that LEE substantially outperforms the benchmark schemes.

Recent advances in Deep Neural Networks (DNNs) have dramatically improved the accuracy of DNN inference, but also introduce larger latency. In this paper, we investigate how to utilize early exit, a novel method that allows inference to exit at earlier exit points at the cost of an acceptable amount of accuracy. Scheduling the optimal exit point on a per-instance basis is challenging because the realized performance (i.e., confidence and latency) of each exit point is random and the statistics vary in different scenarios. Moreover, the performance has dependencies among the exit points, further complicating the problem. Therefore, the optimal exit scheduling decision cannot be known in advance but should be learned in an online fashion. To this end, we propose Dynamic Early Exit (DEE), a real-time online learning algorithm based on contextual bandit analysis. DEE observes the performance at each exit point as context and decides whether to exit or keep processing. Unlike standard contextual bandit analyses, the rewards of the decisions in our problem are temporally dependent. Furthermore, the performances of the earlier exit points are inevitably explored more compared to the later ones, which poses an unbalance exploration-exploitation trade-off. DEE addresses the aforementioned challenges, where its regret per inference asymptotically approaches zero. We compare DEE with four benchmark schemes in the real-world experiment. The experiment result shows that DEE can improve the overall performance by up to 98.1% compared to the best benchmark scheme.

Recent advances in deep neural networks (DNNs) have substantially improved the accuracy of intelligent applications. One effective scheme known as DNN partition further improves the speed of the inference by partitioning the DNN to a mobile device and its connected edge server to jointly process the inference. However, one of the challenges is how to maintain the service during handovers to avoid interruptions. Inspired by the recently developed early exit technique, where the DNN inference can be accelerated by leaving at an earlier exit point, we propose eDeepSave, a promising solution to save a large portion of video frames that cannot be handled during handovers. eDeepSave comprises three subschemes: (1) save the partially completed frames that are affected when the handover begins. (2) determine which frames we should save during a handover to maximize the number of saved frames. (3) repartition the last arriving frame before the end of the handover with a provable performance bound so that the frames after the handover can be processed without experiencing congestion. We build up a real-world prototype for the field experiments and extensive simulations, showing that eDeepSave can save up to 100% of the affected frames during handover.

In recent years, the rapid development of edge computing enables us to process a wide variety of intelligent applications at the edge, such as real-time video analytics. However, edge computing could suffer from service outage caused by the fluctuated wireless connection or congested computing resource. During the service outage, the only choice is to process the deep neural network (DNN) inference at the local mobile devices. The obstacle is that due to the limited resource, it may not be possible to complete inference tasks on time. Inspired by the recently developedearly exit of DNNs, where we can exit DNN at earlier layers to shorten the inference delay by sacrificing an acceptable level of accuracy, we propose to adopt such mechanism to process inference tasks during the service outage. The challenge is how to obtain the optimal schedule with diverse early exit choices. To this end, we formulate an optimal scheduling problem with the objective to maximize a general overall utility. However, the problem is in the form of integer programming, which cannot be solved by a standard approach. We therefore prove the Ordered Scheduling structure, indicating that a frame arrived earlier must be scheduled earlier. Such structure greatly decreases the searching space for an optimal solution. Then, we propose the Scheduling Early Exit (SEE) algorithm based on dynamic programming, to solve the problem optimally with polynomial computational complexity. Finally, we conduct trace-driven simulations and compare SEE with two benchmarks. The result shows that SEE can outperform the benchmarks by 50.9%.