OpenRaiser/Intern-Atlas huggingface dataset:
The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning
Venue: arXiv cs.LG 2024
Year: 2024

No free lunch theorems for supervised learning state that no learner can solve all problems or that all learners achieve exactly the same accuracy on average over a uniform distribution on learning problems. Accordingly, these theorems are often referenced in support of the notion that individual problems require specially tailored inductive biases. While virtually all uniformly sampled datasets have high complexity, real-world problems disproportionately generate low-complexity data, and we argue that neural network models share this same preference, formalized using Kolmogorov complexity. Notably, we show that architectures designed for a particular domain, such as computer vision, can compress datasets on a variety of seemingly unrelated domains. Our experiments show that pre-trained and even randomly initialized language models prefer to generate low-complexity sequences. Whereas no free lunch theorems seemingly indicate that individual problems require specialized learners, we explain how tasks that often require human intervention such as picking an appropriately sized model when labeled data is scarce or plentiful can be automated into a single learning algorithm. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models.
Optimizing Data-driven Causal Discovery Using Knowledge-guided Search
Venue: arXiv cs.AI 2024
Year: 2024

Learning causal relationships solely from observational data often fails to reveal the underlying causal mechanisms due to the vast search space of possible causal graphs, which can grow exponentially, especially for greedy algorithms using score-based approaches. Leveraging prior causal information, such as the presence or absence of causal edges, can help restrict and guide the score-based discovery process, leading to a more accurate search. In the healthcare domain, prior knowledge is abundant from sources like medical journals, electronic health records (EHRs), and clinical intervention outcomes. This study introduces a knowledge-guided causal structure search (KGS) approach that utilizes observational data and structural priors (such as causal edges) as constraints to learn the causal graph. KGS leverages prior edge information between variables, including the presence of a directed edge, the absence of an edge, and the presence of an undirected edge. We extensively evaluate KGS in multiple settings using synthetic and benchmark real-world datasets, as well as in a real-life healthcare application related to oxygen therapy treatment. To obtain causal priors, we use GPT-4 to retrieve relevant literature information. Our results show that structural priors of any type and amount enhance the search process, improving performance and optimizing causal discovery. This guided strategy ensures that the discovered edges align with established causal knowledge, enhancing the trustworthiness of findings while expediting the search process. It also enables a more focused exploration of causal mechanisms, potentially leading to more effective and personalized healthcare solutions.
Learning coordination through new actions
Venue: arXiv cs.GT 2024
Year: 2024

We provide a novel approach to achieving a desired outcome in a coordination game: the original 2x2 game is embedded in a 2x3 game where one of the players may use a third action. For a large set of payoff values only one of the Nash equilibria of the original 2x2 game is stable under replicator dynamics. We show that this Nash equilibrium is the ω-limit of all initial conditions in the interior of the state space for the modified 2x3 game. Thus, the existence of a third action for one of the players, although not used, allows both players to coordinate on one Nash equilibrium. This Nash equilibrium is the one preferred by, at least, the player with access to the new action. This approach deals with both coordination failure (players choose the payoff-dominant Nash equilibrium, if such a Nash equilibrium exists) and miscoordination (players do not use mixed strategies).
Continual Diffusion: Continual Customization of Text-to-Image Diffusion with C-LoRA
Venue: arXiv cs.CV 2024
Year: 2024

Recent works demonstrate a remarkable ability to customize text-to-image diffusion models while only providing a few example images. What happens if you try to customize such models using multiple, fine-grained concepts in a sequential (i.e., continual) manner? In our work, we show that recent state-of-the-art customization of text-to-image models suffer from catastrophic forgetting when new concepts arrive sequentially. Specifically, when adding a new concept, the ability to generate high quality images of past, similar concepts degrade. To circumvent this forgetting, we propose a new method, C-LoRA, composed of a continually self-regularized low-rank adaptation in cross attention layers of the popular Stable Diffusion model. Furthermore, we use customization prompts which do not include the word of the customized object (i.e., "person" for a human face dataset) and are initialized as completely random embeddings. Importantly, our method induces only marginal additional parameter costs and requires no storage of user data for replay. We show that C-LoRA not only outperforms several baselines for our proposed setting of text-to-image continual customization, which we refer to as Continual Diffusion, but that we achieve a new state-of-the-art in the well-established rehearsal-free continual learning setting for image classification. The high achieving performance of C-LoRA in two separate domains positions it as a compelling solution for a wide range of applications, and we believe it has significant potential for practical impact. Project page: https://jamessealesmith.github.io/continual-diffusion/
Choose Your Weapon: Survival Strategies for Depressed AI Academics
Venue: arXiv cs.OH 2024
Year: 2024

