We consider a time-slotted job-assignment system with a central server, N users and a machine which changes its state according to a Markov chain (hence called a Markov machine). The users submit their jobs to the central server according to a stochastic job arrival process. For each user, the server has a dedicated job queue. Upon receiving a job from a user, the server stores that job in the corresponding queue. When the machine is not working on a job assigned by the server, the machine can be either in internally busy or in free state, and the dynamics of these states follow a binary symmetric Markov chain. Upon sampling the state information of the machine, if the server identifies that the machine is in the free state, it schedules a user and submits a job to the machine from the job queue of the scheduled user. To maximize the number of jobs completed per unit time, we introduce a new metric, referred to as the age of job completion. To minimize the age of job completion and the sampling cost, we propose two policies and numerically evaluate their performance. For both of these policies, we find sufficient conditions under which the job queues will remain stable.

We study a status update system with a source, a sampler, a transmitter, and a monitor. The source governs a stochastic process that the monitor wants to observe in a timely manner. To achieve this, the sampler samples fresh update packets which the transmitter transmits via an error prone communication channel to the monitor. The transmitter can transmit without any constraint, i.e., it can transmit whenever an update packet is available to the transmitter. However, the sampler is imposed with a sampling rate constraint. The goal of the sampler is to devise an optimal policy that satisfies the resource constraint while minimizing the age of the monitor. We formulate this problem as a constrained Markov decision process (CMDP). We find several structures of an optimal policy. We leverage the optimal structures to find a low complexity optimal policy in an explicit manner, without resorting to complex iterative schemes or techniques that require bounding the age.

We consider a time-slotted status update system with an error-free preemptive queue. The goal of the sampler-scheduler pair is to minimize the age of information at the monitor by sampling and transmitting the freshly sampled update packets to the monitor. The sampler-scheduler pair also has a choice to preempt an old update packet from the server and transmit a new update packet to the server. We formulate this problem as a Markov decision process (MDP) and find the optimal sampling policy. We find a sufficient, and also separately a necessary, condition for the always preemption policy to be an optimal policy. We show that it is optimal for the sampler-scheduler pair to sample a new packet immediately upon the reception of an update packet at the monitor. We propose a double-threshold sampling policy which we show to be an optimal policy under some assumptions on the queue statistic.

We consider a time slotted status update system with$(N+1)$sources,$N$users and one base station (BS). User$i$aims to receive fresh information from the stochastic processes at source$i$and source$(N+1)$. We measure the freshness of the system with the age of information metric. Thus, for user$i$, there are two notions of age of information, one corresponding to the age of source$i$, and another corresponding to the age of source$(N+1)$. The BS aims to employ an optimal scheduling policy to minimize the total average age of information. When the BS samples an update packet from the$i$th source,$1\leq i\leq N$, the BS transmits that sample only to the$i$th user. However, when the BS samples an update packet from the$(N+1)$th source, the BS transmits that sample to all the$N$users. Due to the energy constraint of the BS, we assume that when the BS transmits an update packet to a dedicated user, the probability of successful transmission is higher compared to the probability of successful transmission to the same user, when the BS transmits an update packet to all the$N$users. Due to this, there is a trade-off between the age of information and the probability of successful transmission. We find several structures for the optimal scheduling policy and exploit those properties to design a low-complexity relative value iteration-based scheduler. We propose a further lower complexity scheduling policy which is a mixture of the optimal scheduling policy and the max-weight policy.

We consider a communication system where a base station (BS) transmits update packets to N users, one user at a time, over a wireless channel. We investigate the age of this status updating system with an adversary that jams the update packets in the downlink. We consider two system models: with diversity and without diversity. In the model without diversity, in each time slot, the BS schedules a user from N users according to a user scheduling algorithm. The constrained adversary blocks at most a given fraction,$\alpha $, of the time slots over a horizon of T slots, i.e., it can block at most$\alpha T$slots of its choosing out of the total T time slots. We show that if the BS schedules the users with a stationary randomized policy, then the optimal choice for the adversary is to block the user which has the lowest probability of getting scheduled by the BS, at the middle of the time horizon, consecutively for$\alpha T$time slots. The interesting consecutive property of the blocked time slots is due to the cumulative nature of the age metric. In the model with diversity, in each time slot, the BS schedules a user from N users and chooses a sub-carrier from$N_{sub}$sub-carriers to transmit update packets to the scheduled user according to a user scheduling algorithm and a sub-carrier choosing algorithm, respectively. The adversary blocks$\alpha T$time slots of its choosing out of T time slots at the sub-carriers of its choosing. We show that for large T, the uniform user scheduling algorithm together with the uniform sub-carrier choosing algorithm is$\frac {2 N_{sub}}{N_{sub}-1}$optimal. Next, we investigate the game theoretic equilibrium points of this status updating system. For the model without diversity, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the BS acts as the leader and the adversary acts as the follower. For the model with diversity, we show that a Nash equilibrium exists and identify the Nash equilibrium. Finally, we extend the model without diversity to the case where the BS can serve multiple users and the adversary can jam multiple users, at a time.

