PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking Learnability in Offline Data-driven Optimization

Chao Qian, Chen-Guang Wang, Rong-Xi Tan, Ke Xue

arXiv:2609.01493v2cs.LGcs.AIcs.NE

TL;DR

Offline optimization needs learnability guarantees that support optimization from fixed data, because PAC or PMAC accuracy can leave the optimal region unreliable. The paper proposes algorithm-dependent learnability and a trajectory-learning framework, instantiates it as UGTL, and reports a best mean rank of 3.1/25 among 25 methods on five Design-Bench tasks.

  • Problem

    PAC or PMAC learnability can leave the optimal region unreliable despite accurate average prediction, so it cannot guarantee good offline approximations.

  • Method

    The paper localizes accuracy to an optimizer’s trajectory, formalizes trajectory construction, modeling, and candidate generation, and proposes UGTL with conditional diffusion and diverse selection.

  • Results

    UGTL achieves the best mean rank, 3.1/25, among 25 methods on five Design-Bench tasks.

  • Takeaways & Limitations

    The value-query form provides good approximation guarantees, while trajectory construction substantially shapes downstream improvement behavior.

  • Takeaways & Limitations

    The paper’s learnability analysis is framed around PAC or PMAC limitations and representative optimizer settings rather than a universally stated guarantee.

Abstract

from arXiv · show

Black-Box Optimization (BBO) has broad applications, while traditional algorithms such as evolutionary algorithms and Bayesian optimization face efficiency challenges as real-world BBO problems grow increasingly complex. Data-driven optimization has been the most popular paradigm to improve the efficiency of BBO, by learning from data. Offline data-driven optimization seeks high-quality solutions using only a fixed set of previous evaluations, attracting substantial attention because it requires no additional online evaluations. Many offline optimization methods have been proposed, but a fundamental question remains unanswered: what learnability is sufficient for offline optimization? Prior theoretical studies show that Probably Approximately Correct (PAC) learnability is insufficient, as the optimal region may remain poorly learned even when most regions are well learned. In this paper, we propose algorithm-dependent learnability, which requires accuracy only on the optimizer's trajectory. We prove that its value-query form is sufficient for representative discrete settings, including greedy and local search for submodular maximization, while its first-order analogue is sufficient for projected gradient descent on convex minimization. Motivated by this notion, we formalize a trajectory-learning framework comprising trajectory construction, trajectory modeling, and candidate generation, and analyze existing trajectory-based methods under it. We further propose Uncertainty-aware Gradient-guided Trajectory Learning (UGTL), which constructs locally coherent improvement trajectories reflecting plausible search paths, models them with conditional diffusion, and selects a diverse candidate set. Our experiments show that UGTL achieves the best average rank, 3.1/25, among 25 methods on Design-Bench tasks, and confirm that our trajectory construction plays a significant role in the improvement.

1. Introduction

Black-box optimization increasingly uses data-driven methods as traditional algorithms face efficiency challenges on complex real-world problems. Offline optimization avoids new evaluations but must extrapolate from partial observations without unsupported high-value predictions, motivating targeted learnability questions.

  • BBO optimizes objectives without available analytic expressions or derivatives.
  • Traditional evolutionary and Bayesian optimization methods rely on expert-derived heuristics and guided sampling.
  • Data-driven optimization learns surrogate models, search spaces, algorithms, components, or complete optimization procedures from collected data.
  • Offline optimization infers promising candidates solely from historical evaluations, eliminating additional evaluation budgets.
  • Without new evaluations, offline optimizers must extrapolate from partial observations while avoiding unsupported high-value predictions.
  • PAC learnability can provide average predictive accuracy while leaving the optimal region poorly learned, preventing reasonable offline approximations.
  • The paper therefore asks what learnability must be accurate along the optimizer’s trajectory for offline optimization to succeed.

offline optimization?

