Rethinking Learnability in Offline Data-driven Optimization

Rethinking Learnability in Offline Data-driven Optimization Chao Qian, Chen-Guang Wang, Rong-Xi Tan, Ke Xue State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China School of Artificial Intelligence, Nanjing University, Nanjing 210023, China

arXiv:2609.01493v1 [cs.LG] 1 Sep 2026

Abstract Black-Box Optimization (BBO) has found many successful applications, while traditional algorithms such as evolutionary algorithms and Bayesian optimization are facing challenges on their efficiency as real-world BBO problems are becoming more and more complex. Data-driven optimization has been the most popular paradigm to improve the efficiency of BBO algorithms, by learning from data. Offline data-driven optimization seeks high-quality solutions using only a fixed set of previously evaluated solutions, which has recently attracted a lot of research attention due to its benefit of not requiring additional online evaluations. Many offline optimization methods have thus been proposed, but a fundamental question that what learnability is sufficient for offline optimization is left unanswered. Previous theoretical studies have shown that the famous Probably Approximately Correct (PAC) learnability is insufficient, as the optimal region may be still poorly learned even though 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 optimization settings, including greedy and local search algorithms for submodular maximization, while its first-order analogue is sufficient for projected gradient descent on convex minimization. Motivated by algorithm-dependent learnability, we formalize a trajectory-learning framework (trajectory construction, trajectory modeling, and candidate generation) for offline optimization, and analyze the existing trajectory-based methods under this framework. We further propose a new trajectory-learning method, Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), that constructs locally coherent improvement trajectories (better 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. Key words: Offline data-driven optimization, learnability, PAC learnability, algorithm-dependent learnability, trajectory learning, theoretical analysis, experiments

Email addresses: qianc@lamda.nju.edu.cn (Chao Qian), 221840189@smail.nju.edu.cn (Chen-Guang Wang), tanrx@lamda.nju.edu.cn (Rong-Xi Tan), xuek@lamda.nju.edu.cn (Ke Xue)

Preprint submitted for review

1. Introduction

Black-Box Optimization (BBO) refers to optimizing objective functions where neither analytic expressions nor derivatives of the objective are available. It has various applications in science and engineering, e.g., drug discovery [60], material design [22], biodiversity curve optimization [44], chip design [55, 67], just to name a few. Popular BBO algorithms include evolutionary algorithms [75] and Bayesian optimization [24], which iteratively improve the quality of solutions through nature-inspired operators or Gaussian-process-guided sampling, and only require the evaluation results of objective functions during their running. Though having found many successful applications, their efficiency faces great challenges, as real-world BBO problems are becoming increasingly complex, e.g., the number of variables to be optimized is very large and the objective evaluation may incur a very high computational cost. BBO algorithms traditionally rely on expert-derived heuristics, e.g., crossover/mutation operators for evolutionary algorithms and acquisition functions for Bayesian optimization. Recently, there has been a growing interest in improving the efficiency of BBO algorithms by learning from previously collected data or accumulated data during the running of algorithms. Many data-driven optimization methods have been developed, e.g., learning surrogate models of objective functions [47, 66], effective search spaces [57, 64], selection of proper algorithms [30, 31], efficient parameter configurations of algorithms [43, 69], advanced components of algorithms [33, 41], and even an entire algorithm in an end-to-end fashion [15, 56]. Among the data-driven optimization methods, offline data-driven optimization [36, 61], also referred to as optimization from samples [5], has recently attracted substantial attention in the BBO community. Instead of interacting with the objective function online, it aims to infer promising candidate solutions solely from offline historical evaluations, which are collected from previous attempts, simulations, or deployments, and exist in many real-world scenarios. Thus, offline optimization can eliminate the need for additional evaluation budgets, which is attractive since acquiring new evaluations may be expensive, time-consuming, or even risky. Meanwhile, without the opportunity of correcting poor decisions through new evaluations, an offline optimizer must therefore extrapolate from partial observations while avoiding unsupported high-value predictions. Existing offline optimization methods address this difficulty from three directions. Forward methods fit a surrogate model from the offline dataset and then optimize the learned surrogate, using conservatism, regularization, ensembles, invariant representations, ranking, or structural assumptions to control extrapolation [12, 23, 39, 45, 50, 59, 62, 72, 73]. Inverse and conditional generative methods instead model promising designs directly, i.e., learn to generate candidate solutions conditioned on desirable

2

objective values [10, 38, 40, 70, 71]. More recently, trajectory-based methods have learned sequences of improving designs through autoregressive models, policies, diffusion models, gradient matching, or probabilistic bridges [11, 16, 32, 46, 74]. For offline optimization, a fundamental question is: where must the learned object be accurate for optimization to succeed? The famous Probably Approximately Correct (PAC) learnability [63] guarantees that with high probability, a learned surrogate can approximate the objective function well when given a polynomial number of observations. However, prior impossibility results show that there are problem classes (maximum coverage [5], unconstrained submodular minimization [6], and convex minimization [7]) that are PAC learnable and efficiently optimizable yet not optimizable from samples. Intuitively, PAC learnability guarantees average predictive accuracy, while the accuracy around the optimal region can still be bad, leading to that no reasonable approximation is achievable for offline optimization. We therefore ask a more targeted question: what type of learnability is sufficient for offline optimization? We answer this question with algorithm-dependent learnability, which localizes the accuracy requirement to the information queried along an optimizer’s trajectory. We formalize a value-query form (in Definition 4) for optimizers driven by function-value comparisons and a first-order analogue (in Definition 5) for optimizers driven by gradients. The value-query condition yields offline guarantees for size-constrained monotone approximately submodular maximization with greedy algorithms (as shown in Theorem 4) and for unconstrained non-monotone submodular maximization with local search algorithms (as shown in Theorem 5); the first-order condition yields an offline guarantee for convex minimization with projected gradient descent (as shown in Theorem 6). The common message is that effective offline optimization may not require globally accurate value prediction; instead, it is sufficient to learn accurately along the trajectory that an optimizer will actually visit. Inspired by the proposed algorithm-dependent learnability, we formalize a trajectory-learning framework for offline optimization, comprising three stages: trajectory construction, trajectory modeling, and candidate generation. The trajectory construction concentrates supervision on plausible search paths instead of asking one model to be uniformly accurate over the design space. We analyze existing trajectory-based methods under this framework, and find that their trajectory construction procedures do not follow the search principle of algorithms well. Thus, we propose a new trajectory-learning method by instantiating the framework with Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), which combines uncertainty-aware gradient-guided trajectory construction with conditional diffusion and diversity-aware selection. Specifically, UGTL constructs locally coherent improvement trajectories from offline data, biases their transitions with an uncertainty-aware surrogate gradient, trains a conditional diffusion model over complete trajectories, and diversifies the final candidate set through clustering. 3

Our experiments show that compared with 24 existing offline optimization methods, UGTL ranks first on average (3.1/25) across five Design-Bench tasks [61], a popular benchmark for offline optimization. We also empirically verify the superiority of our trajectory construction through trajectory-quality diagnostics and controlled BBOB [21] case studies. Furthermore, it can be transferred to other downstream models and training procedures: replacing the original constructor in BONET’s Transformer pipeline [46], PGS’s offline-RL pipeline [11], and GTG’s diffusion pipeline [74] with our UGTL constructor can improve performance in almost all cases. We also verify the benefit of our candidate selection with clustering, and show that the performance of UGTL is not very sensitive to the main hyperparameters. The rest of this paper is organized as follows. Section 2 introduces offline optimization and existing methods. Section 3 reviews previous negative theoretical results of PAC learnability for offline optimization and introduces algorithm-dependent learnability followed by its positive theoretical results under three case studies. Section 4 formalizes the trajectory-learning framework for offline optimization inspired by algorithm-dependent learnability, analyzes existing trajectory-based methods, and proposes a new one. Section 5 presents the experimental results. Finally, Section 6 concludes the paper.

2. Offline Optimization

Offline optimization [36, 61], also called optimization from samples [5], considers the problem of optimizing an unknown objective function using only a static offline dataset. Let X denote the search space and f : X → R denote the objective function. In the maximization setting, the goal is to find x∗ ∈ arg max f (x). x∈X

However, the optimizer cannot query f at arbitrary solutions. Instead, it is given only an offline dataset D = {(xi , yi )}N i=1 ,

yi = f (xi ),

which is usually collected by previous experiments, simulations, or deployments. An offline optimization method takes D as input and returns one or a small batch of candidate solutions for final evaluation. The minimization setting can be handled similarly by replacing maximization with minimization or by considering −f . The key difficulty is that the high-value region of f may be poorly covered by D, and optimizing a learned model can drive the search into out-of-distribution regions where the model is unreliable. A common family of methods is the forward approach. These methods first fit a surrogate model f˜ on D, and then optimize f˜ by gradient ascent, evolutionary algorithms [75], Bayesian optimization [24], or other optimizers. Because a naively trained surrogate can overestimate values outside the 4

data distribution, recent forward methods introduce conservative regularization, normalized maximum likelihood, robust adaptation, invariant representation learning, co-training or mentoring mechanisms, graphical structures, and ranking-based objectives to improve the alignment between model learning and final optimization performance [12, 23, 39, 50, 59, 62, 72, 73]. Forward methods are simple and broadly applicable, but their success relies critically on whether the learned surrogate is reliable on the solutions visited during optimization. Another family is the backward or generative approach. Instead of first learning a scoring function and then optimizing it, these methods directly model the distribution of promising solutions, often by learning an inverse mapping from desired objective values to designs or by steering a generative model toward high-value regions. Representative examples include model inversion networks, conditioningby-adaptive-sampling methods, diffusion-based inverse models, generative adversarial Bayesian optimization, and distribution-matching methods [10, 38, 40, 70, 71]. This paradigm can naturally generate diverse candidates and is particularly attractive in high-dimensional design spaces, but it still faces the challenge of extrapolating beyond the support of the offline data when conditioning on unseen high objective values. A more recent family learns from optimization trajectories. Rather than treating offline samples as independent design–score pairs, these methods synthesize or infer trajectories that mimic how an online optimizer would improve solutions. For example, BONET constructs monotone trajectories and trains an autoregressive Transformer [46]; PGS formulates offline optimization as policy-guided search [11]; GTG trains a conditional diffusion model on locally improving trajectories [74]; MATCHOPT uses trajectory-induced gradient matching to regularize surrogate learning [32]; and ROOT learns a probabilistic bridge between low- and high-value distributions [16]. These methods are especially relevant to our study because they implicitly focus learning on the regions traversed by an optimizer, rather than requiring accurate function approximation over the whole search space.

3. What Learnability is Sufficient for Offline Optimization?

For offline optimization where the target function to be optimized is unknown but only sampled data is available, can we solve such problems? A formal framework named optimization from samples was proposed to measure the performance of offline optimization theoretically [5, 6, 7], which is presented in Definition 1. Note that we have renamed the framework as offline optimizable for the unification of terminology. We have also omitted constraints that the functions need to satisfy for clearness. Definition 1 (Offline Optimizable [5, 6, 7]) A class F of functions is α-offline-optimizable over distribution D if ∀f ∈ F and δ ∈ (0, 1), given

5

a polynomial number of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D, there exists an algorithm that returns a solution x̃ such that, for maximization under the multiplicative setting, h i Prx1 ,...,xm ∼D f (x̃) ≥ α · max f (x) ≥ 1 − δ,

(1)

x

where α ∈ (0, 1]; and for minimization under the additive setting, h i Prx1 ,...,xm ∼D f (x̃) − min f (x) ≤ α ≥ 1 − δ, x

(2)

where α ≥ 0. According to Definition 1, a class of functions is α-offline-optimizable if we can construct an algorithm which, given polynomially many samples, outputs an α-approximate solution with respect to the optimal function value, with high probability. Then, we face a fundamental question: What conditions can make a class of functions offline optimizable? Such sufficient conditions may inspire the design of better offline optimization algorithms in practice. However, if a function is not optimizable or learnable, it is intuitively hard to achieve the offline optimizability. Thus, we are particularly interested in functions that are both learnable and optimizable. That is, When functions are optimizable and learnable, are they offline optimizable? As the optimizability of functions can be defined by approximation straightforwardly, we focus on the characterization of learnability. That is, we reformulate the above question as When functions are optimizable, what learnability can make them offline optimizable?

3.1. PAC Learnability is Not Sufficient The most famous notion of learnability is Probably Approximately Correct (PAC) learnability [63], which implies that, given polynomial number of samples, it is possible to learn a function to approximately mimic the function where the samples are drawn. Unfortunately, recent works [5, 6, 7] have shown that PAC learnability is generally insufficient for offline optimization. Specifically, there are classes of functions (e.g., maximum coverage [5], unconstrained submodular minimization [6], and convex minimization [7]) that are both optimizable and PAC learnable, but for which no reasonable approximation for offline optimization is achievable. Balkanski et al. [5] proved that for the problem of maximum coverage which is both optimizable and learnable, no constant factor approximation for offline optimization is achievable using polynomially many samples drawn from any distribution. As the maximum coverage problem is a special instance of monotone submodular function maximization with a size constraint, it is well known that maximum coverage is optimizable because the greedy algorithm achieves a (1 − 1/e)-approximation ratio [48]. 6

In terms of learnability, it has been proved [3] that coverage functions are (1 − ϵ)-PMAC learnable over any distribution, where ϵ > 0 is any constant. Probably Mostly Approximately Correct (PMAC) learnability as presented in Definition 2 is a generalization of the standard notion of PAC learnability by considering the approximation between the true function value f (x) and the predicted value f˜(x), i.e., requiring that β · f˜(x) ≤ f (x) ≤ f˜(x) where β ∈ (0, 1]. For the standard PAC learnability, β = 1. Thus, a function is PMAC learnable implies that most of the function values can be approximately learned very well with high probability. Theorem 1 shows that even a multiplicative approximation √

better than 2−Ω( n) cannot be achieved for offline optimization using polynomially many samples drawn from any distribution. Definition 2 (PMAC Learnability [4]) A class F of functions is PMAC learnable on distribution D if there exists a learning algorithm such that ∀f ∈ F and ϵ, δ > 0, when running the learning algorithm on a polynomial number of samples ˜ {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D, the algorithm returns a function f : h h i i Prx1 ,...,xm ∼D Prx∼D β · f˜(x) ≤ f (x) ≤ f˜(x) ≥ 1 − ϵ ≥ 1 − δ, where β ∈ (0, 1], and m is polynomial in 1/ϵ, 1/δ, and the size of f ∈ F (i.e., the dimensionality of x ∈ D). Theorem 1 (Theorem 2.2 of [5]) For the problem of maximum coverage under a size constraint that is optimizable with an approximation ratio of 1 − 1/e and PMAC learnable, no algorithm can obtain a multiplicative approximation better √

than 2−Ω( n) , using polynomially many samples drawn from any distribution. Balkanski and Singer [6] proved that even learnable submodular functions cannot be minimized within any non-trivial approximation when given access to polynomially many samples. Submodular functions can be minimized in polynomial time [26].

Balkanski and Singer [6] constructed a family

of submodular functions which is PAC learnable with absolute loss, where the sample complexity m ∈ O(n3 + n2 (log(2n/δ))/ϵ2 ) with n being the size of f . As presented in Definition 3, a function is PAC learnable with absolute loss implies that the expectation of the absolute loss between the true h i function value f (x) and the predicted value f˜(x), i.e., Ex∈D f˜(x) − f (x) , can be well bounded with high probability. But as shown in Theorem 2, for minimizing this family of submodular functions, despite being minimizable in polynomial time and PAC learnable, no algorithm can obtain an additive approximation better than 1/2 − o(1) using polynomially many samples drawn from any distribution. Definition 3 (PAC Learnability with Absolute Loss [63]) A class F of functions is PAC learnable on distribution D if there exists a learning algorithm such that ∀f ∈ F and ϵ, δ > 0, when running the learning algorithm on a polynomial number of samples

7

˜ {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D, the algorithm returns a function f : i i h h Prx1 ,...,xm ∼D Ex∈D f˜(x) − f (x) ≤ ϵ ≥ 1 − δ, where m is polynomial in 1/ϵ, 1/δ, and the size of f ∈ F (i.e., the dimensionality of x ∈ D). Theorem 2 (Theorem 8 of [6]) There exists a family of [0, 1]-bounded submodular functions that can be minimized in polynomial time and is PAC learnable, but no algorithm can obtain an additive approximation better than 1/2−o(1) for minimizing this family of submodular functions without constraints, using polynomially many samples drawn from any distribution. Balkanski and Singer [7] also proved that in general, the number of samples required to obtain a nontrivial approximation to the minimum of a convex function is exponential, even when the function is PAC learnable. It is known that convex functions can be efficiently optimized within an arbitrary degree of precision [49]. Balkanski and Singer [7] constructed a class of convex functions which is PAC learnable with the sample complexity m ∈ O(ϵ−4 δ −1 (n + log(δ −1 ))). Theorem 3 shows that no algorithm can obtain an additive approximation better than 1/2 − o(1) for minimizing this class of convex functions, using polynomially many samples drawn from any distribution. Furthermore, they proved that offline optimizability is impossible even assuming strong convexity and Lipschitz continuity of convex functions. Theorem 3 (Theorem 8 of [7]) There exists a class of convex functions F (where f : [0, 1]n → [0, 1] for f ∈ F) that can be efficiently minimized in polynomial time and is PAC learnable, but no algorithm can obtain an additive approximation better than 1/2 − o(1) for minimizing this class of convex functions, using polynomially many samples drawn from any distribution. The reason why the above functions are not offline optimizable using polynomially many samples drawn from any distribution is similar. The studied class of functions is defined based on partitions of the set of all dimensions {1, 2, . . . , n}, and their optima crucially depend on the partitions. The hardness arises from the fact that some critical parts of the partitions (and thus optimal solutions) cannot be distinguished from polynomially many samples with high probability, while most parts of the partitions can be learned well (and thus the value of almost all solutions can be estimated well), which explains why these functions are learnable but not offline optimizable.

3.2. Algorithm-dependent Learnability The negative results introduced in Section 3.1 show that no reasonable approximation is guaranteed when optimizing a function that has been learned from data, even if this function is both optimizable 8

and PAC/PMAC learnable. That is, PAC/PMAC learnability is insufficient for offline optimization, i.e., to obtain reasonable approximation guarantees when optimizing a function that is learned from data. Thus, an interesting question is what learnability can guarantee reasonable approximations for offline optimization. There have been some attempts in this direction by making strong assumptions or relaxing the approximation requirement [5, 14, 53]. Balkanski et al. [5] proposed the strong concept of recoverability, which requires a function to be learned everywhere within an approximation of 1±1/n2 from samples, i.e., the learned function f˜ satisfies that for every solution x, (1 − 1/n2 ) · f (x) ≤ f˜(x) ≤ (1 + 1/n2 ) · f (x) with high probability. Under recoverability, the problem of monotone submodular maximization with a size constraint (and also the specific instance, maximum coverage) is (1 − 1/e − o(1))-offline-optimizable. However, the condition of recoverability is too strong to hold in practice, which is also shown not necessary in [5] since unit demand functions are offline optimizable but not recoverable. Chen et al. [14] circumvented the impossibility result of offline optimization for maximum coverage by proposing a stronger model called optimization from structured samples, where the data samples encode the structural information of the functions, i.e., the samples could reveal the covered elements rather than just the number of covered elements. Under certain assumptions on the sample distribution, they designed an algorithm that achieves a constant approximation for offline optimization of the maximum coverage problem. However, the applicability of this strong model is limited because often only the values of the functions (rather than the structural information of the functions) are available in practice. To circumvent the difficulty of offline optimization, Rosenfeld et al. [53] proposed a new model called distributional optimization from samples by replacing the approximation of the whole search space with that of a sampled subspace and using a distribution-agnostic notion of approximation. The authors established a tight equivalence between this model and PMAC learnability: A function class is distributional optimization from samples if and only if it is PMAC learnable. However, the approximation concerned in practice is usually with respect to the whole search space rather than a sampled subspace. In this section, we propose a new learning concept called algorithm-dependent learnability that can provide approximation guarantees when optimizing learned functions. As presented in Definition 4, given an algorithm A for solving a class F of functions, it requires that with high probability, the functions can be learned approximately well (i.e., the predicted function value f˜(x) is bounded within (1 ± β) of the true function value f (x)) along the trajectories of the algorithm A running on the learned functions. Note that a solution visited by A on the learned function f˜ in Eq. (3) means that the solution is evaluated during the process of running A on f˜. Compared to recoverability [5], the proposed algorithm-dependent learnability does not require that functions are learnable everywhere from samples. 9

Definition 4 (Algorithm-dependent Learnability) Let A be an algorithm for solving a class F of functions. Then, F is algorithm-dependent learnable with respect to A on distribution D if there exists a learning algorithm such that ∀f ∈ F and δ > 0, when running the learning algorithm on a polynomial number of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D, the algorithm returns a function f˜: h i Prx1 ,...,xm ∼D ∀x visited by running A on f˜ : (1 − β) · f (x) ≤ f˜(x) ≤ (1 + β) · f (x) ≥ 1 − δ, (3) where β ∈ [0, 1), and m is polynomial in 1/δ and the size of f ∈ F (i.e., the dimensionality of x ∈ D). Definition 4 is tailored to algorithms whose decisions depend on function-value comparisons. For a first-order optimizer, the queried gradients, rather than the absolute function values, determine the trajectory. We therefore use the following first-order analogue, which controls gradient accuracy only at the points where the learned function is queried by the optimizer. Definition 5 (First-order Algorithm-dependent Learnability) Let A be a first-order algorithm whose trajectory is determined by gradient queries for solving a class F of functions that are differentiable on an open neighborhood of a domain X . Then, F is firstorder algorithm-dependent learnable with respect to A on distribution D if there exists a learning algorithm such that ∀f ∈ F and δ > 0, when running the learning algorithm on a polynomial number ˜ of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D, the algorithm returns a function f that is differentiable on the open neighborhood of X , and satisfies h i Prx1 ,...,xm ∼D ∀x at which A queries a gradient when solving f˜ : ∥∇f˜(x) − ∇f (x)∥ ≤ ζg ≥ 1 − δ, where ζg ≥ 0, and m is polynomial in 1/δ and the size of f ∈ F. Next, we show that the value-query condition in Definition 4 is sufficient for two discrete settings: monotone approximately submodular maximization with a size constraint by a greedy algorithm (Section 3.2.1) and unconstrained non-monotone submodular maximization by local search (Section 3.2.2). For convex minimization by projected gradient descent (Section 3.2.3), the first-order condition in Definition 5 is sufficient. By running an existing optimizer on the learned function f˜, algorithm-dependent learnability can transfer the optimizer’s query-wise decision relations from f˜ to the unknown objective f , then the structural properties of f , such as approximate submodularity or convexity, convert these local relations into a global approximation guarantee. The three cases instantiate the same principle at the level of the information consumed by each optimizer: reliable values for value-query algorithms and reliable gradients for first-order algorithms.

10

3.2.1. Sufficient for Offline Size-constrained Monotone Approximately Submodular Maximization with Greedy Algorithms First, we study the problem of monotone approximately submodular maximization with a size constraint, as presented in Definition 7. Given a finite set V = {v1 , v2 , . . . , vn }, we consider the functions f : 2V → R defined on subsets of V , where R denotes the set of reals. A set function f : 2V → R is monotone if ∀X ⊆ Y , f (X) ≤ f (Y ). We assume without loss of generality that monotone functions are normalized, i.e., f (∅) = 0; thus, we have ∀X ⊆ V , f (X) ≥ 0. A set function f is submodular [48] if it satisfies the “diminishing returns” property, i.e., ∀X ⊆ Y ⊆ V and v ∈ / Y, f (X ∪ {v}) − f (X) ≥ f (Y ∪ {v}) − f (Y ); or equivalently ∀X ⊆ Y ⊆ V , f (Y ) − f (X) ≤

X v∈Y \X

f (X ∪ {v}) − f (X) ,

(4)

which implies that the increment in f by adding a set of elements to a set X is not larger than the sum of increments of adding its individual elements to X. For a monotone but not necessarily submodular function f , the submodularity ratio as presented in Definition 6 was introduced to measure the closeness of f to submodularity, i.e., to what extent f has the submodular property. We can see that the submodularity ratio is defined based on Eq. (4); γX,l (f ) ∈ [0, 1], and f is submodular if and only if γX,l (f ) = 1 for any X and l. In this paper, we will use γX,l for short when the meaning of f is clear. Definition 6 (Submodularity Ratio [17, 52]) Let f : 2V → R be a set function. The submodularity ratio of f with respect to a set X ⊆ V and a parameter l ≥ 1 is P γX,l (f ) =

v∈S (f (L ∪ {v}) − f (L))

min L⊆X,S:|S|≤l,S∩L=∅

f (L ∪ S) − f (L)

.

As presented in Definition 7, the studied problem is to find a subset X ⊆ V maximizing a monotone approximately submodular function f with a size constraint |X| ≤ k. It is generally NP-hard, and has many applications, e.g., maximum coverage [18], influence maximization [35], sparse regression [17], unsupervised feature selection [20], and human assisted learning [42]. Note that the objective functions of the first two applications are exactly submodular (i.e., ∀X, l : γX,l (f ) = 1), while those of the last three ones are approximately submodular. Definition 7 (Monotone Approximately Submodular Function Maximization with a Size Constraint) Given a monotone and approximately submodular function f : 2V → R+ (where R+ denotes the set of non-negative reals) and a budget k, the goal is to find a subset X ∗ ⊆ V such that X ∗ ∈ arg maxX⊆V,|X|≤k f (X). 11

It has been shown that the greedy algorithm (presented in Algorithm 1) achieves an approximation ratio of 1 − e−γXk ,k , i.e., finds a subset Xk with f (Xk ) ≥ (1 − e−γXk ,k ) · maxX⊆V :|X|≤k f (X) [17]. Furthermore, this approximation ratio has been proved to be optimal [29]. The process of the greedy algorithm is straightforward, which iteratively selects one element with the largest marginal gain on f (i.e., v ∗ ∈ arg maxv∈V \Xi f (Xi ∪ {v}) in lines 3–4 of Algorithm 1) until k elements are selected. Algorithm 1 Greedy Algorithm [17] Input: all elements V = {v1 , . . . , vn }, objective function f , and budget k Output: a subset of V with k elements Process: 1: Let i = 0 and Xi = ∅; 2: repeat 3:

Let v ∗ ∈ arg maxv∈V \Xi f (Xi ∪ {v});

4:

Let Xi+1 = Xi ∪ {v ∗ }, and i = i + 1

5: until i = k 6: return Xk

Theorem 4 shows that the problem of monotone approximately submodular maximization with a size constraint is α-offline-optimizable (Definition 1) when the algorithm-dependent learnablity (Definition 4) with respect to the greedy algorithm holds. Note that a solution in Definitions 1 and 4 is represented by a vector x whereas here it is represented by a subset X of V ; there is no inconsistency because a subset X of V can be naturally represented by a Boolean vector x ∈ {0, 1}n , where the i-th bit xi = 1 means that vi ∈ X, and x / X. The approximation ratio α = i = 0 means that vi ∈  γ  k 1−β Xk ,k γXk ,k
k 1−β 1+β k  1 − 1+β 1− k . When the objective function f is exactly submodular, γX ,k  k 1− 1−β 1+β 1− k    k 1−β 1
1−β 1+β k 1 k 1 − 1+β γXk ,k = 1, and thus the approximation ratio α is specialized to 1− 1−β 1− 1 1− k . 1+β ( k) 2 When β is further set to 1/n as in recoverability [5], α becomes 1 − 1/e − o(1), which is consistent with the result for the specific case, maximum coverage, under the strong learnability concept of recoverability (which requires a function to be learned everywhere within an approximation of 1 ± 1/n2 from samples) [5]. When β = 0, the approximation ratio α recovers that, 1 − (1 −

γXk ,k k k ) , achieved by

the greedy algorithm under the value oracle model where each solution can be exactly evaluated [17]. Theorem 4 If the problem of monotone approximately submodular maximization with a size constraint is algorithm-dependent learnable with respect to the greedy algorithm on distribution D, then it is α-offline-optimizable over D, where 1−β γXk ,k 1+β k α= γXk ,k
1 − 1−β 1 − 1+β k

 1−

That is, Eq. (1) holds with this α. 12

1−β 1+β

! k  γXk ,k k . 1− k

Proof. By the algorithm-dependent learnability with respect to the greedy algorithm, we know from Definition 4 that there is a learning algorithm which can return a function f˜ with probability 1 − δ: ∀X visited by running the greedy algorithm on f˜ : (1 − β) · f (X) ≤ f˜(X) ≤ (1 + β) · f (X), (5) when getting access to a polynomial number of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D. In Eq. (5), β ∈ [0, 1), and f denotes the true function. We consider the greedy algorithm running on the learned function f˜ that satisfies Eq. (5). Let X ∗ denote an optimal subset, i.e., f (X ∗ ) = maxX⊆V :|X|≤k f (X), and Xi denote the subset after selecting i elements by the greedy algorithm on f˜. We have f (X ∗ ) − f (Xi ) ≤ f (X ∗ ∪ Xi ) − f (Xi ) [by the monotonicity of f ] X
1 ≤ f (Xi ∪ {v}) − f (Xi ) [by Definition 6 and |X ∗ | ≤ k] γXi ,k v∈X ∗ \Xi  X  1 1 · f˜(Xi ∪ {v}) − f (Xi ) [by Eq. (5) as Xi ∪ {v} is visited by Algorithm 1] ≤ γXi ,k 1−β ∗ v∈X \Xi  X  1 1 ˜ ≤ · f (Xi+1 ) − f (Xi ) [by line 3 of Algorithm 1] γXi ,k 1−β v∈X ∗ \Xi   k 1+β ≤ · f (Xi+1 ) − f (Xi ) [by γXi ,k ≥ γXi+1 ,k and Eq. (5)] γXk ,k 1 − β (6) The above equation can be equivalently transformed as    γXk ,k  γXk ,k 1 − β  1− f (Xi ) + f (X ∗ ) . f (Xi+1 ) ≥ 1+β k k Then, by induction, the returned subset Xk by Algorithm 1 satisfies 1−β γXk ,k 1+β k f (Xk ) ≥ γXk ,k
1 − 1−β 1 − 1+β k

1−

!

1−β 1+β

k 



! k  γXk ,k k 1− . k



γXk ,k k 1− k

· f (X ∗ ),

i.e., Eq. (1) in Definition 1 holds with 1−β γXk ,k 1+β k α= γXk ,k
1 − 1−β 1 − 1+β k

1−

1−β 1+β

The proof of Theorem 4 directly follows the proof for the approximation ratio of the greedy algorithm under multiplicative noise [51], because the condition (1 − ϵ) · f (X) ≤ F (X) ≤ (1 + ϵ) · f (X) satisfied by the noisy objective function F (X) is similar to Eq. (5) satisfied by the learned function f˜(X) under

13

algorithm-dependent learnability. We can find from the upper bound analysis of f (X ∗ ) − f (Xi ) (i.e., Eq. (6)) in the proof of Theorem 4 that the algorithm-dependent learnability allows the utilization of the algorithm behavior on the learned function f˜ (the fourth ‘≤’ in Eq. (6)) while almost maintaining the required monotone approximately submodular property (the first three and the last ‘≤’ in Eq. (6)).

3.2.2. Sufficient for Offline Unconstrained Non-monotone Submodular Maximization with Local Search Next, we study the problem of non-monotone submodular function maximization without constraints. As presented in Definition 8, it is to find a subset X ⊆ V maximizing a non-monotone and submodular function f . We assume without loss of generality that f is non-negative. This problem has many applications such as the classical NP-hard problem, maximum cut [25]. Definition 8 (Non-monotone Submodular Function Maximization without Constraints) Given a non-monotone and submodular function f : 2V → R+ (where R+ denotes the set of nonnegative reals), the goal is to find a subset X ∗ ⊆ V such that X ∗ ∈ arg maxX⊆V f (X).

It has been proved that the local search algorithm can achieve an approximation ratio of 1/3 − ϵ/n [19]. As presented in Algorithm 2, it starts from the best single element (line 1), and repeatedly adds (lines 2–4) or deletes (lines 5–7) one element until the subset cannot be improved by a factor larger than 1 + ϵ/n2 . Finally, it outputs the better one between the found subset X and its complement V \ X in line 8. Algorithm 2 Local Search Algorithm [19] Input: all elements V = {v1 , . . . , vn }, and objective function f Output: a subset of V Process: 1: Let v ∗ ∈ arg maxv∈V f (v), and X = {v ∗ }; 2: if

∃v ∈ V \ X such that f (X ∪ {v}) > (1 + nϵ2 ) · f (X) then

3:

X = X ∪ {v}, and repeat from line 2

4: end if 5: if

∃v ∈ X such that f (X \ {v}) > (1 + nϵ2 ) · f (X) then

6:

X = X \ {v}, and repeat from line 2

7: end if 8: return the better one between X and V \ X

Theorem 5 shows that the problem of non-monotone submodular maximization without constraints is α-offline-optimizable, when the algorithm-dependent learnability with respect to the local search 14

  −1
1+β ϵ algorithm is satisfied. The approximation ratio α = 1−β . When β = 0, 1+β · 3 + 2n 1−β 1 + n2 − 1 α becomes 1/(3+2ϵ/n), which is slightly better than the approximation ratio of 13 − nϵ achieved by local search under the value oracle model where each solution can be exactly evaluated [19]. In the proof of Theorem 5, we also show that the running time complexity required to achieve the approximation  3   1+β ratio is O nϵ log 1−β n . Theorem 5 If the problem of non-monotone submodular maximization without constraints is algorithm-dependent learnable with respect to the local search algorithm on distribution D, then it is α-offline-optimizable over D, where α=

−1   ϵ  1−β 1+β  1+ 2 −1 . · 3 + 2n 1+β 1−β n

That is, Eq. (1) holds with such an α.

Proof. By the algorithm-dependent learnability with respect to the local search algorithm, we know from Definition 4 that there is a learning algorithm which can return a function f˜ with probability 1 − δ: ∀X visited by running local search on f˜ : (1 − β) · f (X) ≤ f˜(X) ≤ (1 + β) · f (X),

(7)

when getting access to a polynomial number of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D. In Eq. (7), β ∈ [0, 1), and f denotes the true function. Note that a solution visited by local search (i.e., Algorithm 2) actually means that it is evaluated during the process of running Algorithm 2. We consider the local search algorithm running on the learned function f˜ that satisfies Eq. (7). Let Xlocal denote the local optimal solution obtained after finishing the run of lines 1–7 of Algorithm 2. We first have     1+β  ϵ  1 + 2 − 1 + 1 · f (Xlocal ). ∀S ⊆ Xlocal : f (S) ≤ n 1−β n

(8)

We are then to prove Eq. (8). Let S = S1 ⊆ S2 ⊆ · · · ⊆ Sk = Xlocal , where Si \ Si−1 = {ei }. We have f (Si ) − f (Si−1 ) ≥ f (Xlocal ) − f (Xlocal \ {ei }) 1 ˜ ≥ f (Xlocal ) − f (Xlocal \ {ei }) 1−β 1 + ϵ/n2 ˜ f (Xlocal ) ≥ f (Xlocal ) − 1−β   1+β  ϵ  ≥ 1− 1+ 2 · f (Xlocal ) 1−β n

[by the submodularity of f ] [by Eq. (7) as Xlocal \ {ei } is visited by Algorithm 2] [by lines 5–7 of Algorithm 2 and Xlocal ’s local optimality] [by Eq. (7) as Xlocal is visited by Algorithm 2]

15

(9)

By summing up f (Si ) − f (Si−1 ) from i = 2 to k, we can get   k X ϵ  1+β  1+ 2 · f (Xlocal ) f (Xlocal ) − f (S) = (f (Si ) − f (Si−1 )) ≥ (k − 1) · 1 − 1−β n i=2   ϵ  1+β  · f (Xlocal ), ≥n· 1− 1+ 2 1−β n leading to Eq. (8). Similarly, we can derive     1+β  ϵ  ∀Xlocal ⊆ S : f (S) ≤ n 1 + 2 − 1 + 1 f (Xlocal ). 1−β n

(10)

Let Xlocal = S1 ⊆ S2 ⊆ · · · ⊆ Sk = S, where Si \ Si−1 = {ei }. We have f (Si ) − f (Si−1 ) ≤ f (Xlocal ∪ {ei }) − f (Xlocal ) 1 ˜ f (Xlocal ∪ {ei }) − f (Xlocal ) 1−β 1 + ϵ/n2 ˜ ≤ f (Xlocal ) − f (Xlocal ) 1−β   1+β  ϵ  ≤ 1 + 2 − 1 · f (Xlocal ) 1−β n

[by the submodularity of f ]

≤

[by Eq. (7) as Xlocal ∪ {ei } is visited by Algorithm 2] [by lines 2–4 of Algorithm 2 and Xlocal ’s local optimality] [by Eq. (7) as Xlocal is visited by Algorithm 2] (11)

By summing up f (Si ) − f (Si−1 ) from i = 2 to k, we can get   k X 1+β  ϵ  (f (Si ) − f (Si−1 )) ≤ (k − 1) · f (S) − f (Xlocal ) = 1 + 2 − 1 · f (Xlocal ) 1−β n i=2     1+β ϵ ≤n· 1 + 2 − 1 · f (Xlocal ), 1−β n leading to Eq. (10). Let X ∗ denote an optimal subset, i.e., f (X ∗ ) = maxX⊆V f (X). By utilizing Eqs. (8) and (10), we have     1+β  ϵ  1 + 2 − 1 + 1 · f (Xlocal ) ≥ f (Xlocal ∩ X ∗ ); n 1−β n      1+β ϵ  n 1 + 2 − 1 + 1 · f (Xlocal ) ≥ f (Xlocal ∪ X ∗ ), 1−β n which leads to     1+β  ϵ  2 n 1 + 2 − 1 + 1 · f (Xlocal ) + f (V \ Xlocal ) 1−β n ≥ f (Xlocal ∩ X ∗ ) + f (Xlocal ∪ X ∗ ) + f (V \ Xlocal ) ≥ f (Xlocal ∩ X ∗ ) + f (X ∗ \ Xlocal ) + f (V )

[by the submodularity of f ]

≥ f (Xlocal ∩ X ∗ ) + f (X ∗ \ Xlocal )

[by the non-negativity of f ]

≥ f (X ∗ ) + f (∅)

[by the submodularity of f ]

≥ f (X ∗ )

[by the non-negativity of f ] 16

Then, we can conclude that  max{f (Xlocal ), f (V \ Xlocal )} ≥

 3 + 2n

1+β  ϵ  1+ 2 −1 1−β n

−1

· f (X ∗ ).

As the local search algorithm in Algorithm 2 returns the better one between Xlocal and V \ Xlocal in line 8, the returned subset X̃ satisfies f (X̃) ≥

1 1 · f˜(X̃) = · max{f˜(Xlocal ), f˜(V \ Xlocal )} 1+β 1+β 1−β · max{f (Xlocal ), f (V \ Xlocal )} ≥ 1+β −1   ϵ  1−β 1+β  · f (X ∗ ), 1+ 2 −1 ≥ · 3 + 2n 1+β 1−β n

i.e., Eq. (1) in Definition 1 holds with   −1 1−β 1+β  ϵ  α= · 3 + 2n 1+ 2 −1 . 1+β 1−β n Finally, we analyze the time complexity of running the local search algorithm on the learned function f˜. Assume that the local search algorithm has performed k iterations until finding Xlocal , i.e., the maintained subset has been improved k times by local search. Because the local search algorithm starts from the best single element ṽ ∗ ∈ arg maxv∈V f˜(v) in line 1 of Algorithm 2, and each improvement improves the f˜ value of the current subset by a factor larger than 1 + ϵ/n2 , we have  ϵ k f˜(Xlocal ) > 1 + 2 · f˜(ṽ ∗ ). n

(12)

Let v ∗ ∈ arg maxv∈V f (v) denote the best single element for the true function f . We have f˜(ṽ ∗ ) ≥ f˜(v ∗ ) ≥ (1 − β) · f (v ∗ ),

(13)

where the last inequality holds by Eq. (7) as v ∗ is visited by Algorithm 2 during the process of determining the best single element in line 1. Furthermore, we have f˜(Xlocal ) ≤ (1 + β) · f (Xlocal ) ≤ (1 + β) · nf (v ∗ ),

(14)

where the first inequality holds by Eq. (7) as Xlocal is visited by Algorithm 2, and the last inequality holds by the submodularity of f and v ∗ ∈ arg maxv∈V f (v). By combining Eqs. (12), (13) and (14), we have ϵ k · (1 − β) · f (v ∗ ) ≤ (1 + β) · nf (v ∗ ), n2  2   1+β leading to k = O nϵ log 1−β n . As each iteration of Algorithm 2 evaluates at most n subsets (by 

1+

adding a new element to the current subset or deleting an existing element from the current subset),  3   1+β the running time complexity is O nϵ log 1−β n . 17

The proof of Theorem 5 is adapted from the proof for the approximation ratio of local search under the value oracle model, i.e., Theorem 3.4 in [19], by using Eq. (7) under algorithm-dependent learnability to connect the true submodular function f and the learned function f˜. That is, the algorithm-dependent learnability allows the utilization of the local search behavior on the learned function f˜ (e.g., the third ‘≥’ in Eq. (9) and the third ‘≤’ in Eq. (11)) while maintaining the required submodular property approximately (e.g., the first two and the last ‘≥’ in Eq. (9) as well as the first two and the last ‘≤’ in Eq. (11)).

3.2.3. Sufficient for Offline Convex Minimization with Projected Gradient Descent Finally, we study offline convex minimization. Let X ⊆ Rd be a non-empty closed convex domain with finite diameter D = supx,y∈X ∥x − y∥. We consider a real-valued objective f that is convex and continuously differentiable on an open neighborhood of X , with ∥∇f (x)∥ ≤ G for all x ∈ X and some constant G > 0. Requiring differentiability on a neighborhood makes the ambient gradient well-defined even at boundary points of X . Convex minimization in Definition 9 is a basic model for many machine learning problems [49]. Meanwhile, as shown in Theorem 3, even when a class of convex functions is PAC learnable and can be minimized efficiently with exact function access, PAC learnability alone still cannot guarantee a non-trivial additive approximation in the offline optimization setting. Definition 9 (Convex Minimization) Given a non-empty closed convex domain X ⊆ Rd with finite diameter D and a real-valued function f that is convex and continuously differentiable on an open neighborhood of X , the goal is to find x∗ ∈ arg min f (x). x∈X

It is well known that projected gradient descent can achieve an additive approximation guarantee for convex minimization under the first-order oracle model where the exact gradient can be evaluated [49]. As presented in Algorithm 3, starting from an initial solution x1 ∈ X , the algorithm repeatedly moves along the negative gradient direction and projects the updated solution back to X , where ΠX denotes the Euclidean projection onto X . The algorithm returns the arithmetic mean of its first √ T iterates. For a convex objective f with ∥∇f (x)∥ ≤ G, setting η = D/(G T ) guarantees that √ f (x̄T ) − minx∈X f (x) ≤ DG/ T . Theorem 6 shows that the first-order algorithm-dependent learnability in Definition 5 is sufficient for offline convex minimization. Unlike the two algorithms above which require function value evaluations, projected gradient descent determines its trajectory through gradients. Definition 5 therefore controls precisely the first-order information consumed along that trajectory. The resulting additive error contains the usual optimization term and the trajectory-wise gradient error ζg . When ζg = 0, the √ bound recovers the standard guarantee DG/ T under exact first-order access. 18

Algorithm 3 Projected Gradient Descent [49] Input: initial solution x1 ∈ X , objective function f , step size η, and number of iterations T ≥ 1 Output: a solution in X Process: 1: Let t = 1 and x1 ∈ X ; 2: repeat

Let xt+1 = ΠX [xt − η∇f (xt )], and t = t + 1

3:

4: until t > T 5: return x̄T = T1

PT

t=1 xt

Theorem 6 If the problem of convex minimization (having the uniform gradient bound ∥∇f (x)∥ ≤ G for all f ∈ F and x ∈ X ) is first-order algorithm-dependent learnable with respect to the projected gradient descent algorithm (with step size η = (G+ζD )√T ) on distribution D, then it is α-offline-optimizable over D, g

where α=

(G + ζg )D √ + ζg D. T

That is, Eq. (2) holds with such an α.

Proof. By the first-order algorithm-dependent learnability with respect to the projected gradient descent algorithm (with step size η = (G+ζD )√T ), we know from Definition 5 that there is a learning g

algorithm which can return a function f˜ with probability 1 − δ: ∥∇f˜(x̂t ) − ∇f (x̂t )∥ ≤ ζg ,

t = 1, . . . , T,

(15)

when getting access to a polynomial number of samples {xi , f (xi )}m i=1 drawn i.i.d. from the distribution D. Note that x̂1 , . . . , x̂T denote the trajectory generated by running the projected gradient descent algorithm (with η = (G+ζD )√T ) on f˜. g

Let x∗ denote an optimal solution, i.e., f (x∗ ) = minx∈X f (x). As x̂t denotes the solution after t − 1 update steps on f˜, we have h i x̂t+1 = ΠX x̂t − η∇f˜(x̂t ) ,

η=

D √ . (G + ζg ) T

Because x∗ ∈ X , ΠX (x∗ ) = x∗ . The non-expansiveness of Euclidean projection onto a closed convex set therefore gives h i 2 ∥x̂t+1 − x∗ ∥2 = ΠX x̂t − η∇f˜(x̂t ) − ΠX (x∗ ) ≤ x̂t − η∇f˜(x̂t ) − x∗

2

(16)

= ∥x̂t − x∗ ∥2 − 2η⟨∇f˜(x̂t ), x̂t − x∗ ⟩ + η 2 ∥∇f˜(x̂t )∥2 . 19

We then bound the inner product term as ⟨∇f˜(x̂t ), x̂t − x∗ ⟩ = ⟨∇f (x̂t ), x̂t − x∗ ⟩ + ⟨∇f˜(x̂t ) − ∇f (x̂t ), x̂t − x∗ ⟩ ≥ f (x̂t ) − f (x∗ ) − ∥∇f˜(x̂t ) − ∇f (x̂t )∥ · ∥x̂t − x∗ ∥

[by the convexity of f and Cauchy–Schwarz ]

≥ f (x̂t ) − f (x∗ ) − ζg D,

[by Eq. (15) and the definition of D] (17)

and the gradient norm as ∥∇f˜(x̂t )∥ ≤ ∥∇f (x̂t )∥ + ∥∇f˜(x̂t ) − ∇f (x̂t )∥ ≤ G + ζg .

[by the triangle inequality] (18) [by the gradient bound of f and Eq. (15)]

Substituting Eqs. (17) and (18) into Eq. (16) and rearranging, we get 2η(f (x̂t ) − f (x∗ )) ≤ ∥x̂t − x∗ ∥2 − ∥x̂t+1 − x∗ ∥2 + 2ηζg D + η 2 (G + ζg )2 .

(19)

Summing Eq. (19) from t = 1 to T gives 2η

T X (f (x̂t ) − f (x∗ )) ≤ ∥x̂1 − x∗ ∥2 − ∥x̂T +1 − x∗ ∥2 + 2T ηζg D + T η 2 (G + ζg )2

(20)

t=1 2

2

2

≤ D + 2T ηζg D + T η (G + ζg ) , where the last inequality holds because x̂1 , x∗ ∈ X and ∥x̂T +1 − x∗ ∥2 ≥ 0. Let x̄T =

PT

t=1 x̂t /T

be

the solution returned by Algorithm 3. Since X is convex, x̄T ∈ X . By the convexity of f , Jensen’s inequality, and Eq. (20), we have T

f (x̄T ) − f (x∗ ) ≤

D2 η(G + ζg )2 1X (f (x̂t ) − f (x∗ )) ≤ + ζg D + . T t=1 2ηT 2

(21)

√ With η = D/((G + ζg ) T ), Eq. (21) implies f (x̄T ) − f (x∗ ) ≤

(G + ζg )D √ + ζg D. T

Thus, Eq. (2) holds with α =

(G+ζg )D √ + ζg D . T

The proof of Theorem 6 follows the standard analysis of projected gradient descent, using Eq. (15) to connect the learned and true gradients only along the generated trajectory. We can find from the one-step upper-bound analysis in Eqs. (16)–(19) that the first-order algorithm-dependent learnability allows the utilization of the algorithm behavior on the learned function f˜ (the first ‘=’ in Eq. (16)), while retaining the first-order convexity relation of the true function f up to an additive error ζg D (the two ‘≥’ in Eq. (17)) and the gradient bound of f up to an additive error ζg (the second ‘≤’ in 20

Eq. (18)). Finally, the convexity of f converts the average trajectory performance into a guarantee for the returned mean iterate. Together with the two discrete cases in Theorems 4 and 5, this result supports an information-matched view of algorithm-dependent learnability: function values along the generated optimization trajectory must be reliable for value-query optimizers, whereas gradients must be reliable for first-order optimizers.

4. Offline Optimization Inspired by Algorithm-dependent Learnability

The sufficiency of algorithm-dependent learnability for the three offline optimization scenarios proved in Section 3 suggests a practical design principle: an offline optimizer should preserve the information needed along the search process it will execute, rather than approximate the objective uniformly over the entire search space. First, the required precision is query-local: it is needed only on the points evaluated by the optimizer rather than uniformly over the entire search space. Besides, the method should be information-matched: the learned object should preserve the signal that determines the optimizer’s next decision, such as function values for value-query methods or gradients for first-order methods. In practice, offline optimization is given a fixed offline dataset, while the optimizer-induced query trajectory is unavailable. However, we can construct synthetic trajectories from the fixed offline dataset as an operational proxy for modeling, which motivates the trajectory-learning framework for offline optimization, comprising three stages: trajectory construction, trajectory modeling, and candidate generation. We use the framework to analyze existing trajectory-learning-based methods and find that their trajectory-construction rules do not follow optimizers’ decision signal well. Thus, we introduce the concepts of gradient consistency and uncertainty calibration to integrate the optimizers’ decision signal, and propose a new trajectory-learning method by instantiating the framework with Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), which can better learn the local search behavior and thus generate better candidate solutions.

4.1. Trajectory-Learning Framework The analyses in Sections 3.2.1–3.2.3 share one structural feature: the approximation guarantee for offline data-driven optimization is tied to the optimizer’s trajectory. Motivated by this observation, we introduce a trajectory-learning framework that represents an optimizer’s search behavior through candidate improvement paths constructed from offline data. The framework comprises three stages: trajectory construction, trajectory modeling, and candidate generation. Specifically, given an offline N

traj dataset D, the trajectory-construction stage produces a trajectory dataset Dtraj = {τj }j=1 , where

21

each length-H trajectory takes the form τj = (xj,1 , yj,1 ), . . . , (xj,H , yj,H ) . The trajectory-modeling stage learns the transition structure encoded by these paths, while the candidate-generation stage uses the learned behavior to produce candidate designs for evaluation. Algorithm 4 formalizes this three-stage framework. Algorithm 4 Trajectory-Learning Framework for Offline Optimization Input: Offline dataset D, candidate budget Q Output: Candidate set C with |C| ≤ Q Process: 1: Trajectory construction. Construct Dtraj from D, with each trajectory representing a plausible

improvement path. 2: Trajectory modeling.

Train a model Mθ on Dtraj to capture the search behavior encoded by

these paths. 3: Candidate generation. Use Mθ , optionally with a proxy model, to generate and select a set C

of candidate solutions. 4: return C

Together, the three stages specify how trajectory information is extracted from the offline dataset, represented by a learned model, and converted into candidate designs. Trajectory construction determines which empirical search behavior is visible to the learner; trajectory modeling captures that behavior; and candidate generation executes it, typically under a high-value condition. Since later stages can only exploit the supervision supplied by the constructed paths, the stage of trajectory construction is crucial and incoherent trajectories may cause even a capable model to learn unsuitable search dynamics. We want to emphasize that the connection to the sufficient condition, algorithm-dependent learnability, for offline optimization proved in Section 3 is motivational rather than a formal implication. Algorithmdependent learnability is stated using unknown objective information along optimizer-induced queries, whereas a practical method must construct its training trajectories from the offline dataset D alone. The framework therefore operationalizes the principle of concentrating learning on plausible search processes, without verifying the theoretical conditions rigorously.

4.2. Existing Methods under the Framework In this section, we show that some existing representative offline optimization methods can be contained under our trajectory-learning framework and analyzed through the same three stages. Table 1 maps each method’s construction rule, learned trajectory representation, and candidate-generation procedure to Algorithm 4.

22

Table 1: Existing trajectory-related offline optimization methods viewed through the trajectorylearning lens. Method

Trajectory construction

Trajectory modeling

Candidate generation

Autoregressive Transformer

Rollout under low-regret

Generative trajectory learning methods BONET [46]

Monotone sort-sampled paths with regret budgets

PGS [11]

GTG [74]

conditioning

Randomized paths from a

Offline RL policy with a

Policy-guided gradient

top-percentile subset

surrogate

search

Random local score-feasible

Conditional diffusion over

Guided diffusion sampling

paths

trajectories

with proxy filtering

Surrogate with trajectory

Gradient ascent on the

transitions

gradient matching

surrogate

Low/high endpoint pairs

Probabilistic bridges

Reverse bridges from top

from GP-posterior mean

between paired endpoints

offline designs

Trajectory-informed optimization methods MATCH-OPT [32] Monotone binned

ROOT [16]

functions

This formulation provides a taxonomy for these existing methods that some methods directly model complete trajectories, whereas others use trajectory-derived signals as auxiliary supervision or transport paths. Specifically, BONET [46] constructs monotone paths and models them autoregressively; PGS [11] converts randomly sampled transitions from top-p percentile offline data into policy supervision whose actions are defined relative to a surrogate gradient; and GTG [74] fits a diffusion model to locally score-feasible paths. These methods instantiate all three stages explicitly. MATCH-OPT [32] uses monotone paths indirectly as gradient-matching supervision, whereas ROOT [16] directly learns stochastic transport bridges between low- and high-value endpoint distributions. The comparison clearly clarifies what the trajectory-construction stage must provide. Increasing scores alone, as constructed by BONET [46] and PGS [11], do not make a sequence an informative improvement path, since sorting or randomly pairing high-value designs might create long transitions that do not describe how an optimizer moves locally [74]. Restricting transitions to neighborhoods like GTG [74] can improve local coherence, but locality alone does not ensure that successive steps follow a consistent improvement direction. It is expected that useful trajectories should encode both local coherence and directional progress. In Figure 1, we illustrate this distinction on the negated Branin function over [−5, 10] × [0, 15]. We construct the offline dataset by uniformly sampling 50,000 points and retaining only the bottom 60% according to their objective values. As shown in Figure 1(a), BONET’s sort-sampled paths and PGS’s 23

randomly assembled paths contain long, spatially incoherent transitions. Figure 1(b) shows that GTG substantially improves locality by restricting transitions to score-feasible neighborhoods. However, because its next points are sampled without explicit directional guidance, the resulting trajectories (shown in pink color) do not consistently form smooth improvement paths toward high-value regions. Figure 1(c) further shows that the geometry of the constructed paths (generated by the same conditional diffusion model and full-trajectory sampler) persists after trajectory modeling, where the GTG trajectories show limited improvement. BONET

(a) BONET and PGS constructors

PGS

GTG

UGTL

(b) GTG and UGTL constructors

Start

⋆ Optima

(c) Generated trajectories

Figure 1: A motivating example on the negated Branin function. (a) and (b) compare constructed trajectories, and (c) shows trajectories generated by GTG and UGTL with the same conditional diffusion model. Black dots and red stars denote starting points and global optima, respectively. These observations motivate a trajectory constructor that preserves locality while guiding successive transitions toward consistent improvement. We therefore introduce approximate proxy gradients to provide directional guidance and improve trajectory quality, and formulate this design as Uncertaintyaware Gradient-guided Trajectory Learning (UGTL). As illustrated by the green trajectories in Figure 1(b) and (c), UGTL produces smoother ascent-oriented paths whose structure is retained by the downstream diffusion model. In the next subsection, we will introduce UGTL in detail.

4.3. A New Offline Optimization Method: Uncertainty-aware Gradient-guided Trajectory Learning To provide directional guidance of the trajectory construction procedure, we introduce UGTL, which implements the three stages of Algorithm 4. In trajectory construction, it constructs locally coherent paths using proxy-gradient guidance adjusted by the prediction uncertainty of an ensemble of surrogate models. In trajectory modeling, it learns the retained paths using a terminal-score-conditioned diffusion

24

model. In candidate generation, it produces the evaluation batch through guided trajectory sampling and a Cluster-then-Select procedure.

τ Trajectory construction. Each trajectory τ = ((xτ1 , y1τ ), . . . , (xτH , yH )) starts from a point sampled

uniformly from the bottom pinit % of observed scores, leaving scope for improvement. Given the current prefix τ1:k , we define its best observed score as bk = max yhτ . 1≤h≤k

We then construct a score-feasible local neighborhood Sk = NNK (xτk ; {(xj , yj ) ∈ D : xj ∈ / {xτ1 , . . . , xτk }, yj ≥ bk − ξ}) ,

(22)

where NNK (x; S) returns up to K nearest designs to x in the set S. The score constraint yj ≥ bk − ξ keeps candidate scores close to the best value reached by the current trajectory, while ξ ≥ 0 allows short non-monotone transitions. If no unvisited design satisfies the score constraint, we use the K highest-scoring unvisited designs as a fallback, breaking score ties by distance to xτk . Within Sk , we favor transitions aligned with the gradient. For this purpose, we train an ensemble of ens Mens surrogate models {f˜ϕm }M m=1 on D. The ensemble mean µϕ serves as the proxy score, while the

ensemble dispersion σϕ provides an estimate of predictive uncertainty: v u Mens ens u 1 M X
2 1 X ˜ µϕ (x) = fϕm (x), σϕ (x) = t f˜ϕm (x) − µϕ (x) . Mens m=1 Mens m=1

(23)

We use the gradient of the ensemble mean, ∇x µϕ (x), as a proxy gradient to provide directional guidance during trajectory construction. For each (xj , yj ) ∈ Sk , we define the stabilized cosine alignment ak,j =

⟨∇x µϕ (xτk ), xj − xτk ⟩ , ∥∇x µϕ (xτk )∥∥xj − xτk ∥ + ccos

where ccos = 10−8 provides numerical stability. The next point is sampled according to exp(ak,j /κk ) . ′ (xj ′ ,yj ′ )∈Sk exp(ak,j /κk )

τ Pr (xτk+1 , yk+1 ) = (xj , yj ) | τ1:k = P

(24)

The temperature κk is determined by the ensemble uncertainty: κk = 1 +

σϕ (xτk ) , σ̄ϕ + ctemp

N

σ̄ϕ =

1 X σϕ (xi ), N i=1

where ctemp > 0. Low predictive uncertainty yields a sharper preference for gradient-aligned transitions, whereas high uncertainty increases the temperature and spreads probability across the feasible neighborhood. 25

Algorithm 5 UGTL: Uncertainty-aware Gradient-guided Trajectory Construction Input: Offline dataset D, horizon H, trajectory count Ntraj , initial percentile pinit , neighborhood size K, score tolerance ξ, retention ratio ρ, ensemble size Mens Output: Trajectory dataset Dtraj ens 1: Train the surrogate ensemble {f˜ϕm }m=1 on D and compute µϕ (·) and σϕ (·) using Eq. (23);

M

2: Initialize Ttraj ← ∅; 3: for u = 1, . . . , Ntraj do 4:

Sample (xτ1 , y1τ ) from the bottom pinit % of D and initialize τ ← ((xτ1 , y1τ ));

5:

for k = 1, . . . , H − 1 do

6:

Construct Sk using Eq. (22);

7:

if Sk = ∅ then

8:

Use the K highest-scoring unvisited designs

9:

end if

10:

τ Sample (xτk+1 , yk+1 ) from Sk using Eq. (24);

11:

τ Append (xτk+1 , yk+1 ) to τ

12:

end for

13:

Add τ to Ttraj

14: end for τ − y1τ ; 15: Rank the trajectories in Ttraj by ∆y (τ ) = yH

16: Retain the top ⌈ρNtraj ⌉ trajectories as Dtraj 17: return

Dtraj

After constructing Ntraj trajectories, we rank them by their endpoint improvement, τ ∆y (τ ) = yH − y1τ ,

and retain the top ⌈ρNtraj ⌉ trajectories, where ρ ∈ (0, 1]. This filtering removes stagnant paths without requiring every transition to be monotone. The retained trajectories form Dtraj , and Algorithm 5 summarizes the complete construction stage.

Trajectory modeling. For each τ ∈ Dtraj , let Xτ = [xτ1 , . . . , xτH ] denote its design sequence and let τ yτend = yH denote its terminal score. We model the design sequence conditioned on its terminal score

using a conditional diffusion model pθ (Xτ | yτend ). The forward process is q(Xτ(t) | Xτ(0) ) = N

√

 ᾱt Xτ(0) , (1 − ᾱt )I ,

where t = 1, . . . , Tdiff , αt ∈ (0, 1) is the signal-retention coefficient at diffusion step t, and ᾱt =

26

Qt

s=1 αs .

(t)

We train a noise-prediction network εθ (Xτ , t, y) using classifier-free conditioning:   2 (t) , L(θ) = Eτ,t,ε ε − εθ (Xτ , t, y) where τ is sampled from Dtraj , t is sampled uniformly from {1, . . . , Tdiff }, and ε ∼ N (0, I). The condition y equals yτend with probability 1 − pdrop ; otherwise, it is dropped and represented by a dedicated null-conditioning embedding, which enables classifier-free guidance during candidate generation.

Candidate generation. We use the learned diffusion model to generate trajectories toward a target terminal score. Let ytar = λtar · max(x,y)∈D y, where λtar ≥ 1 controls the target level. Classifier-free guidance with scale scfg computes   εbθ (X (t) , t, ytar ) = εθ (X (t) , t, ∅) + scfg εθ (X (t) , t, ytar ) − εθ (X (t) , t, ∅) .

(25)

Each reverse step is X

(t−1)

1 =√ αt

  1 − αt (t) (t) εbθ (X , t, ytar ) + σt zt , X −√ 1 − ᾱt

zt ∼ N (0, I),

(26)

ᾱt−1 where σt2 = 1− 1−ᾱt (1 − αt ), and z1 = 0 at the final reverse step.

For each generated trajectory, we sample τ ctx ∈ Dtraj and use its first Hctx < H designs as the context Xctx = [xτ1

ctx

ctx

, . . . , xτHctx ].

We keep this prefix fixed by overwriting the corresponding positions after each reverse step: (t−1)

X1:Hctx ← Xctx .

(27)

This anchors each generated trajectory to an observed prefix while allowing its suffix to move toward the target score. The generated suffixes form a candidate pool P. To improve robustness, instead of directly returning the top-Q proxy-scored designs, we propose Cluster-then-Select, which retains the top Mpool valid candidates under µϕ , where Mpool ≥ Q, partitions them into Q clusters, and selects the design with the highest proxy score from each cluster Bq : xout = arg max µϕ (x), q

q = 1, . . . , Q.

x∈Bq

Algorithm 6 summarizes the complete candidate-generation stage, where the resulting candidate set combines high proxy scores with coverage across distinct generated regions.

27

Algorithm 6 UGTL: Candidate Generation Input: Trained diffusion model εθ , trajectory dataset Dtraj , proxy µϕ , context length Hctx , candidate budget Q, pre-screening size Mpool , number Ngen of generated trajectories, terminal-score multiplier λtar , guidance scale scfg , diffusion steps Tdiff out Output: Candidate set {xout 1 , . . . , xQ }

1: Initialize the candidate pool P ← ∅; 2: for u = 1, . . . , Ngen do 3:

Sample X (Tdiff ) ∼ N (0, I) and τ ctx ∼ Dtraj ;

4:

Set X1:Hdiff ← [xτ1 ctx

5:

for t = Tdiff , . . . , 1 do

(T

)

ctx

ctx

, . . . , xτHctx ];

6:

Compute the guided noise using Eq. (25);

7:

Compute X (t−1) using Eq. (26);

8:

Apply context conditioning using Eq. (27)

9:

end for

10:

P ← P ∪ XHctx+1 :H

(0)

11: end for 12: Retain the top Mpool valid designs in P according to µϕ ; 13: Partition them into Q clusters {B1 , . . . , BQ } using k-means; 14: for q = 1, . . . , Q do 15:

← arg maxx∈Bq µϕ (x) xout q

16: end for 17: return

out {xout 1 , . . . , xQ }

Comparison with GTG [74]. UGTL adapts GTG’s conditional trajectory diffusion for trajectory modeling. However, GTG constructs trajectories by sampling from score-feasible nearest neighbors, which improves locality but does not distinguish these neighbors according to their alignment with an optimization direction. UGTL instead starts from our proposed algorithm-dependent learnability and uses uncertainty-aware proxy-gradient guidance to construct optimizer-like improvement trajectories (yielding more consistent trajectories, as shown in Figure 1), followed by Cluster-then-Select for candidate selection. Thus, compared with GTG, UGTL retains the trajectory-modeling pipeline while introducing different procedures for trajectory construction and candidate selection.

5. Experiments

In this section, we evaluate the performance of our proposed method UGTL empirically on popular benchmarks, Design-Bench [61] and BBOB [21], for offline data-driven optimization. To assess UGTL 28

systematically, this section organizes the evaluation into three complementary levels, moving from endto-end effectiveness to trajectory-level behavior and then to component contributions and robustness. First, at the end-to-end level, we examine whether UGTL is competitive with existing offline optimization methods in terms of final candidate quality. Second, at the trajectory level, we assess whether the proposed trajectory constructor produces locally coherent, improvement-oriented paths and whether these properties are preserved in model-generated trajectories. Finally, at the component level, we test whether the UGTL constructor remains beneficial across different downstream models and training procedures, isolate the additional contribution of the diversity-aware Cluster-then-Select strategy, and assess sensitivity to the main hyperparameters.

5.1. Experimental Settings Benchmark and tasks. We benchmark UGTL on five Design-Bench tasks [61], following recent offline data-driven optimization studies [59, 74]. The continuous tasks include: 1) Ant Morphology [9], which optimizes a 60-dimensional morphology for locomotion; 2) D’Kitty Morphology [1], which optimizes a 56-dimensional robot morphology; and 3) Superconductor [27], which searches an 86-dimensional material representation to maximize critical temperature. The discrete tasks are TF-Bind-8 and TFBind-10 [8], which optimize DNA sequences of length 8 and 10 for transcription-factor binding affinity. For each task, we directly use the offline datasets provided by Design-Bench, which contain 10,004, 10,004, 17,014, 32,898, and 50,000 designs for Ant, D’Kitty, Superconductor, TF-Bind-8, and TF-Bind10, respectively.

