Conditional PED-ANOVA: Hyperparameter Importance in Hierarchical & Dynamic Search Spaces

AI summary

Overview

Research area: Hyperparameter Importance (HPI) analysis within automated machine learning and hyperparameter optimization (HPO), specifically sensitivity analysis for conditional (hierarchical/dynamic) search spaces.

Technical level: Intermediate. Readers need familiarity with search spaces, quantiles, variance decomposition, and kernel density estimation, but the core idea is stated plainly: measure how much each hyperparameter varies inside its own regime rather than across regimes.

Scope: The paper defines a "conditional local HPI," derives a closed-form estimator called condPED-ANOVA that extends PED-ANOVA to conditional search spaces, and validates it on synthetic problems where the correct importance pattern is known.

What This Paper Is About

Many real hyperparameter search spaces are conditional: whether a hyperparameter exists at all, or what range it takes, depends on other hyperparameters. For example, choosing a neural network makes "number of layers" active while "minimum split gain" is inactive, and choosing a tree-based model reverses that. Existing fast HPI methods such as PED-ANOVA assume a single fixed domain for every hyperparameter, so they cannot be applied to these spaces, and the paper shows that naive workarounds (filtering, imputation, domain expansion) produce misleading or uninterpretable importance values. The goal is a principled definition and an efficient closed-form estimator of HPI that reflects conditional activation and regime-dependent domains correctly.

Key Contributions

1. Identification of a fundamental pitfall. The authors show that the original local HPI definition spuriously attributes the contribution of the conditioning (gating) hyperparameters to the conditionally active or domain-shifted hyperparameters, yielding systematically misleading importance estimates. This is demonstrated empirically in Section 5.5.1 and theoretically in Theorem F.1.
2. A new definition: conditional local HPI. They introduce conditional local HPI, which measures importance within top-performing regions using only the within-regime component of variance, so it is not confounded by conditional activation or domain changes.
3. A closed-form estimator, condPED-ANOVA. They derive a PED-ANOVA-style closed-form estimator for conditional local HPI (Theorem 4.2) that aggregates within-regime Pearson divergences with regime-dependent weights, retaining PED-ANOVA's computational efficiency.
4. Empirical demonstration. They show on synthetic problems that condPED-ANOVA consistently produces meaningful importances reflecting the underlying conditional structure, whereas naive extensions of PED-ANOVA, f-ANOVA, MDI, and SHAP produce unnatural results.

Main Findings

