OpenRaiser/Intern-Atlas huggingface dataset:
Asymmetric Number Partitioning with Splitting and Interval Targets
Venue: arXiv cs.DS 2025
Year: 2025

The n-way number partitioning problem, a fundamental challenge in combinatorial optimization, has significant implications for applications such as fair division and machine scheduling. Despite these problems being NP-hard, many approximation techniques exist. We consider three closely related kinds of approximations, and various objectives such as decision, min-max, max-min, and even a generalized objective, in which the bins are not considered identical anymore, but rather asymmetric (used to solve fair division to asymmetric agents or uniform machine scheduling problems). The first two variants optimize the partition such that: in the first variant some fixed number s of items can be split between two or more bins and in the second variant we allow at most a fixed number t of splittings. The third variant is a decision problem: the largest bin sum must be within a pre-specified interval, parameterized by a fixed rational number u times the largest item size. When the number of bins n is unbounded, we show that every variant is strongly NP-complete. When the number of bins n is fixed, the running time depends on the fixed parameters s,t,u. For each variant, we give a complete picture of its running time. For n=2, the running time is easy to identify. Our main results consider any fixed n>=3. Using a two-way polynomial-time reduction between the first and the third variant, we show that n-way number-partitioning with s split items can be solved in polynomial time if s>=n-2, and it is NP-complete otherwise. Also, n-way number-partitioning with t splittings can be solved in polynomial time if t>=n-1, and it is NP-complete otherwise. Finally, we show that the third variant can be solved in polynomial time if u>=(n-2)/n, and it is NP-complete otherwise. Our positive results for the optimization problems consider both asymmetric min-max and asymmetric max-min versions.
Non-Stationary Bandit Learning via Predictive Sampling
Venue: arXiv cs.LG 2025
Year: 2025

Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to non-stationary environments. We attribute such failures to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to non-stationarity. Building upon this insight, we propose predictive sampling, an algorithm that deprioritizes acquiring information that quickly loses usefulness. A theoretical guarantee on the performance of predictive sampling is established through a Bayesian regret bound. We provide versions of predictive sampling for which computations tractably scale to complex bandit environments of practical interest. Through numerical simulations, we demonstrate that predictive sampling outperforms Thompson sampling in all non-stationary environments examined.
New-Onset Diabetes Assessment Using Artificial Intelligence-Enhanced Electrocardiography
Venue: arXiv cs.LG 2025
Year: 2025

Diabetes has a long asymptomatic period which can often remain undiagnosed for multiple years. In this study, we trained a deep learning model to detect new-onset diabetes using 12-lead ECG and readily available demographic information. To do so, we used retrospective data where patients have both a hemoglobin A1c and ECG measured. However, such patients may not be representative of the complete patient population. As part of the study, we proposed a methodology to evaluate our model in the target population by estimating the probability of receiving an A1c test and reweight the retrospective population to represent the general population. We also adapted an efficient algorithm to generate Shapley values for both ECG signals and demographic features at the same time for model interpretation. The model offers an automated, more accurate method for early diabetes detection compared to current screening efforts. Their potential use in wearable devices can facilitate large-scale, community-wide screening, improving healthcare outcomes.
Assignment Markets with Budget Constraints
Venue: arXiv cs.GT 2025
Year: 2025

This paper studies markets where a set of indivisible items is sold to bidders with quasilinear, unit-demand valuations, subject to a hard budget constraint. Without financial constraints the well-known assignment market model of Shapley and Shubik (1971) allows for a simple ascending auction format that is incentive-compatible, and strongly Pareto-optimal. However, this auction model does not capture the possibility that bidders face hard budget constraints. We design an iterative auction that depends on demand queries and an easily verifiable additional condition to maintain the properties in the presence of budget constraints. If instead this additional condition does not hold, incentive compatibility and core stability are at odds, and we cannot hope to achieve strong Pareto optimality in a simple ascending auction even with truthful bidding. Moreover, even in a complete information model where the auctioneer has access to valuations and budget constraints, the problem is NP-hard.
Pocket2Mol: Efficient Molecular Sampling Based on 3D Protein Pockets
Venue: arXiv cs.LG 2025
Year: 2025

