GenAI4ELab/papercli-papers huggingface dataset:
Improved Bounds for Online Facility Location with Predictions
Authors: Dimitris Fotakis; Evangelia Gergatsouli; Themistoklis Gouleakis; Nikolas Patris; Thanos Tolias
Venue: AAAI 2025 (main)

Abstract: We consider the Online Facility Location (OFL) problem in the framework of learning-augmented online algorithms. In Online Facility Location (OFL), demands arrive one-by-one in a metric space and must be (irrevocably) assigned to an open facility upon arrival, without any knowledge about future demands. We focus on uniform facility opening costs and present an online algorithm for OFL that exploits potentially imperfect predictions on the locations of the optimal facilities. We prove that the competitive ratio decreases from sublogarithmic in the number n of demands to constant as the so-called η1 error, i.e., the sum of distances of the predicted locations to the optimal facility locations, decreases towards zero. E.g., our analysis implies that if for some ε > 0, η1 = OPT / n^ε, where OPT is the cost of the optimal solution, the competitive ratio is O(1/ε). We complement our analysis with a matching lower bound establishing that the dependence of the algorithm's competitive ratio on the η1 error is optimal, up to constant factors.
ConfigX: Modular Configuration for Evolutionary Algorithms via Multitask Reinforcement Learning
Authors: Hongshu Guo; Zeyuan Ma; Jiacheng Chen; Yining Ma; Zhiguang Cao; Xinglin Zhang; Yue-Jiao Gong
Venue: AAAI 2025 (main)

Abstract: Recent advances in Meta-learning for Black-Box Optimization (MetaBBO) have shown the potential of using neural networks to dynamically configure evolutionary algorithms (EAs), enhancing their performance and adaptability across various BBO instances. However, they are often tailored to a specific EA, which limits their generalizability and necessitates retraining or redesigns for different EAs and optimization problems. To address this limitation, we introduce ConfigX, a new paradigm of the MetaBBO framework that is capable of learning a universal configuration agent (model) for boosting diverse EAs. To achieve so, our ConfigX first leverages a novel modularization system that enables the flexible combination of various optimization sub-modules to generate diverse EAs during training. Additionally, we propose a Transformer-based neural network to meta-learn a universal configuration policy through multitask reinforcement learning across a designed joint optimization task space. Extensive experiments verify that, our ConfigX, after large-scale pre-training, achieves robust zero-shot generalization to unseen tasks and outperforms state-of-the-art baselines. Moreover, ConfigX exhibits strong lifelong learning capabilities, allowing efficient adaptation to new tasks through fine-tuning. Our proposed ConfigX represents a significant step toward an automatic, all-purpose configuration agent for EAs.
Suboptimal Search with Dynamic Distribution of Suboptimality
Authors: Mohammadreza Hami; Nathan R. Sturtevant
Venue: AAAI 2025 (main)

Abstract: In bounded-suboptimal heuristic search, the aim is to find a solution path within a given bound as quickly as possible, which is crucial when computational resources are limited. Recent research has demonstrated Weighted A* variants such as XDP that find bounded suboptimal solutions without needing to perform state re-expansions; they work by shifting where the suboptimality in the search is allowed. However, the suboptimality distribution is fixed before the search begins. This paper introduces Dynamic Suboptimality Weighted A* (DSWA*), a search framework that allows suboptimality to be dynamically distributed at runtime, based on the properties of the search. Experiments show that dynamic policies can consistently outperform existing algorithms across a diverse set of domains, particularly those with dynamic costs.
Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs
Authors: Vu Viet Hoang; Quoc Anh Hoang Nguyen; Hung The Tran
Venue: AAAI 2025 (main)

Abstract: Bayesian Optimization (BO) is a widely-used method for optimizing expensive-to-evaluate black-box functions. Traditional BO assumes that the learner has full control over all query variables without additional constraints. However, in many real-world scenarios, controlling certain query variables may incur costs. Therefore, the learner needs to balance the selection of informative subsets for targeted learning against leaving some variables to be randomly sampled to minimize costs. This problem is known as Bayesian Optimization with cost-varying variable subsets (BOCVS). While the goal of BOCVS is to identify the optimal solution with minimal cost, previous works have only guaranteed finding the optimal solution without considering the total costs incurred. Moreover, these works assume precise knowledge of the cost for each subset, which is often unrealistic.  In this paper, we propose a novel algorithm for the extension of the BOCVS problem with random and unknown costs that separates the process into exploration and exploitation phases. The exploration phase will filter out low-quality variable subsets, while the exploitation phase will leverage high-quality ones. Furthermore, we theoretically demonstrate that our algorithm achieves a sub-linear rate in both quality regret and cost regret, addressing the objective of the BOCVS problem more effectively than previous analyses. Finally, we show that our proposed algorithm outperforms comparable baselines across a wide range of benchmarks.
Balanced Adaptive Subspace Collaboration for Mixed Pareto-Lexicographic Multi-Objective Problems with Priority Levels
Authors: Wenjing Hong
Venue: AAAI 2025 (main)

