OpenRaiser/Intern-Atlas huggingface dataset:
Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
Venue: arXiv cs.DS 2024
Year: 2024

We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these fundamental problems in both directed and undirected graphs, both weighted and unweighted. Many of our results are optimal to within a polylog factor: For an $n$-node graph $G$ we establish near linear lower and upper bounds for computing RPaths if $G$ is directed and weighted, and for computing MWC and ANSC if $G$ is weighted, directed or undirected; near $\sqrt{n}$ lower and upper bounds for undirected weighted RPaths; and $Θ(D)$ bound for undirected unweighted RPaths. We also present lower and upper bounds for approximation versions of these problems, notably a $(2-(1/g))$-approximation algorithm for undirected unweighted MWC that runs in $\tilde{O}(\sqrt{n}+D)$ rounds, improving on the previous best bound of $\tilde{O}(\sqrt{ng}+D)$ rounds, where $g$ is the MWC length. We present a $(1+ε)$-approximation algorithm for directed weighted RPaths, which beats the linear lower bound for exact RPaths.
Byzantine Fault-Tolerant Min-Max Optimization
Venue: arXiv cs.DC 2024
Year: 2024

In this paper, we consider a min-max optimization problem under adversarial manipulation, where there are $n$ cost functions, up to $f$ of which may be replaced by arbitrary faulty functions by an adversary. The goal is to minimize the maximum cost over $x$ among the $n$ functions despite the faulty functions. The problem formulation could naturally extend to Byzantine fault-tolerant distributed min-max optimization. We present a simple algorithm for Byzantine min-max optimization, and provide bounds on the output of the algorithm. We also present an approximate algorithm for this problem. We then extend the problem to a distributed setting and present a distributed algorithm. To the best of our knowledge, we are the first to consider this problem.
Controller design and experimental evaluation of a motorised assistance for a patient transfer floor lift
Venue: arXiv cs.RO 2024
Year: 2024

Patient transfer is a challenging, critical task because it exposes caregivers to injury risks. Available transfer devices, like floor lifts, lead to improvements but are far from perfect. They do not eliminate the caregivers risk of musculoskeletal disorders, and they can be burdensome to use due to their poor maneuverability. This paper presents a new motorized floor lift with a single central motorized wheel connected to an instrumented handle. Admittance controllers are designed to 1) improve the device maneuverability, 2) reduce the required caregiver effort, and 3) ensure the security and comfort of patients. Two controller designs, one with a linear admittance law and a non-linear admittance law with variable damping, were developed and implemented on a prototype. Tests were performed on seven participants to evaluate the performance of the assistance system and the controllers. The experimental results show that 1) the motorized assistance with the variable damping controller improves maneuverability by 28%, 2) reduces the amount of effort required to push the lift by 66% and 3) provides the same level of patient comfort compared to a standard unassisted floor lift.
The openESEA Modelling Language for Ethical, Social and Environmental Accounting: Technical Report
Venue: arXiv cs.OH 2024
Year: 2024

Over the years ethical, social and environmental accounting (ESEA) has become a common practice among responsible organisations. ESEA entails assessing and reporting organisations" performance on environmental, social and governance topics. In this report, we present a textual grammar for specifying ESEA methods. With the grammar ESEA models can be created. Such models can be interpreted by our open-source, model-driven tool, called openESEA. The report presents the metamodel of the grammar, the grammar itself, and explanations of each grammar primitive.
AMED: Automatic Mixed-Precision Quantization for Edge Devices
Venue: arXiv cs.LG 2024
Year: 2024

Quantized neural networks are well known for reducing the latency, power consumption, and model size without significant harm to the performance. This makes them highly appropriate for systems with limited resources and low power capacity. Mixed-precision quantization offers better utilization of customized hardware that supports arithmetic operations at different bitwidths. Quantization methods either aim to minimize the compression loss given a desired reduction or optimize a dependent variable for a specified property of the model (such as FLOPs or model size); both make the performance inefficient when deployed on specific hardware, but more importantly, quantization methods assume that the loss manifold holds a global minimum for a quantized model that copes with the global minimum of the full precision counterpart. Challenging this assumption, we argue that the optimal minimum changes as the precision changes, and thus, it is better to look at quantization as a random process, placing the foundation for a different approach to quantize neural networks, which, during the training procedure, quantizes the model to a different precision, looks at the bit allocation as a Markov Decision Process, and then, finds an optimal bitwidth allocation for measuring specified behaviors on a specific device via direct signals from the particular hardware architecture. By doing so, we avoid the basic assumption that the loss behaves the same way for a quantized model. Automatic Mixed-Precision Quantization for Edge Devices (dubbed AMED) demonstrates its superiority over current state-of-the-art schemes in terms of the trade-off between neural network accuracy and hardware efficiency, backed by a comprehensive evaluation.
HyperMAML: Few-Shot Adaptation of Deep Models with Hypernetworks
Venue: arXiv cs.LG 2024
Year: 2024

The aim of Few-Shot learning methods is to train models which can easily adapt to previously unseen tasks, based on small amounts of data. One of the most popular and elegant Few-Shot learning approaches is Model-Agnostic Meta-Learning (MAML). The main idea behind this method is to learn the general weights of the meta-model, which are further adapted to specific problems in a small number of gradient steps. However, the model's main limitation lies in the fact that the update procedure is realized by gradient-based optimisation. In consequence, MAML cannot always modify weights to the essential level in one or even a few gradient iterations. On the other hand, using many gradient steps results in a complex and time-consuming optimization procedure, which is hard to train in practice, and may lead to overfitting. In this paper, we propose HyperMAML, a novel generalization of MAML, where the training of the update procedure is also part of the model. Namely, in HyperMAML, instead of updating the weights with gradient descent, we use for this purpose a trainable Hypernetwork. Consequently, in this framework, the model can generate significant updates whose range is not limited to a fixed number of gradient steps. Experiments show that HyperMAML consistently outperforms MAML and performs comparably to other state-of-the-art techniques in a number of standard Few-Shot learning benchmarks.
6G Survey on Challenges, Requirements, Applications, Key Enabling Technologies, Use Cases, AI integration issues and Security aspects
Venue: arXiv cs.NI 2024
Year: 2024

Fifth-generation (5G) wireless networks will likely offer high data rates, increased reliability, and low delay for mobile, personal, and local area networks. Along with the rapid growth of smart wireless sensing and communication technologies, data traffic has increased significantly and existing 5G networks are not able to fully support future massive data traffic for services, storage, and processing. To meet the challenges ahead, research communities and industry are exploring the sixth generation (6G) Terahertz-based wireless network that is expected to be offered to industrial users in just ten years. Gaining knowledge and understanding of the different challenges and facets of 6G is crucial in meeting the requirements of future communication and addressing evolving quality of service (QoS) demands. This survey provides a comprehensive examination of specifications, requirements, applications, and enabling technologies related to 6G. It covers disruptive and innovative, integration of 6G with advanced architectures and networks such as software-defined networks (SDN), network functions virtualization (NFV), Cloud/Fog computing, and Artificial Intelligence (AI) oriented technologies. The survey also addresses privacy and security concerns and provides potential futuristic use cases such as virtual reality, smart healthcare, and Industry 5.0. Furthermore, it identifies the current challenges and outlines future research directions to facilitate the deployment of 6G networks.
Hybrid Parameter Search and Dynamic Model Selection for Mixed-Variable Bayesian Optimization
Venue: arXiv cs.LG 2024
Year: 2024

This paper presents a new type of hybrid model for Bayesian optimization (BO) adept at managing mixed variables, encompassing both quantitative (continuous and integer) and qualitative (categorical) types. Our proposed new hybrid models (named hybridM) merge the Monte Carlo Tree Search structure (MCTS) for categorical variables with Gaussian Processes (GP) for continuous ones. hybridM leverages the upper confidence bound tree search (UCTS) for MCTS strategy, showcasing the tree architecture's integration into Bayesian optimization. Our innovations, including dynamic online kernel selection in the surrogate modeling phase and a unique UCTS search strategy, position our hybrid models as an advancement in mixed-variable surrogate models. Numerical experiments underscore the superiority of hybrid models, highlighting their potential in Bayesian optimization.
QAGCN: Answering Multi-Relation Questions via Single-Step Implicit Reasoning over Knowledge Graphs
Venue: arXiv cs.AI 2024
Year: 2024

Multi-relation question answering (QA) is a challenging task, where given questions usually require long reasoning chains in KGs that consist of multiple relations. Recently, methods with explicit multi-step reasoning over KGs have been prominently used in this task and have demonstrated promising performance. Examples include methods that perform stepwise label propagation through KG triples and methods that navigate over KG triples based on reinforcement learning. A main weakness of these methods is that their reasoning mechanisms are usually complex and difficult to implement or train. In this paper, we argue that multi-relation QA can be achieved via end-to-end single-step implicit reasoning, which is simpler, more efficient, and easier to adopt. We propose QAGCN -- a Question-Aware Graph Convolutional Network (GCN)-based method that includes a novel GCN architecture with controlled question-dependent message propagation for the implicit reasoning. Extensive experiments have been conducted, where QAGCN achieved competitive and even superior performance compared to state-of-the-art explicit-reasoning methods. Our code and pre-trained models are available in the repository: https://github.com/ruijie-wang-uzh/QAGCN
Estimating and Mitigating the Congestion Effect of Curbside Pick-ups and Drop-offs: A Causal Inference Approach
Venue: arXiv cs.LG 2024
Year: 2024

Curb space is one of the busiest areas in urban road networks. Especially in recent years, the rapid increase of ride-hailing trips and commercial deliveries has induced massive pick-ups/drop-offs (PUDOs), which occupy the limited curb space that was designed and built decades ago. These PUDOs could jam curbside utilization and disturb the mainline traffic flow, evidently leading to significant negative societal externalities. However, there is a lack of an analytical framework that rigorously quantifies and mitigates the congestion effect of PUDOs in the system view, particularly with little data support and involvement of confounding effects. To bridge this research gap, this paper develops a rigorous causal inference approach to estimate the congestion effect of PUDOs on general regional networks. A causal graph is set to represent the spatio-temporal relationship between PUDOs and traffic speed, and a double and separated machine learning (DSML) method is proposed to quantify how PUDOs affect traffic congestion. Additionally, a re-routing formulation is developed and solved to encourage passenger walking and traffic flow re-routing to achieve system optimization. Numerical experiments are conducted using real-world data in the Manhattan area. On average, 100 additional units of PUDOs in a region could reduce the traffic speed by 3.70 and 4.54 mph on weekdays and weekends, respectively. Re-routing trips with PUDOs on curb space could respectively reduce the system-wide total travel time by 2.44% and 2.12% in Midtown and Central Park on weekdays. Sensitivity analysis is also conducted to demonstrate the effectiveness and robustness of the proposed framework.
Pessimistic Off-Policy Optimization for Learning to Rank
Venue: arXiv cs.LG 2024
Year: 2024

Off-policy learning is a framework for optimizing policies without deploying them, using data collected by another policy. In recommender systems, this is especially challenging due to the imbalance in logged data: some items are recommended and thus logged more frequently than others. This is further perpetuated when recommending a list of items, as the action space is combinatorial. To address this challenge, we study pessimistic off-policy optimization for learning to rank. The key idea is to compute lower confidence bounds on parameters of click models and then return the list with the highest pessimistic estimate of its value. This approach is computationally efficient, and we analyze it. We study its Bayesian and frequentist variants and overcome the limitation of unknown prior by incorporating empirical Bayes. To show the empirical effectiveness of our approach, we compare it to off-policy optimizers that use inverse propensity scores or neglect uncertainty. Our approach outperforms all baselines and is both robust and general.
Emergent specialization from participation dynamics and multi-learner retraining
Venue: arXiv cs.LG 2024
Year: 2024

Numerous online services are data-driven: the behavior of users affects the system's parameters, and the system's parameters affect the users' experience of the service, which in turn affects the way users may interact with the system. For example, people may choose to use a service only for tasks that already works well, or they may choose to switch to a different service. These adaptations influence the ability of a system to learn about a population of users and tasks in order to improve its performance broadly. In this work, we analyze a class of such dynamics -- where users allocate their participation amongst services to reduce the individual risk they experience, and services update their model parameters to reduce the service's risk on their current user population. We refer to these dynamics as \emph{risk-reducing}, which cover a broad class of common model updates including gradient descent and multiplicative weights. For this general class of dynamics, we show that asymptotically stable equilibria are always segmented, with sub-populations allocated to a single learner. Under mild assumptions, the utilitarian social optimum is a stable equilibrium. In contrast to previous work, which shows that repeated risk minimization can result in (Hashimoto et al., 2018; Miller et al., 2021), we find that repeated myopic updates with multiple learners lead to better outcomes. We illustrate the phenomena via a simulated example initialized from real data.
Inverse Boundary Value and Optimal Control Problems on Graphs: A Neural and Numerical Synthesis
Venue: arXiv cs.LG 2024
Year: 2024

A general setup for deterministic system identification problems on graphs with Dirichlet and Neumann boundary conditions is introduced. When control nodes are available along the boundary, we apply a discretize-then-optimize method to estimate an optimal control. A key piece in the present architecture is our boundary injected message passing neural network. This will produce more accurate predictions that are considerably more stable in proximity of the boundary. Also, a regularization technique based on graphical distance is introduced that helps with stabilizing the predictions at nodes far from the boundary.
Marked Neural Spatio-Temporal Point Process Involving a Dynamic Graph Neural Network
Venue: arXiv cs.LG 2024
Year: 2024

Temporal Point Processes (TPPs) have recently become increasingly interesting for learning dynamics in graph data. A reason for this is that learning on dynamic graph data is becoming more relevant, since data from many scientific fields, ranging from mathematics, biology, social sciences, and physics to computer science, is naturally related and inherently dynamic. In addition, TPPs provide a meaningful characterization of event streams and a prediction mechanism for future events. Therefore, (semi-)parameterized Neural TPPs have been introduced whose characterization can be (partially) learned and, thus, enable the representation of more complex phenomena. However, the research on modeling dynamic graphs with TPPs is relatively young, and only a few models for node attribute changes or evolving edges have been proposed yet. To allow for learning on fully dynamic graph streams, i.e., graphs that can change in their structure (addition/deletion of nodes/edge) and in their node/edge attributes, we propose a Marked Neural Spatio-Temporal Point Process (MNSTPP). It leverages a Dynamic Graph Neural Network to learn a Marked TPP that handles attributes and spatial data to model and predict any event in a graph stream.
Unsupervised Learning of the Total Variation Flow
Venue: arXiv cs.CV 2024
Year: 2024

The total variation (TV) flow generates a scale-space representation of an image based on the TV functional. This gradient flow observes desirable features for images, such as sharp edges and enables spectral, scale, and texture analysis. Solving the TV flow is challenging; one reason is the the non-uniqueness of the subgradients. The standard numerical approach for TV flow requires solving multiple non-smooth optimisation problems. Even with state-of-the-art convex optimisation techniques, this is often prohibitively expensive and strongly motivates the use of alternative, faster approaches. Inspired by and extending the framework of physics-informed neural networks (PINNs), we propose the TVflowNET, an unsupervised neural network approach, to approximate the solution of the TV flow given an initial image and a time instance. The TVflowNET requires no ground truth data but rather makes use of the PDE for optimisation of the network parameters. We circumvent the challenges related to the non-uniqueness of the subgradients by additionally learning the related diffusivity term. Our approach significantly speeds up the computation time and we show that the TVflowNET approximates the TV flow solution with high fidelity for different image sizes and image types. Additionally, we give a full comparison of different network architecture designs as well as training regimes to underscore the effectiveness of our approach.
A taxonomy of explanations to support Explainability-by-Design
Venue: arXiv cs.AI 2024
Year: 2024

As automated decision-making solutions are increasingly applied to all aspects of everyday life, capabilities to generate meaningful explanations for a variety of stakeholders (i.e., decision-makers, recipients of decisions, auditors, regulators...) become crucial. In this paper, we present a taxonomy of explanations that was developed as part of a holistic 'Explainability-by-Design' approach for the purposes of the project PLEAD. The taxonomy was built with a view to produce explanations for a wide range of requirements stemming from a variety of regulatory frameworks or policies set at the organizational level either to translate high-level compliance requirements or to meet business needs. The taxonomy comprises nine dimensions. It is used as a stand-alone classifier of explanations conceived as detective controls, in order to aid supportive automated compliance strategies. A machinereadable format of the taxonomy is provided in the form of a light ontology and the benefits of starting the Explainability-by-Design journey with such a taxonomy are demonstrated through a series of examples.
Online Paging with Heterogeneous Cache Slots
Venue: arXiv cs.DS 2024
Year: 2024

It is natural to generalize the online $k$-Server problem by allowing each request to specify not only a point $p$, but also a subset $S$ of servers that may serve it. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page $p$, but also a subset $S$ of cache slots, and is satisfied by having a copy of $p$ in some slot in $S$. We call this problem Slot-Heterogenous Paging. We parameterize the problem by specifying a family $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$: - If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard \Paging ($\mathcal S=\{[k]\}$). - As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $Ω(\sqrt{|\mathcal S|})$. - For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized). - The special case of laminar $\mathcal S$ that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio for weighted All-or-One Paging is $Θ(k)$. Offline All-or-One Paging is NP-hard. Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P of pages, and is satisfied by fetching any page from $\mathcal P into the cache. The optimal ratios for the latter problem (with laminar family of height $h$) are at most $hk$ (deterministic) and $h\,H_k$ (randomized).
The Rough Topology for Numerical Data
Venue: arXiv cs.IT 2024
Year: 2024

In this paper, we generalize the rough topology and the core to numerical data by classifying objects in terms of the attribute values. A new approach to finding the core for numerical data is discussed. Then a measurement to find whether an attribute is in the core or not is given. This new method for finding the core is used for attribute reduction. It is tested and compared by using eight different machine-learning algorithms. Also, it is discussed how this material is used to rank the importance of attributes in data classification. Finally, the algorithms and codes to convert data to pertinent data and to find the core is also provided.