Controlled BBOB case studies. Detailed trajectory analysis requires evaluating every intermediate design. Since the evaluations for Design-Bench tasks are quite expensive, Design-Bench mainly measures final candidate quality. We introduce two cheap analytic BBOB functions [21] as controlled case studies to examine the trajectories produced by different methods. Specifically, we use Rastrigin, a multimodal function, and Rosenbrock, a narrow-valley function, with dimensions d ∈ {5, 10, 15, 20}. For each function and dimension, we sample 50,000 points uniformly from the native domain ([−5.12, 5.12]d for Rastrigin and [−5, 5]d for Rosenbrock), transform the minimization objective into a score in [0, 1] using min–max scaling, and remove the top 40% by score to form an offline dataset of 30,000 points.

Compared methods. We compare UGTL with five categories of methods, including 24 baselines. The first class consists of baseline optimization methods that maximize a surrogate model, including BOqEI [24, 54], CMA-ES [28], REINFORCE [65], and Gradient Ascent with its mean- and minimumensemble variants. The second category comprises inverse or conditional generative methods, including CbAS [10], MINs [40], and DDOM [38]. The third category is called regularized surrogate methods, 29

including COMs [62], RoMA [72], IOM [50], BDI [13], ICT [73], Tri-Mentoring [12], FGM [39], LTR [59], GABO [71], and DynAMO-Adam [70]. We further compare trajectory-informed methods, MATCHOPT [32] and ROOT [16], and generative trajectory methods, BONET [46], GTG [74], and PGS [11]. Except for ROOT, LTR, GABO, and DynAMO-Adam, the baseline results are taken from [59] under the same Design-Bench protocol. We run ROOT, LTR, GABO, and the Adam variant of DynAMO using their official implementations.

