OpenRaiser/Intern-Atlas huggingface dataset:
Improving Order with Queues
Venue: arXiv cs.DS 2025
Year: 2025

Given a sequence of $n$ numbers and $k$ parallel First-in-First-Out (FIFO) queues, how close can one bring the sequence to sorted order? It is known that $k$ queues suffice to sort the sequence if the Longest Decreasing Subsequence (LDS) of the input sequence is at most $k$. But, what if the number of queues is too small for sorting completely? - We give a simple algorithm, based on Patience Sort, that reduces the LDS by $k - 1$. We also show, that the algorithm is optimal, i.e., for any $L > 0$ there exists a sequence of LDS $L$ such that the LDS cannot be reduced below $L - k + 1$ with $k$ queues. - Merging two sorted queues is at the core of Merge Sort. In contrast, two sequences of LDS two cannot always be merged into a sequence of LDS two. We characterize when it is possible and give an algorithm to decide whether it is possible. Merging into a sequence of LDS three is always possible. - A down-step in a sequence is an item immediately followed by a smaller item. We give an optimal algorithm for reducing the number of down-steps. The algorithm is online. Our research was inspired by an application in car manufacturing.
SuperTickets: Drawing Task-Agnostic Lottery Tickets from Supernets via Jointly Architecture Searching and Parameter Pruning
Venue: arXiv cs.CV 2025
Year: 2025

Neural architecture search (NAS) has demonstrated amazing success in searching for efficient deep neural networks (DNNs) from a given supernet. In parallel, the lottery ticket hypothesis has shown that DNNs contain small subnetworks that can be trained from scratch to achieve a comparable or higher accuracy than original DNNs. As such, it is currently a common practice to develop efficient DNNs via a pipeline of first search and then prune. Nevertheless, doing so often requires a search-train-prune-retrain process and thus prohibitive computational cost. In this paper, we discover for the first time that both efficient DNNs and their lottery subnetworks (i.e., lottery tickets) can be directly identified from a supernet, which we term as SuperTickets, via a two-in-one training scheme with jointly architecture searching and parameter pruning. Moreover, we develop a progressive and unified SuperTickets identification strategy that allows the connectivity of subnetworks to change during supernet training, achieving better accuracy and efficiency trade-offs than conventional sparse training. Finally, we evaluate whether such identified SuperTickets drawn from one task can transfer well to other tasks, validating their potential of handling multiple tasks simultaneously. Extensive experiments and ablation studies on three tasks and four benchmark datasets validate that our proposed SuperTickets achieve boosted accuracy and efficiency trade-offs than both typical NAS and pruning pipelines, regardless of having retraining or not. Codes and pretrained models are available at https://github.com/RICE-EIC/SuperTickets.
On the Need and Applicability of Causality for Fairness: A Unified Framework for AI Auditing and Legal Analysis
Venue: arXiv cs.LG 2025
Year: 2025

As Artificial Intelligence (AI) increasingly influences decisions in critical societal sectors, understanding and establishing causality becomes essential for evaluating the fairness of automated systems. This article explores the significance of causal reasoning in addressing algorithmic discrimination, emphasizing both legal and societal perspectives. By reviewing landmark cases and regulatory frameworks, particularly within the European Union, we illustrate the challenges inherent in proving causal claims when confronted with opaque AI decision-making processes. The discussion outlines practical obstacles and methodological limitations in applying causal inference to real-world fairness scenarios, proposing actionable solutions to enhance transparency, accountability, and fairness in algorithm-driven decisions.
A Closer Look into Transformer-Based Code Intelligence Through Code Transformation: Challenges and Opportunities
Venue: arXiv cs.SE 2025
Year: 2025

Transformer-based models have demonstrated state-of-the-art performance in many intelligent coding tasks such as code comment generation and code completion. Previous studies show that deep learning models are sensitive to the input variations, but few studies have systematically studied the robustness of Transformer under perturbed input code. In this work, we empirically study the effect of semantic-preserving code transformation on the performance of Transformer. Specifically, 24 and 27 code transformation strategies are implemented for two popular programming languages, Java and Python, respectively. For facilitating analysis, the strategies are grouped into five categories: block transformation, insertion/deletion transformation, grammatical statement transformation, grammatical token transformation, and identifier transformation. Experiments on three popular code intelligence tasks, including code completion, code summarization and code search, demonstrate insertion/deletion transformation and identifier transformation show the greatest impact on the performance of Transformer. Our results also suggest that Transformer based on abstract syntax trees (ASTs) shows more robust performance than the model based on only code sequence under most code transformations. Besides, the design of positional encoding can impact the robustness of Transformer under code transformation. Based on our findings, we distill some insights about the challenges and opportunities for Transformer-based code intelligence.
An extended version of the Ordered Median Tree Location Problem including appendices and detailed computational results
Venue: arXiv cs.DM 2025
Year: 2025

