United States

List Update is a fundamental problem in online algorithms, with a well-known $2$-competitive algorithm that moves every requested element to the front. Randomization can slightly improve the competitive ratio to $1.6$, but not beyond $1.5$. However, practical inputs are not adversarial and one hopes to do better, particularly when additional information from a machine learning oracle is available. With access to predictions, the goal is to incur only a slight overhead compared to the prediction&#39;s accuracy, avoiding significant costs in case of substantial deviation.

We propose a $(1+\epsilon)$-smooth randomized algorithm, offering robustness of $O(1/\epsilon^4)$. This guarantees that the algorithm never exceeds a cost greater than $1+\epsilon$ times the prediction cost, while maintaining a bound within $O(1/\epsilon^4)$ of the optimal cost for every possible sequence. In cases where no paid swaps are permitted for the prediction, we can improve robustness to $O(1/\epsilon^2)$ while retaining $1+\epsilon$ smoothness. We complement these findings by demonstrating a lower bound of $\Omega(1/\epsilon)$ on the robustness for deterministic algorithms and $\Omega(\log(1/\epsilon))$ for randomized ones. 
Finally, the experiments we have made show that our algorithms perform better than the standard competitive algorithms for this problem.

AAAI 2025

List Update with Prediction

online learning bandits

List Update is a fundamental problem in online algorithms, with a well-known $2$-competitive algorithm that moves every requested element to the front. Randomization can slightly improve the competitive ratio to $1.6$, but not beyond $1.5$. However, practical inputs are not adversarial and one hopes to do better, particularly when additional information from a machine learning oracle is available. With access to predictions, the goal is to incur only a slight overhead compared to the prediction's accuracy, avoiding significant costs in case of substantial deviation.

We propose a $(1+\epsilon)$-smooth randomized algorithm, offering robustness of $O(1/\epsilon^4)$. This guarantees that the algorithm never exceeds a cost greater than $1+\epsilon$ times the prediction cost, while maintaining a bound within $O(1/\epsilon^4)$ of the optimal cost for every possible sequence. In cases where no paid swaps are permitted for the prediction, we can improve robustness to $O(1/\epsilon^2)$ while retaining $1+\epsilon$ smoothness. We complement these findings by demonstrating a lower bound of $\Omega(1/\epsilon)$ on the robustness for deterministic algorithms and $\Omega(\log(1/\epsilon))$ for randomized ones. 
Finally, the experiments we have made show that our algorithms perform better than the standard competitive algorithms for this problem.

poster

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.



In this paper, we offer a learning framework in which the agent’s knowledge gaps are overcome through corrective feedback from a teacher whenever the agent explains its (incorrect) predictions. We test it in a low-resource scenario in visual processing, in which the agent must learn to recognize distinct types of toy trucks. The agent starts the learning process with no ontology about what types of trucks exist nor which parts they have, and a deficient model for recognizing those parts from visual data. The teacher’s feedback to the agent’s explanations addresses its lack of relevant knowledge in the ontology via a generic rule (e.g., “dump trucks have dumpers”), whereas an inaccurate part recognition is corrected by a deictic statement (e.g., “this is not a dumper”). The learner utilizes this feedback not only to improve its estimate of the hypothesis space of possible domain ontologies and probability distributions over them, but also uses those estimates to update its visual interpretation of the scene. Our experiments demonstrate that teacher-learner pairs utilizing explanations and corrections are more data-efficient than those without such a faculty.

Learning Visually Grounded Domain Ontologies via Embodied Conversation and Explanation

Multimodal learning with incomplete modality is practical and challenging. Recently, multimodal prompt-based methods that introduce learnable prompts for missing-modality scenarios have exhibited impressive performance. However, these methods face several unresolved limitations: (1) incomplete modalities provide restricted modal cues for task-specific inference; (2) dummy imputation for missing content causes information loss and introduces additional noise; and (3) static prompts are instance-agnostic, offering limited knowledge for instances with various modal conditions. To address these issues, we propose RAGPT, a novel Retrieval-AuGmented dynamic Prompt Tuning framework. Specifically, RAGPT comprises three key modules: the multi-channel retriever, which identifies similar instances through within-modality retrieval relevance; the missing modality generator, designed to recover missing information using retrieved contexts; and the context-aware prompter, which captures contextual knowledge from relevant instances and generates adaptive prompts to largely enhance the model’s robustness. The framework maintains a model-agnostic design, facilitating seamless integration with various prompt-based models. Extensive experiments conducted on real-world datasets demonstrate that RAGPT, with a mere 3\% of the trainable parameters, consistently outperforms all competitive baselines in handling incomplete modality problems.

