Stable matching mechanisms are fundamental to market design but face an inherent tension between stability and social welfare optimality. We study a natural relaxation of stability, termed α-stability, which models agents as willing to deviate only when the potential improvement is sufficiently large. Under α-stability, no pair of agents can deviate and improve their valuations by more than a factor of 1/α, with α ∈ (0,1]. We provide a complete characterization of the stability--efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry μ ∈ (0,1], which bounds the ratio between agents’ valuations for any pair. Our results show that relaxing stability can substantially improve achievable efficiency guarantees. We further present a polynomial-time algorithm that computes an α-stable matching attaining the best possible efficiency guarantee. For α ≤ μ/(μ+1), our algorithm achieves 1-efficiency; for larger α, it computes an α-stable matching achieving at least (1/α) · μ/(μ+1) of the optimal social welfare. Remarkably, our algorithm inflates the values of an optimal matching and then applies the Gale–Shapley algorithm to the modified instance. Finally, we show that computing an optimal α-stable matching is NP-hard, even under slight relaxations of stability, i.e., for α close to 1.
论文检索
输入标题、作者或关键词，从 100,903 篇学术成果中精准定位
Active learning aims to maximize model performance with minimal annotation costs by selecting the most informative samples from large unlabeled pools, which often face a budget dilemma: uncertainty-based methods induce redundancy under low budgets, while representativeness-based methods struggle to mine challenging samples under high budgets. Although some heuristic parameter interpolation schemes attempt to bridge this gap, such strategies suffer from a misalignment between theoretical assumptions and real-world distributions, failing to achieve a good exploration-exploitation balance across all scenarios. In this paper, we propose a general active learning framework based on Distribution-Aware Energy Minimization, which reformulates sample selection as minimizing the energy function for the distributional discrepancy between the selected subset and the global uncertainty field. This physical-inspired perspective naturally derives a Hamiltonian comprising attractive terms and repulsive terms, mathematically achieving an intrinsic and dynamic balance between uncertainty and representativeness. Furthermore, we transform the optimization objective to the ground-state search of an Ising Model, enabling efficient solutions via Coherent Ising Machine. Extensive numerical experiments show that our method outperforms prior state-of-the-art methods across multi-budget regimes on several benchmark datasets. Validation on a real quantum hardware also demonstrates the potential for quantum computer in future large-scale selection tasks.
This research addresses the problem of adaptive modeling in time-series data streams with clear input-output relationships. This problem is challenging because rapid system changes (regime shifts) caused by environmental factors or input delay changes degrade model performance, and the trade-off among accuracy, robustness, and memory usage arises when using multiple small models for each time-series pattern. To address these issues, this paper presents an online framework/method that treats streaming time series as dynamic mixtures of time-delay systems. This framework maintains robustness of model tracking and reduces memory usage by summarizing past regimes using a fixed-length representation that captures both the system dynamics and input-output delays. Concretely, this approach constructs a summary system tensor using the system's Markov parameter series, capturing both dynamic behavior and delay characteristics. If necessary, a tensor decomposition algorithm extracts relevant past models from the tensor and helps select the system that best fits the current regime. This method enables rapid adaptation to environmental changes and is computationally efficient. Tests on real datasets show that DelayMix consistently outperforms other methods, achieving superior forecast accuracy and faster adaptation to delays, especially for highly non-stationary data.
Physiological signals such as EEG, ECG, and PPG are widely used in clinical monitoring. Recent self-supervised learning (SSL) methods offer an attractive way to leverage unlabeled recordings, yet they still fall short in practice. In particular, current SSL methods struggle across heterogeneous datasets, often distorting clinically meaningful structures or learning shortcuts from temporal and cross-channel redundancy. Consequently, existing SSL methods often deliver limited performance under linear probing, a lightweight adaptation setting that better matches real-world medical scenarios. Moreover, most Transformer-based SSL models encode a flattened spatiotemporal token sequence, incurring high computation and memory cost, and are typically developed within a single modality. To address these limitations, we present SPOTR (Spatio-temporal Pooling One-Token Reconstruction), a compress-reconstruct pretraining framework that introduces a single-token global bottleneck for physiological signals. SPOTR compresses each waveform into a single-token representation and reconstructs the signal conditioned only on this representation. Meanwhile, SPOTR introduces an efficient spatio-temporal compaction module to reduce computation and memory cost. Pretrained on 20 datasets spanning EEG, iEEG, ECG, and PPG, SPOTR consistently outperforms the strongest baseline under linear probing, improving average AUC by 18.49%, 21.71%, 17.86%, and 4.64%, respectively. Compared with a representative general-purpose time-series foundation model, SPOTR achieves around 78% lower latency and 52% lower peak GPU memory on average. The code and supplementary material can be found at https://github.com/5GYYYYY/SPOTR.
Integration of Answer Set Programming (ASP) with neural networks has emerged as a promising tool in Neuro-symbolic AI. While existing approaches extend the capabilities of ASP to real world domains, their reasoning pipelines depend on classical solvers, which is a bottleneck for scalability. To tackle this problem, we propose a new method to compute stable models, called decision-propagation (DProp), which alternates falsity decisions and truth propagations. Successful DProp computations are shown to capture the stable model semantics. We then develop Neural DProp (NDProp), a differentiable extension of DProp with neural computation for decisions and fuzzy evaluation for propagations. We evaluate the capabilities of NDProp for learning decision heuristics as well as neuro-symbolic integration, and compare it with existing neuro-symbolic approaches. The results show that NDProp can learn to efficiently compute stable models, and it improves accuracy and scalability on neuro-symbolic benchmarks.
Cross-modal brain networks characterize the complex connections between different brain regions from both functional and structural perspectives, which is of significant importance for brain network analysis and the diagnosis of brain diseases. However, existing methods have failed to fully exploit the complementary information between functional and structural brain networks, neglecting the guiding role of topology in the transmission of functional modal information, as well as the potential associations of cross-modal high-order information. To address these challenges, this paper proposes a cross-modal dynamic hypergraph computing (CDHGC) framework for brain disease diagnosis and an in-depth analysis of coupled functional-structural brain networks. The CDHGC comprises two key modules: the topology-guided dynamic hypergraph generation module, which combines the topology-constrained KNN and topology-guided centroid sampling methods to uncover high-order correlations among brain regions across modalities based on topological structure. This module dynamically optimizes the hypergraph structure during training to explore potential associations of cross-modal information. The cross-modal hypergraph convolution module efficiently aggregates information from functional-structural brain networks through a cross-modal attention mechanism during message-passing, resulting in high-order joint representations. Experiments conducted on the ADNI and ABIDE datasets demonstrate that the proposed method outperforms current state-of-the-art approaches. Interpretability analysis reveals that the proposed method can discover multi-modal biomarkers associated with brain diseases.
The Weighted Partial MaxSAT (WPMS) problem requires finding an assignment that satisfies all hard clauses while maximizing the total weight of satisfied soft clauses. From a computational perspective, WPMS is not merely an extension of the uniform-weight Partial MaxSAT (PMS); rather, it requires search strategies that actively exploit weight information to navigate the solution space. While state-of-the-art heuristic and SAT-based solvers have successfully integrated weight-aware mechanisms, Branch-and-Bound (BnB) solvers, notably WMaxCDCL, largely treat weight information passively during search and pruning. In this paper, we bridge this gap by introducing two novel weight-aware strategies into the BnB framework. Our methods integrate weight information directly into the preprocessing and lower-bound estimation. Experimental results demonstrate that these strategies significantly enhance the performance of WMaxCDCL, establishing a new state-of-the-art for exact WPMS solving.
Image-text alignment relies on large-scale, well-aligned image-text pairs, yet web-crawled datasets inevitably introduce noisy correspondence. Existing methods typically re-weight training pairs by estimating semantic matching degrees from the model's own similarity predictions, which are inherently unreliable under noise and often overestimate partially aligned pairs. To overcome this limitation, we introduce a novel semantic matching degree estimation method based on ranking consistency. Our basic idea is that for a well-aligned image-text pair (I, T), the image I and text T should occupy semantically consistent positions in the embedding space. Thus, using I and T as queries to retrieve other texts (images) should yield two highly consistent rankings. Therefore, we reweight the training paris by measuring the Normalized Discounted Cumulative Gain (NDCG) between its cross-modal and intra-modal retrieval results. This signal is derived from the global data manifold structure rather than point-wise predictions, making it more robust to noise. Experiments on multiple cross-modal retrieval benchmarks validate the effectiveness of our method. Code is available at https://github.com/Aliinton/RCR.
Riemannian optimization has attracted increasing attention recently as it is related to a variety of machine learning problems, including principal component analysis, dictionary learning, and mixture modeling. To tackle modern large-scale machine learning tasks, distributed learning is usually considered as an effective solution that trains a global model over multiple worker nodes collaboratively to enhance the computational power. Centralized learning and decentralized learning are two types of distributed learning. Centralized learning employs a central parameter server to coordinate the training process while in decentralized learning, each worker only communicates with its peer neighbors. In this paper, we propose accelerated distributed Riemannian stochastic gradient descent algorithms with random shuffling in the cases of both centralized and decentralized learning. We improve the stochastic first-order oracle complexity of the Riemannian SGD from to where is the size of training data. We conduct an experiment of the leading eigenvector problem under the condition of centralized learning and decentralized learning to validate the performance of our methods.
Dynamic systems in AI are often complex and heterogeneous, so that an internal specification is not accessible and hence verification techniques like model checking are not applicable. Monitoring is in such cases an attractive alternative, as it deals with the observation of desirable properties along traces generated by an unknown dynamic system. In this work, we consider anticipatory monitoring of linear-time properties enriched with an arbitrary SMT theory over finite traces (data-LTLf). Anticipatory monitoring in this setting is a highly challenging problem and undecidable in general, as the monitoring state depends on both the trace prefix seen so far and all its possible finite continuations. Under reasonable assumptions on the background theory, we present and formally prove the correctness of a novel foundational framework for monitoring data-LTLf properties. The framework combines automata-theoretic methods to handle the temporal aspects of reasoning with automated reasoning techniques to address the first-order dimension. Moreover, we identify for the first time decidable fragments of this monitoring problem that are practically relevant as they combine linear arithmetic with uninterpreted functions, which covers e.g. data-aware business processes and dynamic systems operating over a database. Feasibility is witnessed by a prototype implementation and preliminary evaluation.
The scarcity of paired gene expression and pathology images datasets poses a major bottleneck for training large-scale pathology foundation models. Although gene-to-image generative models offer a promising solution, existing methods typically employ coarse-grained conditional control strategies, resulting in entanglement between background textures and cell layouts. To address this challenge, we propose GeneCaDiff, a three-stage cascaded diffusion model that explicitly aligns the generative process with the hierarchical organization of biological tissues. Two conditional DDPMs independently synthesize tissue backgrounds and cellular foreground components, and a subsequent ControlNet-based fusion generator utilizes niche and cellular community maps as dual conditions to synthesize realistic tissue images. Quantitative and qualitative evaluations demonstrate strong realism and diversity, while controllability experiments validate hierarchical, decoupled control over niche textures and community layouts.
Retrieval-Augmented Generation (RAG) systems have demonstrated remarkable effectiveness in mitigating hallucinations by incorporating external knowledge. However, the retrieval process inevitably introduces noise, posing significant challenges to RAG robustness. Fundamentally, noise robustness is a composite competency encompassing noise identification, retrieval filtering, and robust reasoning. Unfortunately, existing methods often fail to capture this holistic nature, typically restricted to single-dimensional enhancements or hampered by noise-induced optimization interference. To address these limitations, we decompose RAG robustness into three sub-tasks: knowledge boundary perception, retrieval verification, and robust reasoning. Accordingly, we propose ARMOR, an Adaptive Curriculum Meta-Learning for Noise-Robust RAG Reasoning. Inspired by the teaching process, ARMOR introduces an adaptive task scheduler as a "Teacher" to curate training plans according to the absolute learning progress of the model ("student"). Distinct from GRPO, ARMOR utilizes inter-group advantage estimation during learning to effectively mitigate mode collapse caused by limited output spaces. Experiments on three noise-injected complex reasoning datasets (2WikiMultiHopQA, MusiQue, and HotPotQA) indicate that ARMOR achieves synergistic improvements in retrieval noise robustness, significantly outperforming baselines in output quality.
Federated learning (FL) enables collaborative training of deep models while keeping raw data on local devices. A critical factor affecting the global performance is server-side aggregation. The most common strategy weights client updates by the amount of local data, which is often unreliable as the server cannot inspect data. More importantly, it ignores substantial variations in data quality (e.g., label noise) across heterogeneous clients. To address this issue, we propose a data-Quality-aware aggregation framework by introducing an Evolutionary-computation-inspired design into Federated learning (FedEvoQ), with a lightweight dual-branch architecture. Each client trains a main-task branch as usual, while a frozen auxiliary branch (EvoQ) performs evolutionary-style controlled sampling with crossover and mutation at the input and representation level to probe data diversity and reliability. EvoQ outputs a compact quality score that jointly reflects learnability (loss-based signal), geometric consistency (stability under perturbations), representation diversity, and out-of-distribution (OOD) deviation, enabling the server to compute quality-only aggregation weights. Extensive experiments on CIFAR10, CIFAR100, and PathMNIST under noisy and Non-independent and identically distributed (Non-IID) settings demonstrate that FedEvoQ consistently outperforms 10 state-of-the-art (SOTA) federated aggregation methods, improving the average test accuracy of the global model by over 2% with modest overhead.
We propose the notion of statistically likely k-step reachable set in probabilistic programs, a statistically robust notion for high-probability k-step reachable program states. We design an inductive algorithm to capture this set as a symbolic representation in propositional logic for Boolean probabilistic programs. Our methodology iteratively learns a symbolic formula for the statistically likely k-step reachable set that involves (a) learning an initial symbolic candidate via decision tree learning, (b) collecting positive and negative counterexamples via forward and backward verification checks, and (c) refining the current candidate via a sequence of prune and split moves on the decision tree. We demonstrate that the statistically likely k-step reachable set can reveal interesting properties about programs by studying probabilistic programs from the literature.
In this paper, we introduce novel tuple inconsistency measures that quantify the extent to which individual tuples contribute to violations of denial constraints in inconsistent databases. Then, we formally show that one of the proposed measures fully satisfies a set of well-motivated axiomatic properties. As an application, we lift tuple inconsistency to the level of query answers, obtaining a principled framework for measuring and explaining the inconsistency inherent in query results. We further investigate the computational complexity of tuple and answer inconsistency measures under denial constraints, identifying tractable cases that make their application to real-world data feasible. Finally, our experimental study on varying dataset- and inconsistency-settings demonstrates that, in comparison to existing methods, the proposed measures yield more fine-grained and informative assessments of inconsistency in databases.
Object detection in high-resolution wide (HRW) shots presents unique challenges due to the extreme sparsity of objects and the variability in sparsity ratios across images. Conventional detectors, designed for close-up settings like MS COCO, struggle to generalize to these scenarios, leading to inefficient computation and degraded performance. While prior work has focused on spatial sparsity, the potential of sparsity in the channel dimension remains largely underexplored. In this paper, we propose ThinFormer, a dynamic and efficient framework tailored for object detection in HRW shots. ThinFormer leverages sparsity in both the spatial domain and the channel domain, the latter enabled by a novel local feed-forward network (local FFN) that exploits the duality between spatial and channel representations. To adapt to varying levels of scene complexity, we introduce a dynamic sparsity ratio estimator, trained in a self-supervised manner, which guides selective activation of channels based on semantic richness. Extensive experiments on the PANDA benchmark demonstrate that ThinFormer significantly reduces computational cost while maintaining competitive detection performance compared to state-of-the-art methods. Our results highlight the effectiveness of embracing multi-domain sparsity for scalable and robust object detection in complex, real-world HRW imagery. Code and supplementary material are available at https://github.com/LiuKunpeng03/Thinformer.
Cross-domain Named Entity Recognition (CD-NER) aims to transfer the rich knowledge in the source domain to the target domain. Recent studies adopting decomposition or generation paradigms have achieved significant performance improvements, demonstrating high accuracy in entity span detection. However, during entity type classification, models severely suffer from entity type confusion, the erroneous tendency that models classify entities of one type in the text as another similar but incorrect type. To address this issue, we first propose a Multidimensional Confusion Quantification Model (MCQM) that quantifies a model's confusion extent between entity types from three dimensions: source-target hierarchy analysis, semantic similarity analysis, and explicit data evaluation. Moreover, we propose the Progressive Bidirectional Reasoning Chain (PBRC). PBRC leverages the source-target hierarchy and confusion analysis from the MCQM to prompt the LLM to generate two-stage reasoning information. The two-stage reasoning information is utilized to augment the knowledge of the model, significantly mitigating entity type confusion and improving the model's generalization performance. Experimental results demonstrate that our method achieves new state-of-the-art results on all domains of the CrossNER dataset.
Subword tokenization is a standard technique for pre-trained language models, mapping text into sequences of tokens from a fixed-size vocabulary. Despite its widespread use, the impact of tokenization algorithms and vocabulary sizes on downstream performance remains underexplored, particularly for low- and medium-resource languages, where suboptimal configurations are difficult to compensate with additional data. Prior studies have mainly focused on high-resource languages, individual tokenization algorithms, or fixed vocabulary sizes, limiting their scope. In this paper, we present a systematic evaluation of subword tokenization strategies in six diverse low- and medium-resource languages: Icelandic, Estonian, Basque, Galician, Nepali, and Tajik. We pre-trained monolingual TEAMS-Small models using WordPiece, BPE, and Unigram tokenizers with vocabulary sizes of 16k, 32k, and 64k, and additionally compared byte-level and character-level tokenization for Icelandic. Evaluation on a benchmark of NLP tasks revealed that Unigram tokenization with a 64k vocabulary consistently outperformed other configurations, with vocabulary size having a greater impact on downstream performance than algorithm choice. These gains were task-dependent, with statistically significant improvements for part-of-speech tagging, named entity recognition, and question answering, but not for dependency parsing and summarization. Finally, byte-level tokenization provided no measurable advantage in a monolingual setting, suggesting that its benefits are primarily relevant for multilingual models.
Envy-free (EF) allocation is a fundamental problem at the intersection of theoretical computer science and economics. When resources are indivisible, achieving an EF allocation is often impossible. A common remedy is to compensate agents with subsidies. Brustle et al. proved that a total subsidy of n-1 is both necessary and sufficient to guarantee EF in the worst case, where n is the number of agents and each agent has additive valuations with marginal values of at most 1 per item. In this paper, we consider a constrained setting, namely graph orientation, that was recently introduced by Christodoulou et al. In this model, agents correspond to vertices in a multigraph, and resources correspond to edges, with each edge allocated to one of its two incident agents. Despite extensive study of the graph orientation model, it remains unclear how much subsidy is sufficient to guarantee EF. We show that a total subsidy of n/2 is always sufficient to guarantee EF in any multigraph, halving the subsidy required in the unconstrained setting, and provide a polynomial-time algorithm to compute such an allocation. We show that this bound is tight, even for simple graphs.
Persuasive dialogue aims to alter people's attitudes or behaviors through conversation. While LLMs can generate emotional responses, they tend to use a uniform approach across varied scenarios, limiting their persuasive effectiveness. Diverse demands need varied persuasion strategies, which challenge both LLMs and human efforts. To address this, this paper incorporates the idea of meta-learning and proposes PersuHMM, an iterative learning approach for constructing the Hierarchical Meta-strategy Memory to generate Persuasive dialogue. Through the interaction between Meta‑layer and Task‑layer, the approach continuously accumulates automated meta‑strategies from generated outcomes and data labels, forming a persuasive meta‑strategy memory that balances efficiency and generalizability. To facilitate model retrieval and use, the meta-strategy memory is hierarchically organized via clustering for a clearer and more logical storage structure. Experimental results show that the hierarchical meta-strategy memory enhances both the persuasiveness and generalizability of the persuasion model, and even enables cross-model performance improvement.