The paper introduces algorithm-dependent learnability, which localizes accuracy requirements to an optimizer’s trajectory, and uses it to build a trajectory-learning framework. UGTL instantiates this framework and ranks first on average across five Design-Bench tasks.

  • Algorithm-dependent learnability requires accurate predictions along the trajectory an optimizer actually visits.
  • Its value-query form supports offline guarantees for greedy and local search in submodular maximization, while its first-order analogue supports projected gradient descent for convex minimization.
  • The trajectory-learning framework comprises trajectory construction, trajectory modeling, and candidate generation.
  • Analysis finds that existing trajectory-based methods’ construction procedures do not follow optimization algorithms’ search principles well.
  • UGTL constructs locally coherent improvement trajectories, models complete trajectories with conditional diffusion, and diversifies the final candidate set.
  • 3.1/25 was UGTL’s best mean rank among 25 methods across five Design-Bench tasks.
  • Trajectory construction improves performance across transferred downstream pipelines and substantially shapes learned improvement behavior under matched downstream models.

2. Offline Optimization

Offline optimization uses a static dataset to return promising solutions without querying the unknown objective. Existing approaches learn surrogates, promising-solution distributions, or optimization trajectories, each facing different extrapolation challenges.

  • Offline optimization uses only a static dataset of sampled objective evaluations to return one or a small batch of candidates.
  • The high-value region may be poorly covered, and learned-model optimization can enter out-of-distribution regions where predictions are unreliable.
  • Forward approaches: Forward methods fit a surrogate on offline data and optimize it with gradient, evolutionary, Bayesian, or other optimizers.
  • Forward approaches: Forward methods use conservatism, regularization, ensembles, representations, structural assumptions, or ranking to improve model–optimization alignment.
  • Backward or generative approaches: Backward or generative methods directly model promising-solution distributions through inverse mappings or generative steering.
  • Backward or generative approaches: Generative methods can produce diverse candidates but must extrapolate beyond offline-data support when conditioning on unseen high values.
  • Trajectory-based approaches: Trajectory-based methods synthesize or infer improving sequences that focus learning on regions traversed by an optimizer rather than the whole search space.
  • Trajectory-based approaches: Examples include BONET, PGS, GTG, MATCH-OPT, and ROOT, which use autoregressive, policy, diffusion, gradient-matching, or probabilistic-bridge mechanisms.

3. What Learnability is Sufficient for Offline Optimization?

The paper studies what learnability conditions make optimizable function classes offline optimizable from polynomially many samples. It focuses on learnability because PAC-style guarantees can coexist with offline inoptimizable problem classes.

  • Offline optimizability asks whether polynomially many samples enable an algorithm to output an α-approximate solution with high probability.
  • The paper presents offline optimizable as a unified name for the optimization-from-samples framework and omits function constraints for clarity.
  • The central question is what learnability can make already optimizable functions offline optimizable.
  • Such sufficient conditions may inform the design of better offline optimization algorithms.
  • The framework assumes interest in function classes that are both learnable and optimizable, while treating optimizability through approximation.

3.1. PAC Learnability is Not Sufficient

Prior results show that PAC/PMAC learnability can coexist with efficient optimization while remaining insufficient for reliable offline optimization. The obstruction is that critical regions determining optima may be poorly learned even when most function values are estimated accurately.

  • General limitation: PAC learnability is generally insufficient for offline optimization, despite accurate approximation over most sampled regions.Theoretical results establish this limitation across maximum coverage, submodular minimization, and convex minimization.
  • Maximum coverage: For maximum coverage, no multiplicative approximation better than 2^-Ω(√n) is achievable with polynomially many samples.The problem is both optimizable with ratio 1 −1/e and PMAC learnable.
  • Submodular minimization: For unconstrained submodular minimization, PAC learnability and polynomial-time minimizability still permit no additive approximation better than 1/2 −o(1).This negative result holds using polynomially many samples drawn from any distribution.
  • Convex minimization: For convex minimization, PAC learnability does not prevent exponential sample requirements or an additive approximation barrier of 1/2 −o(1).Offline optimizability remains impossible even under strong convexity and Lipschitz continuity.
  • Source of hardness: The hardness arises because samples cannot reliably distinguish critical partition parts that determine optimal solutions, although most partition parts are learned well.Thus, accurate estimates for almost all solutions do not ensure accurate identification of the optimum.

3.2. Algorithm-dependent Learnability

