OpenRaiser/Intern-Atlas huggingface dataset:
Ruin Theory for User Association and Energy Optimization in Multi-access Edge Computing
Venue: arXiv cs.IT 2023
Year: 2023

In this correspondence, a novel framework is proposed for analyzing data offloading in a multi-access edge computing system. Specifically, a two-phase algorithm, is proposed, including two key phases: 1) user association phase and 2) task offloading phase. In the first phase, a ruin theory-based approach is developed to obtain the users association considering the users' transmission reliability and resource utilization efficiency. Meanwhile, in the second phase, an optimization-based algorithm is used to optimize the data offloading process. In particular, ruin theory is used to manage the user association phase, and a ruin probability-based preference profile is considered to control the priority of proposing users. Here, ruin probability is derived by the surplus buffer space of each edge node at each time slot. Giving the association results, an optimization problem is formulated to optimize the amount of offloaded data aiming at minimizing the energy consumption of users. Simulation results show that the developed solutions guarantee system reliability, association efficiency under a tolerable value of surplus buffer size, and minimize the total energy consumption of all users.
Physics-Guided Deep Learning for Dynamical Systems: A Survey
Venue: arXiv cs.LG 2023
Year: 2023

Modeling complex physical dynamics is a fundamental task in science and engineering. Traditional physics-based models are sample efficient, and interpretable but often rely on rigid assumptions. Furthermore, direct numerical approximation is usually computationally intensive, requiring significant computational resources and expertise, and many real-world systems do not have fully-known governing laws. While deep learning (DL) provides novel alternatives for efficiently recognizing complex patterns and emulating nonlinear dynamics, its predictions do not necessarily obey the governing laws of physical systems, nor do they generalize well across different systems. Thus, the study of physics-guided DL emerged and has gained great progress. Physics-guided DL aims to take the best from both physics-based modeling and state-of-the-art DL models to better solve scientific problems. In this paper, we provide a structured overview of existing methodologies of integrating prior physical knowledge or physics-based modeling into DL, with a special emphasis on learning dynamical systems. We also discuss the fundamental challenges and emerging opportunities in the area.
On Tightness of Tsaknakis-Spirakis Descent Methods for Approximate Nash Equilibria
Venue: arXiv cs.GT 2023
Year: 2023

This article explores the minimum approximation ratio for Nash equilibrium in bi-matrix games, focusing on the Tsaknakis and Spirakis (TS) methods. The previous SOTA, TS algorithm, achieved an approximation ratio of 0.3393, but efforts to improve the analysis of the TS algorithm have been unsuccessful. This work demonstrates that the bound of 0.3393 is tight for the TS algorithm and presents a theoretical worst-case analysis. A condition for identifying tight instances is provided, along with a generator. While most generated instances are unstable, indicating potential improvements, stable instances exist where perturbations cannot enhance the 0.3393 bound. Other approximate algorithms, such as regret-matching and fictitious play, achieve better ratios on these instances. The generated instances can serve as benchmarks for approximate Nash equilibrium algorithms. The article also mentions progress in the TS algorithm, achieving an approximation ratio of 1/3, which can be further studied using the presented techniques.
Smoothed Differential Privacy
Venue: arXiv cs.CR 2023
Year: 2023

Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. Often, DP classifies most mechanisms without additive noise as non-private (Dwork et al., 2014). Thus, additive noises are added to improve privacy (to achieve DP). However, in many real-world applications, adding additive noise is undesirable (Bagdasaryan et al., 2019) and sometimes prohibited (Liu et al., 2020). In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis (Spielman & Teng, May 2004). Our notion, smoothed DP, can effectively measure the privacy leakage of mechanisms without additive noises under realistic settings. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP. In addition, we prove several desirable properties of smoothed DP, including composition, robustness to post-processing, and distribution reduction. Based on those properties, we propose an efficient algorithm to calculate the privacy parameters for smoothed DP. Experimentally, we verify that, according to smoothed DP, the discrete sampling mechanisms are private in real-world elections, and some discrete neural networks can be private without adding any additive noise. We believe that these results contribute to the theoretical foundation of realistic privacy measures beyond worst-case analysis.
Memory-aware curriculum federated learning for breast cancer classification
Venue: arXiv cs.CV 2023
Year: 2023