Deep generative models have achieved tremendous success in designing novel drug molecules in recent years. A new thread of works have shown the great potential in advancing the specificity and success rate of in silico drug design by considering the structure of protein pockets. This setting posts fundamental computational challenges in sampling new chemical compounds that could satisfy multiple geometrical constraints imposed by pockets. Previous sampling algorithms either sample in the graph space or only consider the 3D coordinates of atoms while ignoring other detailed chemical structures such as bond types and functional groups. To address the challenge, we develop Pocket2Mol, an E(3)-equivariant generative network composed of two modules: 1) a new graph neural network capturing both spatial and bonding relationships between atoms of the binding pockets and 2) a new efficient algorithm which samples new drug candidates conditioned on the pocket representations from a tractable distribution without relying on MCMC. Experimental results demonstrate that molecules sampled from Pocket2Mol achieve significantly better binding affinity and other drug properties such as druglikeness and synthetic accessibility.
Novel Multicolumn Kernel Extreme Learning Machine for Food Detection via Optimal Features from CNN
Venue: arXiv cs.CV 2025
Year: 2025

Automatic food detection is an emerging topic of interest due to its wide array of applications ranging from detecting food images on social media platforms to filtering non-food photos from the users in dietary assessment apps. Recently, during the COVID-19 pandemic, it has facilitated enforcing an eating ban by automatically detecting eating activities from cameras in public places. Therefore, to tackle the challenge of recognizing food images with high accuracy, we proposed the idea of a hybrid framework for extracting and selecting optimal features from an efficient neural network. There on, a nonlinear classifier is employed to discriminate between linearly inseparable feature vectors with great precision. In line with this idea, our method extracts features from MobileNetV3, selects an optimal subset of attributes by using Shapley Additive exPlanations (SHAP) values, and exploits kernel extreme learning machine (KELM) due to its nonlinear decision boundary and good generalization ability. However, KELM suffers from the 'curse of dimensionality problem' for large datasets due to the complex computation of kernel matrix with large numbers of hidden nodes. We solved this problem by proposing a novel multicolumn kernel extreme learning machine (MCKELM) which exploited the k-d tree algorithm to divide data into N subsets and trains separate KELM on each subset of data. Then, the method incorporates KELM classifiers into parallel structures and selects the top k nearest subsets during testing by using the k-d tree search for classifying input instead of the whole network. For evaluating a proposed framework large food/non-food dataset is prepared using nine publically available datasets. Experimental results showed the superiority of our method on an integrated set of measures while solving the problem of 'curse of dimensionality in KELM for large datasets.
Deep Learning in Business Analytics: A Clash of Expectations and Reality
Venue: arXiv cs.LG 2025
Year: 2025

Our fast-paced digital economy shaped by global competition requires increased data-driven decision-making based on artificial intelligence (AI) and machine learning (ML). The benefits of deep learning (DL) are manifold, but it comes with limitations that have, so far, interfered with widespread industry adoption. This paper explains why DL, despite its popularity, has difficulties speeding up its adoption within business analytics. It is shown that the adoption of deep learning is not only affected by computational complexity, lacking big data architecture, lack of transparency (black-box), skill shortage, and leadership commitment, but also by the fact that DL does not outperform traditional ML models in the case of structured datasets with fixed-length feature vectors. Deep learning should be regarded as a powerful addition to the existing body of ML models instead of a one size fits all solution. The results strongly suggest that gradient boosting can be seen as the go-to model for predictions on structured datasets within business analytics. In addition to the empirical study based on three industry use cases, the paper offers a comprehensive discussion of those results, practical implications, and a roadmap for future research.
Continual Learning with Global Alignment
Venue: arXiv cs.CL 2025
Year: 2025

Continual learning aims to sequentially learn new tasks without forgetting previous tasks' knowledge (catastrophic forgetting). One factor that can cause forgetting is the interference between the gradients on losses from different tasks. When the gradients on the current task's loss are in opposing directions to those on previous tasks' losses, updating the model for the current task may cause performance degradation on previous tasks. In this paper, we first identify causes of the above interference, and hypothesize that correlations between data representations are a key factor of interference. We then propose a method for promoting appropriate correlations between arbitrary tasks' data representations (i.e., global alignment) in individual task learning. Specifically, we learn the data representation as a task-specific composition of pre-trained token representations shared across all tasks. Then the correlations between different tasks' data representations are grounded by correlations between pre-trained token representations. We explore different ways to learn such compositions. Without experience replay, our model achieves SOTA performance in continual learning tasks. It also achieves advanced class-incremental performance through task-incremental training.
Are Akpans Trick or Treat: Unveiling Helpful Biases in Assistant Systems
Venue: arXiv cs.CL 2025
Year: 2025

