Browsing by Author "Ji, Bo"

Now showing 1 - 20 of 34
  • Thumbnail Image
    Advancing the Development and Utilization of Data Infrastructure for Smart Homes
    Anik, Sheik Murad Hassan (Virginia Tech, 2024-09-12)
    The smart home era is inevitably arising towards our everyday life. However, the scarcity of publicly available data remains a major hurdle in the domain, limiting people's capability of performing data analysis and their effectiveness in creating smart home automations. To mitigate this hurdle and its influence, our research explored three research directions to (1) create a better infrastructure that effectively collects and visualizes indoor-environment sensing data, (2) create a machine learning-based approach to demonstrate a novel way of analyzing indoor-environment data to facilitate human-centered building design, and (3) conduct an empirical study to explore the challenges and opportunities in existing smart home development. Specifically, we conducted three research projects. First, we created an open-source IoT-based cost-effective, distributed, scalable, and portable indoor environmental data collection system, Building Data Lite (BDL). We deployed this research prototype in 12 households, which deployment so far has collected more than 2 million records that are available to public in general. Second, building occupant persona is a very important component in human-centered smart home design, so we investigated an approach of applying state-of-the-art machine-learning models to data collected by an existing infrastructure, to enable the automatic creation of building occupant persona while minimizing human effort. Third, Home Assistant (HA) is an open-source off-the-shelf smart home platform that users frequently use to transform their residences into smart homes. However, many users seem to be stuck with the configuration scripts of home automations. We conducted an empirical study by (1) crawling posts on HA forum, (2) manually analyzing those posts to understand users' common technical concerns as well as frequently recommended resolutions, and (3) applying existing tools to assess the tool usefulness in alleviating users' pain. All our research projects will shed light on future directions in smart home design and development.
  • Thumbnail Image
    Building the Foundations and Experiences of 6G and Beyond Networks: A Confluence of THz Systems, Extended Reality (XR), and AI-Native Semantic Communications
    Chaccour, Christina (Virginia Tech, 2023-05-02)
    The emergence of 6G and beyond networks is set to enable a range of novel services such as personalized highly immersive experiences, holographic teleportation, and human-like intelligent robotic applications. Such applications require a set of stringent sensing, communication, control, and intelligence requirements that mandate a leap in the design, analysis, and optimization of today's wireless networks. First, from a wireless communication standpoint, future 6G applications necessitate extreme requirements in terms of bidirectional data rates, near-zero latency, synchronization, and jitter. Concurrently, such services also need a sensing functionality to track, localize, and sense their environment. Owing to its abundant bandwidth, one may naturally resort to terahertz (THz) frequency bands (0.1 − 10 THz) so as to provide significant wireless capacity gains and enable high-resolution environment sensing. Nonetheless, operating a wireless system at the THz band is constrained by a very uncertain channel which brings forth novel challenges. In essence, these channel limitations lead to unreliable intermittent links ergo the short communication range and the high susceptibility to blockage and molecular absorption. Second, given that emerging wireless services are "intelligence-centric", today's communication links must be transformed from a mere bit-pipe into a brain-like reasoning system. Towards this end, one can exploit the concept of semantic communications, a revolutionary paradigm that promises to transform radio nodes into intelligent agents that can extract the underlying meaning (semantics) or significance in a data stream. However, to date, there has been a lack in holistic, fundamental, and scalable frameworks for building next-generation semantic communication networks based on rigorous and well-defined technical foundations. Henceforth, to panoramically develop the fully-fledged theoretical foundations of future 6G applications and guarantee affluent corresponding experiences, this dissertation thoroughly investigates two thrusts. The first thrust focuses on developing the analytical foundations of THz systems with a focus on network design, performance analysis, and system optimization. First, a novel and holistic vision that articulates the unique role of THz in 6G systems is proposed. This vision exposes the solutions and milestones necessary to unleash THz's true potential in next-generation wireless systems. Then, given that extended reality (XR) will be a staple application of 6G systems, a novel risk and tail-based performance analysis is proposed to evaluate the instantaneous performance of THz bands for specific ultimate virtual reality (VR) services. Here, the results showcase that abundant bandwidth and the molecular absorption effect have only a secondary effect on the reliability compared to the availability of line-of-sight. More importantly, the results highlight that average metrics overlook extreme events and tend to provide false positive performance guarantees. To address the identified challenges of THz systems, a risk-oriented learning-based design that exploits reconfigurable intelligent surfaces (RISs) is proposed so as to optimize the instantaneous reliability. Furthermore, the analytical results are extended to investigate the uplink freshness of augmented reality (AR) services. Here, a novel ruin-based performance is conducted that scrutinizes the peak age of information (PAoI) during extreme events. Next, a novel joint sensing, communication, and artificial intelligence (AI) framework is developed to turn every THz communication link failure into a sensing opportunity, with application to digital world experiences with XR. This framework enables the use of the same waveform, spectrum, and hardware for both sensing and communication functionalities. Furthermore, this sensing input is intelligently processed via a novel joint imputation and forecasting system that is designed via non-autoregressive and transformed-based generative AI tools. This joint system enables fine-graining the sensing input to smaller time slots, predicting missing values, and fore- casting sensing and environmental information about future XR user behavior. Then, a novel joint quality of personal experience (QoPE)-centric and sensing-driven optimization is formulated and solved via deep hysteretic multi-agent reinforcement learning tools. Essentially, this dissertation establishes a solid foundation for the future deployment of THz frequencies in next-generation wireless networks through the proposal of a comprehensive set of principles that draw on the theories of tail and risk, joint sensing and communication designs, and novel AI frameworks. By adopting a multi-faceted approach, this work contributes significantly to the understanding and practical implementation of THz technology, paving the way for its integration into a wide range of applications that demand high reliability, resilience, and an immersive user experience. In the second thrust of this dissertation, the very first theoretical foundations of semantic communication and AI-native wireless networks are developed. In particular, a rigorous and holistic vision of an end-to-end semantic communication network that is founded on novel concepts from AI, causal reasoning, transfer learning, and minimum description length theory is proposed. Within this framework, the dissertation demonstrates that moving from data-driven intelligence towards reasoning-driven intelligence requires identifying association (statistical) and causal logic. Additionally, to evaluate the performance of semantic communication networks, novel key performance indicators metrics that include new "reasoning capacity" measures that could go beyond Shannon's bound to capture the imminent convergence of computing and communication resources. Then, a novel contrastive learning framework is proposed so as to disentangle learnable and memoizable patterns in source data and make the data "semantic-ready". Through the development of a rigorous end-to-end semantic communication network founded on novel concepts from communication theory and AI, along with the proposal of novel performance metrics, this dissertation lays a solid foundation for the advancement of reasoning-driven intelligence in the field of wireless communication and paves the way for a wide range of future applications. Ultimately, the various analytical foundations presented in this dissertation will provide key guidelines that guarantee seamless experiences in future 6G applications, enable a successful deployment of THz wireless systems as a versatile band for integrated communication and sensing, and build future AI-native semantic communication networks.
  • Thumbnail Image
    BystandAR: Protecting Bystander Visual Data in Augmented Reality Systems
    Corbett, Matthew; David-John, Brendan; Shang, Jiacheng; Hu, Y. Charlie; Ji, Bo (ACM, 2023-06-18)
    Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this paper, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user’s eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study,we showthat BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.
  • Thumbnail Image
    Computational Offloading for Real-Time Computer Vision in Unreliable Multi-Tenant Edge Systems
    Jackson, Matthew Norman (Virginia Tech, 2023-06-26)
    The demand and interest in serving Computer Vision applications at the Edge, where Edge Devices generate vast quantities of data, clashes with the reality that many Devices are largely unable to process their data in real time. While computational offloading, not to the Cloud but to nearby Edge Nodes, offers convenient acceleration for these applications, such systems are not without their constraints. As Edge networks may be unreliable or wireless, offloading quality is sensitive to communication bottlenecks. Unlike seemingly unlimited Cloud resources, an Edge Node, serving multiple clients, may incur delays due to resource contention. This project describes relevant Computer Vision workloads and how an effective offloading framework must adapt to the constraints that impact the Quality of Service yet have not been effectively nor properly addressed by previous literature. We design an offloading controller, based on closed-loop control theory, that enables Devices to maximize their throughput by appropriately offloading under variable conditions. This approach ensures a Device can utilize the maximum available offloading bandwidth. Finally, we constructed a realistic testbed and conducted measurements to demonstrate the superiority of our offloading controller over previous techniques.
  • Thumbnail Image
    Distributed Linear Bandits with Differential Privacy
    Li, Fengjiao; Zhou, Xingyu; Ji, Bo (IEEE, 2024-02-06)
    In this paper, we study the problem of global reward maximization with only partial distributed feedback. This problem is motivated by several real-world applications (e.g., cellular network configuration, dynamic pricing, and policy selection) where an action taken by a central entity influences a large population that contributes to the global reward. However, collecting such reward feedback from the entire population not only incurs a prohibitively high cost, but often leads to privacy concerns. To tackle this problem, we consider distributed linear bandits with differential privacy, where a subset of users from the population are selected (called clients) to participate in the learning process and the central server learns the global model from such partial feedback by iteratively aggregating these clients’ local feedback in a differentially private fashion. We then propose a unified algorithmic learning framework, called differentially private distributed phased elimination (DP-DPE), which can be naturally integrated with popular differential privacy (DP) models (including central DP, local DP, and shuffle DP). Furthermore, we show that DP-DPE achieves both sublinear regret and sublinear communication cost. Interestingly, DP-DPE also achieves privacy protection “for free” in the sense that the additional cost due to privacy guarantees is a lower-order additive term. In addition, as a by-product of our techniques, the same results of “free” privacy can also be achieved for the standard differentially private linear bandits. Finally, we conduct simulations to corroborate our theoretical results and demonstrate the effectiveness of DP-DPE.
  • Thumbnail Image
    EdgeFn: A Lightweight Customizable Data Store for Serverless Edge Computing
    Paidiparthy, Manoj Prabhakar (Virginia Tech, 2023-06-01)
    Serverless Edge Computing is an extension of the serverless computing paradigm that enables the deployment and execution of modular software functions on resource-constrained edge devices. However, it poses several challenges due to the edge network's dynamic nature and serverless applications' latency constraints. In this work, we introduce EdgeFn, a lightweight distributed data store for the serverless edge computing system. While serverless comput- ing platforms simplify the development and automated management of software functions, running serverless applications reliably on resource-constrained edge devices poses multiple challenges. These challenges include a lack of flexibility, minimum control over management policies, high data shipping, and cold start latencies. EdgeFn addresses these challenges by providing distributed data storage for serverless applications and allows users to define custom policies that affect the life cycle of serverless functions and their objects. First, we study the challenges of existing serverless systems to adapt to the edge environment. Sec- ond, we propose a distributed data store on top of a Distributed Hash Table (DHT) based Peer-to-Peer (P2P) Overlay, which achieves data locality by co-locating the function and its data. Third, we implement programmable callbacks for storage operations which users can leverage to define custom policies for their applications. We also define some use cases that can be built using the callbacks. Finally, we evaluate EdgeFn scalability and performance using industry-generated trace workload and real-world edge applications.
  • Thumbnail Image
    Empirical Investigations of More Practical Fault Localization Approaches
    Dao, Tung Manh (Virginia Tech, 2023-10-18)
    Developers often spend much of their valuable development time on software debugging and bug finding. In addition, software defects cost software industry as a whole hundreds or even a trillion of US dollars. As a result, many fault localization (FL) techniques for localizing bugs automatically, have been proposed. Despite its popularity, adopting FL in industrial environments has been impractical due to its undesirable accuracy and high runtime overhead cost. Motivated by the real-world challenges of FL applicability, this dissertation addresses these issues by proposing two main enhancements to the existing FL. First, it explores different strategies to combine a variety of program execution information with Information Retrieval-based fault localization (IRFL) techniques to increase FL's accuracy. Second, this dissertation research invents and experiments with the unconventional techniques of Instant Fault Localization (IFL) using the innovative concept of triggering modes. Our empirical evaluations of the proposed approaches on various types of bugs in a real software development environment shows that both FL's accuracy is increased and runtime is reduced significantly. We find that execution information helps increase IRFL's Top-10 by 17–33% at the class level, and 62–100% at the method level. Another finding is that IFL achieves as much as 100% runtime cost reduction while gaining comparable or better accuracy. For example, on single-location bugs, IFL scores 73% MAP, compared with 56% of the conventional approach. For multi-location bugs, IFL's Top-1 performance on real bugs is 22%, just right below 24% that of the existing FL approaches. We hope the results and findings from this dissertation help make the adaptation of FL in the real-world industry more practical and prevalent.
  • Thumbnail Image
    Enhancing Security and Privacy in Head-Mounted Augmented Reality Systems Using Eye Gaze
    Corbett, Matthew (Virginia Tech, 2024-04-22)
    Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. Specifically, head-mounted AR devices can accurately sense and understand their environment through an increasingly powerful array of sensors such as cameras, depth sensors, eye gaze trackers, microphones, and inertial sensors. The ability of these devices to collect this information presents both challenges and opportunities to improve existing security and privacy techniques in this domain. Specifically, eye gaze tracking is a ready-made capability to analyze user intent, emotions, and vulnerability, and as an input mechanism. However, modern AR devices lack systems to address their unique security and privacy issues. Problems such as lacking local pairing mechanisms usable while immersed in AR environments, bystander privacy protections, and the increased vulnerability to shoulder surfing while wearing AR devices all lack viable solutions. In this dissertation, I explore how readily available eye gaze sensor data can be used to improve existing methods for assuring information security and protecting the privacy of those near the device. My research has presented three new systems, BystandAR, ShouldAR, and GazePair that each leverage user eye gaze to improve security and privacy expectations in or with Augmented Reality. As these devices grow in power and number, such solutions are necessary to prevent perception failures that hindered earlier devices. The work in this dissertation is presented in the hope that these solutions can improve and expedite the adoption of these powerful and useful devices.
  • Thumbnail Image
    GraphDHT: Scaling Graph Neural Networks' Distributed Training on Edge Devices on a Peer-to-Peer Distributed Hash Table Network
    Gupta, Chirag (Virginia Tech, 2024-01-03)
    This thesis presents an innovative strategy for distributed Graph Neural Network (GNN) training, leveraging a peer-to-peer network of heterogeneous edge devices interconnected through a Distributed Hash Table (DHT). As GNNs become increasingly vital in analyzing graph-structured data across various domains, they pose unique challenges in computational demands and privacy preservation, particularly when deployed for training on edge devices like smartphones. To address these challenges, our study introduces the Adaptive Load- Balanced Partitioning (ALBP) technique in the GraphDHT system. This approach optimizes the division of graph datasets among edge devices, tailoring partitions to the computational capabilities of each device. By doing so, ALBP ensures efficient resource utilization across the network, significantly improving upon traditional participant selection strategies that often overlook the potential of lower-performance devices. Our methodology's core is weighted graph partitioning and model aggregation in GNNs, based on partition ratios, improving training efficiency and resource use. ALBP promotes inclusive device participation in training, overcoming computational limits and privacy concerns in large-scale graph data processing. Utilizing a DHT-based system enhances privacy in the peer-to-peer setup. The GraphDHT system, tested across various datasets and GNN architectures, shows ALBP's effectiveness in distributed GNN training and its broad applicability in different domains and structures. This contributes to applied machine learning, especially in optimizing distributed learning on edge devices.
  • Thumbnail Image
    IEEE Access Special Section: Intelligent Data Sensing, Collection, and Dissemination in Mobile Computing
    Liu, Xuxun; Liu, Anfeng; Tadrous, John; He, Ligang; Ji, Bo; Zheng, Zhongming (IEEE, 2020)
  • Thumbnail Image
    Information Freshness Optimization in Real-time Network Applications
    Liu, Zhongdong (Virginia Tech, 2024-06-12)
    In recent years, the remarkable development in ubiquitous communication networks and smart portable devices spawned a wide variety of real-time applications that require timely information updates (e.g., autonomous vehicular systems, industrial automation systems, and live streaming services). These real-time applications all have one thing in common: they desire their knowledge of the information source to be as fresh as possible. In order to measure the freshness of information, a new metric, called the Age-of-Information (AoI) is proposed. AoI is defined as the time elapsed since the generation time of the freshest delivered update. This metric is influenced by both the inter-arrival time and the delay of the updates. As a result of these dependencies, the AoI metric exhibits distinct characteristics compared to traditional delay and throughput metrics. In this dissertation, our goal is to optimize AoI under various real-time network applications. Firstly, we investigate a fundamental problem of how exactly various scheduling policies impact AoI performance. Though there is a large body of work studying the AoI performance under different scheduling policies, the use of the update-size information and its combinations with other information (such as arrival-time information and service preemption) to reduce AoI has still not been explored yet. Secondly, as a recently introduced measure of freshness, the relationship between AoI and other performance metrics remains largely ambiguous. We analyze the tradeoffs between AoI and additional performance metrics, including service performance and update cost, within real-world applications. This dissertation is organized into three parts. In the first part, we realize that scheduling policies leveraging the update-size information can substantially reduce the delay, one of the key components of AoI. However, it remains largely unknown how exactly scheduling policies (especially those making use of update-size information) impact the AoI performance. To this end, we conduct a systematic and comparative study to investigate the impact of scheduling policies on the AoI performance in single-server queues and provide useful guidelines for the design of AoI-efficient scheduling policies. In the second part, we analyze the tradeoffs between AoI and other performance metrics in real-world systems. Specifically, we focus on the following two important tradeoffs. (i) The tradeoff between service performance and AoI that arises in the data-driven real-time applications (e.g., Google Maps and stock trading applications). In these applications, the computing resource is often shared for processing both updates from information sources and queries from end users. Hence there is a natural tradeoff between service performance (e.g., response time to queries) and AoI (i.e., the freshness of data in response to user queries). To address this tradeoff, we begin by introducing a simple single-server two-queue model that captures the coupled scheduling between updates and queries. Subsequently, we design threshold-based scheduling policies to prioritize either updates or queries. Finally, we conduct a rigorous analysis of the performance of these threshold-based scheduling policies. (ii) The tradeoff between update cost and AoI that appear in the crowdsensing-based applications (e.g., Google Waze and GasBuddy). On the one hand, users are not satisfied if the responses to their requests are stale; on the other side, there is a cost for the applications to update their information regarding certain points of interest since they typically need to make monetary payments to incentivize users. To capture this tradeoff, we first formulate an optimization problem with the objective of minimizing the sum of the staleness cost (which is a function of the AoI) and the update cost, then we obtain a closed-form optimal threshold-based policy by reformulating the problem as a Markov decision process (MDP). In the third part, we study the minimization of data freshness and transmission costs (e.g., energy cost) under an (arbitrary) time-varying wireless channel without and with machine learning (ML) advice. We consider a discrete-time system where a resource-constrained source transmits time-sensitive data to a destination over a time-varying wireless channel. Each transmission incurs a fixed cost, while not transmitting results in a staleness cost measured by the AoI. The source needs to balance the tradeoff between these transmission and staleness costs. To tackle this challenge, we develop a robust online algorithm aimed at minimizing the sum of transmission and staleness costs, ensuring a worst-case performance guarantee. While online algorithms are robust, they tend to be overly conservative and may perform poorly on average in typical scenarios. In contrast, ML algorithms, which leverage historical data and prediction models, generally perform well on average but lack worst-case performance guarantees. To harness the advantages of both approaches, we design a learning-augmented online algorithm that achieves two key properties: (i) consistency: closely approximating the optimal offline algorithm when the ML prediction is accurate and trusted; (ii) robustness: providing a worst-case performance guarantee even when ML predictions are inaccurate.
  • Thumbnail Image
    Interdependent Mission Impact Assessment of an IoT System with Hypergame-Theoretic Attack-Defense Behavior Modeling
    Thukkaraju, Ashrith Reddy (Virginia Tech, 2023-11-17)
    Mission impact assessment (MIA) research has been explored to evaluate the performance and effectiveness of a mission system, such as enterprise networks with organizational missions and military or tactical mission teams with assigned missions. The key components in such mission systems, including assets, services, tasks, vulnerability, attacks, and defenses, are interdependent, and their impacts are interwoven. However, the current state-of-the-art MIA approaches have less studied such interdependencies. In addition, they have not modeled strategic attack-defense interactions under partial observability. In this work, we propose a novel MIA framework that assesses measures of performance (MoP) or measures of effectiveness (MoE) based on the service requirements (e.g., correctness or timeliness) of a given mission system based on full and comprehensive modeling and simulation of the key system components and their interdependencies. Particularly, we model intelligent attack-defense strategy selections based on hypergame theory, which allows considering uncertainty in estimating each player's hypergame expected utility (HEU) for its best strategy selection. As the case study, we consider an Internet-of-Things (IoT)-based mission system aiming to accurately and timely detect an object, given stringent accuracy and time constraints for successful mission completion. Via extensive simulation experiments, we validate the quality of the proposed MIA tool in its inference accuracy of the mission performance under a wide range of different environmental settings hindering the mission performance assessment and attack-defense interactions. Our results prove that the developed MIA framework shows a sufficiently high inference accuracy (e.g., 80%) even with a small portion of the training dataset (e.g., 20-50%). We also found the MIA can better assess the system's mission performance when attackers exhibit clearer patterns to take more strategic actions using hypergame theory.
  • Thumbnail Image
    Learning-to-Learn to Guide Random Search: Derivative-Free Meta Blackbox Optimization on Manifold
    Sel, Bilgehan; Tawaha, Ahmad; Ding, Yuhao; Jia, Ruoxi; Ji, Bo; Lavaei, Javad; Jin, Ming (2023-01-01)
    Solving a sequence of high-dimensional, nonconvex, but potentially similar optimization problems poses a computational challenge in engineering applications. We propose the first meta-learning framework that leverages the shared structure among sequential tasks to improve the computational efficiency and sample complexity of derivative-free optimization. Based on the observation that most practical high-dimensional functions lie on a latent low-dimensional manifold, which can be further shared among instances, our method jointly learns the meta-initialization of a search point and a meta-manifold. Theoretically, we establish the benefit of meta-learning in this challenging setting. Empirically, we demonstrate the effectiveness of the proposed algorithm in two high-dimensional reinforcement learning tasks.
  • Thumbnail Image
    Motion-Prediction-based Wireless Scheduling for Interactive Panoramic Scene Delivery
    Chen, Jiangong; Qin, Xudong; Zhu, Guangyu; Ji, Bo; Li, Bin (IEEE, 2023-10-19)
    Mobile Virtual Reality (VR) and panoramic video streaming rely on interactive panoramic scene delivery to provide desirable user experiences. However, it is pretty challenging to support multiple users via the wireless network since a panoramic scene typically consumes $4\sim 6\times$ bandwidth compared with a regular video with the same resolution. Motivated by the fact that users only perceive the Field-of-View (FoV), we employ the autoregressive process to predict the user's motion and stream only part of the panoramic content. Notably, we analytically characterize the effect of the delivered portion on the user's successful viewing probability. Then, we formulate an optimization problem to maximize the application-level throughput (which measures the average rate for successful viewing the desired content instead of raw network throughput) while providing a regular service. In addition, we impose three main constraints to our problem: minimum required service rate, maximum allowable energy consumption, and wireless interference. We then propose a novel scheduling algorithm that incorporates users' successful viewing probabilities and asymptotically maximizes application-level throughput while providing service regularity guarantees. We conduct real-trace simulations to evaluate the efficiency of our algorithm.
  • Thumbnail Image
    On Kernelized Multi-Armed Bandits with Constraints
    Zhou, Xingyu; Ji, Bo (2022-11-30)
    We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations are small. Our ultimate goal is to study how to utilize the nature of soft constraints to attain a finer complexity-regret-constraint trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which not only is satisfied under general exploration strategies, including upper confidence bound (UCB), Thompson sampling (TS), and new ones based on random exploration, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance of our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties in the analysis, which could be of independent interest to the communities.
  • Thumbnail Image
    On Scheduling Ring-All-Reduce Learning Jobs in Multi-Tenant GPU Clusters with Communication Contention
    Yu, Menglu; Ji, Bo; Rajan, Hridesh; Liu, Jia (ACM, 2022-10-03)
    Powered by advances in deep learning (DL) techniques, machine learning and artificial intelligence have achieved astonishing successes. However, the rapidly growing needs for DL also led to communication- and resource-intensive distributed training jobs for large-scale DL training, which are typically deployed over GPU clusters. To sustain the ever-increasing demand for DL training, the so-called “ring-all-reduce” (RAR) technologies have recently emerged as a favorable computing architecture to efficiently process network communication and computation load in GPU clusters. The most salient feature of RAR is that it removes the need for dedicated parameter servers, thus alleviating the potential communication bottleneck. However, when multiple RAR-based DL training jobs are deployed over GPU clusters, communication bottlenecks could still occur due to contentions between DL training jobs. So far, there remains a lack of theoretical understanding on how to design contention-aware resource scheduling algorithms for RAR-based DL training jobs, which motivates us to fill this gap in this work. Our main contributions are three-fold: i) We develop a new analytical model that characterizes both communication overhead related to the worker distribution of the job and communication contention related to the co-location of different jobs; ii) Based on the proposed analytical model, we formulate the problem as a non-convex integer program to minimize the makespan of all RAR-based DL training jobs. To address the unique structure in this problem that is not amenable for optimization algorithm design, we reformulate the problem into an integer linear program that enables provable approximation algorithm design called SJF-BCO (Smallest Job First with Balanced Contention and Overhead); and iii) We conduct extensive experiments to show the superiority of SJFBCO over existing schedulers. Collectively, our results contribute to the state-of-the-art of distributed GPU system optimization and algorithm design.
  • Thumbnail Image
    Online Learning for Resource Allocation in Wireless Networks: Fairness, Communication Efficiency, and Data Privacy
    Li, Fengjiao (Virginia Tech, 2022-12-13)
    As the Next-Generation (NextG, 5G and beyond) wireless network supports a wider range of services, optimization of resource allocation plays a crucial role in ensuring efficient use of the (limited) available network resources. Note that resource allocation may require knowledge of network parameters (e.g., channel state information and available power level) for package schedule. However, wireless networks operate in an uncertain environment where, in many practical scenarios, these parameters are unknown before decisions are made. In the absence of network parameters, a network controller, who performs resource allocation, may have to make decisions (aimed at optimizing network performance and satisfying users' QoS requirements) while emph{learning}. To that end, this dissertation studies two novel online learning problems that are motivated by autonomous resource management in NextG. Key contributions of the dissertation are two-fold. First, we study reward maximization under uncertainty with fairness constraints, which is motivated by wireless scheduling with Quality of Service constraints (e.g., minimum delivery ratio requirement) under uncertainty. We formulate a framework of combinatorial bandits with fairness constraints and develop a fair learning algorithm that successfully addresses the tradeoff between reward maximization and fairness constraints. This framework can also be applied to several other real-world applications, such as online advertising and crowdsourcing. Second, we consider global reward maximization under uncertainty with distributed biased feedback, which is motivated by the problem of cellular network configuration for optimizing network-level performance (e.g., average user-perceived Quality of Experience). We study both the linear-parameterized and non-parametric global reward functions, which are modeled as distributed linear bandits and kernelized bandits, respectively. For each model, we propose a learning algorithmic framework that can be integrated with different differential privacy models. We show that the proposed algorithms can achieve a near-optimal regret in a communication-efficient manner while protecting users' data privacy ``for free''. Our findings reveal that our developed algorithms outperform the state-of-the-art solutions in terms of the tradeoff among the regret, communication efficiency, and computation complexity. In addition, our proposed models and online learning algorithms can also be applied to several other real-world applications, e.g., dynamic pricing and public policy making, which may be of independent interest to a broader research community.
  • Thumbnail Image
    Optimizing Information Freshness in Wireless Networks
    Li, Chengzhang (Virginia Tech, 2023-01-18)
    Age of Information (AoI) is a performance metric that can be used to measure the freshness of information. Since its inception, it has captured the attention of the research community and is now an area of active research. By its definition, AoI measures the elapsed time period between the present time and the generation time of the information. AoI is fundamentally different from traditional metrics such as delay or latency as the latter only considers the transit time for a packet to traverse the network. Among the state-of-the-art in the literature, we identify two limitations that deserve further investigation. First, many existing efforts on AoI have been limited to information-theoretic exploration by considering extremely simple models and unrealistic assumptions, which are far from real-world communication systems. Second, among most existing work on scheduling algorithms to optimize AoI, there is a lack of research on guaranteeing AoI deadlines. The goal of this dissertation is to address these two limitations in the state-of-the-art. First, we design schedulers to minimize AoI under more practical settings, including varying sampling periods, varying sample sizes, cellular transmission models, dynamic channel conditions, etc. Second, we design schedulers to guarantee hard or soft AoI deadlines for each information source. More important, inspired by our results from guaranteeing AoI deadlines, we develop a general design framework that can be applied to construct high-performance schedulers for AoI-related problems. This dissertation is organized into three parts. In the first part, we study two problems on AoI minimization under general settings. (i) We consider general and heterogeneous sampling behaviors among source nodes, varying sample size, and a cellular-based transmission model. We develop a near-optimal low-complexity scheduler---code-named Juventas---to minimize AoI. (ii) We study the AoI minimization problem under a 5G network with dynamic channels. To meet the stringent real-time requirement for 5G, we develop a GPU-based near-optimal algorithm---code-named Kronos---and implement it on commercial off-the-shelf (COTS) GPUs. In the second part, we investigate three problems on guaranteeing AoI deadlines. (i) We study the problem to guarantee a hard AoI deadline for information from each source. We present a novel low-complexity procedure, called Fictitious Polynomial Mapping (FPM), and prove that FPM can find a feasible scheduler for any hard deadline vector when the system load is under ln 2. (ii) For soft AoI deadlines, i.e., occasional violations can be tolerated, we present a novel procedure called Unstable Tolerant Scheduler (UTS). UTS hinges upon the notions of Almost Uniform Schedulers (AUSs) and step-down rate vectors. We show that UTS has strong performance guarantees under different settings. (iii) We investigate a 5G scheduling problem to minimize the proportion of time when the AoI exceeds a soft deadline. We derive a property called uniform fairness and use it as a guideline to develop a 5G scheduler---Aequitas. To meet the real-time requirement in 5G, we implement Aequitas on a COTS GPU. In the third part, we present Eywa---a general design framework that can be applied to construct high-performance schedulers for AoI-related optimization and decision problems. The design of Eywa is inspired by the notions of AUS schedulers and step-down rate vectors when we develop UTS in the second part. To validate the efficacy of the proposed Eywa framework, we apply it to solve a number of problems, such as minimizing the sum of AoIs, minimizing bandwidth requirement under AoI constraints, and determining the existence of feasible schedulers to satisfy AoI constraints. We find that for each problem, Eywa can either offer a stronger performance guarantee than the state-of-the-art algorithms, or provide new/general results that are not available in the literature.
  • Thumbnail Image
    Poster: BystandAR: Protecting Bystander Visual Data in Augmented Reality Systems
    Corbett, Matthew; David-John, Brendan; Shang, Jiacheng; Hu, Y. Charlie; Ji, Bo (ACM, 2023-06-18)
    Augmented Reality (AR) devices are set apart from other mobile devices by the immersive experience they offer. While the powerful suite of sensors on modern AR devices is necessary for enabling such an immersive experience, they can create unease in bystanders (i.e., those surrounding the device during its use) due to potential bystander data leaks, which is called the bystander privacy problem. In this poster, we propose BystandAR, the first practical system that can effectively protect bystander visual (camera and depth) data in real-time with only on-device processing. BystandAR builds on a key insight that the device user’s eye gaze and voice are highly effective indicators for subject/bystander detection in interpersonal interaction, and leverages novel AR capabilities such as eye gaze tracking, wearer-focused microphone, and spatial awareness to achieve a usable frame rate without offloading sensitive information. Through a 16-participant user study,we showthat BystandAR correctly identifies and protects 98.14% of bystanders while allowing access to 96.27% of subjects. We accomplish this with average frame rates of 52.6 frames per second without the need to offload unprotected bystander data to another device.
  • Thumbnail Image
    Poster: Radar-CA: Radar-Sensing Multiple Access with Collision Avoidance
    Qiu, Yanlong; Zhang, Jiaxi; Huang, Kaiyi; Zhang, Jin; Ji, Bo (ACM, 2023-06-18)
    We propose a practical and efficient radar interference mitigation system, Radar-CA. Radar-CA overcomes the limitations of requiring any additional equipment or resources. Radar-CA transfers the access time estimation problem to a frequency estimation problem, enabling interference mitigation through a central controller, and our preliminary result shows that Radar-CA is capable of mitigating interference efficiently in a dense radar network.