Pith. sign in

REVIEW 3 major objections 3 minor 36 references

Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that giving TPE's categorical kernel a user-defined distance metric lets tree-structured Parzen estimator solve black-box combinatorial optimization problems with fewer evaluations, and it provides two practical…

desk verdict Distance-aware TPE is a genuinely useful idea, but Eq. (8) as written multiplies beta where it should divide, so the paper's central modification is internally inconsistent. read the letter →

arxiv 2507.08053 v2 pith:V5OTK3EW submitted 2025-07-10 cs.LG cs.AI

Kenshin Abe , Yunzhuo Wang , Shuhei Watanabe This is my paper
classification cs.LGcs.AI
keywords tree-structuredParzenestimatorcombinatorialoptimizationcategoricalkerneldistancemetricBayesiansampleefficiencyOptuna
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the tree-structured Parzen estimator (TPE), a standard Bayesian optimization method for hyperparameters, can be made efficient on black-box combinatorial optimization problems by giving its categorical kernel a distance structure. The authors rewrite the categorical kernel in a Gaussian-like form, replace the equality-based same-or-different distance with a user-supplied metric, and add two practical fixes for large search spaces. They report on synthetic problems, an embedding/cosine task and a permutation-shift task, that the proposed method reaches better objective values in fewer evaluations than the original TPE and random search, and that the fixes prevent the overexploration seen without them. The method is shipped in the Optuna framework, so practitioners can call it directly.

What carries the argument

The load-bearing object is the generalized categorical kernel $k_d(x_d,x'_d)=\exp(-\frac12 (M_d(x_d,x'_d)/\beta)^2)$, obtained by rewriting the Aitchison-Aitken kernel and substituting a user-supplied distance $M_d$ for the binary indicator $1-\delta(x_d,x'_d)$. This one identity is what lets TPE see similarity structure among categories. Two practical mechanisms carry the large-search-space part of the argument: an approximation of $M_d^{\max}$ that costs $\Theta(C_d \min(C_d, N_d^{\mathrm{unique}}))$ instead of $\Theta(C_d^2)$, and the rescaled bandwidth $\beta'=\beta\sqrt{\log_{b_d} C_d}$ that prevents the kernel from oversmoothing (and thus overexploring) when several categorical dimensions are packed into one combinatorial parameter. The paper fixes a default $b_d=6$ and presents an ablation study of $b_d$ in the appendix.

What would settle it

Run the proposed method on EmbeddingCosine with a scrambled distance metric (for instance, permuting the labels of the 1000 categories randomly while leaving the objective unchanged) and count evaluations needed to reach a fixed objective value; if it does no better than the original TPE, the claimed efficiency gain rests entirely on the hand-designed metric. A complementary check: rerun the large EmbeddingCosine (C=1000, K=16) setup with $b_d=6$ versus $b_d=2$ and verify the overexploration pattern reported in the ablation.

Watch

Extended reading notes

Core claim

The paper's central claim is that TPE's categorical kernel, which treats every category as equally distant from every other, is the bottleneck for combinatorial optimization, and that replacing the binary coincidence factor with a user-defined distance metric removes that bottleneck. Concretely, the kernel becomes $k_d(x_d,x'_d)=\exp(-\frac12 (M_d(x_d,x'_d)/\beta)^2)$, with the scale $\beta$ chosen so that the kernel falls back to the original Aitchison-Aitken kernel when the distance is maximal. Because computing the exact maximum distance over all category pairs costs $\Theta(C_d^2)$, the paper proposes using the maximum distance to each observed point instead, and it introduces a modified scale $\beta'=\beta\sqrt{\log_{b_d} C_d}$ that assumes a combinatorial parameter encodes $\log_{b_d} C_d$ binary dimensions in order to counteract oversmoothing. The paper states that, in experiments, this identifies better solutions with fewer evaluations than the original TPE on both synthetic problems, and that the modification never degraded performance.

Load-bearing premise

The method requires the user to supply a distance metric between categories that reflects how similar two solutions are for the objective; every experiment uses a hand-designed metric aligned with the synthetic objective, and the paper provides no evidence about what happens when the metric is uninformative or misleading.

Editorial extensions

