pwc-archive/papers-with-abstracts huggingface dataset:
Scalable Offline Reinforcement Learning for Mean Field Games
Authors: Axel Brunnbauer, Julian Lemmel, Zahra Babaiee, Sophie Neubauer, Radu Grosu
Date: 2024-10-23 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning

Reinforcement learning algorithms for mean-field games offer a scalable framework for optimizing policies in large populations of interacting agents. Existing methods often depend on online interactions or access to system dynamics, limiting their practicality in real-world scenarios where such interactions are infeasible or difficult to model. In this paper, we present Offline Munchausen Mirror Descent (Off-MMD), a novel mean-field RL algorithm that approximates equilibrium policies in mean-field games using purely offline data. By leveraging iterative mirror descent and importance sampling techniques, Off-MMD estimates the mean-field distribution from static datasets without relying on simulation or environment dynamics. Additionally, we incorporate techniques from offline reinforcement learning to address common issues like Q-value overestimation, ensuring robust policy learning even with limited data coverage. Our algorithm scales to complex environments and demonstrates strong performance on benchmark tasks like crowd exploration or navigation, highlighting its applicability to real-world multi-agent systems where online experimentation is infeasible. We empirically demonstrate the robustness of Off-MMD to low-quality datasets and conduct experiments to investigate its sensitivity to hyperparameter choices.
Identifiable Representation and Model Learning for Latent Dynamic Systems
Authors: Congxi Zhang, Yongchun Xie
Date: 2024-10-23 00:00:00
Tasks: Decision Making, Inductive Bias

Learning identifiable representations and models from low-level observations is helpful for an intelligent spacecraft to complete downstream tasks reliably. For temporal observations, to ensure that the data generating process is provably inverted, most existing works either assume the noise variables in the dynamic mechanisms are (conditionally) independent or require that the interventions can directly affect each latent variable. However, in practice, the relationship between the exogenous inputs/interventions and the latent variables may follow some complex deterministic mechanisms. In this work, we study the problem of identifiable representation and model learning for latent dynamic systems. The key idea is to use an inductive bias inspired by controllable canonical forms, which are sparse and input-dependent by definition. We prove that, for linear and affine nonlinear latent dynamic systems with sparse input matrices, it is possible to identify the latent variables up to scaling and determine the dynamic models up to some simple transformations. The results have the potential to provide some theoretical guarantees for developing more trustworthy decision-making and control methods for intelligent spacecrafts.
AdaRankGrad: Adaptive Gradient-Rank and Moments for Memory-Efficient LLMs Training and Fine-Tuning
Authors: Yehonathan Refael, Jonathan Svirsky, Boris Shustin, Wasim Huleihel, Ofir Lindenbaum
Date: 2024-10-23 00:00:00

Training and fine-tuning large language models (LLMs) come with challenges related to memory and computational requirements due to the increasing size of the model weights and the optimizer states. Various techniques have been developed to tackle these challenges, such as low-rank adaptation (LoRA), which involves introducing a parallel trainable low-rank matrix to the fixed pre-trained weights at each layer. However, these methods often fall short compared to the full-rank weight training approach, as they restrict the parameter search to a low-rank subspace. This limitation can disrupt training dynamics and require a full-rank warm start to mitigate the impact. In this paper, we introduce a new method inspired by a phenomenon we formally prove: as training progresses, the rank of the estimated layer gradients gradually decreases, and asymptotically approaches rank one. Leveraging this, our approach involves adaptively reducing the rank of the gradients during Adam optimization steps, using an efficient online-updating low-rank projections rule. We further present a randomized SVD scheme for efficiently finding the projection matrix. Our technique enables full-parameter fine-tuning with adaptive low-rank gradient updates, significantly reducing overall memory requirements during training compared to state-of-the-art methods while improving model performance in both pretraining and fine-tuning. Finally, we provide a convergence analysis of our method and demonstrate its merits for training and fine-tuning language and biological foundation models.
Relaxed Equivariance via Multitask Learning
Authors: Ahmed A. Elhag, T. Konstantin Rusch, Francesco Di Giovanni, Michael Bronstein
Date: 2024-10-23 00:00:00
Tasks: Inductive Bias

