OpenRaiser/Intern-Atlas huggingface dataset:
Straggler-Resilient Decentralized Learning via Adaptive Asynchronous Updates
Venue: arXiv cs.LG 2024
Year: 2024

With the increasing demand for large-scale training of machine learning models, fully decentralized optimization methods have recently been advocated as alternatives to the popular parameter server framework. In this paradigm, each worker maintains a local estimate of the optimal parameter vector, and iteratively updates it by waiting and averaging all estimates obtained from its neighbors, and then corrects it on the basis of its local dataset. However, the synchronization phase is sensitive to stragglers. An efficient way to mitigate this effect is to consider asynchronous updates, where each worker computes stochastic gradients and communicates with other workers at its own pace. Unfortunately, fully asynchronous updates suffer from staleness of stragglers' parameters. To address these limitations, we propose a fully decentralized algorithm DSGD-AAU with adaptive asynchronous updates via adaptively determining the number of neighbor workers for each worker to communicate with. We show that DSGD-AAU achieves a linear speedup for convergence and demonstrate its effectiveness via extensive experiments.
Unmasking Deepfakes: Masked Autoencoding Spatiotemporal Transformers for Enhanced Video Forgery Detection
Venue: arXiv cs.CV 2024
Year: 2024

We present a novel approach for the detection of deepfake videos using a pair of vision transformers pre-trained by a self-supervised masked autoencoding setup. Our method consists of two distinct components, one of which focuses on learning spatial information from individual RGB frames of the video, while the other learns temporal consistency information from optical flow fields generated from consecutive frames. Unlike most approaches where pre-training is performed on a generic large corpus of images, we show that by pre-training on smaller face-related datasets, namely Celeb-A (for the spatial learning component) and YouTube Faces (for the temporal learning component), strong results can be obtained. We perform various experiments to evaluate the performance of our method on commonly used datasets namely FaceForensics++ (Low Quality and High Quality, along with a new highly compressed version named Very Low Quality) and Celeb-DFv2 datasets. Our experiments show that our method sets a new state-of-the-art on FaceForensics++ (LQ, HQ, and VLQ), and obtains competitive results on Celeb-DFv2. Moreover, our method outperforms other methods in the area in a cross-dataset setup where we fine-tune our model on FaceForensics++ and test on CelebDFv2, pointing to its strong cross-dataset generalization ability.
Temporal Reachability Dominating Sets: contagion in temporal graphs
Venue: arXiv cs.DM 2024
Year: 2024

Given a population with dynamic pairwise connections, we ask if the entire population could be (indirectly) infected by a small group of $k$ initially infected individuals. We formalise this problem as the Temporal Reachability Dominating Set (TaRDiS}) problem on temporal graphs. We provide positive and negative parameterized complexity results in four different parameters: the number $k$ of initially infected, the lifetime $τ$ of the graph, the number of locally earliest edges in the graph, and the treewidth of the footprint graph $\mathcal{G}_\downarrow$. We additionally introduce and study the MaxMinTaRDiS problem, where the aim is to schedule connections between individuals so that at least $k$ individuals must be infected for the entire population to become fully infected. We classify three variants of the problem: Strict, Nonstrict, and Happy. We show these to be coNP-complete, NP-hard, and $Σ_2^P$-complete, respectively. Interestingly, we obtain hardness of the Nonstrict variant by showing that a natural restriction is exactly the well-studied Distance-3 Independent Set problem on static graphs.
Time arrow without past hypothesis: a toy model explanation
Venue: arXiv cs.DM 2024
Year: 2024

The laws of Physics are time-reversible, making no qualitative distinction between the past and the future -- yet we can only go towards the future. This apparent contradiction is known as the "arrow of time problem". Its current resolution states that the future is the direction of increasing entropy. But entropy can only increase towards the future if it was low in the past, and past low entropy is a very strong assumption to make, because low entropy states are rather improbable, non-generic. Recent works from the Physics literature suggest, however, we may do away with this so-called "past hypothesis", in the presence of reversible dynamical laws featuring expansion. We prove that this can be the case in principle, within a toy model. It consists in graphs upon which particles circulate and interact according to local reversible rules. Some rules locally shrink or expand the graph. We prove that almost all states expand; entropy always increases as a consequence of expansion -- thereby providing a local explanation for the rise of an entropic arrow of time without the need for a past hypothesis. The discrete setting of this toy model allows us to deploy the full rigour of theoretical Computer Science proof techniques. It also allows for the numerical exploration of several physically-motivated variants: a time-symmetric variant; two inflationary variants; and a damping variant -- which slows down thermal death. The fact that all of these models exhibit similar behaviours suggests that local reversible expansion mechanisms constitute a robust recipe for a time arrow without past hypothesis. In this qualitative sense, the explanation may therefore also be relevant at the cosmological level.
AROID: Improving Adversarial Robustness Through Online Instance-Wise Data Augmentation
Venue: arXiv cs.CV 2024
Year: 2024