Implementation details and hyperparameters. For trajectory construction, we follow the hyperparameters in [74] by setting the trajectory horizon to H = 64, the neighborhood size to K = 20, the initial percentile to pinit = 20%, and the number Ntraj of trajectories to 4,000 for continuous tasks and 1,000 for discrete tasks. The score tolerance ξ = 0.01 on D’Kitty and 0.05 on the other tasks. Each surrogate is an independently initialized two-hidden-layer MLP of width 1,024 with LeakyReLU activations trained for 5,000 Adam steps with learning rate 10−3 and batch size 128. We set the ensemble size Mens = 10, retention ratio ρ = 0.5, and uncertainty temperature ctemp = 0.5. For trajectory modeling, the conditional diffusion model is a temporal U-Net [34] with channel multipliers (1, 4, 8), base width 128 on continuous tasks and 32 on discrete tasks, Tdiff = 200 steps, and a cosine noise schedule. The diffusion model is trained by Adam [37] using a batch size of 128 and EMA decay of 0.995. Models for continuous tasks are trained for 50,000 steps at a learning rate of 10−4 , while those for discrete tasks are trained for 20,000 steps at 2 × 10−4 . The condition-drop probability pdrop = 0.25. We report the results of the final checkpoint. For candidate generation, the classifier-free guidance scale, context length, number of generated trajectories, and pre-screening pool size are scfg = 1.5, Hctx = 32, Ngen = 1000, and Mpool = 2048, respectively. λtar is set to 1.5 on TF-Bind-8 and 1.3 otherwise. Cluster-then-Select applies k-means in the normalized diffusion representation, using k-means++ initialization [2] with 10 independent starts. Additionally, in the controlled BBOB comparison, we set H = 64, K = 50, Ntraj = 1000, pinit = 20%, ξ = 0.05, and Ngen = 1000. All experiments are implemented in PyTorch 1.13.1.

