Yin Sun

Baran Tan Bacinoglu, Yin Sun, Elif Uysal et al.

We consider an energy harvesting source equipped with a finite battery, which needs to send timely status updates to a remote destination. The timeliness of status updates is measured by a non-decreasing penalty function of the Age of Information (AoI). The problem is to find a policy for generating updates that achieves the lowest possible time-average expected age penalty among all online policies. We prove that one optimal solution of this problem is a monotone threshold policy, which satisfies (i) each new update is sent out only when the age is higher than a threshold and (ii) the threshold is a non-increasing function of the instantaneous battery level. Let $τ_B$ denote the optimal threshold corresponding to the full battery level $B$, and $p(\cdot)$ denote the age-penalty function, then we can show that $p(τ_B)$ is equal to the optimum objective value, i.e., the minimum achievable time-average expected age penalty. These structural properties are used to develop an algorithm to compute the optimal thresholds. Our numerical analysis indicates that the improvement in average age with added battery capacity is largest at small battery sizes; specifically, more than half the total possible reduction in age is attained when battery storage increases from one transmission's worth of energy to two. This encourages further study of status update policies for sensors with small battery storage.

Hao Chen, Abhishek Gupta, Yin Sun et al.

This paper studies Hoeffding's inequality for Markov chains under the generalized concentrability condition defined via integral probability metric (IPM). The generalized concentrability condition establishes a framework that interpolates and extends the existing hypotheses of Markov chain Hoeffding-type inequalities. The flexibility of our framework allows Hoeffding's inequality to be applied beyond the ergodic Markov chains in the traditional sense. We demonstrate the utility by applying our framework to several non-asymptotic analyses arising from the field of machine learning, including (i) a generalization bound for empirical risk minimization with Markovian samples, (ii) a finite sample guarantee for Ployak-Ruppert averaging of SGD, and (iii) a new regret bound for rested Markovian bandits with general state space.

Fangzhou Chen, Yin Sun, Yiping Qin et al.

Coordinated Multipoint (CoMP) promised substantial throughput gain for next-generation cellular systems. However, realizing this gain is costly in terms of pilots and backhaul bandwidth, and may require substantial modifications in physicallayer hardware. Targeting efficient throughput gain, we develop a novel coordinated power control scheme for uplink cellular networks called Checks and Balances (C&B), which checks the received signal strength of one user and its generated interference to neighboring base stations, and balances the two. C&B has some highly attractive advantages: C&B (i) can be implemented easily in software, (ii) does not require to upgrade non-CoMP physicallayer hardware, (iii) allows for fully distributed implementation for each user equipment (UE), and (iv) does not need extra pilots or backhaul communications. We evaluate the throughput performance of C&B on an uplink LTE system-level simulation platform, which is carefully calibrated with Huawei. Our simulation results show that C&B achieves much better throughput performance, compared to several widely-used power control schemes.

Cagri Ari, Md Kamran Chowdhury Shisher, Yin Sun et al.

We study a setting where an intelligent model (e.g., a pre-trained neural network) infers the real-time value of a target signal using data samples transmitted from a remote source. The transmission scheduler decides (i) the freshness of packets, (ii) their length (i.e., the number of samples they contain), and (iii) when they should be transmitted. The freshness is quantified using the Age of Information (AoI), and the inference quality for a given packet length is a general function of AoI. Previous works assumed i.i.d. transmission delays with immediate feedback or were restricted to the case where inference performance degrades as the input data ages. Our formulation, in addition to capturing non-monotone age dependence, also covers Markovian delay on both forward and feedback links. We model this as an infinite-horizon average-cost Semi-Markov Decision Process. We obtain a closed-form solution that decides on (i) and (iii) for any constant packet length. The solution for when to transmit is an index-based threshold policy, where the index function is expressed in terms of the delay state and AoI at the receiver. In contrast, the freshness of the selected packet is a function of only the delay state. We then separately optimize the value of the constant packet length. Moreover, we also develop an index-based threshold policy for the time-variable packet length case, which allows a complexity reduction. In simulation results, we observe that our goal-oriented scheduler drops inference error down to one-sixth with respect to the age-based scheduling of unit-length packets.

Md Kamran Chowdhury Shisher, Yin Sun, I-Hong Hou

