Search papers, labs, and topics across Lattice.
This paper addresses the limitations of existing offline data-driven optimization methods by introducing the concept of algorithm-dependent learnability, which focuses on the optimizer's trajectory rather than the entire solution space. The authors develop a trajectory-learning framework that includes trajectory construction, modeling, and candidate generation, culminating in the Uncertainty-aware Gradient-guided Trajectory Learning (UGTL) method. UGTL demonstrates superior performance on five Design-Bench tasks, achieving the best aggregate mean rank of 3.1 out of 25 methods, highlighting the importance of trajectory construction in enhancing optimization efficiency.
Algorithm-dependent learnability reveals that focusing on the optimizer's trajectory can significantly enhance offline optimization performance, leading to state-of-the-art results on complex tasks.
Black-Box Optimization (BBO) has found broad applications, but evolutionary algorithms and Bayesian optimization face efficiency challenges as real-world BBO problems grow increasingly complex. Data-driven optimization improves the efficiency of BBO algorithms by learning from data. Offline data-driven optimization seeks high-quality solutions using only a fixed set of previous evaluations, attracting substantial attention because it requires no additional online evaluations. Many offline optimization methods have been proposed, but a fundamental question remains unanswered: what learnability is sufficient for offline optimization? Prior theoretical studies show that Probably Approximately Correct (PAC) learnability is insufficient, as the optimal region may remain poorly learned even when most regions are well learned. In this paper, we propose algorithm-dependent learnability, which requires accuracy only on the optimizer's trajectory. We prove that its value-query form is sufficient for representative discrete settings, including greedy and local search for submodular maximization, while its first-order analogue is sufficient for projected gradient descent on convex minimization. Motivated by this notion, we formalize a trajectory-learning framework comprising trajectory construction, trajectory modeling, and candidate generation, and analyze existing trajectory-based methods under it. We further propose Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), which constructs locally coherent improvement trajectories reflecting plausible search paths, models them with conditional diffusion, and selects a diverse candidate set. On five Design-Bench tasks, UGTL achieves the best aggregate mean rank, $3.1/25$, among 25 methods. Controlled trajectory analyses and cross-architecture replacements confirm that our trajectory construction plays a significant role in the improvement.