Evaluation and metrics. Each method returns Q = 128 candidates. Following the Design-Bench protocol [59, 61], we evaluate the candidates using the ground-truth oracle and report the normalized 100th-percentile score, i.e., the score of the best returned design. A raw score y is normalized as all all all all all (y − ymin )/(ymax − ymin ), where ymin and ymax are the extrema of the full, unobserved benchmark

dataset. We report the mean ± standard deviation over eight independent runs.

30

5.2. Main Results on Design-Bench Table 2 reports the 100th-percentile normalized scores. Among the 25 methods, UGTL achieves the best mean rank of 3.1, followed by LTR [59] with 4.8 and BDI [13] with 5.9. UGTL obtains the highest mean score on Superconductor and TF-Bind-10 and improves over the best observed offline score, D(best), on all five tasks. Among generative trajectory methods, UGTL achieves the highest mean score on every task compared with BONET [46], GTG [74], and PGS [11]. These results demonstrate the overall effectiveness of UGTL on Design-Bench and also motivate the trajectory-level analyses below.

5.3. Trajectory-quality Analysis The comparison in Section 5.2 measures final candidate quality but does not show how complete trajectories evolve. We therefore complement it with trajectory-level diagnostics and the controlled BBOB case studies described in Section 5.1. The analytically evaluable objectives of BBOB allow us to evaluate every point in both constructed and generated trajectories while keeping the downstream diffusion model and sampler fixed.