Abstract: Multi-objective Optimization Problems (MOPs) where objectives have different levels of importance in decision-making, known as Mixed Pareto-Lexicographic MOPs with Priority Levels (PL-MPL-MOPs), are increasingly prevalent in real-world applications. General-purpose Multi-Objective Evolutionary Algorithms (MOEAs) that treat all objectives equally not only increase the workload of decision-making but also suffer from computational inefficiencies due to the necessity of generating many additional solutions. Conversely, strictly adhering to Priority Levels (PLs) during optimization can easily result in premature convergence within some PLs. To address this issue, we suggest an effective Balanced Adaptive Subspace Collaboration (BASC) method in this paper. Specifically, this method decomposes the search space into sub-fronts based on PLs and utilizes a sampling mechanism that operates exclusively within subspaces formed by sub-fronts at the same PL to generate new solutions, thereby emphasizing the exploitation of individual PLs. Furthermore, a set of parameters is employed to control the strictness of adherence to each PL, with these parameters adaptively adjusted to balance exploration across different PLs. The two mechanisms are then collaboratively integrated into MOEAs. Comprehensive experimental studies on benchmark problems and a set of complex job-shop scheduling problems in semiconductor manufacturing demonstrate the competitiveness of the proposed method over existing methods.
Faster Double Adaptive Gradient Methods
Authors: Feihu Huang; Yuning Luo
Venue: AAAI 2025 (main)

Abstract: In this paper, we propose a class of faster double adaptive gradient methods to solve nonconvex finite-sum optimization problems possibly with nonsmooth regularization by simultaneously using adaptive learning rate and adaptive mini-batch size. Specifically, we first  propose a double adaptive stochastic gradient method (i.e., 2AdaSGD), and prove that our 2AdaSGD obtains a low  stochastic first-order oracle (SFO) complexity for finding a stationary solution under the population smoothness condition. Furthermore, we propose a variance reduced double adaptive stochastic gradient method (i.e., 2AdaSPIDER), and prove that our 2AdaSPIDER obtains an optimal SFO complexity under the average smoothness condition, which is lower than the SFO complexity of the existing double adaptive gradient  algorithms. 
In particular, we introduce a new stochastic gradient mapping to adaptively adjust mini-batch size in our stochastic gradient methods.  We conduct some numerical experiments to verify efficiency of our proposed methods.
Trading Off Quality and Uncertainty Through Multi-Objective Optimisation in Batch Bayesian Optimisation
Authors: Chao Jiang; Miqing Li
Venue: AAAI 2025 (main)

Abstract: Batch Bayesian Optimisation (BBO) has emerged as a potent approach for optimising expensive black-box functions. Central to BBO is the issue of selecting a number of solutions at the same time through a batch method, in the hope for them to represent good, yet different, trade-offs between exploitation and exploration. To address this issue, one of the recent advancements has leveraged multi-objective optimisation to simultaneously consider several acquisition functions (e.g., PI, EI, and LCB), allowing them to complement each other. However, acquisition functions may behave similarly (since they all aim for a good balance between exploitation and exploration), restricting the search on different promising areas. In this paper, we attempt to address the above issue. We directly treat exploitation (reflected by quality, i.e., the posterior mean) and exploration (reflected by uncertainty) as two objectives. When selecting trade-off solutions between the two objectives, we consider a dynamically updated Pareto front where the uncertainty changes once a solution is selected, thereby allowing exploration on different promising areas. Through an extensive experiment study, we show the effectiveness of the proposed method in comparison with state-of-the-arts in the area.
Searching for and Avoiding Hidden Sets Using Queries with Local Feedback
Authors: Tomasz Jurdzinski; Dariusz R. Kowalski
Venue: AAAI 2025 (main)

Abstract: Discovering elements of a hidden set, also known as Group Testing (GT), is a well-established area in which one party tries to discover elements hidden by the other party by asking queries and analyzing feedback. The feedback is a function of the intersection of the query with the hidden set - in our case, it is a classical double-threshold function, which returns i if the intersection is a singleton i and "null" otherwise (i.e., when the intersection is empty or of size at least 2). In this work, we enhance GT by two features. First, we introduce a local feedback framework to this problem: each hidden element is an "autonomous" element and can analyze feedback itself, but only for the queries to which it belongs. The goal is to design a deterministic non-adaptive sequence of queries that enables each non-hidden element to learn about all other hidden elements. We show that, surprisingly, this task requires substantially more queries than the classic group testing -- by proving a super-cubic (in terms of the number of hidden elements) lower bound and by constructing a specific query sequence of slightly longer length. Such a query system is also an extension of a well-known superimposed code, in a way that the decoding can be done only by the owners of the codewords. Second, we extend the results to the model where elements may belong to certain clusters and retrieving them could be done only via queries avoiding elements from "interfering" clusters. The main challenge is in not knowing which interfering clusters are non-empty (and thus, need to be avoided) and how to speed up the retrieval process by asking queries across many clusters. Our algorithms can be generalized to other feedback functions, to adversarial/stochastic fault-prone scenarios, implemented in a distributed setting and applied to the information theory and codes.
Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
Authors: Sepehr Lavasani; Lior Siag; Shahaf S. Shperberg; Ariel Felner; Nathan R. Sturtevant
Venue: AAAI 2025 (main)

