OpenRaiser/Intern-Atlas huggingface dataset:
Size-varying reversible causal graph dynamics
Venue: arXiv cs.DM 2025
Year: 2025

Consider a network that evolves according to a reversible, nearest neighbours dynamics. Is the dynamics allowed to vary the size of the network? On the one hand it seems that, being the principal carriers of information, nodes cannot be destroyed without jeopardising bijectivity. On the other hand, there are plenty of bijective functions from the set of graphs to the set of graphs that are non-vertex-preserving. The question has been settled negatively -- for three different reasons. Yet, in this paper we do obtain reversible local node creation/destruction -- in three relaxed settings, whose equivalence we prove for robustness. We motivate our work both by theoretical computer science considerations (reversible computing, cellular automata extensions) and theoretical physics concerns (basic formalisms towards discrete quantum gravity).
Large Language Models for Few-Shot Named Entity Recognition
Venue: arXiv cs.CL 2025
Year: 2025

Named entity recognition (NER) is a fundamental task in numerous downstream applications. Recently, researchers have employed pre-trained language models (PLMs) and large language models (LLMs) to address this task. However, fully leveraging the capabilities of PLMs and LLMs with minimal human effort remains challenging. In this paper, we propose GPT4NER, a method that prompts LLMs to resolve the few-shot NER task. GPT4NER constructs effective prompts using three key components: entity definition, few-shot examples, and chain-of-thought. By prompting LLMs with these effective prompts, GPT4NER transforms few-shot NER, which is traditionally considered as a sequence-labeling problem, into a sequence-generation problem. We conduct experiments on two benchmark datasets, CoNLL2003 and OntoNotes5.0, and compare the performance of GPT4NER to representative state-of-the-art models in both few-shot and fully supervised settings. Experimental results demonstrate that GPT4NER achieves the $F_1$ of 83.15\% on CoNLL2003 and 70.37\% on OntoNotes5.0, significantly outperforming few-shot baselines by an average margin of 7 points. Compared to fully-supervised baselines, GPT4NER achieves 87.9\% of their best performance on CoNLL2003 and 76.4\% of their best performance on OntoNotes5.0. We also utilize a relaxed-match metric for evaluation and report performance in the sub-task of named entity extraction (NEE), and experiments demonstrate their usefulness to help better understand model behaviors in the NER task.
RelDenClu: A Relative Density based Biclustering Method for identifying non-linear feature relations
Venue: arXiv cs.CV 2025
Year: 2025

The existing biclustering algorithms for finding feature relation based biclusters often depend on assumptions like monotonicity or linearity. Though a few algorithms overcome this problem by using density-based methods, they tend to miss out many biclusters because they use global criteria for identifying dense regions. The proposed method, RelDenClu uses the local variations in marginal and joint densities for each pair of features to find the subset of observations, which forms the bases of the relation between them. It then finds the set of features connected by a common set of observations, resulting in a bicluster. To show the effectiveness of the proposed methodology, experimentation has been carried out on fifteen types of simulated datasets. Further, it has been applied to six real-life datasets. For three of these real-life datasets, the proposed method is used for unsupervised learning, while for other three real-life datasets it is used as an aid to supervised learning. For all the datasets the performance of the proposed method is compared with that of seven different state-of-the-art algorithms and the proposed algorithm is seen to produce better results. The efficacy of proposed algorithm is also seen by its use on COVID-19 dataset for identifying some features (genetic, demographics and others) that are likely to affect the spread of COVID-19.
A Large-scale Multimodal Study for Predicting Mortality Risk Using Minimal and Low Parameter Models and Separable Risk Assessment
Venue: arXiv cs.LG 2025
Year: 2025

The majority of biomedical studies use limited datasets that may not generalize over large heterogeneous datasets that have been collected over several decades. The current paper develops and validates several multimodal models that can predict 1-year mortality based on a massive clinical dataset. Our focus on predicting 1-year mortality can provide a sense of urgency to the patients. Using the largest dataset of its kind, the paper considers the development and validation of multimodal models based on 25,137,015 videos associated with 699,822 echocardiography studies from 316,125 patients, and 2,922,990 8-lead electrocardiogram (ECG) traces from 631,353 patients. Our models allow us to assess the contribution of individual factors and modalities to the overall risk. Our approach allows us to develop extremely low-parameter models that use optimized feature selection based on feature importance. Based on available clinical information, we construct a family of models that are made available in the DISIML package. Overall, performance ranges from an AUC of 0.72 with just ten parameters to an AUC of 0.89 with under 105k for the full multimodal model. The proposed approach represents a modular neural network framework that can provide insights into global risk trends and guide therapies for reducing mortality risk.
Efficient Many-To-Many Matching of Points with Demands in One Dimension
Venue: arXiv cs.CG 2025
Year: 2025