In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median hub location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
Contextual Active Model Selection
Venue: arXiv cs.LG 2025
Year: 2025

While training models and labeling data are resource-intensive, a wealth of pre-trained models and unlabeled data exists. To effectively utilize these resources, we present an approach to actively select pre-trained models while minimizing labeling costs. We frame this as an online contextual active model selection problem: At each round, the learner receives an unlabeled data point as a context. The objective is to adaptively select the best model to make a prediction while limiting label requests. To tackle this problem, we propose CAMS, a contextual active model selection algorithm that relies on two novel components: (1) a contextual model selection mechanism, which leverages context information to make informed decisions about which model is likely to perform best for a given context, and (2) an active query component, which strategically chooses when to request labels for data points, minimizing the overall labeling cost. We provide rigorous theoretical analysis for the regret and query complexity under both adversarial and stochastic settings. Furthermore, we demonstrate the effectiveness of our algorithm on a diverse collection of benchmark classification tasks. Notably, CAMS requires substantially less labeling effort (less than 10%) compared to existing methods on CIFAR10 and DRIFT benchmarks, while achieving similar or better accuracy. Our code is publicly available at: https://github.com/xuefeng-cs/Contextual-Active-Model-Selection.
Pseudo-Labeling Based Practical Semi-Supervised Meta-Training for Few-Shot Learning
Venue: arXiv cs.CV 2025
Year: 2025

Most existing few-shot learning (FSL) methods require a large amount of labeled data in meta-training, which is a major limit. To reduce the requirement of labels, a semi-supervised meta-training (SSMT) setting has been proposed for FSL, which includes only a few labeled samples and numbers of unlabeled samples in base classes. However, existing methods under this setting require class-aware sample selection from the unlabeled set, which violates the assumption of unlabeled set. In this paper, we propose a practical semi-supervised meta-training setting with truly unlabeled data to facilitate the applications of FSL in realistic scenarios. To better utilize both the labeled and truly unlabeled data, we propose a simple and effective meta-training framework, called pseudo-labeling based meta-learning (PLML). Firstly, we train a classifier via common semi-supervised learning (SSL) and use it to obtain the pseudo-labels of unlabeled data. Then we build few-shot tasks from labeled and pseudo-labeled data and design a novel finetuning method with feature smoothing and noise suppression to better learn the FSL model from noise labels. Surprisingly, through extensive experiments across two FSL datasets, we find that this simple meta-training framework effectively prevents the performance degradation of various FSL models under limited labeled data, and also significantly outperforms the state-of-the-art SSMT models. Besides, benefiting from meta-training, our method also improves two representative SSL algorithms as well.
Using Anomaly Detection to Detect Poisoning Attacks in Federated Learning Applications
Venue: arXiv cs.LG 2025
Year: 2025

Adversarial attacks such as poisoning attacks have attracted the attention of many machine learning researchers. Traditionally, poisoning attacks attempt to inject adversarial training data in order to manipulate the trained model. In federated learning (FL), data poisoning attacks can be generalized to model poisoning attacks, which cannot be detected by simpler methods due to the lack of access to local training data by the detector. State-of-the-art poisoning attack detection methods for FL have various weaknesses, e.g., the number of attackers has to be known or not high enough, working with i.i.d. data only, and high computational complexity. To overcome above weaknesses, we propose a novel framework for detecting poisoning attacks in FL, which employs a reference model based on a public dataset and an auditor model to detect malicious updates. We implemented a detector based on the proposed framework and using a one-class support vector machine (OC-SVM), which reaches the lowest possible computational complexity O(K) where K is the number of clients. We evaluated our detector's performance against state-of-the-art (SOTA) poisoning attacks for two typical applications of FL: electrocardiograph (ECG) classification and human activity recognition (HAR). Our experimental results validated the performance of our detector over other SOTA detection methods.
Science of science -- Citation models and research evaluation
Venue: arXiv cs.DL 2025
Year: 2025

Citations in science are being studied from several perspectives, among which approaches such as scientometrics and science of science. In this chapter I briefly review some of the literature on citations, citation distributions and models of citations. These citations feature prominently in another part of the literature which is dealing with research evaluation and the role of metrics and indicators in that process. Here I briefly review part of the discussion in research evaluation. This also touches on the subject of how citations relate to peer review. Finally, I conclude by trying to integrate the two literatures. The fundamental problem in research evaluation is that research quality is unobservable. This has consequences for conclusions that we can draw from quantitative studies of citations and citation models. The term ``indicators'' is a relevant concept in this context, which I try to clarify. Causality is important for properly understanding indicators, especially when indicators are used in practice: when we act on indicators, we enter causal territory. Even when an indicator might have been valid, through its very use, the consequences of its use may invalidate it. By combining citation models with proper causal reasoning and acknowledging the fundamental problem about unobservable research quality, we may hope to make progress.
Regret Minimization and Convergence to Equilibria in General-sum Markov Games
Venue: arXiv cs.LG 2025
Year: 2025

