# Rethinking Learnability in Offline Data-driven Optimization

arXiv: https://arxiv.org/abs/2609.01493 · HTML: https://mlsanity.com/paper/2609.01493/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 72 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Builds on (most cited first, 30 of 41)

- [Planning with Diffusion for Flexible Behavior Synthesis](https://mlsanity.com/paper/2205.09991/) (2022)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Conditioning by adaptive sampling for robust design](https://mlsanity.com/paper/1901.10060/) (2019)
- [Design-Bench: Benchmarks for Data-Driven Offline Model-Based Optimization](https://mlsanity.com/paper/2202.08450/) (2022)
- [Conservative Objective Models for Effective Offline Model-Based Optimization](https://mlsanity.com/paper/2107.06882/) (2021)
- [Model Inversion Networks for Model-Based Optimization](https://mlsanity.com/paper/1912.13464/) (2019)
- [Towards Learning Universal Hyperparameter Optimizers with Transformers](https://mlsanity.com/paper/2205.13320/) (2022)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Diffusion Models for Black-Box Optimization](https://mlsanity.com/paper/2306.07180/) (2023)
- [PFNs4BO: In-Context Learning for Bayesian Optimization](https://mlsanity.com/paper/2305.17535/) (2023)
- [ROBEL: Robotics Benchmarks for Learning with Low-Cost Robots](https://mlsanity.com/paper/1909.11639/) (2019)
- [Few-Shot Bayesian Optimization with Deep Kernel Surrogates](https://mlsanity.com/paper/2101.07667/) (2021)
- [Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation](https://mlsanity.com/paper/2102.07970/) (2021)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Generative Pretraining for Black-Box Optimization](https://mlsanity.com/paper/2206.10786/) (2022)
- [Multi-agent Dynamic Algorithm Configuration](https://mlsanity.com/paper/2210.06835/) (2022)
- [Bidirectional Learning for Offline Infinite-width Model-based Optimization](https://mlsanity.com/paper/2209.07507/) (2022)
- [Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization](https://mlsanity.com/paper/2304.03995/) (2023)
- [Data-Driven Offline Decision-Making via Invariant Representation Learning](https://mlsanity.com/paper/2211.11349/) (2022)
- [Importance-aware Co-teaching for Offline Model-based Optimization](https://mlsanity.com/paper/2309.11600/) (2023)
- [Parallel-mentoring for Offline Model-based Optimization](https://mlsanity.com/paper/2309.11592/) (2023)
- [Reinforced Few-Shot Acquisition Function Learning for Bayesian Optimization](https://mlsanity.com/paper/2106.04335/) (2021)
- [Macro Placement by Wire-Mask-Guided Black-Box Optimization](https://mlsanity.com/paper/2306.16844/) (2023)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Offline Model-Based Optimization via Policy-Guided Gradient Search](https://mlsanity.com/paper/2405.05349/) (2024)
- [Guided Trajectory Generation with Diffusion Models for Offline Model-based Optimization](https://mlsanity.com/paper/2407.01624/) (2024)
- [Offline Model-Based Optimization: Comprehensive Review](https://mlsanity.com/paper/2503.17286/) (2025)
- [Reinforced In-Context Black-Box Optimization](https://mlsanity.com/paper/2402.17423/) (2024)
- [Offline Multi-Objective Optimization](https://mlsanity.com/paper/2406.03722/) (2024)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)

## Abstract (arXiv)

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.