Given two point sets $S$ and $T$, the minimum-cost many-to-many matching with demands (MMD) problem is the problem of finding a minimum-cost many-to-many matching between $S$ and $T$ such that each point of $S$ (respectively $T$) is matched to at least a given number of the points of $T$ (respectively $S$). We propose the first $O\left(n^2\right)$-time algorithm for computing a one dimensional MMD (OMMD) of minimum cost between $S$ and $T$, where $\left|S\right|+\left|T\right|=n$. In an OMMD problem, the input point sets $S$ and $T$ lie on the real line and the cost of matching a point to another point equals the Euclidean distance between the two points. We also study a generalized version of the MMD problem, the many-to-many matching with demands and capacities (MMDC) problem, that in which each point has a limited capacity in addition to a demand. We give the first $O(n^2)$-time algorithm for the minimum-cost one dimensional MMDC (OMMDC) problem.
Improving Neural Question Generation using World Knowledge
Venue: arXiv cs.CL 2025
Year: 2025

In this paper, we propose a method for incorporating world knowledge (linked entities and fine-grained entity types) into a neural question generation model. This world knowledge helps to encode additional information related to the entities present in the passage required to generate human-like questions. We evaluate our models on both SQuAD and MS MARCO to demonstrate the usefulness of the world knowledge features. The proposed world knowledge enriched question generation model is able to outperform the vanilla neural question generation model by 1.37 and 1.59 absolute BLEU 4 score on SQuAD and MS MARCO test dataset respectively.
Learning Concepts Definable in First-Order Logic with Counting
Venue: arXiv cs.LO 2025
Year: 2025

We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Turán (TOCS 2004). It is known (Grohe and Ritzert, LICS 2017) that classifiers definable in first-order logic over structures of polylogarithmic degree can be learned in sublinear time, where the degree of the structure and the running time are measured in terms of the size of the structure. We generalise the results to the first-order logic with counting FOCN, which was introduced by Kuske and Schweikardt (LICS 2017) as an expressive logic generalising various other counting logics. Specifically, we prove that classifiers definable in FOCN over classes of structures of polylogarithmic degree can be consistently learned in sublinear time. This can be seen as a first step towards extending the learning framework to include numerical aspects of machine learning. We extend the result to agnostic probably approximately correct (PAC) learning for classes of structures of degree at most $(\log \log n)^c$ for some constant $c$. Moreover, we show that bounding the degree is crucial to obtain sublinear-time learning algorithms. That is, we prove that, for structures of unbounded degree, learning is not possible in sublinear time, even for classifiers definable in plain first-order logic.
Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks
Venue: arXiv cs.LG 2025
Year: 2025

(Frankle & Carbin, 2019) shows that there exist winning tickets (small but critical subnetworks) for dense, randomly initialized networks, that can be trained alone to achieve comparable accuracies to the latter in a similar number of iterations. However, the identification of these winning tickets still requires the costly train-prune-retrain process, limiting their practical benefits. In this paper, we discover for the first time that the winning tickets can be identified at the very early training stage, which we term as early-bird (EB) tickets, via low-cost training schemes (e.g., early stopping and low-precision training) at large learning rates. Our finding of EB tickets is consistent with recently reported observations that the key connectivity patterns of neural networks emerge early. Furthermore, we propose a mask distance metric that can be used to identify EB tickets with low computational overhead, without needing to know the true winning tickets that emerge after the full training. Finally, we leverage the existence of EB tickets and the proposed mask distance to develop efficient training methods, which are achieved by first identifying EB tickets via low-cost schemes, and then continuing to train merely the EB tickets towards the target accuracy. Experiments based on various deep networks and datasets validate: 1) the existence of EB tickets, and the effectiveness of mask distance in efficiently identifying them; and 2) that the proposed efficient training via EB tickets can achieve up to 4.7x energy savings while maintaining comparable or even better accuracy, demonstrating a promising and easily adopted method for tackling cost-prohibitive deep network training. Code available at https://github.com/RICE-EIC/Early-Bird-Tickets.
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Venue: arXiv cs.DS 2025
Year: 2025

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms improve the best known running times of parameterized approximation algorithms for Vertex Cover and $3$-Hitting Set for a wide range of approximation ratios. One notable example is a simple parameterized random $1.5$-approximation algorithm for Vertex Cover, whose running time of $\tilde{O}(1.01657^k)$ substantially improves the best known runnning time of $\tilde{O}(1.0883^k)$ [Brankovic and Fernau, 2013]. For $3$-Hitting Set we present a parameterized random $2$-approximation algorithm with running time of $\tilde{O}(1.0659^k)$, improving the best known $\tilde{O}(1.29^k)$ algorithm of [Brankovic and Fernau, 2012]. The running times of our algorithms are derived from an asymptotic analysis of a wide class of two-variable recurrence relations of the form: $$p(b,k) = \min_{1\leq j \leq N} \sum_{i=1}^{r_j} \barγ_i^j \cdot p(b-\bar{b}^j_i, k-\bar{k}_i^j),$$ where $\bar{b}^j$ and $\bar{k}^j$ are vectors of natural numbers, and $\barγ^j$ is a probability distribution over $r_j$ elements, for $1\leq j \leq N$. Our main theorem asserts that for any $α>0$, $$\lim_{k \rightarrow \infty } \frac{1}{k} \cdot \ln p(\lfloor{αk}\rfloor,k) = -\max_{1\leq j \leq N} M_j,$$ where $M_j$ depends only on $α$, $\barγ^j$, $\bar{b}^j$ and $\bar{k}^j$, and can be efficiently calculated by solving a simple numerical optimization problem. To prove the theorem we show an equivalence between the recurrence and a stochastic process. We analyze this process using the {\em method of types}, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper.
Counterfactual Vision-and-Language Navigation via Adversarial Path Sampling
Venue: arXiv cs.CV 2025
Year: 2025

