United States

We consider a class of optimization problems defined by a system of linear equations with min and max operators. 
	This class of optimization problems has been studied under restrictive conditions, such as,
    (C1) the halting or stability condition;
    (C2) the non-negative coefficients condition;
    (C3) the sum upto $1$ condition; and
    (C4) the only min or only max operator condition.
	Several seminal results in the literature focus on special cases.
	For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4.
	However, the systematic computational complexity study of all the cases has not been explored, which we address in this work.
	Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is \textsc{NP}-complete, whereas with condition C1 only, the problem is in \textsc{UP} $\cap$ \textsc{coUP}.
	Finally, we establish the computational complexity of the decision problem of checking the respective conditions.

AAAI 2025

Linear Equations with Min and Max Operators: Computational Complexity

mixed discrete continuous optimization

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Recent literature uses language to build foundation models for audio. These Audio-Language Models (ALMs) are trained on a vast number of audio-text pairs and show remarkable performance in tasks including Text-to-Audio Retrieval, Captioning, and Question Answering. However, their ability to engage in more complex open-ended tasks, like Interactive Question-Answering, requires proficiency in logical reasoning-- a skill not yet benchmarked. We introduce the novel task of Audio Entailment to evaluate an ALM's deductive reasoning ability. This task assesses whether a text description (hypothesis) of audio content can be deduced from an audio recording (premise), with potential conclusions being entailment, neutral, or contradiction, depending on the sufficiency of the evidence. We create two datasets for this task with audio recordings sourced from two audio captioning datasets-AudioCaps and Clotho-and hypotheses generated using Large Language Models (LLMs). We benchmark state-of-the-art ALMs and find deficiencies in logical reasoning with both zero-shot and linear probe evaluations. Finally, we propose "caption-before-reason", an intermediate step of captioning that improves the Zero-Shot and linear-probe performance of ALMs by an absolute 6% and 3%, respectively.

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Personalized Federated Learning (PFL) is widely used in IoT applications to manage large-scale, non-iid client data while ensuring data privacy. However, the diverse edge devices owned by clients may impose varying degrees of resource constraints, leading to computation and communication bottlenecks for PFL. To tackle this challenge, Federated Dropout has emerged as a popular strategy, where only a subset of the global model, known as a sub-model, is trained on a client's device, thereby reducing computation and communication overheads. Nevertheless, the dropout-based model-pruning strategy may introduce bias, especially towards non-iid local data. This bias can result in performance degradation when biased sub-models absorb highly divergent parameters from other clients. In response, we propose federated learning with stochastic parameter update (FedSPU). Unlike dropout, which tailors the global model to small-size local sub-models, FedSPU maintains the full model architecture on each device but randomly freezes a certain percentage of neurons in the local model during training while updating the remaining neurons. This approach ensures that a portion of the local model remains personalized, thereby enhancing the model's robustness against biased parameters from other clients. Experimental results demonstrate that FedSPU outperforms federated dropout by an average of 7.57% in terms of accuracy. Furthermore, an introduced early stopping scheme leads to a significant reduction in training time by 24.8% to 70.4% while maintaining high accuracy.

FedSPU: Personalized Federated Learning for Resource-Constrained Devices with Stochastic Parameter Update

We study the problem of computing fair divisions of a set of indivisible goods among agents with additive valuations. For the past many decades, the literature has explored various notions of fairness, that can be primarily seen as either having envy-based or share-based lens. For the discrete setting of resource-allocation problems, envy-free up to any good (EFX) and maximin share (MMS) are widely considered as the flag-bearers of fairness notions in the above two categories, thereby capturing different aspects of fairness herein. Due to lack of existence results of these notions and the fact that a good approximation of EFX or MMS does not imply particularly strong guarantees of the other, it becomes important to understand the compatibility of EFX and MMS allocations with one another.

In this work, we identify a novel way to simultaneously achieve MMS guarantees with EFX/EF1 notions of fairness, while beating the best known approximation factors (Chaudhury et al. 2021; Amanatidis, Markakis, and Ntokos 2020). Our main contribution is to constructively prove the existence of (i) a partial allocation that is both $2/3$-MMS and EFX, and (ii) a complete allocation that is both $2/3$-MMS and EF1. Our algorithms run in pseudo-polynomial time if the approximation factor for MMS is relaxed to $2/3$-$\varepsilon$ for any constant \varepsilon>0 and in polynomial time if, in addition, the EFX (or EF1) guarantee is relaxed to $(1-\delta)$-EFX (or $(1-\delta)$-EF1) for any constant $\delta>0$. In particular, we improve from the best approximation factor known prior to our work, which computes partial allocations that are $1/2$-MMS and EFX in pseudo-polynomial time (Chaudhury et al. 2021).

Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously

