🧊of blackbox optimization

[hyunjimoon]

Effect of Three Axes in Optimization Methods

1. Performance Metric (Online to Offline)

min_π E[R_T(π)] → max_i P(i = i* | D_N)

This axis represents the transition from online optimization to offline identification:

Online	Offline
Focuses on minimizing expected regret E[R_T(π)] over T rounds	Aims to maximize probability of identifying best option i* given fixed dataset D_N
Emphasizes exploration-exploitation trade-off during optimization	Focuses on final recommendation quality
Values cumulative performance throughout the process	Can use batch processing and retrospective analysis
Must handle real-time decision making with limited information	Measured by simple regret (final solution quality)
Performance measured by cumulative regret	More emphasis on exploration for thorough understanding

2. Modeling Technique (Frequentist to Bayesian)

θ̂ = argmax_θ L(θ; D) → p(θ | D) ∝ L(θ; D) p(θ)

This axis represents the spectrum of modeling approaches:

Bayesian	Frequentist
Maintains full posterior distribution p(θ | D)	Uses point estimates θ̂ maximizing likelihood
Incorporates prior knowledge p(θ)	Relies on confidence intervals
Enables sophisticated uncertainty quantification	Often simpler computationally
Supports various models including: - Gaussian Processes (most common) - Neural network surrogates - Probabilistic models	Works with fixed parameters
Better handles noisy observations	Limited uncertainty quantification

3. Interaction (Independent to Correlated)

p(x_1, ..., x_n) = ∏_i p(x_i) → p(x_1, ..., x_n) = p(x_1) ∏_i p(x_i | x_1, ..., x_{i-1})

This axis describes how different points in the space relate:

Independent (Left Side)	Correlated (Right Side)
Each point evaluated independently	Models relationships between points
Simpler mathematical analysis	Enables information sharing across space
More suitable for discrete, unrelated options	Uses kernel functions for continuous spaces
Less sample efficient	More sample efficient
Common in classical bandit problems	Better for continuous optimization
	Supports spatial and temporal correlation

Additional Considerations

1. Hybrid Approaches:

   • Methods can combine aspects from different points along each axis
   • Modern algorithms often blend frequentist and Bayesian ideas
   • Can adapt correlation structure based on data

2. Practical Implementation:

   • Choice of position along each axis affects:
     • Computational complexity
     • Sample efficiency
     • Robustness to noise
     • Scalability

3. Application Dependencies:

   • Problem characteristics influence optimal positioning
   • High-dimensional spaces may require different approaches
   • Noise level affects model choice
   • Budget constraints impact online vs offline trade-off

---