Incorporating equivariance as an inductive bias into deep learning architectures to take advantage of the data symmetry has been successful in multiple applications, such as chemistry and dynamical systems. In particular, roto-translations are crucial for effectively modeling geometric graphs and molecules, where understanding the 3D structures enhances generalization. However, equivariant models often pose challenges due to their high computational complexity. In this paper, we introduce REMUL, a training procedure for approximating equivariance with multitask learning. We show that unconstrained models (which do not build equivariance into the architecture) can learn approximate symmetries by minimizing an additional simple equivariance loss. By formulating equivariance as a new learning objective, we can control the level of approximate equivariance in the model. Our method achieves competitive performance compared to equivariant baselines while being $10 \times$ faster at inference and $2.5 \times$ at training.
Population stratification for prediction of mortality in post-AKI patients
Authors: Flavio S. Correa da Silva, Simon Sawhney
Date: 2024-10-23 00:00:00

Acute kidney injury (AKI) is a serious clinical condition that affects up to 20% of hospitalised patients. AKI is associated with short term unplanned hospital readmission and post-discharge mortality risk. Patient risk and healthcare expenditures can be minimised by followup planning grounded on predictive models and machine learning. Since AKI is multi-factorial, predictive models specialised in different categories of patients can increase accuracy of predictions. In the present article we present some results following this approach.
Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs
Authors: Ferdi Kossmann, Bruce Fontaine, Daya Khudia, Michael Cafarella, Samuel Madden
Date: 2024-10-23 00:00:00
Tasks: GPU, Scheduling

Serving systems for Large Language Models (LLMs) improve throughput by processing several requests concurrently. However, multiplexing hardware resources between concurrent requests involves non-trivial scheduling decisions. Practical serving systems typically implement these decisions at two levels: First, a load balancer routes requests to different servers which each hold a replica of the LLM. Then, on each server, an engine-level scheduler decides when to run a request, or when to queue or preempt it. Improved scheduling policies may benefit a wide range of LLM deployments and can often be implemented as "drop-in replacements" to a system's current policy. In this work, we survey scheduling techniques from the literature and from practical serving systems. We find that schedulers from the literature often achieve good performance but introduce significant complexity. In contrast, schedulers in practical deployments often leave easy performance gains on the table but are easy to implement, deploy and configure. This finding motivates us to introduce two new scheduling techniques, which are both easy to implement, and outperform current techniques on production workload traces.
Optimal Streaming Algorithms for Multi-Armed Bandits
Authors: Tianyuan Jin, Keke Huang, Jing Tang, Xiaokui Xiao
Date: 2024-10-23 00:00:00
Tasks: Multi-Armed Bandits

This paper studies two variants of the best arm identification (BAI) problem under the streaming model, where we have a stream of $n$ arms with reward distributions supported on $[0,1]$ with unknown means. The arms in the stream are arriving one by one, and the algorithm cannot access an arm unless it is stored in a limited size memory. We first study the streaming \eps-$top$-$k$ arms identification problem, which asks for $k$ arms whose reward means are lower than that of the $k$-th best arm by at most $\eps$ with probability at least $1-\delta$. For general $\eps \in (0,1)$, the existing solution for this problem assumes $k = 1$ and achieves the optimal sample complexity $O(\frac{n}{\eps^2} \log \frac{1}{\delta})$ using $O(\log^*(n))$ ($\log^*(n)$ equals the number of times that we need to apply the logarithm function on $n$ before the results is no more than 1.) memory and a single pass of the stream. We propose an algorithm that works for any $k$ and achieves the optimal sample complexity $O(\frac{n}{\eps^2} \log\frac{k}{\delta})$ using a single-arm memory and a single pass of the stream. Second, we study the streaming BAI problem, where the objective is to identify the arm with the maximum reward mean with at least $1-\delta$ probability, using a single-arm memory and as few passes of the input stream as possible. We present a single-arm-memory algorithm that achieves a near instance-dependent optimal sample complexity within $O(\log \Delta_2^{-1})$ passes, where $\Delta_2$ is the gap between the mean of the best arm and that of the second best arm.
Non-intrusive Speech Quality Assessment with Diffusion Models Trained on Clean Speech
Authors: Danilo de Oliveira, Julius Richter, Jean-Marie Lemercier, Simon Welker, Timo Gerkmann
Date: 2024-10-23 00:00:00
Tasks: Density Estimation

