OpenRaiser/Intern-Atlas huggingface dataset:
Optimizing Audio Recommendations for the Long-Term: A Reinforcement Learning Perspective
Venue: arXiv cs.LG 2024
Year: 2024

We present a novel podcast recommender system deployed at industrial scale. This system successfully optimizes personal listening journeys that unfold over months for hundreds of millions of listeners. In deviating from the pervasive industry practice of optimizing machine learning algorithms for short-term proxy metrics, the system substantially improves long-term performance in A/B tests. The paper offers insights into how our methods cope with attribution, coordination, and measurement challenges that usually hinder such long-term optimization. To contextualize these practical insights within a broader academic framework, we turn to reinforcement learning (RL). Using the language of RL, we formulate a comprehensive model of users' recurring relationships with a recommender system. Then, within this model, we identify our approach as a policy improvement update to a component of the existing recommender system, enhanced by tailored modeling of value functions and user-state representations. Illustrative offline experiments suggest this specialized modeling reduces data requirements by as much as a factor of 120,000 compared to black-box approaches.
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
Venue: arXiv cs.DM 2024
Year: 2024

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.
Read and Reap the Rewards: Learning to Play Atari with the Help of Instruction Manuals
Venue: arXiv cs.LG 2024
Year: 2024

High sample complexity has long been a challenge for RL. On the other hand, humans learn to perform tasks not only from interaction or demonstrations, but also by reading unstructured text documents, e.g., instruction manuals. Instruction manuals and wiki pages are among the most abundant data that could inform agents of valuable features and policies or task-specific environmental dynamics and reward structures. Therefore, we hypothesize that the ability to utilize human-written instruction manuals to assist learning policies for specific tasks should lead to a more efficient and better-performing agent. We propose the Read and Reward framework. Read and Reward speeds up RL algorithms on Atari games by reading manuals released by the Atari game developers. Our framework consists of a QA Extraction module that extracts and summarizes relevant information from the manual and a Reasoning module that evaluates object-agent interactions based on information from the manual. An auxiliary reward is then provided to a standard A2C RL agent, when interaction is detected. Experimentally, various RL algorithms obtain significant improvement in performance and training speed when assisted by our design.
Imperceptible Sample-Specific Backdoor to DNN with Denoising Autoencoder
Venue: arXiv cs.CR 2024
Year: 2024

The backdoor attack poses a new security threat to deep neural networks. Existing backdoor often relies on visible universal trigger to make the backdoored model malfunction, which are not only usually visually suspicious to human but also catchable by mainstream countermeasures. We propose an imperceptible sample-specific backdoor that the trigger varies from sample to sample and invisible. Our trigger generation is automated through a desnoising autoencoder that is fed with delicate but pervasive features (i.e., edge patterns per images). We extensively experiment our backdoor attack on ImageNet and MS-Celeb-1M, which demonstrates stable and nearly 100% (i.e., 99.8%) attack success rate with negligible impact on the clean data accuracy of the infected model. The denoising autoeconder based trigger generator is reusable or transferable across tasks (e.g., from ImageNet to MS-Celeb-1M), whilst the trigger has high exclusiveness (i.e., a trigger generated for one sample is not applicable to another sample). Besides, our proposed backdoored model has achieved high evasiveness against mainstream backdoor defenses such as Neural Cleanse, STRIP, SentiNet and Fine-Pruning.
A Reduction from Chores Allocation to Job Scheduling
Venue: arXiv cs.GT 2024
Year: 2024

We consider allocating indivisible chores among agents with different cost functions, such that all agents receive a cost of at most a constant factor times their maximin share. The state-of-the-art was presented in In EC 2021 by Huang and Lu. They presented a non-polynomial-time algorithm, called HFFD, that attains an 11/9 approximation, and a polynomial-time algorithm that attains a 5/4 approximation. In this paper, we show that HFFD can be reduced to an algorithm called MultiFit, developed by Coffman, Garey and Johnson in 1978 for makespan minimization in job scheduling. Using this reduction, we prove that the approximation ratio of HFFD is in fact equal to that of MultiFit, which is known to be 13/11 in general, 20/17 for n at most 7, and 15/13 for n=3. Moreover, we develop an algorithm for (13/11+epsilon)-maximin-share allocation for any epsilon>0, with run-time polynomial in the problem size and 1/epsilon. For n=3, we can improve the algorithm to find a 15/13-maximin-share allocation with run-time polynomial in the problem size. Thus, we have practical algorithms that attain the best known approximation to maximin-share chore allocation.
Hierarchical Generative Adversarial Imitation Learning with Mid-level Input Generation for Autonomous Driving on Urban Environments
Venue: arXiv cs.LG 2024
Year: 2024

Deriving robust control policies for realistic urban navigation scenarios is not a trivial task. In an end-to-end approach, these policies must map high-dimensional images from the vehicle's cameras to low-level actions such as steering and throttle. While pure Reinforcement Learning (RL) approaches are based exclusively on engineered rewards, Generative Adversarial Imitation Learning (GAIL) agents learn from expert demonstrations while interacting with the environment, which favors GAIL on tasks for which a reward signal is difficult to derive, such as autonomous driving. However, training deep networks directly from raw images on RL tasks is known to be unstable and troublesome. To deal with that, this work proposes a hierarchical GAIL-based architecture (hGAIL) which decouples representation learning from the driving task to solve the autonomous navigation of a vehicle. The proposed architecture consists of two modules: a GAN (Generative Adversarial Net) which generates an abstract mid-level input representation, which is the Bird's-Eye View (BEV) from the surroundings of the vehicle; and the GAIL which learns to control the vehicle based on the BEV predictions from the GAN as input. hGAIL is able to learn both the policy and the mid-level representation simultaneously as the agent interacts with the environment. Our experiments made in the CARLA simulation environment have shown that GAIL exclusively from cameras (without BEV) fails to even learn the task, while hGAIL, after training exclusively on one city, was able to autonomously navigate successfully in 98% of the intersections of a new city not used in training phase. Videos and code available at: https://sites.google.com/view/hgail
Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
Venue: arXiv cs.DS 2024
Year: 2024