Vision-and-Language Navigation (VLN) is a task where agents must decide how to move through a 3D environment to reach a goal by grounding natural language instructions to the visual surroundings. One of the problems of the VLN task is data scarcity since it is difficult to collect enough navigation paths with human-annotated instructions for interactive environments. In this paper, we explore the use of counterfactual thinking as a human-inspired data augmentation method that results in robust models. Counterfactual thinking is a concept that describes the human propensity to create possible alternatives to life events that have already occurred. We propose an adversarial-driven counterfactual reasoning model that can consider effective conditions instead of low-quality augmented data. In particular, we present a model-agnostic adversarial path sampler (APS) that learns to sample challenging paths that force the navigator to improve based on the navigation performance. APS also serves to do pre-exploration of unseen environments to strengthen the model's ability to generalize. We evaluate the influence of APS on the performance of different VLN baseline models using the room-to-room dataset (R2R). The results show that the adversarial training process with our proposed APS benefits VLN models under both seen and unseen environments. And the pre-exploration process can further gain additional improvements under unseen environments.
Mixability of Integral Losses: a Key to Efficient Online Aggregation of Functional and Probabilistic Forecasts
Venue: arXiv cs.LG 2025
Year: 2025

In this paper we extend the setting of the online prediction with expert advice to function-valued forecasts. At each step of the online game several experts predict a function, and the learner has to efficiently aggregate these functional forecasts into a single forecast. We adapt basic mixable (and exponentially concave) loss functions to compare functional predictions and prove that these adaptations are also mixable (exp-concave). We call this phenomenon mixability (exp-concavity) of integral loss functions. As an application of our main result, we prove that various loss functions used for probabilistic forecasting are mixable (exp-concave). The considered losses include Sliced Continuous Ranked Probability Score, Energy-Based Distance, Optimal Transport Costs and Sliced Wasserstein-2 distance, Beta-2 and Kullback-Leibler divergences, Characteristic function and Maximum Mean Discrepancies.
A Modern Introduction to Online Learning
Venue: arXiv cs.LG 2025
Year: 2025

In this monograph, I introduce the basic concepts of Online Learning through a modern view of Online Convex Optimization. Here, online learning refers to the framework of regret minimization under worst-case assumptions. I present first-order and second-order algorithms for online learning with convex losses, in Euclidean and non-Euclidean settings. All the algorithms are clearly presented as instantiation of Online Mirror Descent or Follow-The-Regularized-Leader and their variants. Particular attention is given to the issue of tuning the parameters of the algorithms and learning in unbounded domains, through adaptive and parameter-free online learning algorithms. Non-convex losses are dealt through convex surrogate losses and through randomization. The bandit setting is also briefly discussed, touching on the problem of adversarial and stochastic multi-armed bandits. These notes do not require prior knowledge of convex analysis and all the required mathematical tools are rigorously explained. Moreover, all the included proofs have been carefully chosen to be as simple and as short as possible.
Conformal e-prediction
Venue: arXiv cs.LG 2025
Year: 2025