Diffusion models have found great success in generating high quality, natural samples of speech, but their potential for density estimation for speech has so far remained largely unexplored. In this work, we leverage an unconditional diffusion model trained only on clean speech for the assessment of speech quality. We show that the quality of a speech utterance can be assessed by estimating the likelihood of a corresponding sample in the terminating Gaussian distribution, obtained via a deterministic noising process. The resulting method is purely unsupervised, trained only on clean speech, and therefore does not rely on annotations. Our diffusion-based approach leverages clean speech priors to assess quality based on how the input relates to the learned distribution of clean data. Our proposed log-likelihoods show promising results, correlating well with intrusive speech quality metrics and showing the best correlation with human scores in a listening experiment.
A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression
Authors: Tin Sum Cheng, Aurelien Lucchi, Anastasis Kratsios, David Belius
Date: 2024-10-23 00:00:00
Tasks: regression

This paper conducts a comprehensive study of the learning curves of kernel ridge regression (KRR) under minimal assumptions. Our contributions are three-fold: 1) we analyze the role of key properties of the kernel, such as its spectral eigen-decay, the characteristics of the eigenfunctions, and the smoothness of the kernel; 2) we demonstrate the validity of the Gaussian Equivalent Property (GEP), which states that the generalization performance of KRR remains the same when the whitened features are replaced by standard Gaussian vectors, thereby shedding light on the success of previous analyzes under the Gaussian Design Assumption; 3) we derive novel bounds that improve over existing bounds across a broad range of setting such as (in)dependent feature vectors and various combinations of eigen-decay rates in the over/underparameterized regimes.
Small Singular Values Matter: A Random Matrix Analysis of Transformer Models
Authors: Max Staats, Matthias Thamm, Bernd Rosenow
Date: 2024-10-23 00:00:00

As large language models (LLMs) become increasingly central to AI applications, understanding their inner workings is essential. In this work, we analyze the spectra of weight matrices in pretrained transformer models through the lens of random matrix theory (RMT) to uncover learned structures. We find that certain regions of the weight matrix spectra deviate markedly from RMT predictions, indicating richer feature encoding. By comparing the corresponding singular vectors to eigenvectors of activation covariance matrices, we observe substantial overlap precisely where the spectra deviate from RMT expectations. Our analysis further reveals the important role of small singular values in LLMs, showing that these values contain significant information, a claim supported by increased perplexity when they are removed from the model. Although these small values may appear unimportant prior to task-specific fine-tuning, removing them afterward significantly degrades performance, revealing that fine-tuning refines the model primarily in these spectral regions. These results emphasize the critical role of small singular values, suggesting that removing them in an already aligned transformer can be detrimental, as it may compromise model alignment.
Faster Language Models with Better Multi-Token Prediction Using Tensor Decomposition
Authors: Artem Basharin, Andrei Chertkov, Ivan Oseledets
Date: 2024-10-23 00:00:00
Tasks: Code Generation, Mixture-of-Experts, Tensor Decomposition