Are you an AI researcher at an academic institution? Are you anxious you are not coping with the current pace of AI advancements? Do you feel you have no (or very limited) access to the computational and human resources required for an AI research breakthrough? You are not alone; we feel the same way. A growing number of AI academics can no longer find the means and resources to compete at a global scale. This is a somewhat recent phenomenon, but an accelerating one, with private actors investing enormous compute resources into cutting edge AI research. Here, we discuss what you can do to stay competitive while remaining an academic. We also briefly discuss what universities and the private sector could do improve the situation, if they are so inclined. This is not an exhaustive list of strategies, and you may not agree with all of them, but it serves to start a discussion.
ASR: Attention-alike Structural Re-parameterization
Venue: arXiv cs.CV 2024
Year: 2024

The structural re-parameterization (SRP) technique is a novel deep learning technique that achieves interconversion between different network architectures through equivalent parameter transformations. This technique enables the mitigation of the extra costs for performance improvement during training, such as parameter size and inference time, through these transformations during inference, and therefore SRP has great potential for industrial and practical applications. The existing SRP methods have successfully considered many commonly used architectures, such as normalizations, pooling methods, and multi-branch convolution. However, the widely used attention modules which drastically slow inference speed cannot be directly implemented by SRP due to these modules usually act on the backbone network in a multiplicative manner and the modules' output is input-dependent during inference, which limits the application scenarios of SRP. In this paper, we conduct extensive experiments from a statistical perspective and discover an interesting phenomenon Stripe Observation, which reveals that channel attention values quickly approach some constant vectors during training. This observation inspires us to propose a simple-yet-effective attention-alike structural re-parameterization (ASR) that allows us to achieve SRP for a given network while enjoying the effectiveness of the attention mechanism. Extensive experiments conducted on several standard benchmarks demonstrate the effectiveness of ASR in generally improving the performance of existing backbone networks, attention modules, and SRP methods without any elaborated model crafting. We also analyze the limitations and provide experimental and theoretical evidence for the strong robustness of the proposed ASR.
In-Distribution and Out-of-Distribution Self-supervised ECG Representation Learning for Arrhythmia Detection
Venue: arXiv cs.LG 2024
Year: 2024

This paper presents a systematic investigation into the effectiveness of Self-Supervised Learning (SSL) methods for Electrocardiogram (ECG) arrhythmia detection. We begin by conducting a novel analysis of the data distributions on three popular ECG-based arrhythmia datasets: PTB-XL, Chapman, and Ribeiro. To the best of our knowledge, our study is the first to quantitatively explore and characterize these distributions in the area. We then perform a comprehensive set of experiments using different augmentations and parameters to evaluate the effectiveness of various SSL methods, namely SimCRL, BYOL, and SwAV, for ECG representation learning, where we observe the best performance achieved by SwAV. Furthermore, our analysis shows that SSL methods achieve highly competitive results to those achieved by supervised state-of-the-art methods. To further assess the performance of these methods on both In-Distribution (ID) and Out-of-Distribution (OOD) ECG data, we conduct cross-dataset training and testing experiments. Our comprehensive experiments show almost identical results when comparing ID and OOD schemes, indicating that SSL techniques can learn highly effective representations that generalize well across different OOD datasets. This finding can have major implications for ECG-based arrhythmia detection. Lastly, to further analyze our results, we perform detailed per-disease studies on the performance of the SSL methods on the three datasets.
Certified Zeroth-order Black-Box Defense with Robust UNet Denoiser
Venue: arXiv cs.CV 2024
Year: 2024

Certified defense methods against adversarial perturbations have been recently investigated in the black-box setting with a zeroth-order (ZO) perspective. However, these methods suffer from high model variance with low performance on high-dimensional datasets due to the ineffective design of the denoiser and are limited in their utilization of ZO techniques. To this end, we propose a certified ZO preprocessing technique for removing adversarial perturbations from the attacked image in the black-box setting using only model queries. We propose a robust UNet denoiser (RDUNet) that ensures the robustness of black-box models trained on high-dimensional datasets. We propose a novel black-box denoised smoothing (DS) defense mechanism, ZO-RUDS, by prepending our RDUNet to the black-box model, ensuring black-box defense. We further propose ZO-AE-RUDS in which RDUNet followed by autoencoder (AE) is prepended to the black-box model. We perform extensive experiments on four classification datasets, CIFAR-10, CIFAR-10, Tiny Imagenet, STL-10, and the MNIST dataset for image reconstruction tasks. Our proposed defense methods ZO-RUDS and ZO-AE-RUDS beat SOTA with a huge margin of $35\%$ and $9\%$, for low dimensional (CIFAR-10) and with a margin of $20.61\%$ and $23.51\%$ for high-dimensional (STL-10) datasets, respectively.
nanoLM: an Affordable LLM Pre-training Benchmark via Accurate Loss Prediction across Scales
Venue: arXiv cs.CL 2024
Year: 2024