This paper discusses a counterpart of conformal prediction for e-values, conformal e-prediction. Conformal e-prediction is conceptually simpler and had been developed in the 1990s as a precursor of conformal prediction. When conformal prediction emerged as result of replacing e-values by p-values, it seemed to have important advantages over conformal e-prediction without obvious disadvantages. This paper re-examines relations between conformal prediction and conformal e-prediction systematically from a modern perspective. Conformal e-prediction has advantages of its own, such as the ease of designing conditional conformal e-predictors and the guaranteed validity of cross-conformal e-predictors (whereas for cross-conformal predictors validity is only an empirical fact and can be broken with excessive randomization). Even where conformal prediction has clear advantages, conformal e-prediction can often emulate those advantages, more or less successfully.
DropCluster: A structured dropout for convolutional networks
Venue: arXiv cs.LG 2025
Year: 2025

Dropout as a common regularizer to prevent overfitting in deep neural networks has been less effective in convolutional layers than in fully connected layers. This is because Dropout drops features randomly, without considering local structure. When features are spatially correlated, as in the case of convolutional layers, information from the dropped features can still propagate to subsequent layers via neighboring features. To address this problem, structured forms of Dropout have been proposed. A drawback of these methods is that they do not adapt to the data. In this work, we leverage the structure in the outputs of convolutional layers and introduce a novel structured regularization method named DropCluster. Our approach clusters features in convolutional layers, and drops the resulting clusters randomly during training iterations. Experiments on CIFAR-10/100, SVHN, and APPA-REAL datasets demonstrate that our approach is effective and controls overfitting better than other approaches.
Robust Policy Search for Robot Navigation
Venue: arXiv cs.LG 2025
Year: 2025

Complex robot navigation and control problems can be framed as policy search problems. However, interactive learning in uncertain environments can be expensive, requiring the use of data-efficient methods. Bayesian optimization is an efficient nonlinear optimization method where queries are carefully selected to gather information about the optimum location. This is achieved by a surrogate model, which encodes past information, and the acquisition function for query selection. Bayesian optimization can be very sensitive to uncertainty in the input data or prior assumptions. In this work, we incorporate both robust optimization and statistical robustness, showing that both types of robustness are synergistic. For robust optimization we use an improved version of unscented Bayesian optimization which provides safe and repeatable policies in the presence of policy uncertainty. We also provide new theoretical insights. For statistical robustness, we use an adaptive surrogate model and we introduce the Boltzmann selection as a stochastic acquisition method to have convergence guarantees and improved performance even with surrogate modeling errors. We present results in several optimization benchmarks and robot tasks.
Notes on Randomized Algorithms
Venue: arXiv cs.DS 2025
Year: 2025

Lecture notes for the Yale Computer Science course CPSC 4690/5690 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lovász Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.
Unmanned Surface Vehicle Path Planning from the Perspective of Multi-Modality Constraints: A Comprehensive Analysis
Venue: arXiv cs.RO 2025
Year: 2025

The essence of the path planning problems is multi-modality constraint. However, most of the current literature has not mentioned this issue. This paper introduces the research progress of path planning based on the multi-modality constraint. The path planning of multi-modality constraint research can be classified into three stages in terms of its basic ingredients (such as shape, kinematics and dynamics et al.): Route Planning, Trajectory Planning and Motion Planning. It then reviews the research methods and classical algorithms, especially those applied to the Unmanned Surface Vehicle (USV) in every stage. Finally, the paper points out some existing problems in every stage and suggestions for future research.
Bounds on the revenue gap of linear posted pricing for selling a divisible item
Venue: arXiv cs.GT 2025
Year: 2025

Selling a perfectly divisible item to potential buyers is a fundamental task with apparent applications to pricing communication bandwidth and cloud computing services. Surprisingly, despite the rich literature on single-item auctions, revenue maximization when selling a divisible item is a much less understood objective. We introduce a Bayesian setting, in which the potential buyers have concave valuation functions (defined for each possible item fraction) that are randomly chosen according to known probability distributions. Extending the sequential posted pricing paradigm, we focus on mechanisms that use linear pricing, charging a fixed price for the whole item and proportional prices for fractions of it. Our goal is to understand the power of such mechanisms by bounding the gap between the expected revenue that can be achieved by the best among these mechanisms and the maximum expected revenue that can be achieved by any mechanism assuming mild restrictions on the behavior of the buyers. Under regularity assumptions for the probability distributions, we show that this revenue gap depends only logarithmically on a natural parameter characterizing the valuation functions and the number of agents. Our results follow by bounding the objective value of a mathematical program that maximizes the ex-ante relaxation of optimal revenue under linear pricing revenue constraints.