OpenRaiser/Intern-Atlas huggingface dataset:
Search and Matching for Adoption from Foster Care
Venue: arXiv cs.GT 2025
Year: 2025

To find families for the more than 100,000 children in need of adoptive placements, most United States child welfare agencies have employed a family-driven search approach in which prospective families respond to announcements made by the agency. However, some agencies have switched to a caseworker-driven search approach in which the caseworker directly contacts families recommended for a child. We introduce a novel search-and-matching model that captures the key features of the adoption process and compare family-driven with caseworker-driven search in a game-theoretical framework. Under either approach, the equilibria are generated by threshold strategies and form a lattice structure. Our main theoretical finding then shows that no family-driven equilibrium can Pareto dominate any caseworker-driven outcome, whereas it is possible that each caseworker-driven equilibrium Pareto dominates every equilibrium attainable under family-driven search. We also find that when families are sufficiently impatient, caseworker-driven search is better for all children. We illustrate numerically that most agents are better off under caseworker-driven search for a wide range of parameters. Finally, we provide empirical evidence from an agency that switched to caseworker-driven search and achieved a three-year adoption probability that outperformed a statewide benchmark by 24%, as well as a statistically significant 27% improvement in adoption hazard rates.
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
Venue: arXiv cs.DM 2025
Year: 2025

We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello, Fellows, and Stillwell asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show some solvable cases and, in particular, completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. We remark that our new characterization results also strengthen previously known results for covering graphs without semi-edges, and they in turn apply to an infinite class of simple target graphs with at most two vertices of degree more than two. Some of the results are moreover proven in a more general setting (e.g., finding $k$-tuples of pairwise disjoint perfect matchings in regular graphs).
Backpropagation Through Time For Networks With Long-Term Dependencies
Venue: arXiv cs.LG 2025
Year: 2025

Backpropagation through time (BPTT) is a technique of updating tuned parameters within recurrent neural networks (RNNs). Several attempts at creating such an algorithm have been made including: Nth Ordered Approximations and Truncated-BPTT. These methods approximate the backpropagation gradients under the assumption that the RNN only utilises short-term dependencies. This is an acceptable assumption to make for the current state of artificial neural networks. As RNNs become more advanced, a shift towards influence by long-term dependencies is likely. Thus, a new method for backpropagation is required. We propose using the 'discrete forward sensitivity equation' and a variant of it for single and multiple interacting recurrent loops respectively. This solution is exact and also allows the network's parameters to vary between each subsequent step, however it does require the computation of a Jacobian.
Solving Homotopy Domain Equations
Venue: arXiv cs.LO 2025
Year: 2025

In order to get $λ$-models with a rich structure of $\infty$-groupoid, which we call "homotopy $λ$-models", a general technique is described for solving domain equations on any cartesian closed $\infty$-category (c.c.i.) with enough points. Finally, the technique is applied in a particular c.c.i., where some examples of homotopy $λ$-models are given.
A Bayesian approach to modeling topic-metadata relationships
Venue: arXiv cs.CL 2025
Year: 2025

The objective of advanced topic modeling is not only to explore latent topical structures, but also to estimate relationships between the discovered topics and theoretically relevant metadata. Methods used to estimate such relationships must take into account that the topical structure is not directly observed, but instead being estimated itself in an unsupervised fashion, usually by common topic models. A frequently used procedure to achieve this is the method of composition, a Monte Carlo sampling technique performing multiple repeated linear regressions of sampled topic proportions on metadata covariates. In this paper, we propose two modifications of this approach: First, we substantially refine the existing implementation of the method of composition from the R package stm by replacing linear regression with the more appropriate Beta regression. Second, we provide a fundamental enhancement of the entire estimation framework by substituting the current blending of frequentist and Bayesian methods with a fully Bayesian approach. This allows for a more appropriate quantification of uncertainty. We illustrate our improved methodology by investigating relationships between Twitter posts by German parliamentarians and different metadata covariates related to their electoral districts, using the Structural Topic Model to estimate topic proportions.
Audio Transformers
Venue: arXiv cs.SD 2025
Year: 2025

Over the past two decades, CNN architectures have produced compelling models of sound perception and cognition, learning hierarchical organizations of features. Analogous to successes in computer vision, audio feature classification can be optimized for a particular task of interest, over a wide variety of datasets and labels. In fact similar architectures designed for image understanding have proven effective for acoustic scene analysis. Here we propose applying Transformer based architectures without convolutional layers to raw audio signals. On a standard dataset of Free Sound 50K,comprising of 200 categories, our model outperforms convolutional models to produce state of the art results. This is significant as unlike in natural language processing and computer vision, we do not perform unsupervised pre-training for outperforming convolutional architectures. On the same training set, with respect mean aver-age precision benchmarks, we show a significant improvement. We further improve the performance of Transformer architectures by using techniques such as pooling inspired from convolutional net-work designed in the past few years. In addition, we also show how multi-rate signal processing ideas inspired from wavelets, can be applied to the Transformer embeddings to improve the results. We also show how our models learns a non-linear non constant band-width filter-bank, which shows an adaptable time frequency front end representation for the task of audio understanding, different from other tasks e.g. pitch estimation.
A rigorous introduction to linear models
Venue: arXiv cs.LG 2025
Year: 2025

This book is meant to provide an introduction to linear models and the theories behind them. Our goal is to give a rigorous introduction to the readers with prior exposure to ordinary least squares. In machine learning, the output is usually a nonlinear function of the input. Deep learning even aims to find a nonlinear dependence with many layers, which require a large amount of computation. However, most of these algorithms build upon simple linear models. We then describe linear models from different perspectives and find the properties and theories behind the models. The linear model is the main technique in regression problems, and the primary tool for it is the least squares approximation, which minimizes a sum of squared errors. This is a natural choice when we're interested in finding the regression function which minimizes the corresponding expected squared error. This book is primarily a summary of purpose, significance of important theories behind linear models, e.g., distribution theory and the minimum variance estimator. We first describe ordinary least squares from three different points of view, upon which we disturb the model with random noise and Gaussian noise. Through Gaussian noise, the model gives rise to the likelihood so that we introduce a maximum likelihood estimator. It also develops some distribution theories via this Gaussian disturbance. The distribution theory of least squares will help us answer various questions and introduce related applications. We then prove least squares is the best unbiased linear model in the sense of mean squared error, and most importantly, it actually approaches the theoretical limit. We end up with linear models with the Bayesian approach and beyond.
Diffusion Approximations for Thompson Sampling in the Small Gap Regime
Venue: arXiv cs.LG 2025
Year: 2025

We study the process-level dynamics of Thompson sampling in the ``small gap'' regime. The small gap regime is one in which the gaps between the arm means are of order $\sqrtγ$ or smaller and the time horizon is of order $1/γ$, where $γ$ is small. As $γ\downarrow 0$, we show that the process-level dynamics of Thompson sampling converge weakly to the solutions to certain stochastic differential equations and stochastic ordinary differential equations. Our weak convergence theory is developed from first principles using the Continuous Mapping Theorem, can handle stationary, weakly dependent reward processes, and can also be adapted to analyze a variety of sampling-based bandit algorithms. Indeed, we show that the process-level dynamics of many sampling-based bandit algorithms -- including Thompson sampling designed for any single-parameter exponential family of rewards, as well as non-parametric bandit algorithms based on bootstrap re-sampling -- satisfy an invariance principle. Namely, their weak limits coincide with that of Gaussian parametric Thompson sampling with Gaussian priors. Moreover, in the small gap regime, the regret performance of these algorithms is generally insensitive to model mis-specification, changing continuously with increasing degrees of mis-specification.
Indirect predicates for geometric constructions
Venue: arXiv cs.CG 2025
Year: 2025

Geometric predicates are a basic ingredient to implement a vast range of algorithms in computational geometry. Modern implementations employ floating point filtering techniques to combine efficiency and robustness, and state-of-the-art predicates are guaranteed to be always exact while being only slightly slower than corresponding (inexact) floating point implementations. Unfortunately, if the input to these predicates is an intermediate construction of an algorithm, its floating point representation may be affected by an approximation error, and correctness is no longer guaranteed. This paper introduces the concept of indirect geometric predicate: instead of taking the intermediate construction as an explicit input, an indirect predicate considers the primitive geometric elements which are combined to produce such a construction. This makes it possible to keep track of the floating point approximation, and thus to exploit efficient filters and expansion arithmetic to exactly resolve the predicate with minimal overhead with respect to a naive floating point implementation. As a representative example, we show how to extend standard predicates to the case of points of intersection of linear elements (i.e. lines and planes) and show that, on classical problems, this approach outperforms state-of-the-art solutions based on lazy exact intermediate representations.
EvalNet: A Practical Toolchain for Generation and Analysis of Extreme-Scale Interconnects
Venue: arXiv cs.NI 2025
Year: 2025