An abundance of recent impossibility results establish that regret minimization in Markov games with adversarial opponents is both statistically and computationally intractable. Nevertheless, none of these results preclude the possibility of regret minimization under the assumption that all parties adopt the same learning procedure. In this work, we present the first (to our knowledge) algorithm for learning in general-sum Markov games that provides sublinear regret guarantees when executed by all agents. The bounds we obtain are for swap regret, and thus, along the way, imply convergence to a correlated equilibrium. Our algorithm is decentralized, computationally efficient, and does not require any communication between agents. Our key observation is that online learning via policy optimization in Markov games essentially reduces to a form of weighted regret minimization, with unknown weights determined by the path length of the agents' policy sequence. Consequently, controlling the path length leads to weighted regret objectives for which sufficiently adaptive algorithms provide sublinear regret guarantees.
Transformer-based assignment decision network for multiple object tracking
Venue: arXiv cs.CV 2025
Year: 2025

Data association is a crucial component for any multiple object tracking (MOT) method that follows the tracking-by-detection paradigm. To generate complete trajectories such methods employ a data association process to establish assignments between detections and existing targets during each timestep. Recent data association approaches try to solve either a multi-dimensional linear assignment task or a network flow minimization problem or tackle it via multiple hypotheses tracking. However, during inference an optimization step that computes optimal assignments is required for every sequence frame inducing additional complexity to any given solution. To this end, in the context of this work we introduce Transformer-based Assignment Decision Network (TADN) that tackles data association without the need of any explicit optimization during inference. In particular, TADN can directly infer assignment pairs between detections and active targets in a single forward pass of the network. We have integrated TADN in a rather simple MOT framework, designed a novel training strategy for efficient end-to-end training and demonstrated the high potential of our approach for online visual tracking-by-detection MOT on several popular benchmarks, i.e. MOT17, MOT20 and UA-DETRAC. Our proposed approach demonstrates strong performance in most evaluation metrics despite its simple nature as a tracker lacking significant auxiliary components such as occlusion handling or re-identification. The implementation of our method is publicly available at https://github.com/psaltaath/tadn-mot.
Practical Guidelines for Ideology Detection Pipelines and Psychosocial Applications
Venue: arXiv cs.CY 2025
Year: 2025

Online ideology detection is crucial for downstream tasks, like countering ideologically motivated violent extremism and modeling opinion dynamics. However, two significant issues arise in practitioners' deployment. Firstly, gold-standard training data is prohibitively labor-intensive to collect and has limited reusability beyond its collection context (i.e., time, location, and platform). Secondly, to circumvent expense, researchers employ ideological signals (such as hashtags shared). Unfortunately, these signals' annotation requirements and context transferability are largely unknown, and the bias they induce remains unquantified. This study provides guidelines for practitioners requiring real-time detection of left, right, and extreme ideologies in large-scale online settings. We propose a framework for pipeline constructions, describing ideology signals by their associated labor and context transferability. We evaluate many constructions, quantifying the bias associated with signals and describing a pipeline that outperforms state-of-the-art methods ($0.95$ AUC ROC). We showcase the capabilities of our pipeline on five datasets containing more than 1.12 million users. We set out to investigate whether the findings in the psychosocial literature, developed for the offline environment, apply to the online setting. We evaluate at scale several psychosocial hypotheses that delineate ideologies concerning morality, grievance, nationalism, and dichotomous thinking. We find that right-wing ideologies use more vice-moral language, have more grievance-filled language, exhibit increased black-and-white thinking patterns, and have a greater association with national flags. This research empowers practitioners with guidelines for ideology detection, and case studies for its application, fostering a safer and better understood digital landscape.
SDWPF: A Dataset for Spatial Dynamic Wind Power Forecasting Challenge at KDD Cup 2022
Venue: arXiv cs.LG 2025
Year: 2025

