OpenRaiser/Intern-Atlas huggingface dataset:
GPEX, A Framework For Interpreting Artificial Neural Networks
Venue: arXiv cs.LG 2024
Year: 2024

The analogy between Gaussian processes (GPs) and deep artificial neural networks (ANNs) has received a lot of interest, and has shown promise to unbox the blackbox of deep ANNs. Existing theoretical works put strict assumptions on the ANN (e.g. requiring all intermediate layers to be wide, or using specific activation functions). Accommodating those theoretical assumptions is hard in recent deep architectures, and those theoretical conditions need refinement as new deep architectures emerge. In this paper we derive an evidence lower-bound that encourages the GP's posterior to match the ANN's output without any requirement on the ANN. Using our method we find out that on 5 datasets, only a subset of those theoretical assumptions are sufficient. Indeed, in our experiments we used a normal ResNet-18 or feed-forward backbone with a single wide layer in the end. One limitation of training GPs is the lack of scalability with respect to the number of inducing points. We use novel computational techniques that allow us to train GPs with hundreds of thousands of inducing points and with GPU acceleration. As shown in our experiments, doing so has been essential to get a close match between the GPs and the ANNs on 5 datasets. We implement our method as a publicly available tool called GPEX: https://github.com/amirakbarnejad/gpex. On 5 datasets (4 image datasets, and 1 biological dataset) and ANNs with 2 types of functionality (classifier or attention-mechanism) we were able to find GPs whose outputs closely match those of the corresponding ANNs. After matching the GPs to the ANNs, we used the GPs' kernel functions to explain the ANNs' decisions. We provide more than 200 explanations (around 30 explanations in the paper and the rest in the supplementary) which are highly interpretable by humans and show the ability of the obtained GPs to unbox the ANNs' decisions.
Duck swarm algorithm: theory, numerical optimization, and applications
Venue: arXiv cs.NE 2024
Year: 2024

A swarm intelligence-based optimization algorithm, named Duck Swarm Algorithm (DSA), is proposed in this study, which is inspired by the searching for food sources and foraging behaviors of the duck swarm. Two rules are modeled from the finding food and foraging of the duck, which corresponds to the exploration and exploitation phases of the proposed DSA, respectively. The performance of the DSA is verified by using multiple CEC benchmark functions, where its statistical (best, mean, standard deviation, and average running-time) results are compared with seven well-known algorithms like Particle swarm optimization (PSO), Firefly algorithm (FA), Chicken swarm optimization (CSO), Grey wolf optimizer (GWO), Sine cosine algorithm (SCA), and Marine-predators algorithm (MPA), and Archimedes optimization algorithm (AOA). Moreover, the Wilcoxon rank-sum test, Friedman test, and convergence curves of the comparison results are utilized to prove the superiority of the DSA against other algorithms. The results demonstrate that DSA is a high-performance optimization method in terms of convergence speed and exploration-exploitation balance for solving the numerical optimization problems. Also, DSA is applied for the optimal design of six engineering constrained optimization problems and the node optimization deployment task of the Wireless Sensor Network (WSN). Overall, the comparison results revealed that the DSA is a promising and very competitive algorithm for solving different optimization problems.
Fairness in Repetitive Scheduling
Venue: arXiv cs.DS 2024
Year: 2024

Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customers fairly. Still, there is a huge lack of models that enable industries to make operational decisions fairly, such as a fair scheduling of the customers' jobs. Our main aim in this research is to provide a unified framework to enable schedulers making fair decisions in repetitive scheduling environments. For doing so, we consider a set of repetitive scheduling problems involving a set of $n$ clients. In each out of $q$ consecutive operational periods (e.g. days), each one of the customers submits a job for processing by an operational system. The scheduler's aim is to provide a schedule for each of the $q$ periods such that the quality of service (QoS) received by each of the clients will meet a certain predefined threshold. The QoS of a client may take several different forms, e.g., the number of days that the customer receives its job later than a given due-date, the number of times the customer receive his preferred time slot for service, or the sum of waiting times for service. We analyze the single machine variant of the problem for several different definitions of QoS, and classify the complexity of the corresponding problems using the theories of classical and parameterized complexity. We also study the price of fairness, i.e., the loss in the system's efficiency that results from the need to provide fair solutions.
Environmental migration? An overview of the literature
Venue: arXiv cs.DL 2024
Year: 2024