Algorithm-dependent learnability localizes accuracy requirements to the trajectory generated by a chosen optimizer rather than the whole search space. Its value-query and first-order forms support representative discrete and convex optimization settings.

  • Definition: Algorithm-dependent learnability requires approximate function accuracy only at points visited by an optimizer running on the learned function.This avoids requiring functions to be learned everywhere, unlike recoverability.
  • First-order analogue: The first-order analogue controls gradient error only where a first-order optimizer queries gradients.Its condition is ||∇f̃(x) −∇f(x)||≤ζ_g at queried points.
  • Sufficient conditions: Value-query algorithm-dependent learnability is sufficient for greedy maximization and local search in representative submodular settings.The covered cases are monotone approximately submodular maximization with a size constraint and unconstrained non-monotone submodular maximization.
  • Sufficient conditions: First-order algorithm-dependent learnability is sufficient for projected gradient descent on convex minimization.The result transfers guarantees by running an existing optimizer on the learned function.
  • Underlying principle: The framework relies on optimizer-specific information: reliable values guide value-query algorithms, while reliable gradients guide first-order algorithms.Structural properties such as approximate submodularity or convexity convert local relations into global approximation guarantees.

Theorem 4

Theorem 4 establishes that algorithm-dependent learnability is sufficient for offline monotone approximately submodular maximization with a size constraint using greedy search.

  • The result concerns monotone approximately submodular maximization under a size constraint, with samples drawn from distribution D.
  • Algorithm-dependent learnability lets greedy optimization on the learned function retain the required monotone approximately submodular property.
  • The greedy algorithm’s returned subset satisfies the offline approximation condition under the theorem’s learnability assumption.
  • The proof adapts the standard greedy approximation analysis by using trajectory-wise accuracy to connect the learned and true functions.

Theorem 5

Theorem 5 shows that algorithm-dependent learnability is sufficient for offline unconstrained non-monotone submodular maximization using local search, which alternates additions and deletions and returns the better set or complement.

  • Algorithm-dependent learnability makes unconstrained non-monotone submodular maximization α-offline-optimizable with local search.
  • The proof uses learned-function accuracy on every solution visited during local search to preserve the analysis linking learned and true objectives.
  • The local-search analysis is adapted from the value-oracle approximation proof and includes a running-time bound based on the number of iterations.

Theorem 6

Theorem 6 establishes that first-order algorithm-dependent learnability is sufficient for offline convex minimization with projected gradient descent, whose trajectory is determined by gradients.

  • Convexity converts the average performance over projected-gradient iterates into a guarantee for the returned mean iterate.
  • The proof follows projected-gradient-descent analysis while connecting learned and true gradients only along the generated trajectory.
  • The guarantee controls gradient accuracy along the generated trajectory rather than function-value accuracy at value-query points.

4. Offline Optimization Inspired by Algorithm-dependent Learnability

The paper develops a trajectory-learning framework for offline optimization that focuses learning on plausible search paths and matches the learned information to the optimizer’s decision signal. It uses this framework to diagnose existing methods and motivate UGTL, whose locally coherent, directionally guided trajectories are retained after modeling.

  • Design principle: Offline optimizers should preserve information along plausible search processes and match the learned object to the signal driving the next decision.
  • Framework: The framework comprises trajectory construction, trajectory modeling, and candidate generation from a fixed offline dataset.
  • Framework: Trajectory construction determines which empirical search behavior is visible, modeling captures it, and candidate generation converts it into designs.
  • Scope: Because later stages can exploit only the supervision supplied by constructed paths, incoherent trajectories may cause capable models to learn unsuitable search dynamics.
  • Scope: The framework’s connection to algorithm-dependent learnability is motivational rather than a formally verified implication because practical trajectories use the offline dataset alone.
  • Existing methods: Existing methods can construct incoherent paths: sorting or random pairing creates long transitions, while locality alone does not ensure directional improvement.
  • Existing methods: On negated Branin, GTG improves locality but lacks consistent directional guidance, producing trajectories that do not smoothly approach high-value regions.
  • UGTL: UGTL adds approximate proxy gradients and uncertainty awareness to preserve locality while guiding successive transitions toward consistent improvement.