We consider a slotted communication system consisting of a source, a cache, a user and a timestomping adversary. The time horizon consists of total$T$time slots, such that the source transmits update packets to the user directly over$T_1$time slots and to the cache over$T_{2}$time slots. We consider$T_{1}\ll T_{2}, T_{1}+T_{2} < T$, such that the source transmits to the user once between two consecutive cache updates. Update packets are marked with timestamps corresponding to their generation times at the source. All nodes have a buffer size of one and store the packet with the latest timestamp to minimize their age of information. In this setting, we consider the presence of an oblivious adversary that fully controls the communication link between the cache and the user. The adversary manipulates the timestamps of outgoing packets from the cache to the user, with the goal of bringing staleness at the user node. At each time slot, the adversary can choose to either forward the cached packet to the user, after changing its timestamp to current time$t$, thereby rebranding an old packet as a fresh packet and misleading the user into accepting it, or stay idle. The user compares the timestamps of every received packet with the latest packet in its possession to keep the fresher one and discard the staler packet. If the user receives update packets from both cache and source in a time slot, then the packet from source prevails. The goal of the source is to design an algorithm to minimize the average age at the user, and the goal of the adversary is to increase the average age at the user. We formulate this problem in an online learning setting and provide a fundamental lower bound on the competitive ratio for this problem. We further propose a deterministic algorithm with a provable guarantee on its competitive ratio.

We consider a time slotted communication network with a base station (BS) and a user. At each time slot a fresh update packet arrives at the BS with probability$p > 0$. When the BS transmits an update packet for the first time, it goes through with a success probability of$q_1$. In all subsequent re-transmissions, the packet goes through with a success probability of$q_{2}$where$q_{2} > q_1$, due to the accumulation of observations at the receiver used to decode the packet. When the packet goes through the first time, the age of the user drops to 1, while when the packet goes through in subsequent transmissions, the age of the user drops to the age of the packet since its generation. Thus, when the BS is in the process of re-transmitting an old packet, if it receives a new packet, it has to decide whether to re-transmit the old packet with higher probability of successful transmission but resulting in higher age, or to transmit the new packet which will result in a lower age upon successful reception but this will happen with lower probability. In this paper, we provide an optimal algorithm to solve this problem.

We investigate the game theoretic equilibrium points of a status updating system with an adversary that jams the updates in the downlink. We consider the system models with and without diversity. The adversary can jam up to α proportion of the entire communication window. In the model without diversity, in each time slot, the base station schedules a user from N users according to a stationary distribution. The adversary blocks (jams) αT time slots of its choosing out of the total T time slots. For this system, we show that a Nash equilibrium does not exist, however, a Stackelberg equilibrium exists when the scheduling algorithm of the base station acts as the leader and the adversary acts as the follower. In the model with diversity, in each time slot, the base station schedules a user from N users and chooses a sub-carrier from Nsubsub-carriers to transmit update packets to the scheduled user according to a stationary distribution. The adversary blocks αT time slots of its choosing out of T time slots at the sub-carriers of its choosing. For this system, we show that a Nash equilibrium exists and identify the Nash equilibrium.