For early breast cancer detection, regular screening with mammography imaging is recommended. Routinary examinations result in datasets with a predominant amount of negative samples. A potential solution to such class-imbalance is joining forces across multiple institutions. Developing a collaborative computer-aided diagnosis system is challenging in different ways. Patient privacy and regulations need to be carefully respected. Data across institutions may be acquired from different devices or imaging protocols, leading to heterogeneous non-IID data. Also, for learning-based methods, new optimization strategies working on distributed data are required. Recently, federated learning has emerged as an effective tool for collaborative learning. In this setting, local models perform computation on their private data to update the global model. The order and the frequency of local updates influence the final global model. Hence, the order in which samples are locally presented to the optimizers plays an important role. In this work, we define a memory-aware curriculum learning method for the federated setting. Our curriculum controls the order of the training samples paying special attention to those that are forgotten after the deployment of the global model. Our approach is combined with unsupervised domain adaptation to deal with domain shift while preserving data privacy. We evaluate our method with three clinical datasets from different vendors. Our results verify the effectiveness of federated adversarial learning for the multi-site breast cancer classification. Moreover, we show that our proposed memory-aware curriculum method is beneficial to further improve classification performance. Our code is publicly available at: https://github.com/ameliajimenez/curriculum-federated-learning.
MPLP: Massively Parallelized Lazy Planning
Venue: arXiv cs.RO 2023
Year: 2023

Lazy search algorithms have been developed to efficiently solve planning problems in domains where the computational effort is dominated by the cost of edge evaluation. The existing algorithms operate by intelligently balancing computational effort between searching the graph and evaluating edges. However, they are designed to run as a single process and do not leverage the multithreading capability of modern processors. In this work, we propose a massively parallelized, bounded suboptimal, lazy search algorithm (MPLP) that harnesses modern multi-core processors. In MPLP, searching of the graph and edge evaluations are performed completely asynchronously in parallel, leading to a drastic improvement in planning time. We validate the proposed algorithm in two different planning domains: 1) motion planning for 3D humanoid navigation and 2) task and motion planning for a robotic assembly task. We show that MPLP outperforms the state-of-the-art lazy search as well as parallel search algorithms. The open-source code for MPLP is available here: https://github.com/shohinm/parallel_search
Strategyproof Mechanisms For Group-Fair Facility Location Problems
Venue: arXiv cs.GT 2023
Year: 2023

We study the facility location problems where agents are located on a real line and divided into groups based on criteria such as ethnicity or age. Our aim is to design mechanisms to locate a facility to approximately minimize the costs of groups of agents to the facility fairly while eliciting the agents' locations truthfully. We first explore various well-motivated group fairness cost objectives for the problems and show that many natural objectives have an unbounded approximation ratio. We then consider minimizing the maximum total group cost and minimizing the average group cost objectives. For these objectives, we show that existing classical mechanisms (e.g., median) and new group-based mechanisms provide bounded approximation ratios, where the group-based mechanisms can achieve better ratios. We also provide lower bounds for both objectives. To measure fairness between groups and within each group, we study a new notion of intergroup and intragroup fairness (IIF) . We consider two IIF objectives and provide mechanisms with tight approximation ratios.
Human Attention during Goal-directed Reading Comprehension Relies on Task Optimization
Venue: arXiv cs.CL 2023
Year: 2023

The computational principles underlying attention allocation in complex goal-directed tasks remain elusive. Goal-directed reading, i.e., reading a passage to answer a question in mind, is a common real-world task that strongly engages attention. Here, we investigate what computational models can explain attention distribution in this complex task. We show that the reading time on each word is predicted by the attention weights in transformer-based deep neural networks (DNNs) optimized to perform the same reading task. Eye-tracking further reveals that readers separately attend to basic text features and question-relevant information during first-pass reading and rereading, respectively. Similarly, text features and question relevance separately modulate attention weights in shallow and deep DNN layers. Furthermore, when readers scan a passage without a question in mind, their reading time is predicted by DNNs optimized for a word prediction task. Therefore, attention during real-world reading can be interpreted as the consequence of task optimization.
Implementation and Experimental Evaluation of Reed-Solomon Identification
Venue: arXiv cs.IT 2023
Year: 2023

Identification is a communication paradigm that promises exponential advantages over transmission for applications that do not actually require all messages to be reliably transmitted. Notably, the identification capacity theorems prove exponentially larger rates compared to classical transmission. However, there exist additional trade-offs that are not captured by these theorems and which become relevant for the deployment of identification in practical communication settings. In particular, in this paper we evaluate the latency introduced by computations at the encoder and decoder when employing identification codes. For this, we implement them using an explicit code construction based on Reed-Solomon codes and integrate it into a single carrier transmission system using software-defined radios. Our evaluation of the practical aspects of identification codes show that unless care is taken, these trade-offs can compromise the theoretical advantage given by the exponentially large identification rates.
DxHash: A Scalable Consistent Hash Based on the Pseudo-Random Sequence
Venue: arXiv cs.DS 2023
Year: 2023

