OpenRaiser/Intern-Atlas huggingface dataset:
The foundations of cost-sensitive causal classification
Venue: arXiv cs.LG 2025
Year: 2025

Classification is a well-studied machine learning task which concerns the assignment of instances to a set of outcomes. Classification models support the optimization of managerial decision-making across a variety of operational business processes. For instance, customer churn prediction models are adopted to increase the efficiency of retention campaigns by optimizing the selection of customers that are to be targeted. Cost-sensitive and causal classification methods have independently been proposed to improve the performance of classification models. The former considers the benefits and costs of correct and incorrect classifications, such as the benefit of a retained customer, whereas the latter estimates the causal effect of an action, such as a retention campaign, on the outcome of interest. This study integrates cost-sensitive and causal classification by elaborating a unifying evaluation framework. The framework encompasses a range of existing and novel performance measures for evaluating both causal and conventional classification models in a cost-sensitive as well as a cost-insensitive manner. We proof that conventional classification is a specific case of causal classification in terms of a range of performance measures when the number of actions is equal to one. The framework is shown to instantiate to application-specific cost-sensitive performance measures that have been recently proposed for evaluating customer retention and response uplift models, and allows to maximize profitability when adopting a causal classification model for optimizing decision-making. The proposed framework paves the way toward the development of cost-sensitive causal learning methods and opens a range of opportunities for improving data-driven business decision-making.
Learning to Play Two-Player Perfect-Information Games without Knowledge
Venue: arXiv cs.AI 2025
Year: 2025

In this paper, several techniques for learning game state evaluation functions by reinforcement are proposed. The first is a generalization of tree bootstrapping (tree learning): it is adapted to the context of reinforcement learning without knowledge based on non-linear functions. With this technique, no information is lost during the reinforcement learning process. The second is a modification of minimax with unbounded depth extending the best sequences of actions to the terminal states. This modified search is intended to be used during the learning process. The third is to replace the classic gain of a game (+1 / -1) with a reinforcement heuristic. We study particular reinforcement heuristics such as: quick wins and slow defeats ; scoring ; mobility or presence. The four is a new action selection distribution. The conducted experiments suggest that these techniques improve the level of play. Finally, we apply these different techniques to design program-players to the game of Hex (size 11 and 13) surpassing the level of Mohex 3HNN with reinforcement learning from self-play without knowledge.
The Curse of Shared Knowledge: Recursive Belief Reasoning in a Coordination Game with Imperfect Information
Venue: arXiv cs.MA 2025
Year: 2025

Common knowledge is crucial for safe group coordination. In its absence, humans must rely on shared knowledge, which is inherently limited in depth and therefore prone to coordination failures, because any finite-order knowledge attribution allows for an even higher order attribution that may change what is known by whom. In three separate experiments involving 802 participants, we investigate the extent to which humans can differentiate between common knowledge and nth-order shared knowledge. We designed a two-person coordination game with imperfect information to simplify the recursive game structure and higher-order uncertainties into a relatable everyday scenario. In this game, coordination for the highest payoff requires a specific fact to be common knowledge between players. However, this fact cannot become common knowledge in the game. The fact can at most be nth-order shared knowledge for some n. Our findings reveal that even at quite shallow depths of shared knowledge (low values of n), players behave as though they possess common knowledge, and claim similar levels of certainty in their actions, despite incurring significant penalties when falsely assuming guaranteed coordination. We term this phenomenon 'the curse of shared knowledge'. It arises either from the players' inability to distinguish between higher-order shared knowledge and common knowledge, or from their implicit assumption that their co-player cannot make this distinction.
Decisiveness for countable MDPs and insights for NPLCSs and POMDPs
Venue: arXiv cs.LO 2025
Year: 2025

Markov chains and Markov decision processes (MDPs) are well-established probabilistic models. While finite Markov models are well-understood, analysing their infinite counterparts remains a significant challenge. Decisiveness has proven to be an elegant property for countable Markov chains: it is general enough to be satisfied by several natural classes of countable Markov chains, and it is a sufficient condition for simple qualitative and approximate quantitative model-checking algorithms to exist. In contrast, existing works on the formal analysis of countable MDPs usually rely on ad hoc techniques tailored to specific classes. We provide here a general framework to analyse countable MDPs by extending the notion of decisiveness. Compared to Markov chains, MDPs exhibit extra non-determinism that can be resolved in an adversarial or cooperative way, leading to multiple natural notions of decisiveness. We show that these notions enable the approximation of reachability and safety probabilities in countable MDPs using simple model-checking procedures. We then instantiate our generic approach to two concrete classes of models inducing countable MDPs: non-deterministic probabilistic lossy channel systems and partially observable MDPs. This leads to an algorithm to approximately compute safety probabilities in each of these classes.
Fully-Dynamic Submodular Cover with Bounded Recourse
Venue: arXiv cs.DS 2025
Year: 2025