In this paper, we analyze the impact of data freshness on remote inference systems, where a pre-trained neural network blue infers a time-varying target (e.g., the locations of vehicles and pedestrians) based on features (e.g., video frames) observed at a sensing node (e.g., a camera). One might expect that the performance of a remote inference system degrades monotonically as the feature becomes stale. Using an information-theoretic analysis, we show that this is true if the feature and target data sequence can be closely approximated as a Markov chain, whereas it is not true if the data sequence is far from being Markovian. Hence, the inference error is a function of Age of Information (AoI), where the function could be non-monotonic. To minimize the inference error in real-time, we propose a new "selection-from-buffer" model for sending the features, which is more general than the "generate-at-will" model used in earlier studies. In addition, we design low-complexity scheduling policies to improve inference performance. For single-source, single-channel systems, we provide an optimal scheduling policy. In multi-source, multi-channel systems, the scheduling problem becomes a multi-action restless multi-armed bandit problem. For this setting, we design a new scheduling policy by integrating Whittle index-based source selection and duality-based feature selection-from-buffer algorithms. This new scheduling policy is proven to be asymptotically optimal. These scheduling results hold for minimizing general AoI functions (monotonic or non-monotonic). Data-driven evaluations demonstrate the significant advantages of our proposed scheduling policies.

Md Kamran Chowdhury Shisher, Heyang Qin, Lei Yang et al.

In this paper, we analyze the impact of information freshness on supervised learning based forecasting. In these applications, a neural network is trained to predict a time-varying target (e.g., solar power), based on multiple correlated features (e.g., temperature, humidity, and cloud coverage). The features are collected from different data sources and are subject to heterogeneous and time-varying ages. By using an information-theoretic approach, we prove that the minimum training loss is a function of the ages of the features, where the function is not always monotonic. However, if the empirical distribution of the training data is close to the distribution of a Markov chain, then the training loss is approximately a non-decreasing age function. Both the training loss and testing loss depict similar growth patterns as the age increases. An experiment on solar power prediction is conducted to validate our theory. Our theoretical and experimental results suggest that it is beneficial to (i) combine the training data with different age values into a large training dataset and jointly train the forecasting decisions for these age values, and (ii) feed the age value as a part of the input feature to the neural network.

Rahul Singh, Fang Liu, Yin Sun et al.

We study a variant of the classical multi-armed bandit problem (MABP) which we call as Multi-Armed Bandits with dependent arms. More specifically, multiple arms are grouped together to form a cluster, and the reward distributions of arms belonging to the same cluster are known functions of an unknown parameter that is a characteristic of the cluster. Thus, pulling an arm $i$ not only reveals information about its own reward distribution, but also about all those arms that share the same cluster with arm $i$. This "correlation" amongst the arms complicates the exploration-exploitation trade-off that is encountered in the MABP because the observation dependencies allow us to test simultaneously multiple hypotheses regarding the optimality of an arm. We develop learning algorithms based on the UCB principle which utilize these additional side observations appropriately while performing exploration-exploitation trade-off. We show that the regret of our algorithms grows as $O(K\log T)$, where $K$ is the number of clusters. In contrast, for an algorithm such as the vanilla UCB that is optimal for the classical MABP and does not utilize these dependencies, the regret scales as $O(M\log T)$ where $M$ is the number of arms.

Yin Sun, Benjamin Cyr

In this paper, we study how to take samples at a data source for improving the freshness of received data samples at a remote receiver. We use non-linear functions of the age of information to measure data freshness, and provide a survey of non-linear age functions and their applications. The sampler design problem is studied to optimize these data freshness metrics, even when there is a sampling rate constraint. This sampling problem is formulated as a constrained Markov decision process (MDP) with a possibly uncountable state space. We present a complete characterization of the optimal solution to this MDP: The optimal sampling policy is a deterministic or randomized threshold policy, where the threshold and the randomization probabilities are characterized based on the optimal objective value of the MDP and the sampling rate constraint. The optimal sampling policy can be computed by bisection search, and the curse of dimensionality is circumvented. These age optimality results hold for (i) general data freshness metrics represented by monotonic functions of the age of information, (ii) general service time distributions of the queueing server, (iii) both continuoustime and discrete-time sampling problems, and (iv) sampling problems both with and without the sampling rate constraint. Numerical results suggest that the optimal sampling policies can be much better than zero-wait sampling and the classic uniform sampling.