The diversity of communication paths in a network - especially non-minimal paths - is a key enabler of performance at extreme scales. We present EvalNet, a toolchain for scalable generation and analysis over 25 important network topologies, such as Slim Fly, PolarFly, and Orthogonal Fat Trees, with a strong focus on path diversity metrics. EvalNet provides an extensive and fine-grained analysis of shortest and non-shortest paths, including their multiplicities, lengths, and interference. It supports exact measurement and visualization of bandwidth and throughput between every router pair, enabling unprecedented insight into routing potential. EvalNet also includes detailed models for construction cost and power consumption, and interfaces seamlessly with established simulators, which we tune to support large-scale evaluations on low-cost hardware. Using EvalNet, we deliver the widest and most comprehensive path diversity study to date, demonstrating how path diversity underpins throughput and scalability, and facilitating progress towards new frontiers in extreme-scale network design.
Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm
Venue: arXiv cs.LG 2025
Year: 2025

Many engineering problems have multiple objectives, and the overall aim is to optimize a non-linear function of these objectives. In this paper, we formulate the problem of maximizing a non-linear concave function of multiple long-term objectives. A policy-gradient based model-free algorithm is proposed for the problem. To compute an estimate of the gradient, a biased estimator is proposed. The proposed algorithm is shown to achieve convergence to within an $ε$ of the global optima after sampling $\mathcal{O}(\frac{M^4σ^2}{(1-γ)^8ε^4})$ trajectories where $γ$ is the discount factor and $M$ is the number of the agents, thus achieving the same dependence on $ε$ as the policy gradient algorithm for the standard reinforcement learning.
InDiD: Instant Disorder Detection via Representation Learning
Venue: arXiv cs.LG 2025
Year: 2025

For sequential data, a change point is a moment of abrupt regime switch in data streams. Such changes appear in different scenarios, including simpler data from sensors and more challenging video surveillance data. We need to detect disorders as fast as possible. Classic approaches for change point detection (CPD) might underperform for semi-structured sequential data because they cannot process its structure without a proper representation. We propose a principled loss function that balances change detection delay and time to a false alarm. It approximates classic rigorous solutions but is differentiable and allows representation learning for deep models. We consider synthetic sequences, real-world data sensors and videos with change points. We carefully labelled available data with change point moments for video data and released it for the first time. Experiments suggest that complex data require meaningful representations tailored for the specificity of the CPD task -- and our approach provides them outperforming considered baselines. For example, for explosion detection in video, the F1 score for our method is 0.53 compared to baseline scores of 0.31 and 0.35.
Low-Dimensional Structure in the Space of Language Representations is Reflected in Brain Responses
Venue: arXiv cs.CL 2025
Year: 2025

How related are the representations learned by neural language models, translation models, and language tagging tasks? We answer this question by adapting an encoder-decoder transfer learning method from computer vision to investigate the structure among 100 different feature spaces extracted from hidden representations of various networks trained on language tasks. This method reveals a low-dimensional structure where language models and translation models smoothly interpolate between word embeddings, syntactic and semantic tasks, and future word embeddings. We call this low-dimensional structure a language representation embedding because it encodes the relationships between representations needed to process language for a variety of NLP tasks. We find that this representation embedding can predict how well each individual feature space maps to human brain responses to natural language stimuli recorded using fMRI. Additionally, we find that the principal dimension of this structure can be used to create a metric which highlights the brain's natural language processing hierarchy. This suggests that the embedding captures some part of the brain's natural language representation structure.
A3C-S: Automated Agent Accelerator Co-Search towards Efficient Deep Reinforcement Learning
Venue: arXiv cs.LG 2025
Year: 2025

Driven by the explosive interest in applying deep reinforcement learning (DRL) agents to numerous real-time control and decision-making applications, there has been a growing demand to deploy DRL agents to empower daily-life intelligent devices, while the prohibitive complexity of DRL stands at odds with limited on-device resources. In this work, we propose an Automated Agent Accelerator Co-Search (A3C-S) framework, which to our best knowledge is the first to automatically co-search the optimally matched DRL agents and accelerators that maximize both test scores and hardware efficiency. Extensive experiments consistently validate the superiority of our A3C-S over state-of-the-art techniques.
HUMAP: Hierarchical Uniform Manifold Approximation and Projection
Venue: arXiv cs.LG 2025
Year: 2025