In submodular covering problems, we are given a monotone, nonnegative submodular function $f: 2^N \rightarrow\mathbb{R}_+$ and wish to find the min-cost set $S\subseteq N$ such that $f(S)=f(N)$. This captures SetCover when $f$ is a coverage function. We introduce a general framework for solving such problems in a fully-dynamic setting where the function $f$ changes over time, and only a bounded number of updates to the solution (recourse) is allowed. For concreteness, suppose a nonnegative monotone submodular function $g_t$ is added or removed from an active set $G^{(t)}$ at each time $t$. If $f^{(t)}=\sum_{g\in G^{(t)}} g$ is the sum of all active functions, we wish to maintain a competitive solution to SubmodularCover for $f^{(t)}$ as this active set changes, and with low recourse. We give an algorithm that maintains an $O(\log(f_{max}/f_{min}))$-competitive solution, where $f_{max}, f_{min}$ are the largest/smallest marginals of $f^{(t)}$. The algorithm guarantees a total recourse of $O(\log(c_{max}/ c_{min})\cdot\sum_{t\leq T}g_t(N))$, where $c_{max},c_{min}$ are the largest/smallest costs of elements in $N$. This competitive ratio is best possible even in the offline setting, and the recourse bound is optimal up to the logarithmic factor. For monotone submodular functions that also have positive mixed third derivatives, we show an optimal recourse bound of $O(\sum_{t\leq T}g_t(N))$. This structured class includes set-coverage functions, so our algorithm matches the known $O(\log n)$-competitiveness and $O(1)$ recourse guarantees for fully-dynamic SetCover. Our work simultaneously simplifies and unifies previous results, as well as generalizes to a significantly larger class of covering problems. Our key technique is a new potential function inspired by Tsallis entropy. We also extensively use the idea of Mutual Coverage, which generalizes the classic notion of mutual information.
PySAD: A Streaming Anomaly Detection Framework in Python
Venue: arXiv cs.LG 2025
Year: 2025

Streaming anomaly detection requires algorithms that operate under strict constraints: bounded memory, single-pass processing, and constant-time complexity. We present PySAD, a comprehensive Python framework addressing these challenges through a unified architecture. The framework implements 17+ streaming algorithms (LODA, Half-Space Trees, xStream) with specialized components including projectors, probability calibrators, and postprocessors. Unlike existing batch-focused frameworks, PySAD enables efficient real-time processing with bounded memory while maintaining compatibility with PyOD and scikit-learn. Supporting all learning paradigms for univariate and multivariate streams, PySAD provides the most comprehensive streaming anomaly detection toolkit in Python. The source code is publicly available at github.com/selimfirat/pysad.
TODS: An Automated Time Series Outlier Detection System
Venue: arXiv cs.DB 2025
Year: 2025

We present TODS, an automated Time Series Outlier Detection System for research and industrial applications. TODS is a highly modular system that supports easy pipeline construction. The basic building block of TODS is primitive, which is an implementation of a function with hyperparameters. TODS currently supports 70 primitives, including data processing, time series processing, feature analysis, detection algorithms, and a reinforcement module. Users can freely construct a pipeline using these primitives and perform end- to-end outlier detection with the constructed pipeline. TODS provides a Graphical User Interface (GUI), where users can flexibly design a pipeline with drag-and-drop. Moreover, a data-driven searcher is provided to automatically discover the most suitable pipelines given a dataset. TODS is released under Apache 2.0 license at https://github.com/datamllab/tods.
Dependence Balance and Capacity Bounds for Multiterminal Communication and Wiretap Channels
Venue: arXiv cs.IT 2025
Year: 2025

An information measure based on fractional partitions of a set is used to develop a general dependence balance inequality for communication. This inequality is used to obtain new upper bounds on reliable and secret rates for multiterminal channels. For example, we obtain a new upper bound on the rate of shared randomness generated among terminals, a counterpart of the cut-set bound for reliable communication. The bounds for reliable communication utilize the concept of auxiliary receivers, and we show the bounds are optimized by Gaussian distributions for Gaussian channels. The bounds are applied to multiaccess channels with generalized feedback and relay channels, and improve the cut-set bound for scalar Gaussian channels. The improvement for Gaussian relay channels complements results obtained with other methods.
Effective Regularization Through Loss-Function Metalearning
Venue: arXiv cs.LG 2025
Year: 2025