Retrieval-Augmented Dynamic Prompt Tuning for Incomplete Multimodal Learning

Learned lossless image compression has achieved significant advancements in recent years. However, existing methods often rely on training amortized generative models on massive datasets, resulting in sub-optimal probability distribution estimation for specific testing images during encoding process.  To address this challenge, we explore the connection between the Minimum Description Length (MDL) principle and Parameter-Efficient Transfer Learning (PETL), leading to the development of a novel content-adaptive approach for learned lossless image compression, dubbed CALLIC. Specifically, we first propose a content-aware autoregressive self-attention mechanism by leveraging convolutional gating operations, termed Masked Gated ConvFormer (MGCF), and pretrain MGCF on training dataset. Cache then Crop Inference (CCI) is proposed to accelerate the coding process. During encoding, we decompose pretrained layers, including depth-wise convolutions, using low-rank matrices and then adapt the incremental weights on testing image by Rate-guided Progressive Fine-Tuning (RPFT). RPFT fine-tunes with gradually  increasing patches that are sorted in descending order by estimated entropy, optimizing learning process and reducing adaptation time. Extensive experiments across diverse datasets demonstrate that CALLIC sets a new state-of-the-art for learned lossless image compression.

CALLIC: Content Adaptive Learning for Lossless Image Compression

Dynamic Music Emotion Recognition (DMER) aims to predict the emotion of different moments in music, playing a crucial role in music information retrieval. The existing DMER methods struggle to capture long-term dependencies when dealing with sequence data, which limits their performance. Furthermore, these methods often overlook the influence of individual differences on emotion perception, even though everyone has their own personalized emotional perception in the real world. Motivated by these issues, we explore more effective sequence processing methods and introduce the Personalized DMER (PDMER) problem, which requires models to predict emotions that align with personalized perception. Specifically, we propose a Dual-Scale Attention-Based Meta-Learning (DSAML) method. This method fuses features from a dual-scale feature extractor and captures both short and long-term dependencies using a dual-scale attention transformer, improving the performance in traditional DMER. To achieve PDMER, we design a novel task construction strategy that divides tasks by annotators. Samples in a task are annotated by the same annotator, ensuring consistent perception. Leveraging this strategy alongside meta-learning, DSAML can predict personalized perception of emotions with just one personalized annotation sample. Our objective and subjective experiments demonstrate that our method can achieve state-of-the-art performance in both traditional DMER and PDMER.

Personalized Dynamic Music Emotion Recognition with Dual-Scale Attention-Based Meta-Learning

Compositional relational reasoning (CRR) is a hallmark of human intelligence, but we lack a clear understanding of whether and how existing transformer large language models (LLMs) can solve CRR tasks. To enable systematic exploration of the CRR capability of LLMs, we first propose a new synthetic benchmark called Generalized Associative Recall (GAR) by integrating and generalizing the essence of several tasks in mechanistic interpretability (MI) study in a unified framework. Evaluation shows that GAR is challenging enough for existing LLMs, revealing their fundamental deficiency in CRR. Meanwhile, it is easy enough for systematic MI study. Then, to understand how LLMs solve GAR tasks, we use attribution patching to discover the core circuits reused by Vicuna-33B across different tasks, and a set of vital attention heads. Intervention experiments show that the correct functioning of these heads significantly impacts task performance. Especially, we identify two classes of heads whose activations represent the abstract notion of true and false in GAR tasks respectively. They play fundamental roles in CRR across various models and tasks.

Benchmarking and Understanding Compositional Relational Reasoning of LLMs

While pruning methods effectively maintain model perfor-
mance without extra training costs, they often focus solely
on preserving crucial connections, overlooking the impact
of pruned weights on subsequent fine-tuning or distillation,
leading to inefficiencies. Moreover, most compression tech-
niques for generative models have been developed primarily
for GANs, tailored to specific architectures like StyleGAN,
and research into compressing Diffusion models has just be-
gun. Even more, these methods are often applicable only to
GANs or Diffusion models, highlighting the need for ap-
proaches that work across both model types. In this paper, we introduce Singular Value Scaling (SVS), a versatile technique for refining pruned weights, applicable to both model types. Our analysis reveals that pruned weights often exhibit dominant singular vectors, hindering fine-tuning efficiency and leading to suboptimal performance compared to random initialization. Our method enhances weight initialization by minimizing the disparities between singular values of pruned
weights, thereby improving the fine-tuning process. This approach not only guides the compressed model toward superior solutions but also significantly speeds up fine-tuning. Extensive experiments on StyleGAN2, StyleGAN3 and DDPM demonstrate that SVS improves compression performance across model types without additional training costs.