Consistent hashing (CH) has been pivotal as a data router and load balancer in diverse fields, including distributed databases, cloud infrastructure, and peer-to-peer networks. However, existing CH algorithms often fall short in simultaneously meeting various critical requirements, such as load balance, minimal disruption, statelessness, high lookup rate, small memory footprint, and low update overhead. To address these limitations, we introduce DxHash, a scalable consistent hashing algorithm based on pseudo-random sequences. To adjust workloads on heterogeneous nodes and enhance flexibility, we propose weighted DxHash. Through comprehensive evaluations, DxHash demonstrates substantial improvements across all six requirements compared to state-of-the-art alternatives. Notably, even when confronted with a 50% failure ratio in a cluster of one million nodes, DxHash maintains remarkable processing capabilities, handling up to 13.3 million queries per second.
Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability
Venue: arXiv cs.LG 2023
Year: 2023

Bayesian neural network (BNN) allows for uncertainty quantification in prediction, offering an advantage over regular neural networks that has not been explored in the differential privacy (DP) framework. We fill this important gap by leveraging recent development in Bayesian deep learning and privacy accounting to offer a more precise analysis of the trade-off between privacy and accuracy in BNN. We propose three DP-BNNs that characterize the weight uncertainty for the same network architecture in distinct ways, namely DP-SGLD (via the noisy gradient method), DP-BBP (via changing the parameters of interest) and DP-MC Dropout (via the model architecture). Interestingly, we show a new equivalence between DP-SGD and DP-SGLD, implying that some non-Bayesian DP training naturally allows for uncertainty quantification. However, the hyperparameters such as learning rate and batch size, can have different or even opposite effects in DP-SGD and DP-SGLD. Extensive experiments are conducted to compare DP-BNNs, in terms of privacy guarantee, prediction accuracy, uncertainty quantification, calibration, computation speed, and generalizability to network architecture. As a result, we observe a new tradeoff between the privacy and the reliability. When compared to non-DP and non-Bayesian approaches, DP-SGLD is remarkably accurate under strong privacy guarantee, demonstrating the great potential of DP-BNN in real-world tasks.
A Novel Evolutionary Algorithm for Hierarchical Neural Architecture Search
Venue: arXiv cs.NE 2023
Year: 2023

In this work, we propose a novel evolutionary algorithm for neural architecture search, applicable to global search spaces. The algorithm's architectural representation organizes the topology in multiple hierarchical modules, while the design process exploits this representation, in order to explore the search space. We also employ a curation system, which promotes the utilization of well performing sub-structures to subsequent generations. We apply our method to Fashion-MNIST and NAS-Bench101, achieving accuracies of $93.2\%$ and $94.8\%$ respectively in a relatively small number of generations.
Influence of a Set of Variables on a Boolean Function
Venue: arXiv cs.IT 2023
Year: 2023

The influence of a variable is an important concept in the analysis of Boolean functions. The more general notion of influence of a set of variables on a Boolean function has four separate definitions in the literature. In the present work, we introduce a new definition of influence of a set of variables which is based on the auto-correlation function and develop its basic theory. Among the new results that we obtain are generalisations of the Poincaré inequality and the edge expansion property of the influence of a single variable. Further, we obtain new characterisations of resilient and bent functions using the notion of influence. We show that the previous definition of influence due to Fischer et. al. (2002) and Blais (2009) is half the value of the auto-correlation based influence that we introduce. Regarding the other prior notions of influence, we make a detailed study of these and show that each of these definitions do not satisfy one or more desirable properties that a notion of influence may be expected to satisfy.
Epistemic Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

Intelligence relies on an agent's knowledge of what it does not know. This capability can be assessed based on the quality of joint predictions of labels across multiple inputs. In principle, ensemble-based approaches produce effective joint predictions, but the computational costs of training large ensembles can become prohibitive. We introduce the epinet: an architecture that can supplement any conventional neural network, including large pretrained models, and can be trained with modest incremental computation to estimate uncertainty. With an epinet, conventional neural networks outperform very large ensembles, consisting of hundreds or more particles, with orders of magnitude less computation. The epinet does not fit the traditional framework of Bayesian neural networks. To accommodate development of approaches beyond BNNs, such as the epinet, we introduce the epistemic neural network (ENN) as an interface for models that produce joint predictions.
Data Hiding with Deep Learning: A Survey Unifying Digital Watermarking and Steganography
Venue: arXiv cs.CV 2023
Year: 2023

The advancement of secure communication and identity verification fields has significantly increased through the use of deep learning techniques for data hiding. By embedding information into a noise-tolerant signal such as audio, video, or images, digital watermarking and steganography techniques can be used to protect sensitive intellectual property and enable confidential communication, ensuring that the information embedded is only accessible to authorized parties. This survey provides an overview of recent developments in deep learning techniques deployed for data hiding, categorized systematically according to model architectures and noise injection methods. The objective functions, evaluation metrics, and datasets used for training these data hiding models are comprehensively summarised. Additionally, potential future research directions that unite digital watermarking and steganography on software engineering to enhance security and mitigate risks are suggested and deliberated. This contribution furthers the creation of a more trustworthy digital world and advances Responsible AI.
PoF: Proof-of-Following for Vehicle Platoons
Venue: arXiv cs.CR 2023
Year: 2023