We propose a new model for multi-token prediction in transformers, aiming to enhance sampling efficiency without compromising accuracy. Motivated by recent work that predicts the probabilities of subsequent tokens using multiple heads, we connect this approach to rank-$1$ canonical tensor decomposition. By generalizing it to a rank-$r$ canonical probability decomposition, we develop an improved model that predicts multiple tokens simultaneously. This model can also be interpreted as a mixture of experts, allowing us to leverage successful techniques from that domain for efficient and robust training. Importantly, the overall overhead for training and sampling remains low. Our method demonstrates significant improvements in inference speed for both text and code generation tasks, proving particularly beneficial within the self-speculative decoding paradigm. It maintains its effectiveness across various model sizes and training epochs, highlighting its robustness and scalability.
Anomaly Resilient Temporal QoS Prediction using Hypergraph Convoluted Transformer Network
Authors: Suraj Kumar, Soumi Chattopadhyay, Chandranath Adak
Date: 2024-10-23 00:00:00
Tasks: Prediction

Quality-of-Service (QoS) prediction is a critical task in the service lifecycle, enabling precise and adaptive service recommendations by anticipating performance variations over time in response to evolving network uncertainties and user preferences. However, contemporary QoS prediction methods frequently encounter data sparsity and cold-start issues, which hinder accurate QoS predictions and limit the ability to capture diverse user preferences. Additionally, these methods often assume QoS data reliability, neglecting potential credibility issues such as outliers and the presence of greysheep users and services with atypical invocation patterns. Furthermore, traditional approaches fail to leverage diverse features, including domain-specific knowledge and complex higher-order patterns, essential for accurate QoS predictions. In this paper, we introduce a real-time, trust-aware framework for temporal QoS prediction to address the aforementioned challenges, featuring an end-to-end deep architecture called the Hypergraph Convoluted Transformer Network (HCTN). HCTN combines a hypergraph structure with graph convolution over hyper-edges to effectively address high-sparsity issues by capturing complex, high-order correlations. Complementing this, the transformer network utilizes multi-head attention along with parallel 1D convolutional layers and fully connected dense blocks to capture both fine-grained and coarse-grained dynamic patterns. Additionally, our approach includes a sparsity-resilient solution for detecting greysheep users and services, incorporating their unique characteristics to improve prediction accuracy. Trained with a robust loss function resistant to outliers, HCTN demonstrated state-of-the-art performance on the large-scale WSDREAM-2 datasets for response time and throughput.
Topology meets Machine Learning: An Introduction using the Euler Characteristic Transform
Authors: Bastian Rieck
Date: 2024-10-23 00:00:00

This overview article makes the case for how topological concepts can enrich research in machine learning. Using the Euler Characteristic Transform (ECT), a geometrical-topological invariant, as a running example, I present different use cases that result in more efficient models for analyzing point clouds, graphs, and meshes. Moreover, I outline a vision for how topological concepts could be used in the future, comprising (1) the learning of functions on topological spaces, (2) the building of hybrid models that imbue neural networks with knowledge about the topological information in data, and (3) the analysis of qualitative properties of neural networks. With current research already addressing some of these aspects, this article thus serves as an introduction and invitation to this nascent area of research.
Can Uncertainty Quantification Enable Better Learning-based Index Tuning?
Authors: Tao Yu, Zhaonian Zou, Hao Xiong
Date: 2024-10-23 00:00:00
Tasks: Management, Uncertainty Quantification

Index tuning is crucial for optimizing database performance by selecting optimal indexes based on workload. The key to this process lies in an accurate and efficient benefit estimator. Traditional methods relying on what-if tools often suffer from inefficiency and inaccuracy. In contrast, learning-based models provide a promising alternative but face challenges such as instability, lack of interpretability, and complex management. To overcome these limitations, we adopt a novel approach: quantifying the uncertainty in learning-based models' results, thereby combining the strengths of both traditional and learning-based methods for reliable index tuning. We propose Beauty, the first uncertainty-aware framework that enhances learning-based models with uncertainty quantification and uses what-if tools as a complementary mechanism to improve reliability and reduce management complexity. Specifically, we introduce a novel method that combines AutoEncoder and Monte Carlo Dropout to jointly quantify uncertainty, tailored to the characteristics of benefit estimation tasks. In experiments involving sixteen models, our approach outperformed existing uncertainty quantification methods in the majority of cases. We also conducted index tuning tests on six datasets. By applying the Beauty framework, we eliminated worst-case scenarios and more than tripled the occurrence of best-case scenarios.
Optimizing Load Scheduling in Power Grids Using Reinforcement Learning and Markov Decision Processes
Authors: Dongwen Luo
Date: 2024-10-23 00:00:00
Tasks: Management, Q-Learning, Reinforcement Learning (RL), Scheduling