Singular Value Scaling: Efficient Generative Model Compression via Pruned Weights Refinement

This paper studies decentralized optimization over a compact submanifold within a communication network of $n$ nodes, where each node possesses a smooth non-convex local cost function, and the goal is to jointly minimize the sum of these local costs. We focus particularly on the online setting, where local data is processed in real-time as it streams in, without the need for full data storage. We propose a decentralized projected Riemannian stochastic recursive momentum (DPRSRM) method that employs local hybrid stochastic gradient estimators and uses the network to track the global gradient. DPRSRM achieves an oracle complexity of  $\mathcal{O}(\epsilon^{-\frac{3}{2}})$, outperforming existing methods that have at most $\mathcal{O}(\epsilon^{-2})$ complexity. Our method requires only $\mathcal{O}(1)$ gradient evaluations per iteration for each local node and does not require restarting with a large batch gradient.   Furthermore, we demonstrate the effectiveness of our proposed methods compared to state-of-the-art ones through numerical experiments on principal component analysis problems and low-rank matrix completion.

Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization

While Nash equilibria are guaranteed to exist, they may exhibit dense support, making them difficult to understand and execute in some applications. In this paper, we study $k$-sparse commitments in games where one player is restricted to mixed strategies with support size at most $k$. Finding $k$-sparse commitments is known to be computationally hard. We start by showing several structural properties of $k$-sparse solutions, including that the optimal support may vary dramatically as $k$ increases. These results suggest that naive greedy or double-oracle-based approaches are unlikely to yield practical algorithms. We then develop a simple approach based on mixed integer linear programs (MILPs) for zero-sum games, general-sum Stackelberg games, and various forms of structured sparsity. We also propose practical algorithms for cases where one or both players have large (i.e., practically innumerable) action sets, utilizing a combination of MILPs and incremental strategy generation. We evaluate our methods on synthetic and real-world scenarios based on security applications. In both settings, we observe that even for small support sizes, we can obtain more than $90\%$ of the true Nash value while maintaining a reasonable runtime, demonstrating the significance of our formulation and algorithms.

Commitment to Sparse Strategies in Two-Player Games

REST APIs have become key components of web services. However, they often contain logic flaws resulting in server side errors or security vulnerabilities. HTTP requests are used as test cases to find and mitigate such issues. Existing methods to modify requests, including those using deep learning, suffer from limited performance and precision, relying on undirected search or making limited usage of the contextual information. In this paper we propose APIRL, a fully automated deep reinforcement learning tool for testing REST APIs. A key novelty of our approach is the use of feedback from a transformer moudle pre-trained on JSON-structured data, akin to that used in API responses. This allows APIRL to learn the subtleties relating to test outcomes, and generalise to unseen API endpoints. We show APIRL can find significantly more bugs than the state-of-the-art in real world REST APIs while minimising the number of required test cases. We also study how reward functions, and other key design choices, affect learnt policies in a thorough ablation study.

APIRL: Deep Reinforcement Learning for REST API Fuzzing

These recent years have witnessed that convolutional neural network (CNN)-based methods for detecting infrared small targets have achieved outstanding performance. However, these methods typically employ standard convolutions, neglecting to consider the spatial characteristics of the pixel distribution of infrared small targets. Therefore, we propose a novel Pinwheel-shaped Convolution (PConv) as a replacement for standard convolutions in the lower layers of the backbone network. PConv better aligns with the pixel gaussian spatial distribution of dim small targets, enhances feature extraction, significantly increases the receptive field, and introduces only a minimal increase in parameters.
Additionally, while recent loss functions combine scale and location losses, they do not adequately account for the varying sensitivity of these losses across different target scales, limiting detection performance on dim-small targets. To overcome this, we propose a Scale-based Dynamic (SD) Loss that dynamically adjusts the influence of scale and location losses based on target size, improving the network’s ability to detect targets of varying scales.
We construct a new benchmark, SIRST-UAVB, which is the largest and most challenging dataset to date for real-shot single-frame infrared small target detection. Lastly, by integrating PConv and SD Loss into the latest small target detection algorithms, we achieved significant performance improvements on IRSTD-1K and our SIRST-UAVB dataset, validating the effectiveness and generalizability of our approach.

List Update with Prediction

Downloads

Next from AAAI 2025

Learning Visually Grounded Domain Ontologies via Embodied Conversation and Explanation