Recent advancements in the field of deep learning have dramatically improved the performance of machine learning models in a variety of applications, including computer vision, text mining, speech processing and fraud detection among others. Mini-batch gradient descent is the standard algorithm to train deep models, where mini-batches of a fixed size are sampled randomly from the training data and passed through the network sequentially. In this paper, we present a novel algorithm to generate a deterministic sequence of mini-batches to train a deep neural network (rather than a random sequence). Our rationale is to select a mini-batch by minimizing the Maximum Mean Discrepancy (MMD) between the already selected mini-batches and the unselected training samples. We pose the mini-batch selection as a constrained optimization problem and derive a linear programming relaxation to determine the sequence of mini-batches. To the best of our knowledge, this is the first research effort that uses the MMD criterion to determine a sequence of mini-batches to train a deep neural network. The proposed mini-batch sequencing strategy is deterministic and independent of the underlying network architecture and prediction task. Our extensive empirical analyses on three challenging datasets corroborate the merit of our framework over competing baselines. We further study the performance of our framework on two other applications besides classification (regression and semantic segmentation) to validate its generalizability.

The growing success and popularity of deep learning in computer vision have resulted in the availability of several pretrained deep learning architectures (such as AlexNet, ResNet, VGGNet among others). A common practice in deep learning research is to use one of the pre-trained models and fine-tune it to a given target task, using training data from the target. However, training a deep learning model efficiently necessitates expensive, high-quality GPUs and distributed computing infrastructures. Some applications (such as those running on mobile platforms) are severely limited in terms of memory and computational resources; in these applications, it is a significant challenge to fine-tune a pre-trained deep learning model to a target task, using large amounts of target training data. Cloud services can be leveraged for training, but involve issues with data privacy and cost. In such applications, it is important to select an informative subset of the training data and fine-tune the deep model using only the selected subset. In this paper, we propose a novel framework to address this problem. We pose subset selection as a constrained NP-hard integer quadratic programming problem and derive an efficient linear relaxation to select a subset of exemplar instances. Our extensive empirical studies on three challenging vision datasets (from different application domains) using three commonly used pre-trained deep learning models corroborate the potential of our framework for real-world, resource-constrained applications.

We study the multi-user scheduling problem for minimizing the Age of Information (AoI) in cellular wireless networks under stationary and non-stationary regimes. We derive fundamental lower bounds for the scheduling problem and design efficient online policies with provable performance guarantees. In the stationary setting, we consider the AoI optimization problem for a set of mobile users travelling around multiple cells. In this setting, we propose a scheduling policy and show that it is 2-optimal. Next, we propose a new adversarial channel model for studying the scheduling problem in non-stationary environments. For N users, we show that the competitive ratio of any online scheduling policy in this setting is at least Ω(N). We then propose an online policy and show that it achieves a competitive ratio of O(N2). Finally, we introduce a relaxed adversarial model with channel state estimations for the immediate future. We propose a heuristic model predictive control policy that exploits this feature and compare its performance through numerical simulations.

Deep learning algorithms automatically learn a set of informative features from a given dataset and have depicted commendable performance on a variety of computer vision applications. However, efficient training of deep learning architectures with a large number of hidden layers is mostly dependent on high-end GPUs and distributed computing infrastructures. Some applications (such as applications running on mobile platforms), have limited access to computational resources and face a fundamental challenge in handling large scale training data. Cloud services can be leveraged for training, but involve challenges with data privacy and cost. In such applications, it is crucial to select a subset of informative training samples and use only the extracted subset to induce the deep model. In this paper, we propose a novel subset selection algorithm, DeepSub, to address this practical challenge. Our framework is computationally efficient, easy to implement and also enjoys nice theoretical properties. Our extensive empirical studies on three challenging computer vision applications (face, handwritten digits and object recognition), using three popular deep learning architectures (AlexNet, GoogleNet and ResNet) corroborate the potential of DeepSub over competing baselines.

Drones or UAVs are widely used today for commercial as well as strategic purposes. When a large numbers of drones fly and manueuver together, the OFDM based communication links between drones would see time-varying Doppler. In particular, we study a measurement model where the Doppler variation is significant even within one OFDM block (symbol) duration. We approximately model the time variation of Doppler within one OFDM symbol as well as one whole frame and propose a low complexity timing correlation based algorithm. This approach exploits the repetition of the preamble symbol as well as theself similarity of the Cyclic Prefix(CP) to estimate the Doppler frequency, track the same throughout the frame. The proposed approach provides a far superior bit error rate performance in this time-varying Doppler models when compared to conventional schemes.