5. Experiments

The experiments evaluate UGTL across Design-Bench and controlled BBOB settings, measuring final candidate quality, trajectory behavior, component contributions, and robustness. UGTL achieves strong benchmark and trajectory-level results, with controlled comparisons isolating the contribution of its trajectory constructor.

  • End-to-end effectiveness: UGTL achieves the best mean rank, 3.1/25, among 25 methods on five Design-Bench tasks.It is followed by LTR at 4.8 and BDI at 5.9.
  • End-to-end effectiveness: UGTL improves over the best observed offline score on all five Design-Bench tasks and leads generative trajectory methods on every task.The compared generative trajectory methods are BONET, GTG, and PGS.
  • Trajectory-level behavior: UGTL ranks first on Design-Bench regret and smoothness, and on BBOB constructed-trajectory regret plus generated-trajectory regret and smoothness.Its Design-Bench mean ranks are 1.2/4 for regret and 1.3/4 for smoothness; it ties GTG on BBOB constructed-trajectory smoothness.
  • Controlled BBOB comparison: UGTL obtains the highest mean on all four Rastrigin tasks and three of four Rosenbrock tasks, achieving a BBOB mean rank of 1.1/4.The corresponding mean ranks are 2.3/4 for GTG, 3.0/4 for PGS, and 3.6/4 for BONET.

5.4. Ablation Studies

The ablations test trajectory-constructor transfer, candidate selection, and hyperparameter sensitivity. UGTL’s constructor improves multiple downstream architectures, Cluster-then-Select improves candidate scores, and most hyperparameters work across tasks with limited adjustment.

  • Trajectory construction and candidate selection: Replacing native constructors with UGTL improves 13 of 15 architecture–task pairs and raises the five-task average for all three architectures.The largest improvement occurs in the offline-RL pipeline, while downstream models and training procedures remain unchanged.
  • Trajectory construction and candidate selection: Cluster-then-Select improves mean score on all five tasks by distributing the evaluation budget across different high-proxy regions.The comparison is against directly returning the top Q candidates ranked by the proxy.
  • Hyperparameter sensitivity: The sweeps vary Ntraj, H, K, ξ, pinit, λtar, and Mpool one at a time while fixing the other parameters at their main values.Figures 5–10 report normalized-score changes from each task’s main setting, with error bars showing ± one standard deviation over eight runs.
  • Hyperparameter sensitivity: The common settings H = 64, K = 20, pinit = 20%, and Mpool = 2048 obtain the best mean on all five tasks in their respective sweeps.These settings suggest that the main hyperparameters can be shared across tasks.
  • Hyperparameter sensitivity: The continuous tasks use Ntraj = 4,000, the discrete tasks use Ntraj = 1,000, and ξ = 0.05 and λtar = 1.3 work well on four of five tasks.The authors report a unified configuration for most hyperparameters, with limited adjustment for the remaining ones.

6. Conclusion

The paper reframes offline optimization learnability around optimizer trajectories, develops a three-stage trajectory-learning framework, and instantiates it with UGTL. UGTL achieves the best mean rank among evaluated methods, while trajectory construction substantially shapes downstream improvement behavior.

  • PAC or PMAC learnability can leave the optimal region unreliable despite accurate average prediction, so it cannot guarantee good offline approximations.
  • Algorithm-dependent learnability localizes required accuracy to information queried along an optimizer’s trajectory.
  • Value-query learnability supports approximation guarantees for greedy and local search on representative submodular problems, while first-order learnability supports projected gradient descent for convex minimization.
  • The trajectory-learning framework consists of trajectory construction, trajectory modeling, and candidate generation, and it is used to analyze existing trajectory-based methods.
  • UGTL combines uncertainty-aware gradient-guided trajectory construction, conditional diffusion modeling, and diversity-aware candidate selection.
  • 3.1/25 is UGTL’s best mean rank among 25 methods on five Design-Bench tasks, while controlled experiments show trajectory construction substantially shapes downstream improvement and diversity-aware selection raises the reported mean on all five tasks.
  • Extending algorithm-dependent learnability to multi-objective and universal offline optimization remains future work.
Loading 2609.01493v2…