Information-seeking AI assistant systems aim to answer users' queries about knowledge in a timely manner. However, both the human-perceived helpfulness of information-seeking assistant systems and its fairness implication are under-explored. In this paper, we study computational measurements of helpfulness. We collect human annotations on the helpfulness of dialogue responses, develop models for automatic helpfulness evaluation, and then propose to use the helpfulness level of a dialogue system towards different user queries to gauge the fairness of a dialogue system. Experiments with state-of-the-art dialogue systems, including ChatGPT, under three information-seeking scenarios reveal that existing systems tend to be more helpful for questions regarding concepts from highly-developed countries than less-developed countries, uncovering potential fairness concerns underlying the current information-seeking assistant systems.
New Intent Discovery with Pre-training and Contrastive Learning
Venue: arXiv cs.CL 2025
Year: 2025

New intent discovery aims to uncover novel intent categories from user utterances to expand the set of supported intent classes. It is a critical task for the development and service expansion of a practical dialogue system. Despite its importance, this problem remains under-explored in the literature. Existing approaches typically rely on a large amount of labeled utterances and employ pseudo-labeling methods for representation learning and clustering, which are label-intensive, inefficient, and inaccurate. In this paper, we provide new solutions to two important research questions for new intent discovery: (1) how to learn semantic utterance representations and (2) how to better cluster utterances. Particularly, we first propose a multi-task pre-training strategy to leverage rich unlabeled data along with external labeled data for representation learning. Then, we design a new contrastive loss to exploit self-supervisory signals in unlabeled data for clustering. Extensive experiments on three intent recognition benchmarks demonstrate the high effectiveness of our proposed method, which outperforms state-of-the-art methods by a large margin in both unsupervised and semi-supervised scenarios. The source code will be available at https://github.com/zhang-yu-wei/MTP-CLNN.
Approximability Landscape of Welfare Maximization within Fair Allocations
Venue: arXiv cs.GT 2025
Year: 2025

Fair allocation of indivisible goods studies allocating $m$ goods among $n$ agents in a fair manner. While fairness is a fundamental requirement in many real-world applications, it often conflicts with (economic) efficiency. This raises a natural and important question: How can we identify the most welfare-efficient allocation among all fair allocations? This paper answers from the perspective of computational complexity. Specifically, we study the problem of maximizing utilitarian social welfare under two widely studied fairness criteria: envy-freeness up to any item (EFX) and envy-freeness up to one item (EF1). We examine both normalized and unnormalized valuations, where normalized valuations require that each agent's total utility for all items is identical. The key contributions of this paper can be summarized as follows: (i) we sketch the complete complexity landscape of welfare maximization subject to fair allocation constraints; and (ii) we provide interesting bounds on the price of fairness for both EFX and EF1. Specifically: (1) For $n=2$ agents, we develop polynomial-time approximation schemes (PTAS) and provide NP-hardness results for EFX and EF1 constraints; (2) For $n>2$ agents, under EFX constraints, we design algorithms that achieve approximation ratios of $O(n)$ and $O(\sqrt{n})$ for unnormalized and normalized valuations, respectively. These results are complemented by asymptotically tight inapproximability results. We also obtain similar results for EF1 constraints; (3) When the number of agents is a fixed constant, we show that the optimal solution can be computed in polynomial time by slightly relaxing the fairness constraints, whereas exact fairness leads to strong inapproximability; (4) Furthermore, our results imply the price of EFX is $Θ(\sqrt{n})$ for normalized valuations, which is unknown in the literature.
Independent and Decentralized Learning in Markov Potential Games
Venue: arXiv cs.LG 2025
Year: 2025

We study a multi-agent reinforcement learning dynamics, and analyze its asymptotic behavior in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players do not know the game parameters, and cannot communicate or coordinate. In each stage, players update their estimate of Q-function that evaluates their total contingent payoff based on the realized one-stage reward in an asynchronous manner. Then, players independently update their policies by incorporating an optimal one-stage deviation strategy based on the estimated Q-function. Inspired by the actor-critic algorithm in single-agent reinforcement learning, a key feature of our learning dynamics is that agents update their Q-function estimates at a faster timescale than the policies. Leveraging tools from two-timescale asynchronous stochastic approximation theory, we characterize the convergent set of learning dynamics.
Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
Venue: arXiv cs.LG 2025
Year: 2025

