Optuna的约束树形帕森估计器是c-TPE的联合密度推广

# Optuna 约束树结构 Parzen 估计器是 c-TPE 的联合密度推广

###### 摘要

受约束的超参数优化（HPO）在实际应用中很常见，然而 Optuna 中广泛使用的约束 TPE 缺乏算法分析。虽然 c-TPE 提出了一种假设目标与约束独立的期望约束改进（ECI）方法，但 Optuna 对两者使用了单一的联合密度。我们证明 Optuna 的约束 TPE 是联合 c-TPE——一种使用联合似然的相同 ECI 采集函数。我们展示了联合 c-TPE 对约束重复具有不变性，而独立 c-TPE 会随着乘积累积重复因子而性能下降。我们概述了两种公式之间的实际权衡以及未来研究的方向。

## 1 引言

深度学习算法的性能对超参数（HP）的选择很敏感，这可以形式化为一个优化问题 x⋆∈argminxf(x)。Optuna (Akiba et al., 2019) 是一个事实上的 HPO 框架，其默认算法是树结构 Parzen 估计器（TPE）(Bergstra et al., 2011; Watanabe, 2023)。TPE 根据观测数据 D={(xn,fn)}n=1N，通过顶部 γ 分位数分割来建模给定 f 的 HP 似然：