Deep neural networks are vulnerable to adversarial examples. Adversarial training (AT) is an effective defense against adversarial examples. However, AT is prone to overfitting which degrades robustness substantially. Recently, data augmentation (DA) was shown to be effective in mitigating robust overfitting if appropriately designed and optimized for AT. This work proposes a new method to automatically learn online, instance-wise, DA policies to improve robust generalization for AT. This is the first automated DA method specific for robustness. A novel policy learning objective, consisting of Vulnerability, Affinity and Diversity, is proposed and shown to be sufficiently effective and efficient to be practical for automatic DA generation during AT. Importantly, our method dramatically reduces the cost of policy search from the 5000 hours of AutoAugment and the 412 hours of IDBH to 9 hours, making automated DA more practical to use for adversarial robustness. This allows our method to efficiently explore a large search space for a more effective DA policy and evolve the policy as training progresses. Empirically, our method is shown to outperform all competitive DA methods across various model architectures and datasets. Our DA policy reinforced vanilla AT to surpass several state-of-the-art AT methods regarding both accuracy and robustness. It can also be combined with those advanced AT methods to further boost robustness. Code and pre-trained models are available at https://github.com/TreeLLi/AROID.
Top-Down Framework for Weakly-supervised Grounded Image Captioning
Venue: arXiv cs.CV 2024
Year: 2024