As language models scale up, it becomes increasingly expensive to verify research ideas because conclusions on small models do not trivially transfer to large ones. A possible solution is to establish a generic system that accurately predicts certain metrics for large models without training them. Existing scaling laws require hyperparameter search on the largest models, limiting their predicative capability. In this paper, we present an approach (namely μScaling) to predict the pre-training loss, based on our observations that Maximal Update Parametrization (μP) enables accurate fitting of scaling laws close to common loss basins in hyperparameter space. With μScaling, different model designs can be compared on large scales by training only their smaller counterparts. Further, we introduce nanoLM: an affordable LLM pre-training benchmark that facilitates this new research paradigm. With around 14% of the one-time pre-training cost, we can accurately forecast the loss for models up to 52B. Our goal with nanoLM is to empower researchers with limited resources to reach meaningful conclusions on large models. We also aspire for our benchmark to serve as a bridge between the academic community and the industry. Code for μScaling is available at https://github.com/cofe-ai/Mu-scaling. Code for nanoLLM will be available later.
Intelligent Reflecting Surface Aided Wireless Communication Systems: Joint Location and Passive Beamforming Design
Venue: arXiv cs.IT 2024
Year: 2024

Intelligent reflecting surface (IRS) has been widely studied in recent years, it has emerged as a new technology which can reflect the incident signal by intelligently configuring the reflection elements, thus changing the signal propagation environment, enhancing the signals users desire and suppressing the interference between users. In this paper, we study an IRS aided multi-users wireless communication where the base station (BS) sends a variety of signals, each user receives desired signals. In order to guarantee the fairness of wireless communications, we need to maximize the minimum rates of users, subject to the power constraint of BS and the phase constraint of IRS. Prior works on IRS mainly consider optimizing BS beamforming and IRS passive beamforming, this paper also aims to optimize the IRS location. The considered problem is shown to be non-convex, we decompose the problem into two subproblems, transforming the two subproblems into a lower bound problem and using alternating optimization (AO) and successive convex approximation (SCA) to solve them, respectively. Finally, the two subproblems are optimized alternately to make the objective function value converge in an acceptable range. Simulation results verify the convergence results of our proposed algorithm, and the performance improvement compared with the benchmark scheme in wireless communication system.
Unifying Privacy Measures via Maximal $(α,β)$-Leakage (M$α$beL)
Venue: arXiv cs.IT 2024
Year: 2024

We introduce a family of information leakage measures called maximal $(α,β)$-leakage (M$α$beL), parameterized by real numbers $α$ and $β$ greater than or equal to 1. The measure is formalized via an operational definition involving an adversary guessing an unknown (randomized) function of the data given the released data. We obtain a simplified computable expression for the measure and show that it satisfies several basic properties such as monotonicity in $β$ for a fixed $α$, non-negativity, data processing inequalities, and additivity over independent releases. We highlight the relevance of this family by showing that it bridges several known leakage measures, including maximal $α$-leakage $(β=1)$, maximal leakage $(α=\infty,β=1)$, local differential privacy (LDP) $(α=\infty,β=\infty)$, and local Renyi differential privacy (LRDP) $(α=β)$, thereby giving an operational interpretation to local Renyi differential privacy. We also study a conditional version of M$α$beL on leveraging which we recover differential privacy and Renyi differential privacy. A new variant of LRDP, which we call maximal Renyi leakage, appears as a special case of M$α$beL for $α=\infty$ that smoothly tunes between maximal leakage ($β=1$) and LDP ($β=\infty$). Finally, we show that a vector form of the maximal Renyi leakage relaxes differential privacy under Gaussian and Laplacian mechanisms.
Region-Enhanced Feature Learning for Scene Semantic Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Semantic segmentation in complex scenes relies not only on object appearance but also on object location and the surrounding environment. Nonetheless, it is difficult to model long-range context in the format of pairwise point correlations due to the huge computational cost for large-scale point clouds. In this paper, we propose using regions as the intermediate representation of point clouds instead of fine-grained points or voxels to reduce the computational burden. We introduce a novel Region-Enhanced Feature Learning Network (REFL-Net) that leverages region correlations to enhance point feature learning. We design a region-based feature enhancement (RFE) module, which consists of a Semantic-Spatial Region Extraction stage and a Region Dependency Modeling stage. In the first stage, the input points are grouped into a set of regions based on their semantic and spatial proximity. In the second stage, we explore inter-region semantic and spatial relationships by employing a self-attention block on region features and then fuse point features with the region features to obtain more discriminative representations. Our proposed RFE module is plug-and-play and can be integrated with common semantic segmentation backbones. We conduct extensive experiments on ScanNetV2 and S3DIS datasets and evaluate our RFE module with different segmentation backbones. Our REFL-Net achieves 1.8% mIoU gain on ScanNetV2 and 1.7% mIoU gain on S3DIS with negligible computational cost compared with backbone models. Both quantitative and qualitative results show the powerful long-range context modeling ability and strong generalization ability of our REFL-Net.
Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
Venue: arXiv cs.CC 2024
Year: 2024

