Bayesian Optimization over Bounded Domains with Beta Product Kernels

Authors: huy  hoang nguyen
han  zhou
matthew b blaschko
aleksei  tiulpin
Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-05 13:04:50

Abstract: Bayesian Optimization with Gaussian Process (GP) and  Matérn and Radial Basis Function (RBF) covariance functions is commonly used to optimize black-box functions. The Matérn and the RBF kernels do not make any assumptions about the domain of the function, which may limit their applicability in bounded domains. To address the limitation issue, we introduce a non-stationary Beta Unit Hyper-Cube (BUC) kernel, which is induced by a product of Beta distribution density functions, and allows to model functions on bounded domains. To provide theoretical insights, we provide analyses of information gain and cumulative regret bounds when using the GP Upper Confidence Bound (GP-UCB) algorithm with the BUC kernel. Our experiments show that the BUC kernel consistently outperforms the well-known Matérn and RBF kernels in different problems, including synthetic function optimization and the compression of vision and language models.

Main paper: 
 introduction: 
 Bayesian Optimization (BO) is a theoretically grounded strategy for sequential optimization of noisy and black-box functions with costly evaluations. A surrogate model, which approximates the objective function and guides the search process is at the core of BO. A Gaussian Process (GP) is frequently employed here due to its flexibility, capability to quantify uncertainty, and inject priors through covariance functions (interchangeably called kernels). A GP f ∼ GP(µ(x), K(x, x ′ )) is specified by its mean µ(x) = E[f (x)] and covariance function K(x,x ′ ) = E[(f (x) -µ(x))(f (x ′ ) -µ(x ′ ))].The choice of kernel plays a critical role in encoding prior beliefs about the characteristics of the target function. Among various options, Matérn and Radical Basis Function (RBF) are frequently chosen kernels for a wide range of optimization problems due to their flexibility (Pedregosa et al., 2011; Head et al., 2018; Gardner et al., 2018) 1 . The Matérn kernel is expressed as (Rasmussen, 2003 )EQUATIONwhere r = ∥x -x ′ ∥ 2 , ν > 0 is a smoothness parameter, ℓ is a positive length scale, Γ(•) is the Gamma function, and K ν is a modified Bessel function (Abramowitz and Stegun, 1968) . When ν → ∞, the Matérn kernel is equivalent to the RBF kernel, formulated asEQUATION)The Matérn and RBF kernels are defined on unbounded domains; however, in many practical applications, a function of choice may be defined on a bounded domain, which may result in sub-optimal performance.In this work, we propose a novel non-stationary kernel BUC, named after Beta distribution-based Unit Hyper-Cube, which is specifically designed for modeling functions over bounded domains.Our kernel is constructed from a product of multiple Beta distribution density functions, each of which naturally represents a wide range of functions defined on [0, 1]. We theoretically derive bounds for the maximum information gain and the cumulative regret when optimizing with the GP Upper Confidence Bound (GP-UCB) algorithm. Our results show that BUC consistently outperforms the RBF and Matérn kernels across various tasks, including synthetic function optimization and deep learning-based vision and language model compression.2 Beta Distribution-based Unit HyperCube Kernel 