The literature on the relationship between environmental factors such as climatic changes and natural hazards and human mobility (both internal and international) is characterized by heterogeneous results: some contributions highlight the role of climate changes as a driver of migratory flows, while others underline how this impact is mediated by geographical, economic and the features of the environmental shock. This paper attempts to map this literature, focusing on economics and empirical essays. The paper improves on the existing literature: (a) providing systematic research of the literature through main bibliographic databases, followed by a review and bibliometric analysis of all resulting papers; (b) building a citation-based network of contributions, that hollows to identify four separate clusters of paper; (c) applying meta-analysis methods on the sample of 96 papers released between 2003 and 2020, published in an academic journal, working papers series or unpublished studies, providing 3,904 point estimates of the effect of slow-onset events and 2,065 point estimates of the effect of fast-onset events. Overall, the meta-analytic average effect estimates a small impact of slow- and rapid-onset variables on migration, however positive and significant. When the clustering of the literature is accounted for, however, a significant heterogeneity emerges among the four clusters of papers, giving rise to new evidence on the formation of club-like convergence of literature outcomes.
Broadcasting on Adversarial Multiple Access Channels
Venue: arXiv cs.DC 2024
Year: 2024

We study deterministic distributed algorithms for broadcasting on multiple-access channels. Packet injection is modeled by leaky-bucket adversaries. There is a fixed set of stations attached to a channel. Additional features of the model of communication include an upper bound on the number of stations activated in a round, an individual injection rate, and randomness in generating and injecting packets. We demonstrate that some broadcast algorithms designed for ad-hoc channels have bounded latency for increased ranges of injection rates than in ad-hoc channels when executed on channels with a fixed number of stations against adversaries that can activate at most one station per round. Individual injection rates are shown to impact latency, as compared to the model of general leaky bucket adversaries. Outcomes of experiments are given that compare the performance of broadcast algorithms against randomized adversaries. The experiments include deterministic algorithms and randomized backoff algorithms.
Sequential memory improves sample and memory efficiency in Episodic Control
Venue: arXiv cs.LG 2024
Year: 2024

State of the art deep reinforcement learning algorithms are sample inefficient due to the large number of episodes they require to achieve asymptotic performance. Episodic Reinforcement Learning (ERL) algorithms, inspired by the mammalian hippocampus, typically use extended memory systems to bootstrap learning from past events to overcome this sample-inefficiency problem. However, such memory augmentations are often used as mere buffers, from which isolated past experiences are drawn to learn from in an offline fashion (e.g., replay). Here, we demonstrate that including a bias in the acquired memory content derived from the order of episodic sampling improves both the sample and memory efficiency of an episodic control algorithm. We test our Sequential Episodic Control (SEC) model in a foraging task to show that storing and using integrated episodes as event sequences leads to faster learning with fewer memory requirements as opposed to a standard ERL benchmark, Model-Free Episodic Control, that buffers isolated events only. We also study the effect of memory constraints and forgetting on the sequential and non-sequential version of the SEC algorithm. Furthermore, we discuss how a hippocampal-like fast memory system could bootstrap slow cortical and subcortical learning subserving habit formation in the mammalian brain.
Efficiently Disentangle Causal Representations
Venue: arXiv cs.LG 2024
Year: 2024

This paper proposes an efficient approach to learning disentangled representations with causal mechanisms based on the difference of conditional probabilities in original and new distributions. We approximate the difference with models' generalization abilities so that it fits in the standard machine learning framework and can be efficiently computed. In contrast to the state-of-the-art approach, which relies on the learner's adaptation speed to new distribution, the proposed approach only requires evaluating the model's generalization ability. We provide a theoretical explanation for the advantage of the proposed method, and our experiments show that the proposed technique is 1.9--11.0$\times$ more sample efficient and 9.4--32.4 times quicker than the previous method on various tasks. The source code is available at \url{https://github.com/yuanpeng16/EDCR}.
Degrees of Freedom Analysis of Mechanisms using the New Zebra Crossing Method
Venue: arXiv cs.RO 2024
Year: 2024

Mobility, which is a basic property for a mechanism has to be analyzed to find the degrees of freedom. A quick method for calculation of degrees of freedom in a mechanism is proposed in this work. The mechanism is represented in a way that resembles a zebra crossing. An algorithm is proposed which is used to determine the mobility from the zebra crossing diagram. This algorithm takes into account the number of patches between the black patches, the number of joints attached to the fixed link and the number of loops in the mechanism. A number of cases have been discussed which fail to give the desired results using the widely used classical Kutzbach-Grubler formula.
SoK: Rowhammer on Commodity Operating Systems
Venue: arXiv cs.CR 2024
Year: 2024

