Black-box Optimization with Simultaneous Statistical Inference for Optimal Performance

Teng Lian, Jian-Qiang Hu, Yuhang Wu, Zeyu ZhengarXiv 2025 · DOI · arXiv

Abstract

Black-box optimization is often encountered for decision-making in complex systems management, where the knowledge of system is limited. Under these circumstances, it is essential to balance the utilization of new information with computational efficiency. In practice, decision-makers often face the dual tasks of optimization and statistical inference for the optimal performance, in order to achieve it with a high reliability. Our goal is to address the dual tasks in an online fashion. Wu et al (2022) point out that the sample average of performance estimates generated by the optimization algorithm needs not to admit a central limit theorem. We propose an algorithm that not only tackles this issue, but also provides an online consistent estimator for the variance of the performance. Furthermore, we characterize the convergence rate of the coverage probabilities of the asymptotic confidence intervals.

Introduction

In the management of complex systems—ranging from high-frequency trading and power grid stabilization to real-time advertising auctions—decision-makers frequently operate within "black-box" environments. In these scenarios, the internal dynamics of the system are unknown, and one can only observe outputs based on specific inputs. The primary objective is typically to find the input parameters that maximize a reward or minimize a cost. However, in high-stakes industrial applications, identifying the optimal setting is only half the battle. Reliability requires a precise understanding of the expected performance at that optimum, supported by statistically sound confidence intervals (CIs).

The Challenge: Optimization vs. Inference

Traditional black-box optimization (BBO) relies on Stochastic Approximation (SA) or Simultaneous Perturbation Stochastic Approximation (SPSA) to iteratively move toward an optimal parameter set $\theta^*$. While these methods are effective at locating the optimum, they struggle with the simultaneous task of statistical inference.

The core issue lies in the data used for estimation. If a decision-maker simply averages the performance observations gathered during the search process, the resulting estimate is heavily biased by the early samples taken when the parameters were far from the optimum. Wu et al. (2022) demonstrated that such sample averages do not necessarily satisfy a Central Limit Theorem (CLT), making it impossible to construct reliable confidence intervals. Previous attempts to solve this were often "offline," requiring a secondary, computationally expensive data-collection phase after the optimization had concluded. This paper seeks a way to do it all online—updating the optimum, the performance estimate, and the variance estimate as every new data point arrives.

Methodology: Multi-Time-Scale Online Inference

Lian et al. (2025) propose a novel online algorithm that addresses these dual tasks simultaneously. The approach integrates standard SPSA for optimization with a specialized exponential smoothing technique for performance estimation.

1. Optimization via SPSA

The algorithm utilizes SPSA with decreasing step sizes to ensure that the parameter search converges to the true optimum $\theta^*$. SPSA is particularly valued in black-box settings because it requires only two function evaluations per iteration to estimate the gradient, regardless of the dimensionality of the parameter space.

2. Inference via Exponential Smoothing

The key innovation is the use of a constant step size ($\gamma$) for the performance estimator rather than a decreasing one. This creates a "multi-time-scale" effect. By maintaining a constant step size, the algorithm effectively applies an exponential window that prioritizes recent, more accurate observations as the optimizer nears $\theta^*$, effectively "forgetting" the biased data from early in the search.

3. Theoretical Framework

The authors prove that this normalized estimator asymptotically behaves like an Ornstein-Uhlenbeck (OU) process. This theoretical bridge is significant; it allows for the derivation of a consistent online estimator for the variance of the performance. Unlike previous methods, this algorithm does not need to store the entire history of realizations, making it highly efficient for streaming data environments like IoT or 5G networks.

Experimental Results

The algorithm's performance was validated through extensive synthetic simulations, focusing on both convergence rates and the reliability of the generated confidence intervals.

Simulation Settings

The researchers tested the algorithm on a 2D Quadratic function and a more complex 10D Perm function. To ensure the method's robustness, they applied five distinct noise profiles: Bernoulli, Normal, Gamma, Pareto (heavy-tailed), and Lognormal.

Key Findings

  • Convergence Efficiency: The algorithm maintains the optimal $O(n^{-1/3})$ convergence rate characteristic of SPSA.
  • Statistical Reliability: While "Ordinary SPSA" often resulted in 0% coverage for confidence intervals due to inherent bias, the proposed method consistently achieved the target coverage probability (e.g., 95%) much faster and more accurately than benchmarks like the "Four-point method."
  • Robustness: The normalized estimates centered around a standard normal distribution across all tested noise distributions, confirming the validity of the asymptotic confidence intervals even under heavy-tailed noise.

Conclusion and Future Work

This research provides a rigorous framework for simultaneous optimization and inference in black-box systems. By leveraging the properties of OU processes and exponential smoothing, the authors offer a solution that is both statistically sound and computationally efficient for real-time applications.

However, several avenues for future research remain. The current theoretical guarantees rely on the objective function being strongly convex, which may not hold in deep learning or complex non-convex landscapes. Additionally, the model assumes independent noise at each step; future iterations could explore more complex dependencies, such as those found in Hidden Markov Models. Finally, while the paper provides guidance on selecting the constant step size $\gamma$, developing automated tuning mechanisms for this hyperparameter remains an open challenge.

Summary updated

Abstract

Black-box optimization is often encountered for decision-making in complex systems management, where the knowledge of system is limited. Under these circumstances, it is essential to balance the utilization of new information with computational efficiency. In practice, decision-makers often face the dual tasks of optimization and statistical inference for the optimal performance, in order to achieve it with a high reliability. Our goal is to address the dual tasks in an online fashion. Wu et al (2022) [arXiv preprint: 2210.06737] point out that the sample average of performance estimates generated by the optimization algorithm needs not to admit a central limit theorem. We propose an algorithm that not only tackles this issue, but also provides an online consistent estimator for the variance of the performance. Furthermore, we characterize the convergence rate of the coverage probabilities of the asymptotic confidence intervals.
BibTeX
@misc{lian2025black,
  author = {Teng Lian and Jian-Qiang Hu and Yuhang Wu and Zeyu Zheng},
  title = {{Black-box Optimization with Simultaneous Statistical Inference for Optimal Performance}},
  year = {2025},
  eprint = {2501.07795},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07795},
  howpublished = {arXiv},
}
Figure