Cooperative vehicle platooning significantly improves highway safety, fuel efficiency, and traffic flow. In this model, a set of vehicles move in line formation and coordinate acceleration, braking, and steering using a combination of physical sensing and vehicle-to-vehicle (V2V) messaging. The authenticity and integrity of the V2V messages are paramount to safety. For this reason, recent V2V and V2X standards support the integration of a PKI. However, a PKI cannot bind a vehicle's digital identity to the vehicle's physical state (location, velocity, etc.). As a result, a vehicle with valid cryptographic credentials can impact platoons from a remote location. In this paper, we seek to provide the missing link between the physical and the digital world in the context of vehicle platooning. We propose a new access control protocol we call Proof-of-Following (PoF) that verifies the following distance between a candidate and a verifier. The main idea is to draw security from the common, but constantly changing environment experienced by the closely traveling vehicles. We use the large-scale fading effect of ambient RF signals as a common source of randomness to construct a {\em PoF} primitive. The correlation of large-scale fading is an ideal candidate for the mobile outdoor environment because it exponentially decays with distance and time. We evaluate our PoF protocol on an experimental platoon of two vehicles in freeway, highway, and urban driving conditions. We demonstrate that the PoF withstands both the pre-recording and following attacks with overwhelming probability.
Federated Causal Inference in Heterogeneous Observational Data
Venue: arXiv cs.LG 2023
Year: 2023

We are interested in estimating the effect of a treatment applied to individuals at multiple sites, where data is stored locally for each site. Due to privacy constraints, individual-level data cannot be shared across sites; the sites may also have heterogeneous populations and treatment assignment mechanisms. Motivated by these considerations, we develop federated methods to draw inference on the average treatment effects of combined data across sites. Our methods first compute summary statistics locally using propensity scores and then aggregate these statistics across sites to obtain point and variance estimators of average treatment effects. We show that these estimators are consistent and asymptotically normal. To achieve these asymptotic properties, we find that the aggregation schemes need to account for the heterogeneity in treatment assignments and in outcomes across sites. We demonstrate the validity of our federated methods through a comparative study of two large medical claims databases.
Power Allocation for Uplink Communications of Massive Cellular-Connected UAVs
Venue: arXiv cs.IT 2023
Year: 2023

Cellular-connected unmanned aerial vehicle (UAV) has attracted a surge of research interest in both academia and industry. To support aerial user equipment (UEs) in the existing cellular networks, one promising approach is to assign a portion of the system bandwidth exclusively to the UAV-UEs. This is especially favorable for use cases where a large number of UAV-UEs are exploited, e.g., for package delivery close to a warehouse. Although the nearly line-of-sight (LoS) channels can result in higher powers received, UAVs can in turn cause severe interference to each other in the same frequency band. In this contribution, we focus on the uplink communications of massive cellular-connected UAVs. Different power allocation algorithms are proposed to either maximize the minimal spectrum efficiency (SE) or maximize the overall SE to cope with severe interference based on the successive convex approximation (SCA) principle. One of the challenges is that a UAV can affect a large area meaning that many more UAV-UEs must be considered in the optimization problem, which is essentially different from that for terrestrial UEs. The necessity of single-carrier uplink transmission further complicates the problem. Nevertheless, we find that the special property of large coherent bandwidths and coherent times of the propagation channels can be leveraged. The performances of the proposed algorithms are evaluated via extensive simulations in the full-buffer transmission mode and bursty-traffic mode. Results show that the proposed algorithms can effectively enhance the uplink SEs. This work can be considered the first attempt to deal with the interference among massive cellular-connected UAV-UEs with optimized power allocations.
Pixyz: a Python library for developing deep generative models
Venue: arXiv cs.LG 2023
Year: 2023

With the recent rapid progress in the study of deep generative models (DGMs), there is a need for a framework that can implement them in a simple and generic way. In this research, we focus on two features of DGMs: (1) deep neural networks are encapsulated by probability distributions, and (2) models are designed and learned based on an objective function. Taking these features into account, we propose a new Python library to implement DGMs called Pixyz. This library adopts a step-by-step implementation method with three APIs, which allows us to implement various DGMs more concisely and intuitively. In addition, the library introduces memoization to reduce the cost of duplicate computations in DGMs to speed up the computation. We demonstrate experimentally that this library is faster than existing probabilistic programming languages in training DGMs.