definition: 
 Let x, x ′ ∈ [0, 1] d denote two random variables in a d-dimensional unit hypercube. We aim to develop some positive semi-definite functionEQUATIONwhere x i represents the mode of the i-th Beta distribution,α i = xi hi + 1, β i = 1-xi hi + 1, h i is the smoothing bandwidth of the i-th dimension, and s = [s 1 , . . . , s d ] ⊺ ∈ [0, 1] d isthe variables of the Beta distributions. Then, the BUC kernel is expressed asEQUATIONwhereEQUATION)Based on the cumulative distribution function of the Beta distribution Beta(α, β), we have thatEQUATIONeach individual integral becomesEQUATION)Assume that s i 's are independent of each other, the BUC kernel can be simplified toK BUC (x, x ′ ) = C d i=1 Γ(α i + α ′ i -1)Γ(β i + β ′ i -1) Γ(α i + α ′ i + β i + β ′ i -2) (8) As α i + β i = α ′ i + β ′ i = 1 hi + 2, the kernel can be expressed asEQUATION)We graphically compare the BUC kernel to the Matérn kernel on the unit 1D domain in Figures 1a and 1b . Whereas Matérn is a stationary kernel with a constant diagonal, our proposed kernel is non-stationary. Consider a GP f ∼ GP(0, K BUC (x, x ′ )) on the d-dimensional unit hypercube D = [0, 1] d . Assume that we use the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm to find the optimal solution x * = arg min x∈[0,1] d f (x). Here, we aim to derive bounds of the maximum information gain γ T and the corresponding cumulative regret R T after T iterations. γ T is defined asEQUATIONwheref A = [f (x)]x∈A , and I(y A , f A ) is the information gain, defined asEQUATIONwhere H(•) is the Shannon entropy. The maximum information gain can also be expressed as (Cover, 1999; Srinivas et al., 2009) . The cumulative regret is defined as R T = T t=1 f (x t ) -f (x * ). We derive the bound of γ T as O d log(T 2 3d-2d h h -3d 2 ) in Theorem 1, and the bound of the cumulative regret w.r.t. the BUC kernel in Theorem 2.I(y A , f A ) = 1 2 log |I + σ -2 K A |, where K A = [K(x, x ′ )] x,x ′ ∈ATheorem 1. The maximum information gain γ T of the BUC kernel is bounded by O hdT where h = 3 log 2 -2 log 2 h + 3 2 log 1 h . Proof. We directly bound I(y A , f A ) = 1 2 log |I + σ -2 K A | ≤ 1 2 log |diag(I + σ -2 K A )| using the Hadamard's inequality. K BUC (x, x) can bounded by 2 3d-2d h ( 1 h +1) d ( 1 hπ + 3 2π ) d 2 given that Γ 2 (x+1) Γ(2x+1) = √ πΓ(x+1) 2 2x Γ(x+ 1 2 ) and 2 2x+1 1 2 ≤ Γ(x+ 1 2 ) Γ(x+1) ≤ 2, ∀x ≥ 0. Theorem 2. Let D = [0, 1] d with d ∈ N, pick δ ∈ (0,≤ T C 1 β T hd + 2 ∀T ≥ 1 ≥ 1 -δ,where C 1 = 8/ log(1 + σ 2 ).Proof. Apply Theorem 1 and Theorem 2 of Srinivas et al. (2009) .In Figure 1c , we present the spectral decay analysis for the RBF, Matérn, and BUC kernels. Our analysis demonstrates a strong correlation between the bandwidth parameter h and the eigenvalue decay rate of the BUC kernel. With h < 1, the BUC kernel shows a slower eigenvalue decay rate BUC kernel. The experiments show that our kernel consistently outperforms the widely used RBF and Matérn kernels across different optimization tasks. 
 
 Appendix:  


Decision: While the scores of this work are borderline accept, the actual text of the reviews is largely positive and makes clear this work is above the bar for a workshop.

Reviews: review: title: title: Evaluation of the Work: "Bayesian Optimization over Bounded Domains with Beta Product Kernels"
main_review: main_review: The paper presents a new kernel, the Beta Unit Hyper-Cube (BUC) kernel, designed for bounded domains in Bayesian optimization. The quality of the theoretical and experimental work is solid. 

The paper is generally clear, especially in its explanation of the motivation for using a bounded-domain kernel. The introduction of a kernel specifically designed for bounded domains is a novel contribution. The BUC kernel addresses an important limitation in Gaussian processes using traditional kernels like Matérn and RBF. 

The significance of this work lies in its potential for practical applications in fields requiring optimization over bounded domains, such as hyperparameter tuning in machine learning and model compression. 

Pros:
1.Novelty: The BUC kernel fills a gap in Bayesian optimization for bounded domains.
2.Theoretical Rigor: The paper provides a well-justified theoretical framework for the BUC kernel, including bounds on information gain and regret.

Cons:
1.Limited Benchmark Tasks: The experiments are not thorough enough. Expanding the range of real-world benchmarks could further validate the new kernel's robustness.
2.Few Practical Guidelines: While the paper performs well in theory and experiments, it lacks discussion on how to choose parameters like the bandwidth $h$ for the BUC kernel in practice.
title: title: Improving Deferral Decisions in Learning-to-Defer Framework via Conformal Prediction for Enhanced Uncertainty Management
main_review: main_review: **Summary**

The paper proposes an enhancement to the Learning-to-Defer (L2D) framework by incorporating conformal prediction to quantify uncertainty in the rejector component. Instead of binary deferral decisions, the rejector outputs uncertainty sets, allowing more flexible decision-making between human and machine. The approach is evaluated on the CIFAR-10 dataset, showing improved performance in abstention and consensus prediction tasks compared to traditional methods.

- **Quality:**
The paper is well-structured, with solid theoretical grounding and clear experimental validation, though limited to a single dataset (CIFAR-10)

- **Clarity:**
The explanations are clear and precise, but additional visual aids could enhance accessibility for less technical readers.

- **Originality:**
The use of conformal prediction in the L2D framework is a novel approach for uncertainty quantification, offering a fresh contribution to deferral decision-making.

- **Significance:**
This work has strong practical implications for human-AI collaboration, improving decision reliability in uncertain scenarios, particularly in safety-critical applications.

**Strength**
- Novel integration of conformal prediction with the L2D framework
- Strong theoretical foundation for uncertainty quantification
- Demonstrates improved performance in deferral and consensus predictions

**Weakness**
- Limited evaluation to a single dataset (CIFAR-10)
- Could benefit from more visual aids for better clarity and accessibility

**Questions**
- How does this framework perform on more complex or higher-dimensional datasets beyond CIFAR-10?
- Can the conformal prediction-based rejector be extended to more nuanced real-world decision-making scenarios, such as multi-expert systems?
- What is the computational complexity of integrating conformal prediction into the L2D framework, especially in real-time applications?