Hierarchical Knowledge Gradient for Sequential Sampling

Martijn R. K. Mes, Warren B. Powell, Peter I. FrazierJMLR 2011 · OpenReview

TL;DR

This paper introduces the Hierarchical Knowledge Gradient (HKG) policy, a novel sequential sampling strategy for optimizing functions with both numerical and categorical attributes. HKG efficiently explores a vast search space by leveraging a hierarchical aggregation of alternatives, significantly reducing the number of measurements needed to find the optimal solution. This approach is particularly valuable in scenarios where measurements are costly or time-consuming.

What Problem Does This Paper Address?

The paper tackles the challenge of finding the maximum of an unknown function, where the input is a multi-dimensional vector containing both numerical and categorical attributes. This is a common problem in areas like hyperparameter tuning, drug discovery, and system design. The core difficulty lies in efficiently exploring a potentially enormous search space of alternatives, especially when each evaluation (measurement) is expensive or time-consuming. Traditional methods often struggle with the high dimensionality and the mixed nature of attributes, leading to either slow convergence or an infeasible number of evaluations. The authors aim to develop a policy that can effectively balance exploration (gathering information) and exploitation (using information to find the optimum) to achieve fast convergence to the globally optimal solution.

Methods

The paper proposes the Hierarchical Knowledge Gradient (HKG) policy. This policy builds upon the knowledge-gradient (KG) policy, which myopically optimizes the expected increment in knowledge gained from a single measurement. The key innovation of HKG is its hierarchical aggregation of alternatives. Instead of treating each individual alternative independently, HKG groups them into higher-level "aggregated alternatives" based on shared features. This allows information gained from measuring one alternative to inform beliefs about others within the same aggregated group.

The Bayesian model used by HKG estimates the unknown function values and their uncertainties. It employs a Bayesian inference procedure that recursively updates beliefs based on new measurements. The aggregation structure is problem-specific and can be defined using a set of aggregation functions. The paper also details how to estimate model parameters (like variances and biases) using an empirical Bayes approach, avoiding the need for explicit prior specification of all parameters. The measurement decision itself is made by selecting the alternative that maximizes the expected knowledge gain, calculated using the hierarchical KG formulation.

Datasets

Not discussed in the paper. The paper focuses on synthetic test functions and a case study for evaluation.

Key Insights and Ideas

  • Hierarchical Aggregation as a Scalability Solution: The core insight is that by grouping similar alternatives hierarchically, HKG can drastically reduce the effective search space. This allows it to handle problems with a vast number of alternatives that would be intractable for standard methods.
  • Leveraging Categorical Attributes: The hierarchical structure naturally accommodates categorical attributes by allowing them to define the aggregation levels. This is a significant advantage over methods that primarily focus on continuous spaces.
  • Balancing Variance and Bias: The aggregation process inherently involves a trade-off between variance (lower at higher aggregation levels due to more data) and bias (higher at higher levels due to averaging). HKG's Bayesian framework and weight estimation implicitly manage this trade-off.
  • Robustness to Function Structure: While HKG benefits from a well-designed aggregation structure, its theoretical guarantees of convergence hold even for arbitrary sampling distributions, suggesting a degree of robustness.

Key Results

  • Theoretical Guarantees: The paper proves that the HKG policy is consistent, meaning it eventually finds the globally optimal alternative with probability one as the number of measurements goes to infinity. This is achieved by showing that HKG measures each alternative infinitely often.
  • Competitive Performance: Numerical experiments show that HKG often outperforms other state-of-the-art sequential sampling policies (like KGCB, SKO, and IKG) across various one- and two-dimensional test functions, especially those with categorical attributes or where aggregation is natural.
  • Efficiency: HKG significantly reduces the number of measurements required compared to simpler policies, making it suitable for expensive evaluation scenarios.
  • Sensitivity to Aggregation: The performance of HKG is sensitive to the choice of aggregation structure, highlighting the importance of domain knowledge in defining these structures. However, it still performs well even with simpler aggregation schemes.

Limitations and Future Work

  • Dependence on Aggregation Structure: The primary limitation is that HKG requires a predefined aggregation structure. Designing this structure can be a modeling burden if domain knowledge is limited.
  • Computational Complexity: While HKG scales better than methods that ignore structure, its computational complexity is still O(M² logM), limiting it to problems with thousands, rather than millions, of alternatives.
  • Convergence Issues in Low Noise: The paper notes convergence problems for HKG in low measurement noise scenarios (small λ), where it can become overly confident about unmeasured alternatives. This is attributed to the base level aggregation and the estimation of variance.
  • No Theoretical Bounds on Convergence Rate: While convergence is proven, there are no theoretical results bounding the rate of convergence.
  • Future Work: The authors suggest exploring ways to automatically discover aggregation structures, developing methods to handle millions of alternatives, addressing the low-noise convergence issues (potentially with informative priors), and deriving theoretical bounds on the convergence rate.

Summary updated

Abstract

We propose a sequential sampling policy for noisy discrete global optimization and ranking and selection, in which we aim to efficiently explore a finite set of alternatives before selecting an alternative as best when exploration stops. Each alternative may be characterized by a multi-dimensional vector of categorical and numerical attributes and has independent normal rewards. We use a Bayesian probability model for the unknown reward of each alternative and follow a fully sequential sampling policy called the knowledge-gradient policy. This policy myopically optimizes the expected increment in the value of sampling information in each time period. We propose a hierarchical aggregation technique that uses the common features shared by alternatives to learn about many alternatives from even a single measurement. This approach greatly reduces the measurement effort required, but it requires some prior knowledge on the smoothness of the function in the form of an aggregation function and computational issues limit the number of alternatives that can be easily considered to the thousands. We prove that our policy is consistent, finding a globally optimal alternative when given enough measurements, and show through simulations that it performs competitively with or significantly better than other policies.
BibTeX
@article{mes2011hierarchical,
  author = {Martijn R. K. Mes and Warren B. Powell and Peter I. Frazier},
  title = {{Hierarchical Knowledge Gradient for Sequential Sampling}},
  journal = {J. Mach. Learn. Res.},
  year = {2011},
  url = {https://openreview.net/forum?id=oN2ZDnW3-88},
}
Figure