Self-learning of Large Language Models (LLMs) facilitates their advancement towards super-intelligence by training with self-synthesized experiences. However, a critical challenge is the amplification of hallucinations in generated data during iterative self-learning, underscoring the need for reliable data selection. To address this, we investigate the mechanism of Inner Knowledge Explicitation, which involves explicitly extracting the inner knowledge from memory of LLMs, to concurrently improves reasoning, and enables reliable self-learning data selection. This paper introduces a Self Knowledge Explicitation Learning (SKE-Learn) framework, which equips the LLMs with meta-skills to explicitly extract, verify and utilize inner knowledge for reasoning. By leveraging these meta-skills, SKE-Learn establishes a self-learning approach that ensures reliable selection of self-synthetic data. This approach enhances performance through iterative self-learning while mitigating the problem of hallucinations. Empirical results from six benchmarks demonstrate that Inner Knowledge Explicitation improves reasoning by serving as a more effective prompting method. Additionally, SKE-Learn, based on the verifiability of explicit knowledge, shows consistent performance improvements over multiple self-training iterations, with an average performance increase from 52.79% to 56.54% across all benchmarks. Furthermore, Inner Knowledge Explicitation provides explaination and intervention space during LLM's generation process. The code will be made available upon acceptance.

Empowering Self-Learning of LLMs: Inner Knowledge Explicitation as a Catalyst

Responsibility plays a key role in the development and deployment of trustworthy autonomous systems. In this paper, we focus on the problem of strategic reasoning in probabilistic multi-agent systems with responsibility-aware agents. We introduce the logic PATL+R, a variant of Probabilistic Alternating-time Temporal Logic. The novelty of PATL+R lies in its incorporation of modalities for causal responsibility, providing a framework for responsibility-aware multi-agent strategic reasoning. We present an approach to synthesise joint strategies that satisfy an outcome specified in PATL+R, while optimising the share of expected causal responsibility and reward. This provides a notion of balanced distribution of responsibility and reward gain among agents. To this end, we utilise the Nash equilibrium as the solution concept for our strategic reasoning problem and demonstrate how to compute responsibility-aware Nash equilibrium strategies via a reduction to parametric model checking of concurrent stochastic multi-player games.

Responsibility-aware Strategic Reasoning in Probabilistic Multi-Agent Systems

Rap, a prominent genre of vocal performance, remains underexplored in vocal generation. General vocal synthesis depends on precise note and duration inputs, requiring users to have related musical knowledge, which limits flexibility. In contrast, rap typically features simpler melodies, with a core focus on a strong rhythmic sense that harmonizes with accompanying beats. In this paper, we propose Freestyler, the first system that generates rapping vocals directly from lyrics and accompaniment inputs. Freestyler utilizes language model-based token generation, followed by a conditional flow matching model to produce spectrograms and a neural vocoder to restore audio. It allows a 3-second prompt to enable zero-shot timbre control. Due to the scarcity of publicly available rap datasets, we collected a large volume of rap songs from the internet and designed a meticulous pipeline for data cleaning, processing, and filtering.

Drop the Beat! Freestyler for Accompaniment Conditioned Rapping Voice Generation

Fairness and efficiency have become the pillars of modern fair division research, but prior work on achieving both simultaneously is largely limited to the unconstrained setting. We study fair and efficient allocations of indivisible goods under additive valuations and various types of allocation feasibility constraints, and demonstrate the unreasonable effectiveness of the maximum Nash welfare (MNW) solution in this previously uncharted territory. 

Our main result is that MNW allocations are 1/2-envy-free up to one good (EF1) and Pareto optimal under the broad family of (arbitrary) matroid constraints. We extend these guarantees to complete MNW allocations for base-orderable matroid constraints, and to a family of non-matroidal constraints (which includes balancedness) using a novel "alternate worlds" technique. We establish tightness of our results by providing counterexamples for the satisfiability of certain stronger desiderata, but show an improved result for the special case of goods with copies (Gafni et al. 2023). Finally, we also establish novel best-of-both-worlds guarantees for goods with copies and balancedness.