If this is right

  • If the central claim holds, TPE users can solve permutation and K-ary combinatorial problems with a user-supplied distance metric and will reach the same objective value in fewer evaluations than the original TPE.
  • The per-kernel calculation cost no longer grows quadratically with the number of categories, so larger combinatorial search spaces become feasible in memory-constrained settings.
  • Because the modification only changes the per-dimension kernel, it can be combined with other TPE extensions such as multi-objective, constrained, and multi-fidelity variants.
  • The availability in Optuna means the result is directly usable in existing HPO pipelines rather than remaining a standalone algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is to study metric misspecification: if the supplied distance is uncorrelated with the objective's similarity structure, the method should degrade to (or below) the original TPE, so real applications hinge on finding a meaningful metric; the paper does not yet address this.
  • The $\beta'$ scaling suggests an interpretation of a combinatorial parameter as a packed binary string; one could push this further by making $b_d$ adaptive to the observed objective landscape instead of fixing it at 6.
  • Since the kernel is now metric-based, a natural next step is connecting it to embeddings: choosing $M_d$ implicitly defines a geometry on the category space, so categorical variables could be embedded and handled by the numerical kernel machinery already in TPE.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. This paper proposes a distance-aware extension of the categorical kernel used in TPE, replacing the Aitchison-Aitken kernel with a Gaussian-like kernel over a user-supplied distance metric, and adds two practical modifications: an efficient approximate maximum-distance computation and a scaling of the bandwidth parameter beta intended to correct oversmoothing on large combinatorial spaces. The method is evaluated on two synthetic problems (EmbeddingCosine and PermutationShiftL1) against original TPE and random search, with code released in Optuna.

Significance. If correct, the contribution is practically relevant: a working distance-aware TPE for combinatorial spaces would fill a real gap in a widely deployed optimizer. The theoretical generalization in Section 3.1 is clean, and the release of the implementation in Optuna is a concrete asset. However, the central modification in Section 3.2.2 contains a direction error in the bandwidth scaling, and the empirical evaluation is too limited to support the paper's stated verification. The significance is therefore contingent on correcting the formulation and strengthening the experiments.

major comments (3)
  1. [Section 3.2.2, Eq. (8)] The scaling beta' = beta * sqrt(log_b C_d) is in the wrong direction. Substituting this beta' into Eq. (7), the kernel exponent at the maximum distance becomes -log((C_d-1)/h) / log_b C_d, which is smaller in magnitude than the original -log((C_d-1)/h); hence the kernel is broader, not narrower. The text and Appendix A state that a smaller b_d leads to more exploitation, but under Eq. (8) a smaller b_d gives a larger beta' and a wider kernel. To increase the maximum exponent from 1 to K (or log_b C_d), beta must be divided by sqrt(log_b C_d). Either Eq. (8) is a typo or the implemented method differs from the paper; as written, the paper does not correctly specify the modification claimed to drive the performance gains in Figure 1.
  2. [Section 3.2.2] The text states that the combined kernel for a K-bit Hamming distance is (1/(N+1))^{M_Ham/K}, but substituting h = (C_d-1)/(N+1) and M_max = K into Eq. (7) yields exp(-log(N+1) (M_Ham/K)^2), i.e. (1/(N+1))^{(M_Ham/K)^2}. The squared exponent follows from the quadratic form of the Gaussian kernel in Eq. (7) and differs from the linear exponent of the product-of-binary-kernels representation. This derivation error should be corrected; the maximum-exponent comparison (1 vs K) survives, but the interpolation behavior is not as described.
  3. [Section 4 and Section 5] The empirical evidence is too thin to support the abstract's claim that the method 'identifies better solutions with fewer evaluations' as a verification. The evaluation uses only two synthetic problems, 10 seeds, and 100 evaluations per run, with no statistical tests and no comparison to existing combinatorial Bayesian optimization methods. The paper itself acknowledges an 'inadequate methodological evaluation' in Section 5. Additionally, the default b_d = 6 is selected from an ablation on the same benchmarks (Appendix A), so the reported improvement is partly fitted rather than predicted. The experiments should be expanded with more tasks, error bars with formal comparisons, and at least one established combinatorial BO baseline; the conclusion should be tempered accordingly.
minor comments (3)
  1. [Section 4] The sentence 'we used the proposed method without the modification discussed in Section 3.2.2' is confusing, since Figure 1 shows both 'Ours' and 'Ours (No Modification)'. Please clarify that two variants of the proposed method were run.
  2. [Section 4] The phrase 'the modification in Eq. (7)' should refer to Eq. (8), since Eq. (7) defines the base kernel and Eq. (8) defines the modification.
  3. [Section 3.2.2] The assumption that a combinatorial parameter with C combinations behaves like log_b C independent categorical parameters is not derived or validated; it is used to motivate Eq. (8), so it should be stated explicitly and tested, especially because the direction of Eq. (8) depends on this assumption.

Circularity Check

1 steps flagged · score 4.0 of 10