• Variance decomposition exposes the problem. The standard local marginal variance decomposes by the law of total variance into a within-regime term and an inter-regime term. Because the regime of a conditional hyperparameter is determined by other hyperparameters (its parents), attributing the inter-regime term to that hyperparameter is inappropriate.
• Systematic leakage is provable. The paper states (Theorem F.1) that the standard local marginal variance of a conditioned hyperparameter is lower-bounded by the local marginal variance of the conditioning variable, implying that even inactive hyperparameters can receive non-negligible importance purely from upstream choices. Tuning an inactive hyperparameter has no effect on the objective, so such importance is meaningless.
• The fix is to keep only the within-regime term. Conditional local HPI is defined by normalizing the within-regime local marginal variance across all hyperparameters (Equation 8). When a hyperparameter is not conditional (K^(d) = 1), the inter-regime term vanishes and the definition reduces to the standard local HPI.
• Closed-form estimator (Theorem 4.2). For 0 < γ' < γ ≤ 1, the within-regime local marginal variance equals (γ'/γ)^2 times a sum over regimes of (α_i^(d))^2 / β_i^(d) multiplied by the Pearson divergence between the one-dimensional PDFs of the top-γ' and top-γ subsets within that regime. Here α_i^(d) and β_i^(d) are the regime probabilities in the top-γ' and top-γ subsets respectively.
• Weighting has a clear interpretation. Regimes enriched in the tighter top set (larger (α_i^(d))^2 / β_i^(d)) receive more weight. If a regime corresponds to an inactive configuration (value is always ⊥), the two PDFs are degenerate at ⊥ and the divergence is zero.
• Reduction to PED-ANOVA. With K^(d) = 1 and α_1^(d) = β_1^(d) = 1, the new estimator reduces exactly to the original PED-ANOVA expression (Equation 5).
• Synthetic conditional activation (disjoint domains). With f(c, x, y) = x if c < 0.5 and y if c ≥ 0.5, c ∈ [0, 1], x ∈ [-5, -2], y ∈ [2, 5], and γ = 1.0: around γ' ≈ 0.5 the gating variable c has the largest HPI, at a tighter target (γ' ≈ 0.1) the HPI shifts to x, and at a looser target (γ' ≈ 0.9) HPI is dominated by y. For γ' < 0.5, y has near-zero importance; for γ' > 0.5, x is inactive and hence unimportant.
• Synthetic conditional activation (overlapping domains). With x ∈ [-5, 2] and y ∈ [-2, 5], the objective values are no longer cleanly separated by c, so around γ' ≈ 0.5 the HPI of c is no longer close to one and both x and y have non-negligible HPI. The contribution of y persists until about γ' ≈ 0.2, reflecting the best values attainable in the y-branch (near y = -2). For tighter targets, y's importance falls to near zero and x's grows.
• Approximate symmetry. Under both domain settings, the HPI is approximately symmetric for γ' < 0.5 and γ' > 0.5, reflecting the objective's top–bottom symmetry. For γ' > 0.5, changing c can still improve the objective, so c retains a non-zero HPI even near γ' ≈ 1.0, a slight asymmetry caused by minimization.
• Regime-dependent domains. With f(c, x, y) = x + y, c ∈ [0, 1], where x ∈ [-7, -2], y ∈ [-5, -2] if c < 0.5 and x ∈ [2, 7], y ∈ [2, 5] if c ≥ 0.5: the gating variable c again largely determines top-half performance with high importance near γ' ≈ 0.5. Both x and y are always active, and their importance grows toward more extreme targets. x is consistently more important than y, reflecting its ability to attain more extreme values (around ±7).
• Baseline failure modes are claimed but not quantified here. The paper reports that naive adaptations of PED-ANOVA, f-ANOVA, MDI, and SHAP yield misleading or uninterpretable importances in conditional settings. The provided paper content is truncated at the start of this section, so the specific baseline numbers are not available in the text supplied. Results on real-world benchmarks are announced for Section 6 but the details are likewise not present in the truncated content.

Methodology in Plain English

The authors start from an existing method, PED-ANOVA, which estimates how important each hyperparameter is in the best-performing region of a search space. PED-ANOVA does this quickly by comparing the one-dimensional distributions of each hyperparameter in two nested top-performing subsets (the best γ' fraction and the best γ fraction) using the Pearson divergence, rather than fitting an expensive surrogate model.

The problem is that PED-ANOVA assumes each hyperparameter has one fixed domain. To handle conditional behavior, the authors introduce the notion of a regime: each hyperparameter is split into a finite number of regimes, and each regime has its own domain. When a hyperparameter is inactive in a regime, that regime's domain is just the special symbol ⊥. A parent hyperparameter such as "which algorithm" determines which regime the child hyperparameter is in.

They then take the standard local marginal variance and split it into two pieces: variation between regimes and variation within regimes. The between-regime piece is driven by parent choices, not by the hyperparameter itself, so they discard it. What remains, the within-regime variance, measures how much the hyperparameter's own value changes the likelihood of landing in the tighter top set, holding the regime fixed.

To compute this efficiently, they derive a closed-form expression. For each regime, they take the samples in the top γ' and top γ subsets that fall in that regime, estimate each hyperparameter's one-dimensional density with a kernel density estimator, compute the Pearson divergence between the two densities, and then take a weighted sum over regimes. The weights, (α_i^(d))^2 / β_i^(d), upweight regimes that are over-represented in the tighter top set. The final conditional local HPI is this within-regime variance normalized across all hyperparameters.

Validation is done on synthetic objectives with a known correct answer, using 1,000 evaluations sampled uniformly, three values of γ (1.0, 0.75, 0.5), γ' swept from 0.01 to γ − 0.01 in increments of 0.01, and 10 random seeds, reporting means and standard errors. The implementation builds on the PED-ANOVA implementation in Optuna. Baselines are the original PED-ANOVA, f-ANOVA (random-forest surrogate functional ANOVA), MDI (mean decrease impurity from a random forest), and SHAP (Shapley-value attributions from a surrogate), combined with naive extensions: Filtering (keep only samples where it is active), Imputation (fill inactive values with the domain midpoint), and Expansion (treat the hyperparameter as sampled from one expanded domain covering all regimes).

Why This Matters

Impact on research. HPI is a standard post-hoc tool for interpreting optimization runs, detecting irrelevant parameters, and guiding search-space design. By showing that the original local HPI is not just imprecise but systematically misleading in conditional spaces—with a theorem showing leakage from conditioning variables—the paper reframes conditional structure as a first-class concern for sensitivity analysis rather than a preprocessing detail. It also preserves PED-ANOVA's speed advantage, which matters for adoption.

Real-world applications (from the paper's own examples):

• Model selection, where hyperparameters depend on which algorithm is chosen (as in Auto-WEKA and auto-sklearn style spaces).
• Neural network architecture design, where which parameters are active depends on the chosen layers.
• HPO toolchains and analysis suites, such as SMAC-style CASH spaces, CAVE, BOAH, and DeepCAVE, which currently map conditional configurations to a fixed representation by imputing defaults.
• Framework-level importance APIs, such as Optuna's, which by default only evaluate parameters that appear with the same domain in all samples and thereby exclude conditional parameters.

Industry relevance. Conditional search spaces are common in practical AutoML and model-tuning pipelines. Tooling that silently drops conditional hyperparameters, or that imputes defaults, gives practitioners importance numbers that do not correspond to anything tunable. A method that assigns zero importance to genuinely inactive parameters and correctly credits parent choices gives more trustworthy guidance for where to spend tuning budget.

Future Directions

• Real-world benchmark validation. The paper announces experiments on real-world benchmarks in Section 6, but the supplied content does not include their results; how well the synthetic findings transfer to real objectives remains the key open question.
• Extending beyond the evaluated settings. The paper points to appendices covering multi-level conditional hierarchies (Section E.1), combinations of conditional activation with regime-dependent domains (Section E.2), non-uniform sampling (Section D.6), and sensitivity to the number of evaluations N, indicating these regimes are natural extension points.
• Scaling and runtime behavior. Appendix D.1 contains runtime comparisons between condPED-ANOVA and alternatives, but a full characterization of cost as the number of regimes K^(d) grows is not resolved in the main text.
• Integration with multi-objective and multi-fidelity analysis. The paper notes that recent multi-objective HPI work handles missing values from conditional hyperparameters in preprocessing; how conditional local HPI composes with multi-objective and multi-fidelity (e.g., BOHB-style) runs is not addressed.

Target Audience

Researchers and practitioners in AutoML and hyperparameter optimization who analyze or design search spaces; developers of HPO frameworks and analysis tools (Optuna, SMAC, CAVE, DeepCAVE, auto-sklearn, Auto-WEKA and similar) who need importance estimates for conditional and hierarchical configuration spaces; and methodologists interested in variance-based sensitivity analysis under structured, non-fixed domains. Readers with a working knowledge of quantiles, variance decomposition, and kernel density estimation will get the most out of the derivation, though the core insight—separate within-regime from between-regime variation—is accessible without it.

Authors’ abstract

We propose conditional PED-ANOVA (condPED-ANOVA), a principled framework for estimating hyperparameter importance (HPI) in conditional search spaces, where the presence or domain of a hyperparameter can depend on other hyperparameters. Although the original PED-ANOVA provides a fast and efficient way to estimate HPI within the top-performing regions of the search space, it assumes a fixed, unconditional search space and therefore cannot properly handle conditional hyperparameters. To address this, we introduce a conditional HPI for top-performing regions and derive a closed-form estimator that accurately reflects conditional activation and domain changes. Experiments show that naive adaptations of existing HPI estimators yield misleading or uninterpretable importances in conditional settings, whereas condPED-ANOVA consistently provides meaningful importances that reflect the underlying conditional structure. Our code is publicly available at https://github.com/kAIto47802/condPED-ANOVA.