We show a fully dynamic algorithm for maintaining $(1+ε)$-approximate \emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges using $m^{0.5-Ω_ε(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna SODA'22]). Our key technical component is the first sublinear algorithm for $(1,εn)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least $1.499$ or assumed that the graph has a very small maximum degree.
Combining Reconstruction and Contrastive Methods for Multimodal Representations in RL
Venue: arXiv cs.LG 2024
Year: 2024

Learning self-supervised representations using reconstruction or contrastive losses improves performance and sample complexity of image-based and multimodal reinforcement learning (RL). Here, different self-supervised loss functions have distinct advantages and limitations depending on the information density of the underlying sensor modality. Reconstruction provides strong learning signals but is susceptible to distractions and spurious information. While contrastive approaches can ignore those, they may fail to capture all relevant details and can lead to representation collapse. For multimodal RL, this suggests that different modalities should be treated differently based on the amount of distractions in the signal. We propose Contrastive Reconstructive Aggregated representation Learning (CoRAL), a unified framework enabling us to choose the most appropriate self-supervised loss for each sensor modality and allowing the representation to better focus on relevant aspects. We evaluate CoRAL's benefits on a wide range of tasks with images containing distractions or occlusions, a new locomotion suite, and a challenging manipulation suite with visually realistic distractions. Our results show that learning a multimodal representation by combining contrastive and reconstruction-based losses can significantly improve performance and solve tasks that are out of reach for more naive representation learning approaches and other recent baselines.
Brain Effective Connectome based on fMRI and DTI Data: Bayesian Causal Learning and Assessment
Venue: arXiv cs.LG 2024
Year: 2024

Neuroscientific studies aim to find an accurate and reliable brain Effective Connectome (EC). Although current EC discovery methods have contributed to our understanding of brain organization, their performances are severely constrained by the short sample size and poor temporal resolution of fMRI data, and high dimensionality of the brain connectome. By leveraging the DTI data as prior knowledge, we introduce two Bayesian causal discovery frameworks -- the Bayesian GOLEM (BGOLEM) and Bayesian FGES (BFGES) methods -- that offer significantly more accurate and reliable ECs and address the shortcomings of the existing causal discovery methods in discovering ECs based on only fMRI data. Through a series of simulation studies on synthetic and hybrid (DTI of the Human Connectome Project (HCP) subjects and synthetic fMRI) data, we demonstrate the effectiveness of the proposed methods in discovering EC. To numerically assess the improvement in the accuracy of ECs with our method on empirical data, we first introduce the Pseudo False Discovery Rate (PFDR) as a new computational accuracy metric for causal discovery in the brain. We show that our Bayesian methods achieve higher accuracy than traditional methods on HCP data. Additionally, we measure the reliability of discovered ECs using the Rogers-Tanimoto index for test-retest data and show that our Bayesian methods provide significantly more reproducible ECs than traditional methods. Overall, our study's numerical and graphical results highlight the potential for these frameworks to advance our understanding of brain function and organization significantly.
Robust Knowledge Transfer in Tiered Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

In this paper, we study the Tiered Reinforcement Learning setting, a parallel transfer learning framework, where the goal is to transfer knowledge from the low-tier (source) task to the high-tier (target) task to reduce the exploration risk of the latter while solving the two tasks in parallel. Unlike previous work, we do not assume the low-tier and high-tier tasks share the same dynamics or reward functions, and focus on robust knowledge transfer without prior knowledge on the task similarity. We identify a natural and necessary condition called the ``Optimal Value Dominance'' for our objective. Under this condition, we propose novel online learning algorithms such that, for the high-tier task, it can achieve constant regret on partial states depending on the task similarity and retain near-optimal regret when the two tasks are dissimilar, while for the low-tier task, it can keep near-optimal without making sacrifice. Moreover, we further study the setting with multiple low-tier tasks, and propose a novel transfer source selection mechanism, which can ensemble the information from all low-tier tasks and allow provable benefits on a much larger state-action space.
A Reparameterized Discrete Diffusion Model for Text Generation
Venue: arXiv cs.CL 2024
Year: 2024

This work studies discrete diffusion probabilistic models with applications to natural language generation. We derive an alternative yet equivalent formulation of the sampling from discrete diffusion processes and leverage this insight to develop a family of reparameterized discrete diffusion models. The derived generic framework is highly flexible, offers a fresh perspective of the generation process in discrete diffusion models, and features more effective training and decoding techniques. We conduct extensive experiments to evaluate the text generation capability of our model, demonstrating significant improvements over existing diffusion models.
Is Distance Matrix Enough for Geometric Deep Learning?
Venue: arXiv cs.LG 2024
Year: 2024

Graph Neural Networks (GNNs) are often used for tasks involving the 3D geometry of a given graph, such as molecular dynamics simulation. While incorporating Euclidean distance into Message Passing Neural Networks (referred to as Vanilla DisGNN) is a straightforward way to learn the geometry, it has been demonstrated that Vanilla DisGNN is geometrically incomplete. In this work, we first construct families of novel and symmetric geometric graphs that Vanilla DisGNN cannot distinguish even when considering all-pair distances, which greatly expands the existing counterexample families. Our counterexamples show the inherent limitation of Vanilla DisGNN to capture symmetric geometric structures. We then propose $k$-DisGNNs, which can effectively exploit the rich geometry contained in the distance matrix. We demonstrate the high expressive power of $k$-DisGNNs from three perspectives: 1. They can learn high-order geometric information that cannot be captured by Vanilla DisGNN. 2. They can unify some existing well-designed geometric models. 3. They are universal function approximators from geometric graphs to scalars (when $k\geq 2$) and vectors (when $k\geq 3$). Most importantly, we establish a connection between geometric deep learning (GDL) and traditional graph representation learning (GRL), showing that those highly expressive GNN models originally designed for GRL can also be applied to GDL with impressive performance, and that existing complicated, equivariant models are not the only solution. Experiments verify our theory. Our $k$-DisGNNs achieve many new state-of-the-art results on MD17.
Federated attention consistent learning models for prostate cancer diagnosis and Gleason grading
Venue: arXiv cs.CV 2024
Year: 2024

Artificial intelligence (AI) holds significant promise in transforming medical imaging, enhancing diagnostics, and refining treatment strategies. However, the reliance on extensive multicenter datasets for training AI models poses challenges due to privacy concerns. Federated learning provides a solution by facilitating collaborative model training across multiple centers without sharing raw data. This study introduces a federated attention-consistent learning (FACL) framework to address challenges associated with large-scale pathological images and data heterogeneity. FACL enhances model generalization by maximizing attention consistency between local clients and the server model. To ensure privacy and validate robustness, we incorporated differential privacy by introducing noise during parameter transfer. We assessed the effectiveness of FACL in cancer diagnosis and Gleason grading tasks using 19,461 whole-slide images of prostate cancer from multiple centers. In the diagnosis task, FACL achieved an area under the curve (AUC) of 0.9718, outperforming seven centers with an average AUC of 0.9499 when categories are relatively balanced. For the Gleason grading task, FACL attained a Kappa score of 0.8463, surpassing the average Kappa score of 0.7379 from six centers. In conclusion, FACL offers a robust, accurate, and cost-effective AI training model for prostate cancer pathology while maintaining effective data safeguards.
Efficient Graph Laplacian Estimation by Proximal Newton
Venue: arXiv cs.LG 2024
Year: 2024

The Laplacian-constrained Gaussian Markov Random Field (LGMRF) is a common multivariate statistical model for learning a weighted sparse dependency graph from given data. This graph learning problem can be formulated as a maximum likelihood estimation (MLE) of the precision matrix, subject to Laplacian structural constraints, with a sparsity-inducing penalty term. This paper aims to solve this learning problem accurately and efficiently. First, since the commonly used $\ell_1$-norm penalty is inappropriate in this setting and may lead to a complete graph, we employ the nonconvex minimax concave penalty (MCP), which promotes sparse solutions with lower estimation bias. Second, as opposed to existing first-order methods for this problem, we develop a second-order proximal Newton approach to obtain an efficient solver, utilizing several algorithmic features, such as using Conjugate Gradients, preconditioning, and splitting to active/free sets. Numerical experiments demonstrate the advantages of the proposed method in terms of both computational complexity and graph learning accuracy compared to existing methods.
Languages given by Finite Automata over the Unary Alphabet
Venue: arXiv cs.FL 2024
Year: 2024

This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let $n$ denote the maximum of the number of states of the input finite automata considered in the corresponding results. The following main results are obtained: (1) Given two unary NFAs recognising $L$ and $H$, respectively, one can decide whether $L \subseteq H$ as well as whether $L = H$ in time $2^{O((n \log n)^{1/3})}$. The previous upper bound on time was $2^{O((n \log n)^{1/2})}$ as given by Chrobak (1986), and this bound was not significantly improved since then. (2) Given two unary UFAs (unambiguous finite automata) recognising $L$ and $H$, respectively, one can determine a UFA recognising $L \cup H$ and a UFA recognising complement of $L$, where these output UFAs have the number of states bounded by a quasipolynomial in $n$. However, in the worst case, a UFA for recognising concatenation of languages recognised by two $n$-state UFAs, uses $2^{Θ((n \log^2 n)^{1/3})}$ states. (3) Given a unary language $L$, if $L$ contains the word of length $k$, then let $L(k)=1$ else let $L(k)=0$. Let $ω_L$ be the $ω$-word $L(0)L(1)\ldots$ and let $\cal L$ be a fixed $ω$-regular language. The last section studies how difficult it is to decide, given an $n$-state UFA or NFA
Movable-Antenna Enhanced Multiuser Communication via Antenna Position Optimization
Venue: arXiv cs.IT 2024
Year: 2024

Movable antenna (MA) is a promising technology to improve wireless communication performance by varying the antenna position in a given finite area at the transceivers to create more favorable channel conditions. In this paper, we investigate the MA-enhanced multiple-access channel (MAC) for the uplink transmission from multiple users each equipped with a single MA to a base station (BS) with a fixed-position antenna (FPA) array. A field-response based channel model is used to characterize the multi-path channel between the antenna array of the BS and each user's MA with a flexible position. To evaluate the MAC performance gain provided by MAs, we formulate an optimization problem for minimizing the total transmit power of users, subject to a minimum-achievable-rate requirement for each user, where the positions of MAs and the transmit powers of users, as well as the receive combining matrix of the BS are jointly optimized. To solve this non-convex optimization problem involving intricately coupled variables, we develop two algorithms based on zero-forcing (ZF) and minimum mean square error (MMSE) combining methods, respectively. Specifically, for each algorithm, the combining matrix of the BS and the total transmit power of users are expressed as a function of the MAs' position vectors, which are then optimized by using the proposed multi-directional descent (MDD) framework. It is shown that the proposed ZF-based and MMSE-based MDD algorithms can converge to high-quality suboptimal solutions with low computational complexities. Simulation results demonstrate that the proposed solutions for MA-enhanced multiple access systems can significantly decrease the total transmit power of users as compared to conventional FPA systems employing antenna selection under both perfect and imperfect field-response information.
When mitigating bias is unfair: multiplicity and arbitrariness in algorithmic group fairness
Venue: arXiv cs.LG 2024
Year: 2024

Most research on fair machine learning has prioritized optimizing criteria such as Demographic Parity and Equalized Odds. Despite these efforts, there remains a limited understanding of how different bias mitigation strategies affect individual predictions and whether they introduce arbitrariness into the debiasing process. This paper addresses these gaps by exploring whether models that achieve comparable fairness and accuracy metrics impact the same individuals and mitigate bias in a consistent manner. We introduce the FRAME (FaiRness Arbitrariness and Multiplicity Evaluation) framework, which evaluates bias mitigation through five dimensions: Impact Size (how many people were affected), Change Direction (positive versus negative changes), Decision Rates (impact on models' acceptance rates), Affected Subpopulations (who was affected), and Neglected Subpopulations (where unfairness persists). This framework is intended to help practitioners understand the impacts of debiasing processes and make better-informed decisions regarding model selection. Applying FRAME to various bias mitigation approaches across key datasets allows us to exhibit significant differences in the behaviors of debiasing methods. These findings highlight the limitations of current fairness criteria and the inherent arbitrariness in the debiasing process.