Empirical gains are partly fitted: the default b_d=6 is selected by an ablation on the same benchmarks used for the main comparison; the kernel generalization itself is self-contained and not circular.

  1. fitted input called prediction [Section 3.2.2, Eq. (8), and Appendix A (Fig. 2)]
    "Although users can customize the control parameter b_d, e.g. b_d should be 2 in the example above, we fix b_d = 6 as a default value. Note that we performed the ablation study of b_d in Appendix A."

    The main empirical claim—'our proposed method identifies better solutions with fewer evaluations than the original TPE'—is made on the EmbeddingCosine and PermutationShiftL1 benchmarks in Fig. 1. The 'Ours' curves in Fig. 1 use the default b_d=6, which was chosen by running an ablation on the very same benchmark settings in Appendix A, Fig. 2. In other words, the default is not prespecified independently of the test problems; it is selected from the performance curves of the evaluation tasks. The reported comparison is therefore partly a tuned-configuration comparison rather than a prediction with a fixed, pre-chosen default. The core kernel derivation in Eqs.

full rationale

The central derivation is self-contained: Eq. (7) defines beta so that the new distance kernel falls back exactly to the Aitchison-Aitken kernel at maximal distance, and the modifications in Eqs. (6)-(8) are presented with explicit formulas. No load-bearing self-citation or imported uniqueness theorem is used; the citation to Watanabe (2023b) only supplies the bandwidth heuristic and is not challenged. The only substantial circular element is the choice of the default control parameter b_d=6, which is made after an ablation on the same synthetic benchmarks that are later used to claim improvement over original TPE. This does not make the kernel generalization itself circular, but it means the headline empirical result is partly fitted to the evaluation tasks. The paper's own limitation statement—'inadequate methodological evaluation to claim a more general high performance'—further tempers the empirical claim. The apparent sign-direction issue in Eq. (8) is a mathematical correctness concern about the stated modification, not a circularity in the derivation chain, so it is not counted in the circularity score.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central claim rests on one free parameter (b_d), the triangle inequality for the user metric, the unproven log_b C representation assumption, and the standard TPE framework. No new physical entities are introduced. The most fragile item is the log_b C assumption, which is essential to the overexploitation fix.

free parameters (1)
  • control parameter b_d = default 6
    Introduced in Eq (8) to scale the kernel bandwidth. The default value is set after an ablation study in Appendix A over b_d in {2,...,10} on the same synthetic benchmark problems.
assumptions (4)
  • standard math The distance metric M_d satisfies the triangle inequality.
    Used in Section 3.2.1 to bound M_max <= 2 M_d^*(x') for the per-reference maximum distance approximation.
  • ad hoc to paper A combinatorial parameter with C combinations can be treated as log_b C independent categorical parameters.
    Section 3.2.2 uses this to justify the beta' scaling in Eq (8). It is an assumption stated without derivation or empirical verification.
  • domain assumption TPE's density-ratio acquisition (argmax of p_good/p_bad) is a valid way to pick new candidates.
    The paper relies on the standard TPE framework from Section 2.2 without re-deriving its convergence or optimality properties.
  • standard math The Aitchison-Aitken kernel is the appropriate baseline categorical kernel for TPE.
    Borrowed from the established TPE literature (Section 2.2) as the starting point for the generalization.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently." pith.science (2026). https://pith.science/paper/V5OTK3EW

@misc{pith2026250708053,
  author       = {Pith},
  title        = {Pith review of: Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V5OTK3EW}},
  note         = {Machine review of arXiv:2507.08053}
}
read the original abstract

Tree-structured Parzen estimator (TPE) is a versatile hyperparameter optimization (HPO) method supported by popular HPO tools. Since these HPO tools have been developed in line with the trend of deep learning (DL), the problem setups often used in the DL domain have been discussed for TPE such as multi-objective optimization and multi-fidelity optimization. However, the practical applications of HPO are not limited to DL, and black-box combinatorial optimization is actively utilized in some domains, e.g., chemistry and biology. As combinatorial optimization has been an untouched, yet very important, topic in TPE, we propose an efficient combinatorial optimization algorithm for TPE. In this paper, we first generalize the categorical kernel with the numerical kernel in TPE, enabling us to introduce a distance structure to the categorical kernel. Then we discuss modifications for the newly developed kernel to handle a large combinatorial search space. These modifications reduce the time complexity of the kernel calculation with respect to the size of a combinatorial search space. In the experiments using synthetic problems, we verified that our proposed method identifies better solutions with fewer evaluations than the original TPE. Our algorithm is available in Optuna, an open-source framework for HPO.

Figures

Figures reproduced from arXiv: 2507.08053 by the authors.