5.3.1. Trajectory-quality Diagnostics In this subsection, we compare the trajectory quality of BONET [46], PGS [11], GTG [74], and UGTL. On Design-Bench, we evaluate the constructed trajectories; on BBOB, we evaluate both constructed and model-generated trajectories. For the generated BBOB trajectories, all methods use the same conditional diffusion model, training schedule, and full-trajectory sampler. We evaluate the final sampled trajectories. For a trajectory τ , we measure cumulative regret and smoothness as R(τ ) =

H X k=1

H−2

(1 − sk ),

S(τ ) =

1 X ∥xk+2 − 2xk+1 + xk ∥2 , H −2 k=1

where sk is the normalized objective value. The regret is small when a trajectory remains in highvalue regions. Since xk+2 − 2xk+1 + xk = (xk+2 − xk+1 ) − (xk+1 − xk ) is the difference between two consecutive displacement vectors, a smaller smoothness value indicates less variation between successive moves and hence a smoother trajectory. Before computing smoothness, we normalize the design coordinates using min–max scaling. We report Design-Bench smoothness only on the three continuous tasks because distances between discrete latent representations are not directly comparable. Each diagnostic is computed over eight independent runs. Figure 2 summarizes the trajectory diagnostics. UGTL ranks first on Design-Bench regret (1.2/4) and smoothness (1.3/4). On BBOB, it ranks first on constructed-trajectory regret and on both regret and 31

Table 2: 100th-percentile normalized score among Q = 128 candidates on five Design-Bench tasks (mean ± standard deviation over eight runs). Blue and Violet denote the best and runner-up reported means. D(best) is the best score in the offline dataset. Mean rank is computed across all 25 methods with average ranks for ties. Category

Method

Ant

D’Kitty

Superconductor

TF-Bind-8

TF-Bind-10

Mean Rank

D(best)

0.565

0.884

0.400

0.439

0.467

/

BO-qEI

0.812 ± 0.000

0.896 ± 0.000

0.382 ± 0.013

0.802 ± 0.081

0.628 ± 0.036

19.4/25

CMA-ES

1.712 ± 0.754

0.725 ± 0.002

0.463 ± 0.042

0.944 ± 0.017

0.641 ± 0.036

12.2/25

Proxy

REINFORCE

0.248 ± 0.039

0.541 ± 0.196

0.478 ± 0.017

0.935 ± 0.049

0.673 ± 0.074

15.0/25

Optimization

Grad. Ascent

0.273 ± 0.023

0.853 ± 0.018

0.510 ± 0.028

0.969 ± 0.021

0.646 ± 0.037

12.0/25

Grad. Ascent Mean

0.306 ± 0.053

0.875 ± 0.024

0.508 ± 0.019

0.985 ± 0.008

0.633 ± 0.030

11.8/25

Grad. Ascent Min

0.282 ± 0.033

0.884 ± 0.018

0.514 ± 0.020

0.979 ± 0.014

0.632 ± 0.027

11.6/25

CbAS

0.846 ± 0.032

0.896 ± 0.009

0.421 ± 0.049

0.921 ± 0.046

0.630 ± 0.039

16.7/25

MINs

0.906 ± 0.024

0.939 ± 0.007

0.464 ± 0.023

0.910 ± 0.051

0.633 ± 0.034

14.0/25

DDOM

0.908 ± 0.024

0.930 ± 0.005

0.452 ± 0.028

0.913 ± 0.047

0.616 ± 0.018

15.8/25

COMs

0.916 ± 0.026

0.949 ± 0.016

0.460 ± 0.040

0.953 ± 0.038

0.644 ± 0.052

10.3/25

RoMA

0.430 ± 0.048

0.767 ± 0.031

0.494 ± 0.025

0.665 ± 0.000

0.553 ± 0.000

20.1/25

IOM

0.889 ± 0.034

0.928 ± 0.008

0.491 ± 0.034

0.925 ± 0.054

0.628 ± 0.036

14.1/25

BDI

0.963 ± 0.000

0.941 ± 0.000

0.508 ± 0.013

0.973 ± 0.000

0.658 ± 0.000

5.9/25

ICT

0.915 ± 0.024

0.947 ± 0.009

0.494 ± 0.026

0.897 ± 0.050

0.659 ± 0.024

10.0/25

Tri-Mentoring

0.891 ± 0.011

0.947 ± 0.005

0.503 ± 0.013

0.956 ± 0.000

0.662 ± 0.012

8.0/25

FGM

0.923 ± 0.023

0.944 ± 0.014