Graph autoencoders (GAE) and variational graph autoencoders (VGAE) emerged as two powerful groups of unsupervised node embedding methods, with various applications to graph-based machine learning problems such as link prediction and community detection. Nonetheless, at the beginning of this Ph.D. project, GAE and VGAE models were also suffering from key limitations, preventing them from being adopted in the industry. In this thesis, we present several contributions to improve these models, with the general aim of facilitating their use to address industrial-level problems involving graph representations. Firstly, we propose two strategies to overcome the scalability issues of previous GAE and VGAE models, permitting to effectively train these models on large graphs with millions of nodes and edges. These strategies leverage graph degeneracy and stochastic subgraph decoding techniques, respectively. Besides, we introduce Gravity-Inspired GAE and VGAE, providing the first extensions of these models for directed graphs, that are ubiquitous in industrial applications. We also consider extensions of GAE and VGAE models for dynamic graphs. Furthermore, we argue that GAE and VGAE models are often unnecessarily complex, and we propose to simplify them by leveraging linear encoders. Lastly, we introduce Modularity-Aware GAE and VGAE to improve community detection on graphs, while jointly preserving good performances on link prediction. In the last part of this thesis, we evaluate our methods on several graphs extracted from the music streaming service Deezer. We put the emphasis on graph-based music recommendation problems. In particular, we show that our methods can improve the detection of communities of similar musical items to recommend to users, that they can effectively rank similar artists in a cold start setting, and that they permit modeling the music genre perception across cultures.
Adversarial Bandits against Arbitrary Strategies
Venue: arXiv cs.LG 2025
Year: 2025

We study the adversarial bandit problem against arbitrary strategies, where the difficulty is captured by an unknown parameter $S$, which is the number of switches in the best arm in hindsight. To handle this problem, we adopt the master-base framework using the online mirror descent method (OMD). We first provide a master-base algorithm with simple OMD, achieving $\tilde{O}(S^{1/2}K^{1/3}T^{2/3})$, in which $T^{2/3}$ comes from the variance of loss estimators. To mitigate the impact of the variance, we propose using adaptive learning rates for OMD and achieve $\tilde{O}(\min\{\sqrt{SKTρ},S\sqrt{KT}\})$, where $ρ$ is a variance term for loss estimators.
Learnable Patchmatch and Self-Teaching for Multi-Frame Depth Estimation in Monocular Endoscopy
Venue: arXiv cs.CV 2025
Year: 2025

This work delves into unsupervised monocular depth estimation in endoscopy, which leverages adjacent frames to establish a supervisory signal during the training phase. For many clinical applications, e.g., surgical navigation, temporally correlated frames are also available at test time. Due to the lack of depth clues, making full use of the temporal correlation among multiple video frames at both phases is crucial for accurate depth estimation. However, several challenges in endoscopic scenes, such as low and homogeneous textures and inter-frame brightness fluctuations, limit the performance gain from the temporal correlation. To fully exploit it, we propose a novel unsupervised multi-frame monocular depth estimation model. The proposed model integrates a learnable patchmatch module to adaptively increase the discriminative ability in regions with low and homogeneous textures, and enforces cross-teaching and self-teaching consistencies to provide efficacious regularizations towards brightness fluctuations. Furthermore, as a byproduct of the self-teaching paradigm, the proposed model is able to improve the depth predictions when more frames are input at test time. We conduct detailed experiments on multiple datasets, including SCARED, EndoSLAM, Hamlyn and SERV-CT. The experimental results indicate that our model exceeds the state-of-the-art competitors. The source code and trained models will be publicly available upon the acceptance.
Efficient Self-supervised Vision Pretraining with Local Masked Reconstruction
Venue: arXiv cs.CV 2025
Year: 2025

Self-supervised learning for computer vision has achieved tremendous progress and improved many downstream vision tasks such as image classification, semantic segmentation, and object detection. Among these, generative self-supervised vision learning approaches such as MAE and BEiT show promising performance. However, their global masked reconstruction mechanism is computationally demanding. To address this issue, we propose local masked reconstruction (LoMaR), a simple yet effective approach that performs masked reconstruction within a small window of 7$\times$7 patches on a simple Transformer encoder, improving the trade-off between efficiency and accuracy compared to global masked reconstruction over the entire image. Extensive experiments show that LoMaR reaches 84.1% top-1 accuracy on ImageNet-1K classification, outperforming MAE by 0.5%. After finetuning the pretrained LoMaR on 384$\times$384 images, it can reach 85.4% top-1 accuracy, surpassing MAE by 0.6%. On MS COCO, LoMaR outperforms MAE by 0.5 $\text{AP}^\text{box}$ on object detection and 0.5 $\text{AP}^\text{mask}$ on instance segmentation. LoMaR is especially more computation-efficient on pretraining high-resolution images, e.g., it is 3.1$\times$ faster than MAE with 0.2% higher classification accuracy on pretraining 448$\times$448 images. This local masked reconstruction learning mechanism can be easily integrated into any other generative self-supervised learning approach. Our code is publicly available in https://github.com/junchen14/LoMaR.