Abstract: In recent years the understanding of optimal bidirectional heuristic search (BiHS) has progressed significantly. Yet, Bi-HS is relatively unexplored in unbounded suboptimal search. Front-to-end (F2E) and front-to-front (F2F) bidirectional search have been used in optimal algorithms, but adapting them for unbounded suboptimal search remains an open challenge. We introduce a framework for suboptimal BiHS, called anchor search, and use it to derive a parameterized family of algorithms. Because our new algorithms need F2F heuristic evaluations, we propose using pattern databases (PDBs) as differential heuristics (DHs) to construct F2F heuristics. Our experiments evaluate three anchor search instances across diverse domains, outperforming existing methods, particularly as the search scales.
Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game
Authors: Per Kristian Lehre; Shishen Lin
Venue: AAAI 2025 (main)

Abstract: The maximin optimisation problem, inspired by Von Neumann’s work (von Neumann 1928) and widely applied in adversarial optimisation, has become a key research area in machine learning. Gradient Descent Ascent (GDA) is a common method for solving these problems but requires the pay-off function to be differentiable, making it unsuitable for discrete or binary functions that often occur in game-theoretical scenarios. Co-evolutionary algorithms (CoEAs), which are derivative-free, offer an alternative to these problems. However, the theoretical understanding of CoEAs is still limited. 

This paper provides the first rigorous runtime analysis of CoEAs with pairwise dominance on binary two-player zero-sum games (or maximin problems), specifically focusing on the DIAGONAL game. The mathematical analysis rigorously shows that the PDCoEA can efficiently find the optimum in polynomial runtime with high probability under low mutation rates and large population sizes. Empirical evidence also identifies an error threshold where higher mutation rates lead to inefficiency. In contrast, single-pair-individual algorithms, i.e., RLS-PD and (1+1)-CoEAs, fail to find the optimum in polynomial time. These findings highlight the usefulness of pairwise dominance, low mutation rates, and large populations in maintaining a “co-evolutionary arms race”.
Expensive Multi-Objective Bayesian Optimization Based on Diffusion Models
Authors: Bingdong Li; Zixiang Di; Yongfan Lu; Hong Qian; Feng Wang; Peng Yang; Ke Tang; Aimin Zhou
Venue: AAAI 2025 (main)

Abstract: Multi-objective Bayesian optimization (MOBO) has shown promising performance on various expensive multi-objective optimization problems (EMOPs). However, effectively modeling complex distributions of the Pareto optimal solutions is difficult with limited function evaluations. Existing Pareto set learning algorithms may exhibit considerable instability in such expensive scenarios, leading to significant deviations between the obtained solution set and the Pareto set (PS). In this paper, we propose a novel Composite Diffusion Model based Pareto Set Learning algorithm (CDM-PSL) for expensive MOBO. CDM-PSL includes both unconditional and conditional diffusion model for generating high-quality samples efficiently. Besides, we introduce a weighting method based on information entropy to balance different objectives. This method is integrated with a guiding strategy to appropriately balancing different objectives during the optimization process. Experimental results on both synthetic and real-world problems demonstrates that CDM-PSL attains superior performance compared with state-of-the-art MOBO algorithms.
DELTA: Pre-Train a Discriminative Encoder for Legal Case Retrieval via Structural Word Alignment
Authors: Haitao Li; Qingyao Ai; Xinyan Han; Jia Chen; Qian Dong; Yiqun Liu
Venue: AAAI 2025 (main)