In the parameterized $k$-clique problem, or $k$-Clique for short, we are given a graph $G$ and a parameter $k\ge 1$. The goal is to decide whether there exist $k$ vertices in $G$ that induce a complete subgraph (i.e., a $k$-clique). This problem plays a central role in the theory of parameterized intractability as one of the first W[1]-complete problems. Existing research has shown that even an FPT-approximation algorithm for $k$-Clique with arbitrary ratio does not exist, assuming the Gap-Exponential-Time Hypothesis (Gap-ETH) [Chalermsook et al., FOCS'17 and SICOMP]. However, whether this inapproximability result can be based on the standard assumption of $\mathrm{W} 1\ne \mathrm{FPT}$ remains unclear. The recent breakthrough of Bingkai Lin [STOC'21] and subsequent works by Karthik C.S. and Khot [CCC'22], and by Lin, Ren, Sun Wang [ICALP'22] give a technique that bypasses Gap-ETH, thus leading to the inapproximability ratio of $O(1)$ and $k^{o(1)}$ under $\mathrm{W}[1]$-hardness (the first two) and ETH (for the latter one). All the work along this line follows the framework developed by Lin, which starts from the $k$-vector-sum problem and requires some involved algebraic techniques. This paper presents an alternative framework for proving the W[1]-hardness of the $k^{o(1)}$-FPT-inapproximability of $k$-Clique. Using this framework, we obtain a gap-producing self-reduction of $k$-Clique without any intermediate algebraic problem. More precisely, we reduce from $(k,k-1)$-Gap Clique to $(q^k, q^{k-1})$-Gap Clique, for any function $q$ depending only on the parameter $k$, thus implying the $k^{o(1)}$-inapproximability result when $q$ is sufficiently large. Our proof is relatively simple and mostly combinatorial. At the core of our construction is a novel encoding of $k$-element subset stemming from the theory of "network coding" and a "Sidon set" representation of a graph.
MR-Scout: Automated Synthesis of Metamorphic Relations from Existing Test Cases
Venue: arXiv cs.SE 2024
Year: 2024

Metamorphic Testing (MT) alleviates the oracle problem by defining oracles based on metamorphic relations (MRs), that govern multiple related inputs and their outputs. However, designing MRs is challenging, as it requires domain-specific knowledge. This hinders the widespread adoption of MT. We observe that developer-written test cases can embed domain knowledge that encodes MRs. Such encoded MRs could be synthesized for testing not only their original programs but also other programs that share similar functionalities. In this paper, we propose MR-Scout to automatically synthesize MRs from test cases in open-source software (OSS) projects. MR-Scout first discovers MR-encoded test cases (MTCs), and then synthesizes the encoded MRs into parameterized methods (called codified MRs), and filters out MRs that demonstrate poor quality for new test case generation. MR-Scout discovered over 11,000 MTCs from 701 OSS projects. Experimental results show that over 97% of codified MRs are of high quality for automated test case generation, demonstrating the practical applicability of MR-Scout. Furthermore, codified-MRs-based tests effectively enhance the test adequacy of programs with developer-written tests, leading to 13.52% and 9.42% increases in line coverage and mutation score, respectively. Our qualitative study shows that 55.76% to 76.92% of codified MRs are easily comprehensible for developers.
Self-collaboration Code Generation via ChatGPT
Venue: arXiv cs.SE 2024
Year: 2024

Although Large Language Models (LLMs) have demonstrated remarkable code-generation ability, they still struggle with complex tasks. In real-world software development, humans usually tackle complex tasks through collaborative teamwork, a strategy that significantly controls development complexity and enhances software quality. Inspired by this, we present a self-collaboration framework for code generation employing LLMs, exemplified by ChatGPT. Specifically, through role instructions, 1) Multiple LLM agents act as distinct `experts', each responsible for a specific subtask within a complex task; 2) Specify the way to collaborate and interact, so that different roles form a virtual team to facilitate each other's work, ultimately the virtual team addresses code generation tasks collaboratively without the need for human intervention. To effectively organize and manage this virtual team, we incorporate software-development methodology into the framework. Thus, we assemble an elementary team consisting of three LLM roles (i.e., analyst, coder, and tester) responsible for software development's analysis, coding, and testing stages. We conduct comprehensive experiments on various code-generation benchmarks. Experimental results indicate that self-collaboration code generation relatively improves 29.9%-47.1% Pass@1 compared to the base LLM agent. Moreover, we showcase that self-collaboration could potentially enable LLMs to efficiently handle complex repository-level tasks that are not readily solved by the single LLM agent.