Weakly-supervised grounded image captioning (WSGIC) aims to generate the caption and ground (localize) predicted object words in the input image without using bounding box supervision. Recent two-stage solutions mostly apply a bottom-up pipeline: (1) encode the input image into multiple region features using an object detector; (2) leverage region features for captioning and grounding. However, utilizing independent proposals produced by object detectors tends to make the subsequent grounded captioner overfitted in finding the correct object words, overlooking the relation between objects, and selecting incompatible proposal regions for grounding. To address these issues, we propose a one-stage weakly-supervised grounded captioner that directly takes the RGB image as input to perform captioning and grounding at the top-down image level. Specifically, we encode the image into visual token representations and propose a Recurrent Grounding Module (RGM) in the decoder to obtain precise Visual Language Attention Maps (VLAMs), which recognize the spatial locations of the objects. In addition, we explicitly inject a relation module into our one-stage framework to encourage relation understanding through multi-label classification. This relation semantics served as contextual information facilitating the prediction of relation and object words in the caption. We observe that the relation semantic not only assists the grounded captioner in generating a more accurate caption but also improves the grounding performance. We validate the effectiveness of our proposed method on two challenging datasets (Flick30k Entities captioning and MSCOCO captioning). The experimental results demonstrate that our method achieves state-of-the-art grounding performance.
Invertible Bloom Lookup Tables with Less Memory and Randomness
Venue: arXiv cs.DS 2024
Year: 2024

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - δ$, existing IBLT constructions require $Ω(n(\frac{\log(1/δ)}{\log(n)}+1))$ space and they crucially rely on fully random hash functions. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $δ$, our data structure only requires $\mathcal{O}\left(n + \log(1/δ)\log\log(1/δ)\right)$ space and $\mathcal{O}\left(\log(\log(n)/δ)\right)$-wise independent hash functions. As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U \to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1 - 2^{-Ω(k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest. We apply our new IBLTs to the encrypted compression problem, recently studied by Fleischhacker, Larsen, Simkin (Eurocrypt 2023). We extend their approach to work for a more general class of encryption schemes and using our new IBLT we achieve an asymptotically better compression rate.
Rate-Splitting with Hybrid Messages: DoF Analysis of the Two-User MIMO Broadcast Channel with Imperfect CSIT
Venue: arXiv cs.IT 2024
Year: 2024

Most of the existing research on degrees-of-freedom (DoF) with imperfect channel state information at the transmitter (CSIT) assume the messages are private, which may not reflect reality as the two receivers can request the same content. To overcome this limitation, we therefore consider the hybrid unicast and multicast messages. In particular, we characterize the optimal DoF region for the two-user multiple-input multiple-output (MIMO) broadcast channel (BC) with imperfect CSIT and hybrid messages. For the converse, we establish a three-step procedure to exploit the utmost possible relaxation. For the achievability, since the DoF region is with specific three-dimensional structure regarding antenna configurations and CSIT qualities, we verify the existence or non-existence of corner point candidates via the feature of antenna configurations and CSIT qualities categorization and provide a hybrid message-aware rate-splitting scheme. Besides, we show that to achieve the strictly positive corner points, it is unnecessary to split the unicast messages into private and common parts. This implies adding a multicast message may mitigate the rate-splitting complexity.
Optimal Inference in Contextual Stochastic Block Models
Venue: arXiv cs.SI 2024
Year: 2024

The contextual stochastic block model (cSBM) was proposed for unsupervised community detection on attributed graphs where both the graph and the high-dimensional node information correlate with node labels. In the context of machine learning on graphs, the cSBM has been widely used as a synthetic dataset for evaluating the performance of graph-neural networks (GNNs) for semi-supervised node classification. We consider a probabilistic Bayes-optimal formulation of the inference problem and we derive a belief-propagation-based algorithm for the semi-supervised cSBM; we conjecture it is optimal in the considered setting and we provide its implementation. We show that there can be a considerable gap between the accuracy reached by this algorithm and the performance of the GNN architectures proposed in the literature. This suggests that the cSBM, along with the comparison to the performance of the optimal algorithm, readily accessible via our implementation, can be instrumental in the development of more performant GNN architectures.
Dynamic Bayesian Networks for Predicting Cryptocurrency Price Directions: Uncovering Causal Relationships
Venue: arXiv cs.LG 2024
Year: 2024

Cryptocurrencies have gained popularity across various sectors, especially in finance and investment. Despite their growing popularity, cryptocurrencies can be a high-risk investment due to their price volatility. The inherent volatility in cryptocurrency prices, coupled with the effects of external global economic factors, makes predicting their price movements challenging. To address this challenge, we propose a dynamic Bayesian network (DBN)-based approach to uncover potential causal relationships among various features including social media data, traditional financial market factors, and technical indicators. Six popular cryptocurrencies, Bitcoin, Binance Coin, Ethereum, Litecoin, Ripple, and Tether are studied in this work. The proposed model's performance is compared to five baseline models of auto-regressive integrated moving average, support vector regression, long short-term memory, random forests, and support vector machines. The results show that while DBN performance varies across cryptocurrencies, with some cryptocurrencies exhibiting higher predictive accuracy than others, the DBN significantly outperforms the baseline models.
Where Does My Model Underperform? A Human Evaluation of Slice Discovery Algorithms
Venue: arXiv cs.HC 2024
Year: 2024

Machine learning (ML) models that achieve high average accuracy can still underperform on semantically coherent subsets ("slices") of data. This behavior can have significant societal consequences for the safety or bias of the model in deployment, but identifying these underperforming slices can be difficult in practice, especially in domains where practitioners lack access to group annotations to define coherent subsets of their data. Motivated by these challenges, ML researchers have developed new slice discovery algorithms that aim to group together coherent and high-error subsets of data. However, there has been little evaluation focused on whether these tools help humans form correct hypotheses about where (for which groups) their model underperforms. We conduct a controlled user study (N = 15) where we show 40 slices output by two state-of-the-art slice discovery algorithms to users, and ask them to form hypotheses about an object detection model. Our results provide positive evidence that these tools provide some benefit over a naive baseline, and also shed light on challenges faced by users during the hypothesis formation step. We conclude by discussing design opportunities for ML and HCI researchers. Our findings point to the importance of centering users when creating and evaluating new tools for slice discovery.
System Information Decomposition
Venue: arXiv cs.IT 2024
Year: 2024

To characterize the complex higher-order interactions among variables within a system, this study introduces a novel framework, termed System Information Decomposition (SID), aimed at decomposing the information entropy of variables into information atoms based on their interrelations. Diverging from the established Partial Information Decomposition (PID) framework, which predominantly concentrates on the directional interactions stemming from an array of source variables to a single target variable, SID adopts a holistic approach, scrutinizing the interactions across all variables within the system. Specifically, we proved all the information atoms are symmetric, which means the disentanglement of unique, redundant, and synergistic information from any specific target variable. Hence, our proposed SID framework can capture the symmetric pairwise and higher-order relationships among variables. This advance positions SID as a promising framework with the potential to foster a deeper understanding of higher-order relationships within complex systems across disciplines.
Characterizing First Arrival Position Channels: Noise Distribution and Capacity Analysis
Venue: arXiv cs.IT 2024
Year: 2024

This paper introduces a novel mathematical model for Molecular Communication (MC) systems, utilizing First Arrival Position (FAP) as a fundamental mode of information transmission. We address two critical challenges: the characterization of FAP density and the establishment of capacity bounds for channels with vertically-drifted FAP. Our method relate macroscopic Partial Differential Equation (PDE) models to microscopic Stochastic Differential Equation (SDE) models, resulting in a precise expression that links FAP density with elliptic-type Green's function. This formula is distinguished by its wide applicability across any spatial dimensions, any drift directions, and various receiver geometries. We demonstrate the practicality of our model through case studies: 2D and 3D planar receivers. The accuracy of our formula is also validated by particle-based simulations. Advancing further, the explicit FAP density forms enable us to establish closed-form upper and lower bounds for the capacity of vertically-drifted FAP channels under a second-moment constraint, significantly advancing the understanding of FAP channels in MC systems.
Skill-Critic: Refining Learned Skills for Hierarchical Reinforcement Learning
Venue: arXiv cs.LG 2024
Year: 2024

Hierarchical reinforcement learning (RL) can accelerate long-horizon decision-making by temporally abstracting a policy into multiple levels. Promising results in sparse reward environments have been seen with skills, i.e. sequences of primitive actions. Typically, a skill latent space and policy are discovered from offline data. However, the resulting low-level policy can be unreliable due to low-coverage demonstrations or distribution shifts. As a solution, we propose the Skill-Critic algorithm to fine-tune the low-level policy in conjunction with high-level skill selection. Our Skill-Critic algorithm optimizes both the low-level and high-level policies; these policies are initialized and regularized by the latent space learned from offline demonstrations to guide the parallel policy optimization. We validate Skill-Critic in multiple sparse-reward RL environments, including a new sparse-reward autonomous racing task in Gran Turismo Sport. The experiments show that Skill-Critic's low-level policy fine-tuning and demonstration-guided regularization are essential for good performance. Code and videos are available at our website: https://sites.google.com/view/skill-critic.
Extending CLIP's Image-Text Alignment to Referring Image Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Referring Image Segmentation (RIS) is a cross-modal task that aims to segment an instance described by a natural language expression. Recent methods leverage large-scale pretrained unimodal models as backbones along with fusion techniques for joint reasoning across modalities. However, the inherent cross-modal nature of RIS raises questions about the effectiveness of unimodal backbones. We propose RISCLIP, a novel framework that effectively leverages the cross-modal nature of CLIP for RIS. Observing CLIP's inherent alignment between image and text features, we capitalize on this starting point and introduce simple but strong modules that enhance unimodal feature extraction and leverage rich alignment knowledge in CLIP's image-text shared-embedding space. RISCLIP exhibits outstanding results on all three major RIS benchmarks and also outperforms previous CLIP-based methods, demonstrating the efficacy of our strategy in extending CLIP's image-text alignment to RIS.
OCAtari: Object-Centric Atari 2600 Reinforcement Learning Environments
Venue: arXiv cs.LG 2024
Year: 2024

Cognitive science and psychology suggest that object-centric representations of complex scenes are a promising step towards enabling efficient abstract reasoning from low-level perceptual features. Yet, most deep reinforcement learning approaches only rely on pixel-based representations that do not capture the compositional properties of natural scenes. For this, we need environments and datasets that allow us to work and evaluate object-centric approaches. In our work, we extend the Atari Learning Environments, the most-used evaluation framework for deep RL approaches, by introducing OCAtari, that performs resource-efficient extractions of the object-centric states for these games. Our framework allows for object discovery, object representation learning, as well as object-centric RL. We evaluate OCAtari's detection capabilities and resource efficiency. Our source code is available at github.com/k4ntz/OC_Atari.
Augment then Smooth: Reconciling Differential Privacy with Certified Robustness
Venue: arXiv cs.LG 2024
Year: 2024

Machine learning models are susceptible to a variety of attacks that can erode trust, including attacks against the privacy of training data, and adversarial examples that jeopardize model accuracy. Differential privacy and certified robustness are effective frameworks for combating these two threats respectively, as they each provide future-proof guarantees. However, we show that standard differentially private model training is insufficient for providing strong certified robustness guarantees. Indeed, combining differential privacy and certified robustness in a single system is non-trivial, leading previous works to introduce complex training schemes that lack flexibility. In this work, we present DP-CERT, a simple and effective method that achieves both privacy and robustness guarantees simultaneously by integrating randomized smoothing into standard differentially private model training. Compared to the leading prior work, DP-CERT gives up to a 2.5% increase in certified accuracy for the same differential privacy guarantee on CIFAR10. Through in-depth per-sample metric analysis, we find that larger certifiable radii correlate with smaller local Lipschitz constants, and show that DP-CERT effectively reduces Lipschitz constants compared to other differentially private training methods. The code is available at github.com/layer6ai-labs/dp-cert.