Abstract: Recent research demonstrates the effectiveness of using pre-trained language models for legal case retrieval. Most of the existing works focus on improving the representation ability for the contextualized embedding of the [CLS] token and calculate relevance using textual semantic similarity. However, in the legal domain, textual semantic similarity does not always imply that the cases are relevant enough. Instead, relevance in legal cases primarily depends on the similarity of key facts that impact the final judgment. Without proper treatments, the discriminative ability of learned representations could be limited since legal cases are lengthy and contain numerous non-key facts.
To this end, we introduce DELTA, a discriminative model designed for legal case retrieval. The basic idea involves pinpointing key facts in legal cases and pulling the contextualized embedding of the [CLS] token closer to the key facts while pushing away from the non-key facts, which can warm up the case embedding space in an unsupervised manner. To be specific, this study brings the word alignment mechanism to the contextual masked auto-encoder. First, we leverage shallow decoders to create information bottlenecks, aiming to enhance the representation ability. Second, we employ the deep decoder to enable ``translation'' between different structures, with the goal of pinpointing key facts to enhance discriminative ability. Comprehensive experiments conducted on publicly available legal benchmarks show that our approach can outperform existing state-of-the-art methods in legal case retrieval.
It provides a new perspective on the in-depth understanding and processing of legal case documents.
MetaSymNet: A Tree-like Symbol Network with Adaptive Architecture and Activation Functions
Authors: Yanjie Li; Weijun Li; Lina Yu; Min Wu; Jingyi Liu; Shu Wei; Yusong Deng; Meilan Hao
Venue: AAAI 2025 (main)

Abstract: Mathematical formulas are the language of communication between humans and nature. Discovering latent formulas from observed data is an important challenge in artificial intelligence, commonly known as symbolic regression(SR). The current mainstream SR algorithms regard SR as a combinatorial optimization problem and use Genetic Programming (GP) or Reinforcement Learning (RL) to solve the SR problem. These methods perform well on simple problems, but poorly on slightly more complex tasks. In addition, this class of algorithms ignores an important aspect: in SR tasks, symbols have explicit numerical meaning. So can we take full advantage of this important property and try to solve the SR problem with more efficient numerical optimization methods? Extrapolation and Learning Equation (EQL) replaces activation functions in neural networks with basic symbols and sparsifies connections to derive a simplified expression from a large network. However, EQL's fixed network structure can't adapt to the complexity of different tasks, often resulting in redundancy or insufficient, limiting its effectiveness. Based on the above analysis, we propose MetaSymNet, a tree-like network that employs the PANGU meta-function as its activation function. PANGU meta-function can evolve into various candidate functions during training. The network structure can also be adaptively adjusted according to different tasks. Then the symbol network evolves into a concise, interpretable mathematical expression. To evaluate the performance of MetaSymNet and five baseline algorithms, we conducted experiments across more than ten datasets, including SRBench. The experimental results show that MetaSymNet has achieved relatively excellent results on various evaluation metrics.
Fast and Interpretable Mixed-Integer Linear Program Solving by Learning Model Reduction
Authors: Yixuan Li; Can Chen; Jiajun Li; Jiahui Duan; Xiongwei Han; Tao Zhong; Vincent Chau; Weiwei Wu; Wanyuan Wang
Venue: AAAI 2025 (main)

Abstract: By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.
REM: A Scalable Reinforced Multi-Expert Framework for Multiplex Influence Maximization
Authors: Huyen Nguyen; Hieu Dam; Nguyen Hoang Khoi Do; Cong Tran; Cuong Pham
Venue: AAAI 2025 (main)

Abstract: In social online platforms, identifying influential seed users to maximize influence spread is a crucial as it can greatly diminish the cost and efforts required for information dissemination. While effective, traditional methods for Multiplex Influence Maximization (MIM) have reached their performance limits, prompting the emergence of learning-based approaches. These novel methods aim for better generalization and scalability for more sizable graphs but face significant challenges, such as (1) inability to handle unknown diffusion patterns and (2) reliance on high-quality training samples. To address these issues, we propose the Reinforced Expert Maximization  framework (REM). REM leverages a Propagation Mixture of Experts technique to encode dynamic propagation of large multiplex networks effectively in order to generate enhanced influence propagation. Noticeably, REM treats a generative model as a policy to autonomously generate different seed sets and learn how to improve them from a Reinforcement Learning perspective. Extensive experiments on several real-world datasets demonstrate that REM  surpasses state-of-the-art methods in terms of influence spread, scalability, and inference time in influence maximization tasks.
A Many-Objective Problem Where Crossover Is Provably Indispensable
Authors: Andre Opris
Venue: AAAI 2025 (main)

Abstract: This paper addresses theory in evolutionary multiobjective optimisation (EMO) and focuses on the role of crossover operators in many-objective optimisation. The advantages of using crossover are hardly understood and rigorous runtime analyses with crossover are lagging far behind its use in practice, specifically in the case of more than two objectives. We present a many-objective problem class together with a theoretical runtime analysis of the widely used NSGA-III to demonstrate that crossover can yield an exponential speedup on the runtime. In particular, this algorithm can find the Pareto set in expected polynomial time when using crossover while without crossover it requires exponential time to even find a single Pareto-optimal point. To our knowledge, this is the first rigorous runtime analysis in many-objective optimisation demonstrating an exponential performance gap when using crossover for more than two objectives.