Figure 1
Figure 1. Performance over time of each method. Each line and weak-color band show the mean and the standard error over 10 random seeds. The 𝑥- and 𝑦-axes represent the number of HP evaluations and the best objective value. Top: the results on EmbeddingCosine (𝐶 = 500, 𝐾 = 8 (Left), and 𝐶 = 1000, 𝐾 = 16 (Right)). Bottom: the results on PermutationShiftL1 (𝑝 = 6 (Left), and 𝑝 = 7 (Right)). experiments are required to draw soli… view at source ↗
Figure 2
Figure 2. Ablation study of 𝑏𝑑 in our method. Each line and weak-color band show the mean and the standard error over 10 random seeds. 𝑏𝑑 becomes higher as the plot color approaches red. The 𝑥- and 𝑦-axes represent the number of HP evaluations and the best objective value. Top: the results on EmbeddingCosine (𝐶 = 500, 𝐾 = 8 (Left), and 𝐶 = 1000, 𝐾 = 16 (Right)). Bottom: the results on PermutationShiftL1 (𝑝 = 6 (Left), and 𝑝 =… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 28 canonical work pages

  1. [1]

    and Aitken, C

    Aitchison, J. and Aitken, C. (1976). Multivariate binary discrimination by the kernel method. Biometrika , 63

    work page 1976

  2. [2]

    Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. (2019). O ptuna: A next-generation hyperparameter optimization framework. In International Conference on Knowledge Discovery & Data Mining

    work page 2019

  3. [3]

    and Poloczek, M

    Baptista, R. and Poloczek, M. (2018). B ayesian optimization of combinatorial structures. In International Conference on Machine Learning

    work page 2018

  4. [4]

    Bergstra, J., Bardenet, R., Bengio, Y., and K \'e gl, B. (2011). Algorithms for hyper-parameter optimization. In Advances in Neural Information Processing Systems

    work page 2011

  5. [5]

    Bergstra, J., Brent, K., Chris, E., Dan, Y., and David, D. (2015). H yperopt: a P ython library for model selection and hyperparameter optimization. Computational Science & Discovery , 8

    work page 2015

  6. [6]

    Cheeseman, T., Southerland, K., Reade, W., and Howard, A. (2022). H appywhale - whale and dolphin identification

    work page 2022

  7. [7]

    Deshwal, A., Ament, S., Balandat, M., Bakshy, E., Doppa, J., and Eriksson, D. (2023). B ayesian optimization over high-dimensional combinatorial spaces via dictionary-based embeddings. In International Conference on Artificial Intelligence and Statistics

    work page 2023

  8. [8]

    Dreczkowski, K., Grosnit, A., and Ammar, H. B. (2024). Framework and benchmarks for combinatorial and mixed-variable B ayesian optimization. Advances in Neural Information Processing Systems

    work page 2024

Show all 36 references
  1. [9]

    Falkner, S., Klein, A., and Hutter, F. (2018). BOHB : Robust and efficient hyperparameter optimization at scale. In International Conference on Machine Learning

    2018

  2. [10]

    Garnett, R. (2023). B ayesian optimization . Cambridge University Press

    2023

  3. [11]

    Hansen, N. (2016). The CMA evolution strategy: A tutorial. arXiv:1604.00772

    2016 arXiv

  4. [12]

    Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D. (2018). Deep reinforcement learning that matters. In The AAAI conference on Artificial Intelligence

    2018

  5. [13]

    Khan, A., Cowen-Rivers, A., Grosnit, A., Robert, P., Greiff, V., Smorodina, E., Rawat, P., Akbar, R., Dreczkowski, K., Tutunov, R., et al. (2023). Toward real-world automated antibody design with combinatorial B ayesian optimization. Cell Reports Methods , 3

    2023

  6. [14]

    and Li, F

    Li, K. and Li, F. (2024). Multi-fidelity methods for optimization: A survey. arXiv:2402.09638

    2024 arXiv

  7. [15]

    Liaw, R., Liang, E., Nishihara, R., Moritz, P., Gonzalez, J., and Stoica, I. (2018). T une: A research platform for distributed model selection and training. arXiv:1807.05118

    2018 arXiv

  8. [16]

    and Hutter, F

    Loshchilov, I. and Hutter, F. (2016). CMA-ES for hyperparameter optimization of deep neural networks. arXiv:1604.07269

    2016 arXiv

  9. [17]

    Oh, C., Tomczak, J., Gavves, E., and Welling, M. (2019). Combinatorial B ayesian optimization using the graph cartesian product. Advances in Neural Information Processing Systems

    2019

  10. [18]

    Ozaki, Y., Tanigaki, Y., Watanabe, S., Nomura, M., and Onishi, M. (2022). Multiobjective tree-structured P arzen estimator. Journal of Artificial Intelligence Research , 73

    2022

  11. [19]

    Ozaki, Y., Tanigaki, Y., Watanabe, S., and Onishi, M. (2020). Multiobjective tree-structured P arzen estimator for computationally expensive optimization problems. In Genetic and Evolutionary Computation Conference

    2020

  12. [20]

    Papenmeier, L., Nardi, L., and Poloczek, M. (2023). B ounce: Reliable high-dimensional B ayesian optimization for combinatorial and mixed spaces. Advances in Neural Information Processing Systems

    2023

  13. [21]

    Patton, P., Cheeseman, T., Abe, K., Yamaguchi, T., Reade, W., Southerland, K., Howard, A., Oleson, E., Allen, J., Ashe, E., et al. (2023). A deep learning approach to photo--identification demonstrates high performance on two dozen cetacean species. Methods in Ecology and Evol...

    2023

  14. [22]

    Shahriari, B., Swersky, K., Wang, Z., Adams, R., and Freitas, N. D. (2015). Taking the human out of the loop: A review of B ayesian optimization. Proceedings of the IEEE , 104

    2015

  15. [23]

    Snoek, J., Larochelle, H., and Adams, R. (2012). Practical B ayesian optimization of machine learning algorithms. Advances in Neural Information Processing Systems , 25

    2012

  16. [24]

    Sukthanker, R., Dooley, S., Dickerson, J., White, C., Hutter, F., and Goldblum, M. (2022). On the importance of architectures and hyperparameters for fairness in face recognition. arXiv:2210.09943

    2022 arXiv

  17. [25]

    Vallati, M., Chrpa, L., McCluskey, T., and Hutter, F. (2021). On the importance of domain model configuration for automated planning engines. Journal of Automated Reasoning , 65

    2021

  18. [26]

    Wagner, D., Ferreira, F., Stoll, D., Schirrmeister, R., M \"u ller, S., and Hutter, F. (2022). On the importance of hyperparameters and data augmentation for self-supervised learning. arXiv:2207.07875

    2022 arXiv

  19. [27]

    Watanabe, S. (2023a). Python wrapper for simulating multi-fidelity optimization on HPO benchmarks without any wait. arXiv:2305.17595

    2023 arXiv

  20. [28]

    Watanabe, S. (2023b). Tree-structured P arzen estimator: Understanding its algorithm components and their roles for better empirical performance. arXiv:2304.11127

    2023 arXiv

  21. [29]

    Watanabe, S., Awad, N., Onishi, M., and Hutter, F. (2022). Multi-objective tree-structured P arzen estimator meets meta-learning. In Meta-Learning Workshop at Advances in Neural Information Processing Systems

    2022

  22. [30]

    Watanabe, S., Awad, N., Onishi, M., and Hutter, F. (2023). Speeding up multi-objective hyperparameter optimization by task similarity-based meta-learning for the tree-structured P arzen estimator. International Joint Conference on Artificial Intelligence

    2023

  23. [31]

    and Hutter, F

    Watanabe, S. and Hutter, F. (2022). c-TPE : Generalizing tree-structured P arzen estimator with inequality constraints for continuous and categorical hyperparameter optimization. arXiv:2211.14411

    2022 arXiv

  24. [32]

    and Hutter, F

    Watanabe, S. and Hutter, F. (2023). c-TPE : tree-structured P arzen estimator with inequality constraints for expensive hyperparameter optimization. In International Joint Conference on Artificial Intelligence

    2023

  25. [33]

    Watanabe, S., Mallik, N., Bergman, E., and Hutter, F. (2024). Fast benchmarking of asynchronous multi-fidelity optimization on zero-cost benchmarks. arXiv:2403.01888

    2024 arXiv

  26. [34]

    Wu, T., Flam-Shepherd, D., and Aspuru-Guzik, A. (2020). B ayesian variational optimization for combinatorial spaces. arXiv:2011.02004

    2020 arXiv

  27. [35]

    Yang, G., Hu, E., Babuschkin, I., Sidor, S., Liu, X., Farhi, D., Ryder, N., Pachocki, J., Chen, W., and Gao, J. (2022). T ensor P rograms V : Tuning large neural networks via zero-shot hyperparameter transfer. arXiv:2203.03466

    2022 arXiv

  28. [36]

    Zhang, B., Rajan, R., Pineda, L., Lambert, N., Biedenkapp, A., Chua, K., Hutter, F., and Calandra, R. (2021). On the importance of hyperparameter optimization for model-based reinforcement learning. In International Conference on Artificial Intelligence and Statistics

    2021

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.