Rowhammer has drawn much attention from both academia and industry in the past years as rowhammer exploitation poses severe consequences to system security. Since the first comprehensive study of rowhammer in 2014, a number of rowhammer attacks have been demonstrated against dynamic random access memory (DRAM)-based commodity systems to break software confidentiality, integrity and availability. Accordingly, numerous software defenses have been proposed to mitigate rowhammer attacks on commodity systems of either legacy (e.g., DDR3) or recent DRAM (e.g., DDR4). Besides, multiple hardware defenses (e.g., Target Row Refresh) from the industry have been deployed into recent DRAM to eliminate rowhammer, which we categorize as production defenses. In this paper, we systematize rowhammer attacks and defenses with a focus on DRAM-based commodity systems. Particularly, we have established a unified framework demonstrating how a rowhammer attack affects a commodity system. With the framework, we characterize existing attacks, shedding light on new attack vectors that have not yet been explored. We further leverage the framework to categorize software and production defenses, generalize their key defense strategies and summarize their key limitations, from which potential defense strategies are identified.
Robust and Resource-Efficient Data-Free Knowledge Distillation by Generative Pseudo Replay
Venue: arXiv cs.LG 2024
Year: 2024

Data-Free Knowledge Distillation (KD) allows knowledge transfer from a trained neural network (teacher) to a more compact one (student) in the absence of original training data. Existing works use a validation set to monitor the accuracy of the student over real data and report the highest performance throughout the entire process. However, validation data may not be available at distillation time either, making it infeasible to record the student snapshot that achieved the peak accuracy. Therefore, a practical data-free KD method should be robust and ideally provide monotonically increasing student accuracy during distillation. This is challenging because the student experiences knowledge degradation due to the distribution shift of the synthetic data. A straightforward approach to overcome this issue is to store and rehearse the generated samples periodically, which increases the memory footprint and creates privacy concerns. We propose to model the distribution of the previously observed synthetic samples with a generative network. In particular, we design a Variational Autoencoder (VAE) with a training objective that is customized to learn the synthetic data representations optimally. The student is rehearsed by the generative pseudo replay technique, with samples produced by the VAE. Hence knowledge degradation can be prevented without storing any samples. Experiments on image classification benchmarks show that our method optimizes the expected value of the distilled model accuracy while eliminating the large memory overhead incurred by the sample-storing methods.
A Taxonomy of Testable HTML5 Canvas Issues
Venue: arXiv cs.SE 2024
Year: 2024

The HTML5 <canvas> is widely used to display high quality graphics in web applications. However, the combination of web, GUI, and visual techniques that are required to build <canvas> applications, together with the lack of testing and debugging tools, makes developing such applications very challenging. To help direct future research on testing <canvas> applications, in this paper we present a taxonomy of testable <canvas> issues. First, we extracted 2,403 <canvas>-related issue reports from 123 open-source GitHub projects that use the HTML5 <canvas>. Second, we constructed our taxonomy by manually classifying a random sample of 332 issue reports. Our manual classification identified five broad categories of testable <canvas> issues, such as Visual and Performance issues. We found that Visual issues are the most frequent (35%), while Performance issues are relatively infrequent (5%). We also found that many testable <canvas> issues that present themselves visually on the <canvas> are actually caused by other components of the web application. Our taxonomy of testable <canvas> issues can be used to steer future research into <canvas> issues and testing.
Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees
Venue: arXiv cs.LG 2024
Year: 2024