0.481 ± 0.024

0.811 ± 0.079

0.611 ± 0.008

14.2/25

LTR

0.920 ± 0.026

0.958 ± 0.011

0.509 ± 0.027

0.977 ± 0.008

0.655 ± 0.013

4.8/25

GABO

0.038 ± 0.012

0.719 ± 0.001

0.374 ± 0.020

0.926 ± 0.038

0.619 ± 0.043

21.1/25

DynAMO-Adam

0.113 ± 0.085

0.789 ± 0.059

0.413 ± 0.106

0.719 ± 0.142

0.556 ± 0.090

23.0/25

0.933 ± 0.016

0.952 ± 0.008

0.504 ± 0.021

0.824 ± 0.067

0.655 ± 0.050

8.7/25

ROOT

0.955 ± 0.017

0.971 ± 0.005

0.451 ± 0.032

0.977 ± 0.015

0.653 ± 0.030

7.1/25

BONET

0.921 ± 0.031

0.949 ± 0.016

0.390 ± 0.022

0.798 ± 0.123

0.575 ± 0.039

16.5/25

GTG

0.855 ± 0.044

0.942 ± 0.017

0.480 ± 0.055

0.910 ± 0.040

0.619 ± 0.029

15.0/25

Trajectory Learning PGS

0.715 ± 0.046

0.954 ± 0.022

0.444 ± 0.020

0.889 ± 0.061

0.634 ± 0.040

14.6/25

0.958 ± 0.012

0.955 ± 0.013

0.535 ± 0.030

0.956 ± 0.013

0.674 ± 0.044

3.1/25

Inverse/Conditional Generative Modeling

Regularized Surrogate Modeling

Trajectory-Informed MATCH-OPT Optimization

Generative

UGTL

smoothness for generated trajectories, while tying GTG on constructed-trajectory smoothness. These results show that UGTL produces trajectories that remain in high-value regions and change more smoothly between successive moves.

5.3.2. Controlled BBOB Comparison Figure 3 reports the controlled BBOB results, i.e., the 100th-percentile normalized scores achieved by different trajectory construction methods (using the same downstream diffusion model and sampler) 32

BONET

3

3

4

4

3.8

3.9

GTG

2.2

1.7

1.9

1.5

1.9

1.6

PGS

3.6

4

3

3

3.2

3.1

UGTL

1.2

1.3

1.1

1.5

1.1

1.4

DB regret

DB smooth.

BBOB-C regret

BBOB-C smooth.

BBOB-G regret

BBOB-G smooth.

Figure 2: Mean-rank summary of trajectory quality (lower is better).

3

2

1

Mean rank (lower is better)

4

DB reports constructed-

trajectory regret over five Design-Bench tasks and smoothness over its three continuous tasks. BBOB reports regret/smoothness for constructed (C) and generated (G) trajectories over eight function– dimension pairs. Each cell is the task-averaged rank of one method.

in BBOB tasks. UGTL obtains the highest mean on all four Rastrigin tasks and three of the four Rosenbrock tasks. It achieves the best mean rank of 1.1/4, compared with 2.3/4 for GTG, 3.0/4 for PGS, and 3.6/4 for BONET. Since the downstream diffusion model and sampler are shared, the improvement directly demonstrates the effect of the trajectory constructor in this controlled setting. BONET

PGS

GTG

UGTL

Best normalized score

Rastrigin

Rosenbrock 1.000

0.80

0.975

0.75

0.950

0.70

0.925 0.65

0.900

0.60 5

10

15

20

5

Dimension

10

15

20

Dimension

Figure 3: Controlled BBOB performance as the dimension increases (mean ± standard deviation over eight runs). Each result is the final 100th percentile normalized score achieved by different trajectory construction methods, with standard deviation across different runs. All methods use the same downstream diffusion model and sampler.

5.4. Ablation Studies We first examine whether the UGTL constructor can transfer to other trajectory models and whether Cluster-then-Select improves candidate generation. Then, we study sensitivity to the main hyperpa33

rameters of trajectory construction and candidate generation.

5.4.1. Trajectory Construction and Candidate Selection Trajectory-constructor replacement. We replace the original constructor in BONET’s Transformer pipeline, PGS’s offline-RL pipeline, and GTG’s diffusion pipeline with the UGTL constructor, while leaving their downstream models and training procedures unchanged. Figure 4(a) reports the change from each original pipeline. The replacement improves 13 of the 15 architecture–task pairs and increases the five-task average for all three architectures, with the largest improvement in the offline-RL pipeline. This transfer shows that the constructed trajectories are useful beyond UGTL’s diffusion model.

Candidate selection. Figure 4(b) compares Cluster-then-Select with directly returning the top Q candidates ranked by the proxy. Cluster-then-Select improves the mean score on all five tasks, showing the benefit of distributing the evaluation budget across different high-proxy regions. 0.15 +0.027

-0.006

+0.053

+0.008

+0.038

0.05 Offline RL

+0.153

+0.024

+0.052

+0.088

+0.061

0.00 −0.05

Diffusion

+0.041

An

t

-0.008

i D 'K

tty Su

p

+0.049

+0.015

d.

-8

on erc

T

ind F-B

TF

+0.029

d Bin

-10

+0.062

0.06

0.10

Selection gain

Transformer

0.04

+0.031 +0.026 +0.021

0.02

−0.10 −0.15

(a) Gain from replacing the trajectory constructor

+0.006

0.00 An

t

. itty ond ind-8 d-10 n D'K perc -B -Bi F T TF Su

(b) Gain from Cluster-then-Select

Figure 4: Module ablations on Design-Bench. (a) Change in normalized score after replacing the native constructor of each downstream architecture with the UGTL constructor. (b) Change from applying Cluster-then-Select to the diffusion pipeline. Positive values indicate improvement.

5.4.2. Hyperparameter Sensitivity To better understand the sensitivity of UGTL, we vary one hyperparameter at a time while fixing the others at their main values. The sweeps use Ntraj ∈ {1000, 2000, 4000}, H ∈ {32, 64, 128}, K ∈ {10, 20, 50}, ξ ∈ {0.01, 0.05, 0.10}, pinit ∈ {10%, 20%, 30%}, and λtar ∈ {1.0, 1.3, 1.5}. The three Mpool settings shown as 1k, 2k, and 4k are 1024, 2048 and 4096, respectively. Figures 5–10 report the change

34

1k

2k

4k

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 5: Sensitivity to the number Ntraj of constructed trajectories. Points show the change from each task’s main setting; black rings identify the main settings. Higher is better. 32

64

128

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 6: Sensitivity to the trajectory horizon H. Points show the change from each task’s main setting; black rings identify the main setting. Higher is better. 10

20

50

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 7: Sensitivity to the neighborhood size K. Points show the change from each task’s main setting; black rings identify the main setting. Higher is better.

in normalized score from each task’s main setting. Black rings indicate the settings used in the main experiments, while horizontal error bars show ± one standard deviation over eight independent runs. We can observe from Figures 5–10 consistent patterns across tasks. The common settings H = 64, K = 20, pinit = 20%, and Mpool = 2048 obtain the best mean on all five tasks in their respective 35

.01

.05

.10

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 8: Sensitivity to the score-relaxation tolerance ξ. Points show the change from each task’s main setting; black rings identify the main settings. Higher is better. 10%

20%

30%

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 9: Sensitivity to the initial percentile pinit . Points show the change from each task’s main setting; black rings identify the main setting. Higher is better. 1.0

1.3

1.5

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 10: Sensitivity to the target multiplier λtar . Points show the change from each task’s main setting; black rings identify the main settings. Higher is better.

studies, showing that these hyperparameters can be shared across tasks. The remaining parameters also follow simple choices: for trajectory construction, the three continuous tasks use Ntraj = 4,000 and the two discrete tasks use Ntraj = 1,000, while ξ = 0.05 and λtar = 1.3 work well on four of the five tasks. Overall, UGTL admits a unified configuration for most hyperparameters, with only limited

36

1k

2k

4k

Main setting

Ant D'Kitty Supercond. TF-Bind-8 TF-Bind-10 −30

−20

−10

0

10

Change from the main setting (normalized-score points)

Figure 11: Sensitivity to the pre-screening pool size Mpool . Points show the change from each task’s main setting; black rings identify the main setting. Higher is better.

adjustment for the remaining ones, suggesting that extensive per-task tuning is unnecessary.

6. Conclusion

This paper revisits learnability in offline data-driven optimization from an algorithm-dependent perspective. PAC or PMAC learnability can leave the optimal region unreliable even when average prediction under the sampling distribution is accurate, and thus cannot guarantee good approximations for offline optimization [5, 6, 7]. Algorithm-dependent learnability instead localizes accuracy to the information queried along an optimizer’s trajectory. Its value-query form yields good approximation guarantees for greedy and local search algorithms on representative submodular optimization problems, while its first-order form yields a good guarantee for projected gradient descent on convex minimization. Motivated by algorithm-dependent learnability, we develop a trajectory-learning framework (which consists of trajectory construction, trajectory modeling, and candidate generation) and analyze existing trajectory-based methods in a unified way. Using this framework, we further propose UGTL, an uncertainty-aware gradient-guided instantiation with conditional diffusion and diversity-aware selection. To better reflect the behavior of optimizers, the trajectories are constructed with the guidance of the gradient and prediction uncertainty of an ensemble of surrogate models. UGTL achieves the best mean rank, 3.1/25, among 25 methods on five Design-Bench tasks. Under matched downstream models and samplers, controlled BBOB experiments and cross-architecture replacements show that the constructor substantially shapes the improvement behavior learned by the downstream model; diversity-aware selection further raises the reported mean on all five tasks. Extending the principle of algorithm-dependent learnability to more complex offline scenarios (e.g., multi-objective [68] and universal [58] offline optimization) will be interesting future work.

37

7. Acknowledgements

We want to thank Dr. Shen-Huan Lyu from Hohai University for his helpful discussion and proofreading the paper. This work was supported by the National Science and Technology Major Project (2022ZD0116600), the National Science Foundation of China (62276124, 624B2069), the Fundamental Research Funds for the Central Universities (14380020), the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (JYB2025XDXM118), and the “111 Center” (B26023). Chao Qian is the corresponding author.

References [1] M. Ahn, H. Zhu, K. Hartikainen, H. Ponte, A. Gupta, S. Levine, and V. Kumar. ROBEL: Robotics benchmarks for learning with low-cost robots. In Proceedings of the 4th Conference on Robot Learning (CoRL’20), pages 1300–1313, Virtual, 2020. [2] D. Arthur and S. Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’07), pages 1027–1035, New Orleans, LA, 2007. [3] A. Badanidiyuru, S. Dobzinski, H. Fu, R. Kleinberg, N. Nisan, and T. Roughgarden. Sketching valuation functions. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12), pages 1025–1035, Kyoto, Japan, 2012. [4] M.-F. Balcan and N. J. A. Harvey. Learning submodular functions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC’11), pages 793–802, San Jose, CA, 2011. [5] E. Balkanski, A. Rubinstein, and Y. Singer. The limitations of optimization from samples. Journal of the ACM, 69(3):1–33, 2022. [6] E. Balkanski and Y. Singer. Minimizing a submodular function from samples. In Advances in Neural Information Processing Systems 30 (NeurIPS’17), pages 814–822, Long Beach, CA, 2017. [7] E. Balkanski and Y. Singer. The sample complexity of optimizing a convex function. In Proceedings of the 30th Conference on Learning Theory (COLT’17), pages 275–301, Amsterdam, The Netherlands, 2017. [8] L. A. Barrera, A. Vedenko, J. V. Kurland, J. M. Rogers, S. S. Gisselbrecht, E. J. Rossin, J. C. Woodard, L. Mariani, K. H. Kock, S. Inukai, T. Siggers, L. Shokri, R. Gordân, N. Sahni, C. Cotsapas, T. Hao, S. S. Yi, M. Kellis, M. J. Daly, M. Vidal, D. E. Hill, and M. L. Bulyk. Survey 38

of variation in human transcription factors reveals prevalent DNA binding changes. Science, 351(6280):1450–1454, 2016. [9] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAI Gym. arXiv:1606.01540, 2016. [10] D. Brookes, H. Park, and J. Listgarten. Conditioning by adaptive sampling for robust design. In Proceedings of the 36th International Conference on Machine Learning (ICML’19), pages 773–782, Long Beach, CA, 2019. [11] Y. Chemingui, A. Deshwal, T. N. Hoang, and J. R. Doppa. Offline model-based optimization via policy-guided gradient search. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI’24), pages 11230–11239, Vancouver, Canada, 2024. [12] C. Chen, C. Beckham, Z. Liu, X. Liu, and C. Pal. Parallel-mentoring for offline model-based optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS’23), pages 76619–76636, New Orleans, LA, 2023. [13] C. Chen, Y. Zhang, J. Fu, X. Liu, and M. Coates. Bidirectional learning for offline infinitewidth model-based optimization.