p(x|f,D)={p(x|D(l))p(x|D(g))(f≤fγ)(f>fγ)(1)

其中 fγ 是顶部 γ 分位数目标值，D(l) 和 D(g) 分别包含低于（更好）和高于（更差）fγ 的观测，两种密度都由 Parzen 估计器（也称为核密度估计器 KDE）建模。Watanabe 和 Hutter (2023) 证明了密度比与改进概率成正比：p(x|D(l))/p(x|D(g))∝P(f≤fγ∣x)。

虽然上述 TPE 公式能很好地解决单目标 HPO，但现实世界中的 HPO 通常涉及黑盒约束，例如内存预算或推理延迟。此前，Watanabe 和 Hutter (2023) 提出了一种使用期望约束改进（ECI）(Gardner et al., 2014; Gelbart et al., 2014) 的约束 TPE，该方法假设目标与约束相互独立：

ECIfγ[x|c⋆,D]=EIfγ[x|D]∏i=1CP(i≤i⋆|x,D)(2)

其中 ci(x)≤ci⋆ 对于 i∈{1,...,C} 是黑盒约束。

Optuna 的 TPE 也支持约束优化，但其实现缺乏正式文档，并且与文献中称为 c-TPE 的方法不同。Optuna 只构建一对 KDE，而 Watanabe 和 Hutter (2023) 构建了 C+1 对 KDE。尽管存在这种实现上的差异，我们发现两种方法共享相同的期望约束改进（ECI）理论基础。因此，我们将 Watanabe 和 Hutter (2023) 中给出的 c-TPE 定义限定为专门使用 ECI 作为其采集函数的公式。在此定义下，我们证明 Optuna 的约束 TPE（称为联合 c-TPE）是原始 c-TPE（称为独立 c-TPE）的联合密度推广。请注意，尽管独立 c-TPE 也可以通过 OptunaHub (Ozaki et al., 2026) 获得，但该算法并未包含在主包中。我们通过实验证明了联合 c-TPE 的关键优势，它避免了独立公式在约束相关时遭受的相对重要性稀释问题。最后，我们讨论了联合 c-TPE 中的权衡和未探索的开放问题。

## 2 研究发现：Optuna 约束 TPE 是 c-TPE 的联合密度推广

在本文中，我们分析了 Optuna v4.8 中的实现。为了形式化这种方法，我们依赖于关于可行区域中边际约束密度 p(c|D)=∫p(f,c|D)df 的以下假设：

###### 假设 1。

给定可行区域 Ω≔∏i=1C(−∞,ci⋆]，γ≤∫c∈Ωp(c|D)dc 成立。

非正式地说，这个假设要求可行区域至少包含比例为 γ 的观测（其中 c∈Ω），确保 D(l) 中存在足够的可行观测。第 4 节讨论了此假设的局限性。Optuna 方法首先将观测 D={(xn,fn,cn)}n=1N 划分为可行集 Dfeas={(xn,fn,cn)∈D∣c∈Ω} 和不可行集 D∖Dfeas。然后按目标值 fn 对可行观测排序，并用顶部 ⌈γN⌉ 个可行观测填充 D(l)。下一个 HP 通过最大化密度比 p(x|D(l))/p(x|D(g)) 选择，其中 D(g)≔D∖D(l)。重要的是，Optuna 方法联合计算目标和约束的似然：

p(x|f,c,D)={p(x|D(l))p(x|D(g))(f≤fγ and c∈Ω)(otherwise).(3)

该公式引出了以下命题：

###### 命题 1。

在公式 (3) 的联合似然下，ECIfγ[x|c⋆,D]≃rank p(x|D(l))/p(x|D(g))，其中秩等价 f(x)≃rankg(x) 表示排序保持不变：f(x)≤f(x′)⇔g(x)≤g(x′)。

**证明。** 将贝叶斯规则应用于 ECIfγ[x∣c⋆,D]∝P(f≤fγ,c∈Ω∣x,D)（由 Watanabe 和 Hutter (2023) 证明）：

ECIfγ[x∣c⋆,D]∝P(f≤fγ,c∈Ω∣x,D)=∫(f,c)∈Fγ×Ωp(x|f,c,D)p(f,c|D)p(x|D)dfdc=p(x|D(l))p(x|D)∫(f,c)∈Fγ×Ωp(f,c|D)dfdc⏟=γ∝(γ+(1−γ)p(x|D(g))p(x|D(l)))−1≃rank p(x|D(l))p(x|D(g))(4)

其中 Fγ≔(−∞,fγ] 是可行区域上的 γ 分位数目标区域，最后一行使用了 p(x|D)=γ p(x|D(l))+(1−γ) p(x|D(g))，这是通过对公式 (3) 中的联合似然在 (f,c) 上边际化得到的。∎

这个结果有三个显著的特性。首先，当所有观测都可行时，公式 (3) 中的联合分割简化为公式 (1) 中的标准 TPE 分割。其次，在可行区域上约束的 γ 分位数 fγ 与 c-TPE 对目标分量的分割相同。第三，也是最重要的，联合公式使用一对 KDE，其分割同时考虑了所有约束，而独立 c-TPE 使用 C+1 对 KDE 并分别处理每个约束的边际。这意味着在联合 c-TPE 下，重复一个约束不会改变可行/不可行划分，使得采集函数对约束重复具有不变性，这与独立 c-TPE 不同。我们在下一节中通过实验验证最后一个性质。

## 3 实验评估

我们在一个 2D 玩具问题上比较独立和联合 c-TPE，最小化 f(x,y)=(x−2)2+(y−2)2，受两个约束 c1(x,y)=x≤0, c2(x,y)=y≤0 约束，搜索空间为 [−5,5]2。我们考虑两种情景：(1) 独立约束 c1, c2，以及 (2) c1 和许多重复的 c2 副本（完全相关约束）。将具有许多重复约束的情景（底部）与独立约束情景（图 1 顶部）进行比较，独立 c-TPE 性能下降，因为每个重复项都会给相对密度比乘积增加一个因子，累积约束信息并相对于 x 轴夸大了沿 y 轴的可行性。同时，联合 c-TPE 对重复具有不变性，因为可行/不可行划分保持不变。但请注意，在独立约束情景下独立 c-TPE 优于联合 c-TPE，因为该情景更符合独立公式。

图 1：独立 c-TPE（左）和联合 c-TPE（右）在具有 50 个观测的 2D 问题上的比较。阴影区域表示可行区域，颜色渐变表示目标值，颜色越深表示目标越好。每个点代表一个观测。点根据观测顺序着色；黑色表示早期观测，白色表示后期观测。**顶部：** 没有重复约束的情况。独立 c-TPE 通过利用约束对的独立性在边界处积极探索。**底部：** 具有许多重复约束的情况；其不可行区域颜色深得多。虽然联合 c-TPE 表现出相同的采样行为，但独立 c-TPE 沿 x 轴的探索非常保守，因为沿 y 轴的可行性被过度强调了。

## 4 局限性与结论

联合 c-TPE 的一个主要方法论局限性来自假设 1。当假设 1 被违反时，Optuna 会从按总约束违反排序的不可行观测中填充 D(l) 的空槽 (Deb et al., 2002)。然而，这种回退策略的有效性和理论有效性在很大程度上尚未被探索，这与 Watanabe 和 Hutter (2023) 精心设计和分析的独立 c-TPE 不同。未解决的问题包括：(1) 哪些打破平局的策略是可行的，(2) 哪种策略表现最好，以及 (3) 联合 c-TPE 何时优于独立 c-TPE（以及何时不优）。一个关键的结构性差异是，独立 c-TPE 只需要每个约束单独有一个可行解，而联合 c-TPE 要求同时跨越所有约束的可行性。这种更严格的可行性要求可能在独立或严重约束的场景中有问题。此外，联合 c-TPE 在结构上无法容纳部分观测（参见 Watanabe 和 Hutter (2023) 的附录 C），当某些约束的评估成本低于目标时，可能会减慢收敛速度。

另一方面，联合 c-TPE 具有互补的优势。它在结构上更简单，并且自然地对约束重复具有不变性——这是独立 c-TPE 缺乏的特性。由于联合 c-TPE 只维护一对 KDE 而不是 C+1 对，它自然地与多目标 TPE 公式 (Ozaki et al., 2020, 2022) 保持一致，便于未来扩展。确定何时每种公式更可取仍然是一个悬而未决的问题，需要未来在不同问题结构上进行系统的实验比较。

### 引用指南

当使用 Optuna 的约束 TPE 时，我们建议同时引用本文和 Watanabe 和 Hutter (2023)，因为后者提供了对约束 TPE 机制和问题设置的更详细处理。

## 参考文献

- Akiba et al., (2019) Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. In *ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*.
- Bergstra et al., (2011) Bergstra, J., Bardenet, R., Bengio, Y., and Kégl, B. (2011). Algorithms for hyper-parameter optimization. In *Advances in Neural Information Processing Systems*.
- Deb et al., (2002) Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. *IEEE Transactions on Evolutionary Computation*, 6(2):182–197.
- Gardner et al., (2014) Gardner, J. R., Kusner, M. J., Xu, Z. E., Weinberger, K. Q., and Cunningham, J. P. (2014). Bayesian optimization with inequality constraints. In *International Conference on Machine Learning*.
- Gelbart et al., (2014) Gelbart, M. A., Snoek, J., and Adams, R. P. (2014). Bayesian optimization with unknown constraints. In *Uncertainty in Artificial Intelligence*.
- Ozaki et al., (2020) Ozaki, Y., Tanigaki, K., Watanabe, S., and Onishi, M. (2020). Multiobjective tree-structured Parzen estimator for computationally expensive optimization problems. In *Genetic and Evolutionary Computation Conference*.
- Ozaki et al., (2022) Ozaki, Y., Tanigaki, K., Watanabe, S., and Onishi, M. (2022). Multiobjective tree-structured Parzen estimator. *Journal of Artificial Intelligence Research*, 73:1151–1203.
- Ozaki et al., (2026) Ozaki, Y., Watanabe, S., and Onishi, M. (2026). OptunaHub: A community-driven repository for Optuna extensions. *arXiv preprint arXiv:2606.09889*.
- Watanabe (2023) Watanabe, S. (2023). Tree-structured Parzen estimator: Understanding its algorithm components and their roles for better empirical performance. *arXiv preprint arXiv:2304.11127*.
- Watanabe and Hutter (2023) Watanabe, S. and Hutter, F. (2023). c-TPE: Generalizing tree-structured Parzen estimator with inequality constraints for black-box optimization. *arXiv preprint arXiv:2311.05214*.