Dimensionality reduction (DR) techniques help analysts to understand patterns in high-dimensional spaces. These techniques, often represented by scatter plots, are employed in diverse science domains and facilitate similarity analysis among clusters and data samples. For datasets containing many granularities or when analysis follows the information visualization mantra, hierarchical DR techniques are the most suitable approach since they present major structures beforehand and details on demand. This work presents HUMAP, a novel hierarchical dimensionality reduction technique designed to be flexible on preserving local and global structures and preserve the mental map throughout hierarchical exploration. We provide empirical evidence of our technique's superiority compared with current hierarchical approaches and show a case study applying HUMAP for dataset labelling.
Beyond Predictions in Neural ODEs: Identification and Interventions
Venue: arXiv cs.LG 2025
Year: 2025

Spurred by tremendous success in pattern matching and prediction tasks, researchers increasingly resort to machine learning to aid original scientific discovery. Given large amounts of observational data about a system, can we uncover the rules that govern its evolution? Solving this task holds the great promise of fully understanding the causal interactions and being able to make reliable predictions about the system's behavior under interventions. We take a step towards answering this question for time-series data generated from systems of ordinary differential equations (ODEs). While the governing ODEs might not be identifiable from data alone, we show that combining simple regularization schemes with flexible neural ODEs can robustly recover the dynamics and causal structures from time-series data. Our results on a variety of (non)-linear first and second order systems as well as real data validate our method. We conclude by showing that we can also make accurate predictions under interventions on variables or the system itself.
Noisy (Binary) Searching: Simple, Fast and Correct
Venue: arXiv cs.DS 2025
Year: 2025

This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter $p$ that dictates that a comparison can be incorrect with probability $p$, independently of other queries. We state two types of upper bounds on the number of queries: the worst-case and expected query complexity scenarios. The bounds improve the ones known to date, i.e., our algorithms require fewer queries. Additionally, they have simpler statements, and work for the full range of parameters. All query complexities for the expected query scenarios are tight up to lower order terms. For the problem where the target prior is uniform over all possible inputs, we provide an algorithm with expected complexity upperbounded by $(\log_2 n + \log_2 δ^{-1} + 3)/I(p)$, where $n$ is the domain size, $0\le p < 1/2$ is the noise ratio, and $δ>0$ is the failure probability, and $I(p)$ is the information gain function. As a side-effect, we close some correctness issues regarding previous work. Also, en route, we obtain new and improved query complexities for the search generalized to arbitrary graphs. This paper continues and improves the lines of research of Burnashev--Zigangirov [Prob. Per. Informatsii, 1974], Ben-Or and Hassidim [FOCS 2008], Gu and Xu [STOC 2023], and Emamjomeh-Zadeh et al. [STOC 2016], Dereniowski et al. [SOSA@SODA 2019].
DANCE: DAta-Network Co-optimization for Efficient Segmentation Model Training and Inference
Venue: arXiv cs.CV 2025
Year: 2025

Semantic segmentation for scene understanding is nowadays widely demanded, raising significant challenges for the algorithm efficiency, especially its applications on resource-limited platforms. Current segmentation models are trained and evaluated on massive high-resolution scene images ("data level") and suffer from the expensive computation arising from the required multi-scale aggregation("network level"). In both folds, the computational and energy costs in training and inference are notable due to the often desired large input resolutions and heavy computational burden of segmentation models. To this end, we propose DANCE, general automated DAta-Network Co-optimization for Efficient segmentation model training and inference. Distinct from existing efficient segmentation approaches that focus merely on light-weight network design, DANCE distinguishes itself as an automated simultaneous data-network co-optimization via both input data manipulation and network architecture slimming. Specifically, DANCE integrates automated data slimming which adaptively downsamples/drops input images and controls their corresponding contribution to the training loss guided by the images' spatial complexity. Such a downsampling operation, in addition to slimming down the cost associated with the input size directly, also shrinks the dynamic range of input object and context scales, therefore motivating us to also adaptively slim the network to match the downsampled data. Extensive experiments and ablating studies (on four SOTA segmentation models with three popular segmentation datasets under two training settings) demonstrate that DANCE can achieve "all-win" towards efficient segmentation(reduced training cost, less expensive inference, and better mean Intersection-over-Union (mIoU)).