We study sparse linear regression over a network of agents, modeled as an undirected graph and no server node. The estimation of the $s$-sparse parameter is formulated as a constrained LASSO problem wherein each agent owns a subset of the $N$ total observations. We analyze the convergence rate and statistical guarantees of a distributed projected gradient tracking-based algorithm under high-dimensional scaling, allowing the ambient dimension $d$ to grow with (and possibly exceed) the sample size $N$. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the loss functions, suitable conditions on the network connectivity and algorithm tuning, the distributed algorithm converges globally at a {\it linear} rate to an estimate that is within the centralized {\it statistical precision} of the model, $O(s\log d/N)$. When $s\log d/N=o(1)$, a condition necessary for statistical consistency, an $\varepsilon$-optimal solution is attained after $\mathcal{O}(κ\log (1/\varepsilon))$ gradient computations and $O (κ/(1-ρ) \log (1/\varepsilon))$ communication rounds, where $κ$ is the restricted condition number of the loss function and $ρ$ measures the network connectivity. The computation cost matches that of the centralized projected gradient algorithm despite having data distributed; whereas the communication rounds reduce as the network connectivity improves. Overall, our study reveals interesting connections between statistical efficiency, network connectivity \& topology, and convergence rate in high dimensions.
Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
Venue: arXiv cs.CC 2024
Year: 2024

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in $P \cap Z^n$, assuming that $P$ is a polyhedron, defined by systems $A x \leq b$ or $Ax = b,\, x \geq 0$ with a sparse matrix $A$. We develop algorithms for these problems that outperform state of the art ILP and counting algorithms on sparse instances with bounded elements. We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximal Matching problems.
Constant Inapproximability for PPA
Venue: arXiv cs.CC 2024
Year: 2024

In the $\varepsilon$-Consensus-Halving problem, we are given $n$ probability measures $v_1, \dots, v_n$ on the interval $R = [0,1]$, and the goal is to partition $R$ into two parts $R^+$ and $R^-$ using at most $n$ cuts, so that $|v_i(R^+) - v_i(R^-)| \leq \varepsilon$ for all $i$. This fundamental fair division problem was the first natural problem shown to be complete for the class PPA, and all subsequent PPA-completeness results for other natural problems have been obtained by reducing from it. We show that $\varepsilon$-Consensus-Halving is PPA-complete even when the parameter $\varepsilon$ is a constant. In fact, we prove that this holds for any constant $\varepsilon < 1/5$. As a result, we obtain constant inapproximability results for all known natural PPA-complete problems, including Necklace-Splitting, the Discrete-Ham-Sandwich problem, two variants of the pizza sharing problem, and for finding fair independent sets in cycles and paths.
On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
Venue: arXiv cs.DS 2024
Year: 2024

Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős--Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms.
Building time-surfaces by exploiting the complex volatility of an ECRAM memristor
Venue: arXiv cs.ET 2024
Year: 2024

Memristors have emerged as a promising technology for efficient neuromorphic architectures owing to their ability to act as programmable synapses, combining processing and memory into a single device. Although they are most commonly used for static encoding of synaptic weights, recent work has begun to investigate the use of their dynamical properties, such as Short Term Plasticity (STP), to integrate events over time in event-based architectures. However, we are still far from completely understanding the range of possible behaviors and how they might be exploited in neuromorphic computation. This work focuses on a newly developed Li$_\textbf{x}$WO$_\textbf{3}$-based three-terminal memristor that exhibits tunable STP and a conductance response modeled by a double exponential decay. We derive a stochastic model of the device from experimental data and investigate how device stochasticity, STP, and the double exponential decay affect accuracy in a hierarchy of time-surfaces (HOTS) architecture. We found that the device's stochasticity does not affect accuracy, that STP can reduce the effect of salt and pepper noise in signals from event-based sensors, and that the double exponential decay improves accuracy by integrating temporal information over multiple time scales. Our approach can be generalized to study other memristive devices to build a better understanding of how control over temporal dynamics can enable neuromorphic engineers to fine-tune devices and architectures to fit their problems at hand.
Faster Convergence of Local SGD for Over-Parameterized Models
Venue: arXiv cs.LG 2024
Year: 2024

Modern machine learning architectures are often highly expressive. They are usually over-parameterized and can interpolate the data by driving the empirical loss close to zero. We analyze the convergence of Local SGD (or FedAvg) for such over-parameterized models in the heterogeneous data setting and improve upon the existing literature by establishing the following convergence rates. For general convex loss functions, we establish an error bound of $Ø(1/T)$ under a mild data similarity assumption and an error bound of $Ø(K/T)$ otherwise, where $K$ is the number of local steps and $T$ is the total number of iterations. For non-convex loss functions we prove an error bound of $Ø(K/T)$. These bounds improve upon the best previous bound of $Ø(1/\sqrt{nT})$ in both cases, where $n$ is the number of nodes, when no assumption on the model being over-parameterized is made. We complete our results by providing problem instances in which our established convergence rates are tight to a constant factor with a reasonably small stepsize. Finally, we validate our theoretical results by performing large-scale numerical experiments that reveal the convergence behavior of Local SGD for practical over-parameterized deep learning models, in which the $Ø(1/T)$ convergence rate of Local SGD is clearly shown.