Constrained Fair and Efficient Allocations

Prototype-based federated learning has emerged as a promising approach that shares lightweight prototypes to transfer knowledge among clients with data heterogeneity in a model-agnostic manner.
However, existing methods often collect prototypes directly from local models, which inevitably introduce inconsistencies into representation learning due to the biased data distributions and differing model architectures among clients.
In this paper, we identify that both statistical and model heterogeneity create a vicious cycle of representation inconsistency, classifier divergence, and skewed prototype alignment, which negatively impacts the performance of clients.
To break the vicious cycle, we propose a novel framework named Federated Learning via Semantic Anchors (FedSA) to decouple the generation of prototypes from local representation learning.
We introduce a novel perspective that uses simple yet effective semantic anchors serving as prototypes to guide local models in learning consistent representations.
By incorporating semantic anchors, we further propose anchor-based regularization with margin-enhanced contrastive learning and anchor-based classifier calibration to correct feature extractors and calibrate classifiers across clients, achieving intra-class compactness and inter-class separability of prototypes while ensuring consistent decision boundaries.
We then update the semantic anchors with these consistent and discriminative prototypes, which iteratively encourage clients to collaboratively learn a unified data representation with robust generalization.
Extensive experiments under both statistical and model heterogeneity settings show that FedSA significantly outperforms existing prototype-based FL methods on various classification tasks.

FedSA: A Unified Representation Learning via Semantic Anchors for Prototype-based Federated Learning

Communication has been widely employed to enhance multi-agent collaboration. Previous research has typically assumed delay-free communication, a strong assumption that is challenging to meet in practice. However, real-world agents suffer from channel delays, receiving  messages sent at different time points, termed Asynchronous Communication, leading to cognitive biases and breakdowns in collaboration. This paper first defines two communication delay settings in MARL and emphasizes their harm to collaboration. To handle the above delays, this paper proposes a novel framework, Communication Delay-Tolerant Multi-Agent Collaboration (CoDe). At first, CoDe learns an intent representation as messages through future action inference, reflecting the stable future behavioral trends of the agents. Then, CoDe devises a dual alignment mechanism of intent and timeliness to strengthen the fusion process of asynchronous messages. In this way, agents can extract the long-term intent of others, even from delayed messages, and selectively utilize the most recent messages that are relevant to their intent. Experimental results demonstrate that CoDe outperforms baseline algorithms in three MARL benchmarks without delay and exhibits robustness under fixed and time-varying delays.

CoDe: Communication Delay-Tolerant Multi-Agent Collaboration via Dual Alignment of Intent and Timeliness

The accelerated MRI reconstruction process presents a challenging ill-posed inverse problem due to the extensive under-sampling in k-space. Recently, Vision Transformers (ViTs) have become the mainstream for this task, demonstrating substantial performance improvements. However, there are still three significant issues remain unaddressed: (1) ViTs struggle to capture high-frequency components of images, limiting their ability to detect local textures and edge information, thereby impeding MRI restoration; (2) Previous methods calculate multi-head self-attention (MSA) among both related and unrelated tokens in content, introducing noise and significantly increasing computational burden; (3) The naive feed-forward network in ViTs cannot model the multi-scale information that is important for image restoration. In this paper, we propose FPS-Former, a powerful ViT-based framework, to address these issues from the perspectives of frequency modulation, spatial purification, and scale diversification. Specifically, to address issue (1), we introduce a frequency modulation attention module to enhance the self-attention map by adaptively re-calibrating the frequency information in a Laplacian pyramid. For issue (2), we customize a spatial purification attention module to capture interactions among closely related tokens, thereby reducing redundant or irrelevant feature representations. For issue (3), we propose an efficient feed-forward network based on a hybrid-scale fusion strategy that effectively models multi-scale information. We conduct extensive experiments on three public datasets for MRI reconstruction under various undersampling patterns. Comprehensive results demonstrate that our FPS-Former significantly outperforms state-of-the-art methods while requiring lower computational costs. Codes will be available.

Linear Equations with Min and Max Operators: Computational Complexity

Downloads

Next from AAAI 2025

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Linear Equations with Min and Max Operators: Computational Complexity

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2025

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads