Joint Optimization and Statistical Inference for Zero-th Order Simulation Optimization

Yuhang Wu, Zeyu Zheng, Guangyu Zhang, Zuohua Zhang, Chu Wang, Wang, ChuarXiv 2022 · DOI · arXiv

Abstract

We consider stochastic optimization problems with the dual tasks of (i) effectively finding the optimizer and (ii) reliably conducting statistical inference for the optimal objective function value. We find that classical simulation optimization and stochastic optimization algorithms, despite their fast convergence rates to the optimizer under strong convexity assumptions, may not come with a valid central limit theorem (CLT) with a vanishing bias. This non-vanishing bias can harm statistical inference and the construction of asymptotically valid confidence intervals. We fix this issue by providing a new stochastic optimization algorithm that on one hand maintains the same fast convergence rate and on the other hand permits the establishment of a valid CLT with vanishing bias. We discuss practical implementations of the proposed algorithm and conduct numerical experiments to illustrate the theoretical findings.

Introduction

In the realm of black-box (zero-th order) stochastic optimization, the primary objective is typically to locate the optimal parameter $\theta^*$ that minimizes or maximizes a noisy objective function $f(\theta)$. However, in many high-stakes applications—such as clinical trials, economic policy-making, or adaptive A/B testing—finding the "best" setting is only half the battle. Decision-makers also require a reliable estimate of the optimal performance level $f(\theta^*)$ and a measure of the uncertainty surrounding that estimate.

This paper addresses the "inference gap" in existing simulation optimization literature. While classical algorithms like the Kiefer-Wolfowitz (KW) procedure are efficient at converging to the optimizer, they often fail to provide a foundation for valid statistical inference. Specifically, the bias inherent in their gradient estimation does not vanish quickly enough to satisfy a standard Central Limit Theorem (CLT), leading to shifted confidence intervals and potentially erroneous conclusions.

The Problem: The Hidden Bias of Two-Point Methods

Consider an adaptive A/B test where a researcher seeks to optimize a continuous parameter, such as a discount rate in an e-commerce application. The outcomes (sales) are noisy, and the underlying function relating the discount to revenue is unknown.

Standard zero-th order algorithms rely on finite-difference (FD) estimators to approximate the gradient. For example, the two-point FD method samples the function at $\theta^t \pm c_t$. While this is sufficient for the algorithm to eventually reach the optimum, the bias in the function value estimate at the estimated optimum $\hat{\theta}$ decays slower than the square root of the sample size ($T^{-1/2}$). Consequently, any confidence interval (CI) constructed using these methods will be centered incorrectly. In practice, this means a 95% CI might have an actual coverage rate far lower than intended, as the "true" value frequently falls outside the biased range.

Methodology: The Four-Point Sampling Algorithm

To resolve this bias, the authors propose a novel algorithm that utilizes a four-point sampling strategy in each iteration. Instead of two points, the algorithm samples the noisy function at four specific locations:

  1. $\theta^t \pm c_t w^t$
  2. $\theta^t \pm k c_t w^t$

where $w^t$ is a random direction and $k > 1$ is a scaling factor (typically recommended between 3 and 5).

Bias Cancellation and Joint Execution

By utilizing four points, the researchers can construct higher-order estimators for both the gradient and the function value. This specific construction allows for the cancellation of lower-order bias terms that typically plague two-point methods.

Furthermore, the algorithm employs a "joint execution" strategy. Traditional heuristics often split data into two phases: a search phase to find the optimum and an evaluation phase to estimate its value. This data splitting is inefficient. The proposed algorithm uses every sample for both tasks simultaneously, maximizing statistical power and achieving an asymptotic variance that is nearly as low as if the optimal parameter $\theta^*$ were known from the start.

Key Theoretical Insights

  • Third-Order Smoothness: The authors demonstrate that if the objective function is third-order differentiable, the four-point estimator can achieve a vanishing bias at the $T^{-1/2}$ scale. This is the critical threshold required to establish a valid CLT for the optimal value.
  • Convergence Rates: The algorithm does not sacrifice search efficiency for inference validity. It maintains a convergence rate of $O(T^{-1/3+\epsilon})$ for the optimizer, which is the standard rate for zero-th order optimization under strong convexity.

Experimental Results

The algorithm was tested against synthetic models calibrated from real-world e-commerce A/B test data, including a 6-dimensional logistic model and various noise distributions (Bernoulli, Pareto, and Student’s t).

  • Inference Accuracy: In numerical experiments, the proposed algorithm produced 95% confidence intervals with actual coverage rates between 93.5% and 94.2%, demonstrating high reliability.
  • Failure of Classical Methods: In contrast, the standard two-point FD method exhibited massive bias. In heavy-tailed noise scenarios, the bias was so significant that the resulting confidence intervals were entirely unreliable for decision-making.

Limitations and Future Directions

While the four-point algorithm represents a significant step forward, it currently relies on the assumption of strong convexity. Relaxing this to ordinary convexity would likely require a more complex iterative procedure. Additionally, while the method scales better than many zero-th order approaches, the "curse of dimensionality" remains a factor; as the number of parameters grows, the number of samples required for high-precision inference increases. Future work may explore how to adapt this bias-cancellation technique to even higher-dimensional spaces or non-convex landscapes.

Conclusion

This research highlights a critical oversight in classical simulation optimization: an algorithm can be optimal for searching but broken for inference. By introducing a four-point sampling mechanism, the authors provide a robust framework for researchers to not only find the best settings in a black-box environment but to trust the statistical significance of their results.

Summary updated

Abstract

We consider stochastic optimization problems with the dual tasks of (i) effectively finding the optimizer and (ii) reliably conducting statistical inference for the optimal objective function value. We find that classical simulation optimization and stochastic optimization algorithms, despite of their fast convergence rates to the optimizer under strong convexity assumptions, may not come with a valid central limit theorem (CLT) with a vanishing bias. This non-vanishing bias can harm statistical inference and the construction of asymptotically valid confidence intervals. We fix this issue by providing a new stochastic optimization algorithm that on one hand maintains the same fast convergence rate and on the other hand permits the establishment of a valid CLT with vanishing bias. We discuss practical implementations of the proposed algorithm and conduct numerical experiments to illustrate the theoretical findings.
BibTeX
@misc{wu2022joint,
  author = {Yuhang Wu and Zeyu Zheng and Guangyu Zhang and Zuohua Zhang and Chu Wang and Wang, Chu},
  title = {{Joint Optimization and Statistical Inference for Zero-th Order Simulation Optimization}},
  year = {2022},
  eprint = {2210.06737},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2210.06737},
}
Figure