Evolutionary computation can be used to optimize several different aspects of neural network architectures. For instance, the TaylorGLO method discovers novel, customized loss functions, resulting in improved performance, faster training, and improved data utilization. A likely reason is that such functions discourage overfitting, leading to effective regularization. This paper demonstrates theoretically that this is indeed the case for TaylorGLO. Learning rule decomposition reveals that evolved loss functions balance two factors: the pull toward zero error, and a push away from it to avoid overfitting. This is a general principle that may be used to understand other regularization techniques as well (as demonstrated in this paper for label smoothing). The theoretical analysis leads to a constraint that can be utilized to find more effective loss functions in practice; the mechanism also results in networks that are more robust (as demonstrated in this paper with adversarial inputs). The analysis in this paper thus constitutes a first step towards understanding regularization, and demonstrates the power of evolutionary neural architecture search in general.
Finitely (In)tractable Promise Constraint Satisfaction Problems
Venue: arXiv cs.CC 2025
Year: 2025

The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph coloring problems. Barto [LICS '19] has shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability and characterizing finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18].
Decentralized Structural-RNN for Robot Crowd Navigation with Deep Reinforcement Learning
Venue: arXiv cs.RO 2025
Year: 2025

Safe and efficient navigation through human crowds is an essential capability for mobile robots. Previous work on robot crowd navigation assumes that the dynamics of all agents are known and well-defined. In addition, the performance of previous methods deteriorates in partially observable environments and environments with dense crowds. To tackle these problems, we propose decentralized structural-Recurrent Neural Network (DS-RNN), a novel network that reasons about spatial and temporal relationships for robot decision making in crowd navigation. We train our network with model-free deep reinforcement learning without any expert supervision. We demonstrate that our model outperforms previous methods in challenging crowd navigation scenarios. We successfully transfer the policy learned in the simulator to a real-world TurtleBot 2i. For more information, please visit the project website at https://sites.google.com/view/crowdnav-ds-rnn/home.
On the performance of downlink NOMA in underlay spectrum sharing
Venue: arXiv cs.IT 2025
Year: 2025

Non-orthogonal multiple access (NOMA) and spectrum sharing are two potential technologies for providing massive connectivity in beyond fifth-generation (B5G) networks. In this paper, we present the performance analysis of a multi-antenna-assisted two-user downlink NOMA system in an underlay spectrum sharing system. We derive closed-form expressions for the average achievable sum-rate and outage probability of the secondary network under a peak interference constraint and/or peak power constraint, depending on the availability of channel state information (CSI) of the interference link between secondary transmitter (ST) and primary receiver (PR). For the case where the ST has a fixed power budget, we show that performance can be divided into two specific regimes, where either the interference constraint or the power constraint primarily dictates the performance. Our results confirm that the NOMA-based underlay spectrum sharing system significantly outperforms its orthogonal multiple access (OMA) based counterpart, by achieving higher average sum-rate and lower outage probability. We also show the effect of information loss at the ST in terms of CSI of the link between the ST and PR on the system performance. Moreover, we also present closed-form expressions for the optimal power allocation coefficient that minimizes the outage probability of the NOMA system for the special case where the secondary users are each equipped with a single antenna. A close agreement between the simulation and analytical results confirms the correctness of the presented analysis.
Efficient stream-based Max-Min diversification with minimal failure rate
Venue: arXiv cs.DS 2025
Year: 2025

The streaming max-min diversification problem concerns the selection of a limited and diverse sample of items out of a data stream of known finite length. The objective to be maximized is the minimum distance among any pair of selected items. We consider the irrevocable-choice sampling, where decisions need to be immediate and irrevocable while processing the items of the stream, which is a setting little studied in the literature. Standard algorithmic approaches for sequential selection disregard selection failures, which is when the last items of the stream are picked by default, to prevent delivering an incomplete selection set. This defect can be catastrophic for the max-min diversification objective. The proposed Failure Rate Minimization (FRM) is a rank-based algorithm that selects a set of diverse items and, in addition, reduces significantly the probability of having failures. We demonstrate with simulations FRM's performance comparing with existing selection strategies.
Adaptive Risk Mitigation in Demand Learning
Venue: arXiv cs.LG 2025
Year: 2025

We study dynamic pricing of a product with an unknown demand distribution over a finite horizon. Departing from the standard no-regret learning environment in which prices can be adjusted at any time, we restrict price changes to predetermined points in time to reflect common retail practice. This constraint, coupled with demand model ambiguity and an unknown customer arrival pattern, imposes a high risk of revenue loss, as a price based on a misestimated demand model may be applied to many customers before it can be revised. We develop an adaptive risk learning (ARL) framework that embeds a data-driven ambiguity set (DAS) to quantify demand model ambiguity by adapting to the unknown arrival pattern. Initially, when arrivals are few, the DAS includes a broad set of plausible demand models, reflecting high ambiguity and revenue risk. As new data is collected through pricing, the DAS progressively shrinks, capturing the reduction in model ambiguity and associated risk. We establish the probabilistic convergence of the DAS to the true demand model and derive a regret bound for the ARL policy that explicitly links revenue loss to the data required for the DAS to identify the true model with high probability. The dependence of our regret bound on the arrival pattern is unique to our constrained dynamic pricing problem and contrasts with no-regret learning environments, where regret is constant and arrival-pattern independent. Relaxing the constraint on infrequent price changes, we show that ARL attains the known constant regret bound. Numerical experiments further demonstrate that ARL outperforms benchmarks that prioritize either regret or risk alone by adaptively balancing both without knowledge of the arrival pattern. This adaptive risk adjustment is crucial for achieving high revenues and low downside risk when prices are sticky and both demand and arrival patterns are unknown.
Reflective-Net: Learning from Explanations
Venue: arXiv cs.LG 2025
Year: 2025

We examine whether data generated by explanation techniques, which promote a process of self-reflection, can improve classifier performance. Our work is based on the idea that humans have the ability to make quick, intuitive decisions as well as to reflect on their own thinking and learn from explanations. To the best of our knowledge, this is the first time that the potential of mimicking this process by using explanations generated by explainability methods has been explored. We found that combining explanations with traditional labeled data leads to significant improvements in classification accuracy and training efficiency across multiple image classification datasets and convolutional neural network architectures. It is worth noting that during training, we not only used explanations for the correct or predicted class, but also for other classes. This serves multiple purposes, including allowing for reflection on potential outcomes and enriching the data through augmentation.
Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
Venue: arXiv cs.NE 2025
Year: 2025

The theoretical understanding of MOEAs is lagging far behind their success in practice. In particular, previous theory work considers mostly easy problems that are composed of unimodal objectives. As a first step towards a deeper understanding of how evolutionary algorithms solve multimodal multiobjective problems, we propose the OJZJ problem, a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime. In contrast, for all problem sizes $n$ and all jump sizes ${k \in [4..\frac n2 - 1]}$, the global SEMO (GSEMO) covers the Pareto front in an expected number of $Θ((n-2k)n^{k})$ iterations. For $k = o(n)$, we also show the tighter bound $\frac 32 e n^{k+1} \pm o(n^{k+1})$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms. We also combine the GSEMO with two approaches that showed advantages in single-objective multimodal problems. When using the GSEMO with a heavy-tailed mutation operator, the expected runtime improves by a factor of at least $k^{Ω(k)}$. When adapting the recent stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the expected runtime also improves by a factor of at least $k^{Ω(k)}$ and surpasses the heavy-tailed GSEMO by a small polynomial factor in $k$. Via an experimental analysis, we show that these asymptotic differences are visible already for small problem sizes: A factor-$5$ speed-up from heavy-tailed mutation and a factor-$10$ speed-up from stagnation detection can be observed already for jump size~$4$ and problem sizes between $10$ and $50$. Overall, our results show that the ideas recently developed to aid single-objective evolutionary algorithms to cope with local optima can be effectively employed also in multiobjective optimization.
The Atlas for the Aspiring Network Scientist
Venue: arXiv cs.CY 2025
Year: 2025

Network science is the field dedicated to the investigation and analysis of complex systems via their representations as networks. We normally model such networks as graphs: sets of nodes connected by sets of edges and a number of node and edge attributes. This deceptively simple object is the starting point of never-ending complexity, due to its ability to represent almost every facet of reality: chemical interactions, protein pathways inside cells, neural connections inside the brain, scientific collaborations, financial relations, citations in art history, just to name a few examples. If we hope to make sense of complex networks, we need to master a large analytic toolbox: graph and probability theory, linear algebra, statistical physics, machine learning, combinatorics, and more. This book aims at providing the first access to all these tools. It is intended as an "Atlas", because its interest is not in making you a specialist in using any of these techniques. Rather, after reading this book, you will have a general understanding about the existence and the mechanics of all these approaches. You can use such an understanding as the starting point of your own career in the field of network science. This has been, so far, an interdisciplinary endeavor. The founding fathers of this field come from many different backgrounds: mathematics, sociology, computer science, physics, history, digital humanities, and more. This Atlas is charting your path to be something different from all of that: a pure network scientist.