Power grid load scheduling is a critical task that ensures the balance between electricity generation and consumption while minimizing operational costs and maintaining grid stability. Traditional optimization methods often struggle with the dynamic and stochastic nature of power systems, especially when faced with renewable energy sources and fluctuating demand. This paper proposes a reinforcement learning (RL) approach using a Markov Decision Process (MDP) framework to address the challenges of dynamic load scheduling. The MDP is defined by a state space representing grid conditions, an action space covering control operations like generator adjustments and storage management, and a reward function balancing economic efficiency and system reliability. We investigate the application of various RL algorithms, from basic Q-Learning to more advanced Deep Q-Networks (DQN) and Actor-Critic methods, to determine optimal scheduling policies. The proposed approach is evaluated through a simulated power grid environment, demonstrating its potential to improve scheduling efficiency and adapt to variable demand patterns. Our results show that the RL-based method provides a robust and scalable solution for real-time load scheduling, contributing to the efficient management of modern power grids.
Towards Active Participant-Centric Vertical Federated Learning: Some Representations May Be All You Need
Authors: Jon Irureta, Jon Imaz, Aizea Lojo, Marco González, Iñigo Perona
Date: 2024-10-23 00:00:00
Tasks: All, Federated Learning, Knowledge Distillation, Representation Learning, Vertical Federated Learning

Vertical Federated Learning (VFL) enables collaborative model training across different participants with distinct features and common samples, while preserving data privacy. Existing VFL methodologies often struggle with realistic data partitions, typically incurring high communication costs and significant operational complexity. In this work, we introduce a novel simplified approach to VFL, Active Participant-Centric VFL (APC-VFL), that, to the best of our knowledge, is the first to require only a single communication round between participants, and allows the active participant to do inference in a non collaborative fashion. This method integrates unsupervised representation learning with knowledge distillation to achieve comparable accuracy to traditional VFL methods based on vertical split learning in classical settings, reducing required communication rounds by up to $4200\times$, while being more flexible. Our approach also shows improvements compared to non-federated local models, as well as a comparable VFL proposal, VFedTrans, offering an efficient and flexible solution for collaborative learning.
Entity-based Reinforcement Learning for Autonomous Cyber Defence
Authors: Isaac Symes Thompson, Alberto Caron, Chris Hicks, Vasilios Mavroudis
Date: 2024-10-23 00:00:00
Tasks: Deep Reinforcement Learning, reinforcement-learning, Reinforcement Learning

A significant challenge for autonomous cyber defence is ensuring a defensive agent's ability to generalise across diverse network topologies and configurations. This capability is necessary for agents to remain effective when deployed in dynamically changing environments, such as an enterprise network where devices may frequently join and leave. Standard approaches to deep reinforcement learning, where policies are parameterised using a fixed-input multi-layer perceptron (MLP) expect fixed-size observation and action spaces. In autonomous cyber defence, this makes it hard to develop agents that generalise to environments with network topologies different from those trained on, as the number of nodes affects the natural size of the observation and action spaces. To overcome this limitation, we reframe the problem of autonomous network defence using entity-based reinforcement learning, where the observation and action space of an agent are decomposed into a collection of discrete entities. This framework enables the use of policy parameterisations specialised in compositional generalisation. We train a Transformer-based policy on the Yawning Titan cyber-security simulation environment and test its generalisation capabilities across various network topologies. We demonstrate that this approach significantly outperforms an MLP-based policy when training across fixed-size networks of varying topologies, and matches performance when training on a single network. We also demonstrate the potential for zero-shot generalisation to networks of a different size to those seen in training. These findings highlight the potential for entity-based reinforcement learning to advance the field of autonomous cyber defence by providing more generalisable policies capable of handling variations in real-world network environments.