In Advances in Neural Information Processing Systems 35

(NeurIPS’22), pages 29454–29467, New Orleans, LA, 2022. [14] W. Chen, X. Sun, J. Zhang, and Z. Zhang. Optimization from structured samples for coverage functions. In Proceedings of the 37th International Conference on Machine Learning (ICML’20), pages 1715–1724, Virtual Event, 2020. [15] Y. Chen, X. Song, C. Lee, Z. Wang, R. Zhang, D. Dohan, K. Kawakami, G. Kochanski, A. Doucet, M. Ranzato, S. Perel, and N. de Freitas. Towards learning universal hyperparameter optimizers with transformers. In Advances in Neural Information Processing Systems 35 (NeurIPS’22), New Orleans, LA, 2022. [16] M. C. Dao, T. H. Tran, P. L. Nguyen, T. N. Truong, and T. N. Hoang. ROOT: Rethinking offline optimization as distributional translation via probabilistic bridge. In Advances in Neural Information Processing Systems 38 (NeurIPS’25), pages 98783–98817, San Diego, CA, 2025. [17] A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML’11), pages 1057–1064, Bellevue, WA, 2011. [18] U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634–652, 1998.

39

[19] U. Feige, V. S. Mirrokni, and J. Vondrak. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133–1153, 2011. [20] C. Feng, C. Qian, and K. Tang. Unsupervised feature selection by Pareto optimization. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI’19), pages 3534–3541, Honolulu, HI, 2019. [21] S. Finck, N. Hansen, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Presentation of the noiseless functions. Technical Report 2009/20, Research Center PPE, 2009. [22] P. I. Frazier and J. Wang. Bayesian Optimization for Materials Design. Springer, 2016. [23] J. Fu and S. Levine. Offline model-based optimization via normalized maximum likelihood estimation. In Proceedings of the 9th International Conference on Learning Representations (ICLR’21), Virtual, 2021. [24] R. Garnett. Bayesian Optimization. Cambridge University Press, 2023. [25] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42(6):1115–1145, 1995. [26] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. [27] K. Hamidieh. A data-driven statistical model for predicting the critical temperature of a superconductor. Computational Materials Science, 154:346–354, 2018. [28] N. Hansen. The CMA evolution strategy: A tutorial. arXiv:1604.00772, 2016. [29] C. Harshaw, M. Feldman, J. Ward, and A. Karbasi. Submodular maximization beyond nonnegativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning (ICML’19), pages 2634–2643, Long Beach, CA, 2019. [30] X. He, H. Shang, and C. Qian. How to train algorithm selection models: Insights from black-box continuous optimization. In Proceedings of the 26th ACM Genetic and Evolutionary Computation Conference (GECCO’25) Companion, pages 1957–1965, Málaga, Spain, 2025. [31] X. He, H. Shang, B. Zhang, W. Yang, and C. Qian. Budget-aware algorithm selection for black-box optimization. In Proceedings of the 27th ACM Genetic and Evolutionary Computation Conference (GECCO’26) Companion, pages 521–524, San José, Costa Rica, 2026.

40

[32] M. Hoang, A. Fadhel, A. Deshwal, J. R. Doppa, and T. N. Hoang. Learning surrogates for offline black-box optimization via gradient matching. In Proceedings of the 41st International Conference on Machine Learning (ICML’24), pages 18374–18393, Vienna, Austria, 2024. [33] B. Hsieh, P. Hsieh, and X. Liu. Reinforced few-shot acquisition function learning for Bayesian optimization. In Advances in Neural Information Processing Systems 34 (NeurIPS’21), pages 7718–7731, Virtual, 2021. [34] M. Janner, Y. Du, J. Tenenbaum, and S. Levine. Planning with diffusion for flexible behavior synthesis. In Proceedings of the 39th International Conference on Machine Learning (ICML’22), pages 9902–9915, Baltimore, MD, 2022. [35] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03), pages 137–146, Washington, DC, 2003. [36] M. Kim, J. Gu, Y. Yuan, T. Yun, Z. Liu, Y. Bengio, and C. Chen. Offline model-based optimization: Comprehensive review. Transactions on Machine Learning Research, 2026. [37] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR’15), San Diego, CA, 2015. [38] S. Krishnamoorthy, S. M. Mashkaria, and A. Grover. Diffusion models for black-box optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML’23), pages 17842– 17857, Honolulu, HI, 2023. [39] J. G. Kuba, M. Uehara, S. Levine, and P. Abbeel. Functional graphical models: Structure enables offline data-driven optimization. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS’24), pages 2449–2457, Valencia, Spain, 2024. [40] A. Kumar and S. Levine. Model inversion networks for model-based optimization. In Advances in Neural Information Processing Systems 33 (NeurIPS’20), pages 5126–5137, Virtual, 2020. [41] R. T. Lange, T. Schaul, Y. Chen, C. Lu, T. Zahavy, V. Dalibard, and S. Flennerhag. Discovering attention-based genetic algorithms via meta-black-box optimization. In Proceedings of the 25th ACM Conference on Genetic and Evolutionary Computation (GECCO’23), pages 929–937, Lisbon, Portugal, 2023. [42] D.-X. Liu, X. Mu, and C. Qian. Human assisted learning by evolutionary multi-objective optimization. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI’23), pages 12453–12461, Washington, DC, 2023.

41

[43] C. Lu, K. Xue, L. Yuan, Y. Wang, Y. Wang, S. Fu, and C. Qian. Sequential multi-agent dynamic algorithm configuration. In Advances in Neural Information Processing Systems 38 (NeurIPS’25), San Diego, CA, 2025. [44] Z. Lu, K. Xue, Y. Deng, J. Fan, P. Fang, B. S. Wade, L. Alegret, M. J. Benton, Y. Wu, C. Qian, et al. Complex marine ecological response during the Eocene-Oligocene revealed by global foraminiferal record. Nature Communications, 17(1):3954, 2026. [45] S.-H. Lyu, R.-X. Tan, K. Xue, Y.-X. He, Y. Huang, Q. Zhang, and C. Qian. On the learnability of offline model-based optimization: A ranking perspective. arXiv:2603.04000, 2026. [46] S. M. Mashkaria, S. Krishnamoorthy, and A. Grover. Generative pretraining for black-box optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML’23), pages 24173–24197, Honolulu, HI, 2023. [47] S. Müller, M. Feurer, N. Hollmann, and F. Hutter. PFNs4BO: In-context learning for Bayesian optimization. In Proceedings of the 40th International Conference on Machine Learning (ICML’23), pages 25444–25470, Honolulu, HI, 2023. [48] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions – I. Mathematical Programming, 14(1):265–294, 1978. [49] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer, 2004. [50] H. Qi, Y. Su, A. Kumar, and S. Levine. Data-driven offline decision-making via invariant representation learning. In Advances in Neural Information Processing Systems 35 (NeurIPS’22), pages 13226–13237, New Orleans, LA, 2022. [51] C. Qian, J.-C. Shi, Y. Yu, K. Tang, and Z.-H. Zhou. Subset selection under noise. In Advances in Neural Information Processing Systems 30 (NeurIPS’17), pages 3563–3573, Long Beach, CA, 2017. [52] C. Qian, Y. Yu, and Z.-H. Zhou. Subset selection by Pareto optimization. In Advances in Neural Information Processing Systems 28 (NeurIPS’15), pages 1765–1773, Montreal, Canada, 2015. [53] N. Rosenfeld, E. Balkanski, A. Globerson, and Y. Singer. Learning to optimize combinatorial functions. In Proceedings of the 35th International Conference on Machine Learning (ICML’18), pages 4374–4383, Stockholm, Sweden, 2018. [54] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas. Taking the human out of the loop: A review of Bayesian optimization. Proceedings of the IEEE, 104(1):148–175, 2016.

42

[55] Y. Shi, K. Xue, L. Song, and C. Qian. Macro placement by wire-mask-guided black-box optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS’23), pages 6825–6843, New Orleans, LA, 2023. [56] L. Song, C.-X. Gao, K. Xue, C. Wu, D. Li, J. Hao, Z. Zhang, and C. Qian. Reinforced in-context black-box optimization. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI’25), pages 8939–8947, Montreal, Canada, 2025. [57] L. Song, K. Xue, X. Huang, and C. Qian. Monte Carlo tree search based variable selection for high dimensional Bayesian optimization. In Advances in Neural Information Processing Systems 35 (NeurIPS’22), New Orleans, LA, 2022. [58] R.-X. Tan, M. Chen, K. Xue, Y. Wang, Y. Wang, S. Fu, and C. Qian. Towards universal offline black-box optimization via learning language model embeddings. In Proceedings of the 42nd International Conference on Machine Learning (ICML’25), pages 58499–58544, Vancouver, Canada, 2025. [59] R.-X. Tan, K. Xue, S.-H. Lyu, H. Shang, Y. Wang, Y. Wang, S. Fu, and C. Qian. Offline modelbased optimization by learning to rank. In Proceedings of the 13th International Conference on Learning Representations (ICLR’25), Singapore, 2025. [60] K. Terayama, M. Sumita, R. Tamura, and K. Tsuda. Black-box optimization for automated discovery. Accounts of Chemical Research, 54(6):1334–1346, 2021. [61] B. Trabucco, X. Geng, A. Kumar, and S. Levine. Design-Bench: Benchmarks for data-driven offline model-based optimization. In Proceedings of the 39th International Conference on Machine Learning (ICML’22), pages 21658–21676, Baltimore, MD, 2022. [62] B. Trabucco, A. Kumar, X. Geng, and S. Levine. Conservative objective models for effective offline model-based optimization. In Proceedings of the 38th International Conference on Machine Learning (ICML’21), pages 10358–10368, Virtual, 2021. [63] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. [64] S. Wang, K. Xue, L. Song, X. Huang, and C. Qian. Monte Carlo tree search based space transfer for black box optimization. In Advances in Neural Information Processing Systems 37 (NeurIPS’24), Vancouver, Canada, 2024. [65] R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8:229–256, 1992.

43

[66] M. Wistuba and J. Grabocka. Few-shot Bayesian optimization with deep kernel surrogates. In Proceedings of the 9th International Conference on Learning Representations (ICLR’21), Virtual, 2021. [67] K. Xue, R.-T. Chen, R.-X. Tan, X. Lin, Y. Shi, S. Xu, M. Yuan, and C. Qian. BBOPlace-bench: Benchmarking black-box optimization for chip placement. IEEE Transactions on Evolutionary Computation, 2026. [68] K. Xue, R.-X. Tan, X. Huang, and C. Qian. Offline multi-objective optimization. In Proceedings of the 41st International Conference on Machine Learning (ICML’24), pages 55595–55624, Vienna, Austria, 2024. [69] K. Xue, J. Xu, L. Yuan, M. Li, C. Qian, Z. Zhang, and Y. Yu. Multi-agent dynamic algorithm configuration. In Advances in Neural Information Processing Systems 35 (NeurIPS’22), New Orleans, LA, 2022. [70] M. S. Yao, J. C. Gee, and O. Bastani. Diversity by design: Leveraging distribution matching for offline model-based optimization. In Proceedings of the 42nd International Conference on Machine Learning (ICML’25), pages 71687–71738, Vancouver, Canada, 2025. [71] M. S. Yao, Y. Zeng, H. Bastani, J. R. Gardner, J. C. Gee, and O. Bastani. Generative adversarial model-based optimization via source critic regularization. In Advances in Neural Information Processing Systems 37 (NeurIPS’24), pages 44009–44039, Vancouver, Canada, 2024. [72] S. Yu, S. Ahn, L. Song, and J. Shin. RoMA: Robust model adaptation for offline model-based optimization. In Advances in Neural Information Processing Systems 34 (NeurIPS’21), pages 4619–4631, Virtual, 2021. [73] Y. Yuan, C. Chen, Z. Liu, W. Neiswanger, and X. Liu.

Importance-aware co-teaching for

offline model-based optimization. In Advances in Neural Information Processing Systems 36 (NeurIPS’23), pages 55718–55733, New Orleans, LA, 2023. [74] T. Yun, S. Yun, J. Lee, and J. Park. Guided trajectory generation with diffusion models for offline model-based optimization. In Advances in Neural Information Processing Systems 37 (NeurIPS’24), Vancouver, Canada, 2024. [75] Z.-H. Zhou, Y. Yu, and C. Qian. Evolutionary Learning: Advances in Theories and Algorithms. Springer, 2019.

44

Related documents

• Rethinking Learnability in Offline Data-driven Optimization#822048
• Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications#974633
• Find Your Optimal Teacher: Personalized Data Synthesis via Router-Guided Multi-Teacher Distillation#1049687
• Sustainability of Open-Source Machine Learning Robustness Assessment Tools: A Repository Mining Study#618630
• Offline Policy Evaluation as a decision support tool for designing Adaptive Experiments#1104472