Axis	Simplest → Complex (Mathematical Change)	Symbol Definitions
Performance Metric (Online to Offline)
1. Thompson → Best arm id. in Beta-Bernoulli bandits	argmax_t E[r_t|H_t] → argmax_i P(μ_i = max_j μ_j | D_N)	In Thompson Sampling, we select the arm t that maximizes the expected reward r_t given the history H_t at each step. In Best Arm Identification, we identify the arm i that has the highest probability of being the best after N fixed samples, where μ_i is the true mean of arm i and D_N is the collected data.
2. Bandits → Best arm id.	min_π E[∑_t=1^T (μ* - μ_π(t))] → max_i P(i = argmax_j μ_j | D_N)	In the bandit setting, we minimize the expected regret over T rounds, where π is the policy, μ* is the optimal arm's mean, and μ_π(t) is the mean of the chosen arm at time t. In Best Arm Identification, we maximize the probability of correctly identifying the best arm i after N samples, where μ_j are the true means and D_N is the collected data.
3. X-armed linear bandits → Best arm id. in linear bandits	argmax_x∈X θ^T x → argmax_i∈{1,...,K} P(θ^T x_i = max_j θ^T x_j | D_N)	In X-armed linear bandits, we choose x from a continuous set X to maximize the linear reward θ^T x. In linear best arm identification, we find the arm i among K discrete arms with the highest probability of having the maximum reward, given the data D_N. θ is the unknown parameter vector, and x_i are the feature vectors of the arms.
4. BO analysis → BayesOpt	E[f(x)|D_n] → argmax_x α(x|D_n)	In Bayesian Optimization analysis, we compute the expected value of f(x) given data D_n. In BayesOpt, we actively seek the x that maximizes the acquisition function α(x|D_n), which balances exploration and exploitation based on the posterior distribution.
Modeling Technique (Frequentist to Bayesian)
1. Bandits → Thompson	argmax_i μ̂_i → argmax_i θ_i, where θ_i ~ p(θ_i|D_t)	In frequentist bandits, we choose the arm i with the highest estimated mean μ̂_i. In Thompson Sampling, we sample θ_i from the posterior distribution p(θ_i|D_t) given data D_t, and choose the arm with the highest sampled value.
2. X-armed linear bandits → BO analysis	y = θ^T x + ε → f(x) ~ GP(m(x), k(x,x'))	X-armed linear bandits model the reward y as a linear function of x with parameters θ and noise ε. BO analysis models the function f(x) as a Gaussian Process with mean function m(x) and covariance function k(x,x').
3. Best arm id. → Best arm id. in Beta-Bernoulli bandits	[μ̂_i - ε, μ̂_i + ε] → Beta(α_i, β_i)	Frequentist approach uses confidence intervals [μ̂_i - ε, μ̂_i + ε] for each arm's mean. Bayesian approach models each arm's mean with a Beta distribution with parameters α_i and β_i.
4. Best arm id. in linear bandits → BayesOpt	argmax_i x_i^T θ̂ → argmax_x [μ(x) + β σ(x)]	In linear bandits, we choose the arm i with the highest estimated reward x_i^T θ̂. In BayesOpt, we maximize the acquisition function, typically of the form μ(x) + β σ(x), where μ(x) is the posterior mean, σ(x) is the posterior standard deviation, and β is an exploration parameter.
Interaction (Independent to Correlated)
1. Bandits → X-armed linear	r_i ~ P(r|i) → r(x) = θ^T x + ε	In classic bandits, rewards r_i for each arm i are drawn independently. In X-armed linear bandits, the reward r(x) is a linear function of the arm's features x, with unknown parameters θ and noise ε.
2. Thompson → BO analysis	p(θ_i) = Beta(α_i, β_i) → f(x) ~ GP(m(x), k(x,x'))	Thompson Sampling uses independent Beta distributions for each arm's parameter θ_i. BO analysis uses a Gaussian Process to model the function f(x), introducing correlations via the kernel k(x,x').
3. Best arm id. → Best arm id. in linear bandits	∏_i P(μ_i ∈ [μ̂_i - ε_i, μ̂_i + ε_i]) → P(θ ∈ C_δ) ≥ 1 - δ	In classic best arm id., we use independent confidence intervals for each arm's mean μ_i. In linear bandits, we use a confidence ellipsoid C_δ for the parameter vector θ, with confidence level 1 - δ.
4. Best arm id. in Beta-Bernoulli bandits → BayesOpt	p(μ_1,...,μ_K) = ∏_i Beta(α_i, β_i) → f(x) ~ GP(m(x), k(x,x'))	Beta-Bernoulli bandits use independent Beta distributions for each arm's mean μ_i. BayesOpt uses a Gaussian Process to model the function f(x), introducing spatial correlation via the kernel k(x,x').

[hyunjimoon]

@jeanbaptiste you might be interested in the above - could you explain more on your discovery of different tribes/origin/user group of optimization and bayesian?

[hyunjimoon]

Hart Pozen asked

I agree with your framing of a bandit as (necessarily) frequentist - perhaps this is because the figure labeled backwards? In your discussion of the modeling technique axis, you discuss "The right side shows the Bayesian approach", but in the figure, the right side is labeled frequentist

the goal of this thread is to understand the above frame which I heard from Bayesian Optimization as Black Box Method for Complex Engineering Applications phd seminar. I found three sources

1. source of cube diagram
   this explains the cube

2. comment on frequentist

• "frequentist version of the greedy algorithm replaces posterior mean with empirical mean: in each round, it chooses an arm with a largest empirical mean reward." from Introduction to Multi-Armed Bandits,

• p.14 of Bayesian optimization and Gaussian process bandits:Theory and Applications

Aspect	(Stochastic) Bandits	Bayesian Optimization
Theoretical Foundation	Strong theory	Little theory
Flexibility	Not as "flexible"	Highly configurable
Statistical Approach	(Often) Frequentist	Bayesian
Operation Mode	Contextual, dueling	Parallel, multi-fidelity
Types/Objectives	• Finite (Robbins '52, Gittins '79, Auer et al '02...) • Linear objectives (Dani et al. '08; Rusmevichientong & Tsitsiklis '08) • Lipschitz objectives (Slivkins et al. '08, Bubeck et al. '08)	• Sample Bayesian (GP) model of f acc. to Expected Improvement (Močkus et al. '78) • Most Probable Improvement (Močkus '89) • Information gain about maximum (Villemonteix et al. '09) • Knowledge gradient (Powell et al. '10)