The variability of wind power supply can present substantial challenges to incorporating wind power into a grid system. Thus, Wind Power Forecasting (WPF) has been widely recognized as one of the most critical issues in wind power integration and operation. There has been an explosion of studies on wind power forecasting problems in the past decades. Nevertheless, how to well handle the WPF problem is still challenging, since high prediction accuracy is always demanded to ensure grid stability and security of supply. We present a unique Spatial Dynamic Wind Power Forecasting dataset: SDWPF, which includes the spatial distribution of wind turbines, as well as the dynamic context factors. Whereas, most of the existing datasets have only a small number of wind turbines without knowing the locations and context information of wind turbines at a fine-grained time scale. By contrast, SDWPF provides the wind power data of 134 wind turbines from a wind farm over half a year with their relative positions and internal statuses. We use this dataset to launch the Baidu KDD Cup 2022 to examine the limit of current WPF solutions. The dataset is released at https://aistudio.baidu.com/aistudio/competition/detail/152/0/datasets.
Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization
Venue: arXiv cs.LG 2025
Year: 2025

We study the problem of finding a near-stationary point for smooth minimax optimization. The recently proposed extra anchored gradient (EAG) methods achieve the optimal convergence rate for the convex-concave minimax problem in the deterministic setting. However, the direct extension of EAG to stochastic optimization is not efficient. In this paper, we design a novel stochastic algorithm called Recursive Anchored IteratioN (RAIN). We show that the RAIN achieves near-optimal stochastic first-order oracle (SFO) complexity for stochastic minimax optimization in both convex-concave and strongly-convex-strongly-concave cases. In addition, we extend the idea of RAIN to solve structured nonconvex-nonconcave minimax problem and it also achieves near-optimal SFO complexity.
Fair Assortment Planning
Venue: arXiv cs.DS 2025
Year: 2025

Many online platforms, ranging from online retail stores to social media platforms, employ algorithms to optimize their offered assortment of items (e.g., products and contents). These algorithms often focus exclusively on achieving the platforms' objectives, highlighting items with the highest popularity or revenue. This approach, however, can compromise the equality of opportunities for the rest of the items, in turn leading to less content diversity and increased regulatory scrutiny for the platform. Motivated by this, we introduce and study a fair assortment planning problem that enforces equality of opportunities via pairwise fairness, which requires any two items to be offered similar outcomes. We show that the problem can be formulated as a linear program (LP), called (FAIR), that optimizes over the distribution of all feasible assortments. To find a near-optimal solution to (FAIR), we propose a framework based on the Ellipsoid method, which requires a polynomial-time separation oracle to the dual of the LP. We show that finding an optimal separation oracle to the dual problem is an NP-complete problem, and hence we propose a series of approximate separation oracles, which then result in a 1/2-approx. algorithm and an FPTAS for Problem (FAIR). The approximate separation oracles are designed by (i) showing the separation oracle to the dual of the LP is equivalent to solving an infinite series of parameterized knapsack problems, and (ii) leveraging the structure of knapsack problems. Finally, we perform numerical studies on both synthetic data and real-world MovieLens data, showcasing the effectiveness of our algorithms and providing insights into the platform's price of fairness.
Secret-Key Agreement Using Physical Identifiers for Degraded and Less Noisy Authentication Channels
Venue: arXiv cs.IT 2025
Year: 2025

Secret-key agreement based on biometric or physical identifiers is a promising security protocol for authenticating users or devices with small chips due to its lightweight security. In previous studies, the fundamental limits of such a protocol were analyzed, and the results showed that two auxiliary random variables were involved in the capacity region expressions. However, with these two auxiliary random variables, the complexity of computing the capacity regions may be prohibitively high. To deal with this problem, we explore classes of authentication channels that require only one auxiliary random variable in the expressions of the capacity regions. It is revealed that for the classes of degraded and less noisy authentication channels, a single auxiliary random variable is sufficient to express the capacity regions. As specific examples, we derive the closed-form expressions for binary and Gaussian sources. Also, numerical calculations for Gaussian sources are provided to show the trade-off between secret-key and privacy-leakage rates under a given storage rate, and to illustrate how the noise in the enrollment phase affects the capacity region.
Event-Triggered Time-Varying Bayesian Optimization
Venue: arXiv cs.LG 2025
Year: 2025

We consider the problem of sequentially optimizing a time-varying objective function using time-varying Bayesian optimization (TVBO). Current approaches to TVBO require prior knowledge of a constant rate of change to cope with stale data arising from time variations. However, in practice, the rate of change is usually unknown. We propose an event-triggered algorithm, ET-GP-UCB, that treats the optimization problem as static until it detects changes in the objective function and then resets the dataset. This allows the algorithm to adapt online to realized temporal changes without the need for exact prior knowledge. The event trigger is based on probabilistic uniform error bounds used in Gaussian process regression. We derive regret bounds for adaptive resets without exact prior knowledge of the temporal changes and show in numerical experiments that ET-GP-UCB outperforms competing GP-UCB algorithms on both synthetic and real-world data. The results demonstrate that ET-GP-UCB is readily applicable without extensive hyperparameter tuning.