pith. sign in

arxiv: 2604.13965 · v1 · submitted 2026-04-15 · 🧮 math.OC

Understanding the Variance Dichotomy in Continuous Simulation Optimization: A Minimax Lower Bound Perspective

Jianzhong Du , L. Jeff Hong This is my paper

Pith reviewed 2026-05-10 12:33 UTC · model grok-4.3

classification 🧮 math.OC
keywords continuous simulation optimizationminimax lower boundvariance dichotomystochastic optimizationcomplexity analysisfinite budgetnoise variance
0
0 comments X

The pith

A minimax lower bound shows that finite-budget complexity in continuous simulation optimization is the larger of a variance-dependent term and a variance-independent term.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines why stochastic continuous simulation optimization appears to converge at rates insensitive to noise variance in asymptotic analyses, yet behaves differently under limited simulation budgets. It develops a minimax lower-bound argument that decomposes the problem complexity into the maximum of two quantities, one that scales with noise variance and one that does not. When the budget remains moderate and the noise level is low, the variance-independent term sets the rate, so stochastic problems require essentially the same effort as deterministic ones. Only when the budget grows large enough does the variance-dependent term dominate, producing slower convergence that depends on both noise magnitude and available simulations.

Core claim

Through minimax lower-bound analysis, the complexity of continuous simulation optimization is determined by the maximum of a variance-dependent term and a variance-independent term. This implies that low-noise stochastic CSO under moderate simulation budgets has the same complexity as deterministic CSO; increasing the budget beyond a variance-dependent threshold causes the variance term to dominate and shifts the convergence behavior to a slower, noise-limited regime.

What carries the argument

The minimax lower bound that expresses complexity as the maximum of a variance-dependent term and a variance-independent term.

Load-bearing premise

The minimax lower bound derivation accurately reflects the finite-budget behavior of continuous simulation optimization under the function classes and noise models considered.

What would settle it

Numerical runs on a low-variance stochastic CSO problem that show convergence rates matching the deterministic case at moderate budgets but slowing exactly when the budget exceeds a threshold scaling with one over the noise variance.

Figures

Figures reproduced from arXiv: 2604.13965 by Jianzhong Du, L. Jeff Hong.

Figure 1
Figure 1. Figure 1: The decrease of optimization error when the observation’s variance is different. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Plot of several possible functions under Assumption 3. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Plot of yG(x|c, c0, ζ) when c = 0.2, 0.5, 0.8, c0 = 0.5, ζ = 0.01, α = 1, β = 2, M = 1 and M˜ = 1 512 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Plot of yC(x|κa, a) when the highest partition level is ¯a = 2. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: When the objective function is y1(x) and problem dimension is one. 10 3 10 4 10 5 Budget 10 6 10 5 10 4 10 3 10 2 Optimization Error KWSA = 10 1 = 10 3 = 10 5 = 0 benchmark 10 3 10 4 10 5 Budget 10 5 10 4 10 3 10 2 Optimization Error Random Search = 10 1 = 10 3 = 10 5 = 0 benchmark 10 3 10 4 10 5 Budget 10 6 10 5 10 4 10 3 10 2 Optimization Error GASSO = 10 1 = 10 3 = 10 5 = 0 benchmark 10 3 10 4 10 5 Budg… view at source ↗
Figure 6
Figure 6. Figure 6: When the objective function is y2(x) and problem dimension is one. We first examine the behavior of existing CSO algorithms under the variance dichotomy. The benchmark methods include the stochastic approximation algorithm KWSA (Kiefer and Wolfowitz 1952), two random search methods, Uniform Search (Chia and Glynn 2013) and GASSO (Zhou and Bhatnagar 2017), and a model-based method, STRONG (Chang et al. 2013… view at source ↗
Figure 7
Figure 7. Figure 7: The optimization errors for synthetic CSO problems with objective function [PITH_FULL_IMAGE:figures/full_fig_p027_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: The optimization errors for synthetic CSO problems with objective function [PITH_FULL_IMAGE:figures/full_fig_p028_9.png] view at source ↗
read the original abstract

This paper studies the variance dichotomy in continuous simulation optimization (CSO). Existing literature shows a sharp contrast between deterministic CSO and stochastic CSO, with convergence rates in stochastic settings appearing insensitive to the magnitude of the noise variance. However, this asymptotic view does not fully explain the behavior of CSO under finite simulation budgets, especially in low-noise settings. To address this gap, this work develops a minimax lower-bound analysis and shows that the complexity is decided by the maximum of a variance-dependent term and a variance-independent term. When the simulation budget is not very large and the noise variance is low, the variance-independent term dominates, implying that low-noise stochastic CSO has essentially the same complexity as deterministic CSO. As the budget increases, the variance-dependent term becomes dominant, and the convergence behavior of stochastic CSO transitions to a slower regime determined jointly by the noise variance and the simulation budget.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops a minimax lower-bound analysis for continuous simulation optimization (CSO) to explain the variance dichotomy. It establishes that the complexity is given by the maximum of a variance-dependent term (from standard information-theoretic arguments on noisy queries) and a variance-independent term (recovering the deterministic black-box optimization lower bound on the chosen function class). This implies that for moderate simulation budgets and low noise variance, stochastic CSO has essentially the same complexity as deterministic CSO, with a transition to a slower noise-dominated regime only as the budget grows large.

Significance. If the lower bound holds, the result supplies a clean theoretical resolution to the apparent insensitivity of stochastic CSO rates to noise variance in finite-budget regimes, showing an explicit transition between deterministic-like and noise-limited behavior. The construction is free of circularity and hidden restrictions on the noise model or smoothness class, directly addressing the gap between asymptotic analyses and practical low-noise settings. This characterization could usefully inform algorithm design and budget allocation in simulation-based optimization.

minor comments (3)
  1. [§2] §2: The definition of the function class and the precise query model (oracle access) could be stated more explicitly with a short example to make the variance-independent term immediately comparable to standard deterministic lower bounds.
  2. [§3.2] §3.2, Eq. (8): The transition threshold between the two terms is derived but its dependence on the problem parameters (e.g., smoothness constants) is not numerically illustrated; adding a short table or plot would clarify when the variance-independent term dominates.
  3. Related work: A brief comparison paragraph contrasting the new finite-budget max-of-two-terms bound with existing asymptotic variance-insensitive rates (e.g., those cited in the introduction) would strengthen the motivation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and constructive review. The summary accurately captures the main contribution of our minimax lower-bound analysis, which resolves the apparent insensitivity of stochastic CSO rates to noise variance in finite-budget regimes by showing that complexity is governed by the maximum of the variance-dependent and variance-independent terms. We appreciate the recognition of the result's significance for algorithm design and budget allocation. Since the recommendation is for minor revision and no specific major comments were raised, we will proceed with any editorial or minor clarifications in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity in the minimax lower bound derivation

full rationale

The paper's central result is a minimax lower bound on the complexity of continuous simulation optimization, constructed via standard information-theoretic arguments applied to a chosen function class and noise model. The bound is expressed as the maximum of a variance-dependent term and a variance-independent term that recovers the deterministic case; this follows directly from the lower-bound construction without any self-definitional reductions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation is self-contained against external benchmarks and does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract provides no explicit free parameters, new entities, or ad-hoc axioms; the claim rests on standard minimax analysis applied to continuous simulation optimization.

axioms (1)
  • domain assumption Standard assumptions on the objective function class and noise model that permit a minimax lower bound to be derived for continuous simulation optimization.
    Typical background assumptions for complexity analysis in stochastic optimization; not detailed in the abstract.

pith-pipeline@v0.9.0 · 5453 in / 1331 out tokens · 46390 ms · 2026-05-10T12:33:27.049002+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address annote author booktitle chapter edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.s...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

    work page

  3. [3]

    year 1995

    author Agrawal, R. year 1995 . title The continuum-armed bandit problem . journal SIAM journal on control and optimization , volume 33 ( number 6 ), pages 1926--1951 . agrawal1995continuum

    work page 1995

  4. [4]

    , author E

    author Akhavan, A. , author E. Chzhen , author M. Pontil , author A. B. Tsybakov . year 2024 . title Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm . journal Journal of Machine Learning Research , volume 25 ( number 370 ), pages 1--50 . akhavan2024gradient

    work page 2024

  5. [5]

    , author M

    author Akhavan, A. , author M. Pontil , author A. Tsybakov . year 2020 . title Exploiting higher order smoothness in derivative-free optimization and continuous bandits . journal Advances in Neural Information Processing Systems , volume 33 , pages 9017--9027 . akhavan2020exploiting

    work page 2020

  6. [6]

    year 2014

    author Andrad \'o ttir, S. year 2014 . title A review of random search methods . journal Handbook of Simulation Optimization , pages 277--292 . andradottir2014review

    work page 2014

  7. [7]

    , author S

    author Arjevani, Y. , author S. Shalev-Shwartz , author O. Shamir . year 2016 . title On lower and upper bounds in smooth and strongly convex optimization . journal Journal of Machine Learning Research , volume 17 ( number 126 ), pages 1--51 . arjevani2016lower

    work page 2016

  8. [8]

    author Bartlett, P. L. , author V. Gabillon , author M. Valko . year 2019 . title A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption . In booktitle Algorithmic Learning Theory , pages 184--206 . organization PMLR . bartlett2019simple

    work page 2019

  9. [9]

    author Barton, R. R. , author M. Meckesheimer . year 2006 . title Metamodel-based simulation optimization . journal Handbooks in operations research and management science , volume 13 , pages 535--574 . barton2006metamodel

    work page 2006

  10. [10]

    , author L

    author Boyd, S. , author L. Vandenberghe . year 2004 . title Convex optimization . publisher Cambridge university press . boyd2004convex

    work page 2004

  11. [11]

    , author R

    author Bubeck, S. , author R. Munos , author G. Stoltz , author C. Szepesvari . year 2018 . title X-armed bandits . journal arXiv preprint arXiv:10014475 . bubeck2018

    work page 2018

  12. [12]

    , author D

    author B \"u hler, T. , author D. A. Salamon . year 2018 . title Functional analysis , volume volume 191 . publisher American Mathematical Soc. buhler2018functional

    work page 2018

  13. [13]

    author Bull, A. D. year 2011 . title Convergence rates of efficient global optimization algorithms. journal Journal of Machine Learning Research , volume 12 ( number 10 ). bull2011convergence

    work page 2011

  14. [14]

    , author L

    author Chang, K.-H. , author L. J. Hong , author H. Wan . year 2013 . title Stochastic trust-region response-surface method (strong)—a new response-surface framework for simulation optimization . journal INFORMS Journal on Computing , volume 25 ( number 2 ), pages 230--243 . chang2013stochastic

    work page 2013

  15. [15]

    , author H

    author Chen, H. , author H. Lam . year 2023 . title Pseudo-bayesian optimization . journal arXiv preprint arXiv:231009766 . chen2023pseudo

    work page 2023

  16. [16]

    author Chia, Y. L. , author P. W. Glynn . year 2013 . title Limit theorems for simulation-based optimization via random search . journal ACM Transactions on Modeling and Computer Simulation (TOMACS) , volume 23 ( number 3 ), pages 1--18 . chia2013limit

    work page 2013

  17. [17]

    , author S

    author Eckman, D. , author S. Henderson , author S. Shashaani , author R. Pasupathy . year 2025 . title SimOpt . ://github.com/simopt-admin/simopt. Eckman_SimOpt

    work page 2025

  18. [18]

    , author L

    author Fan, W.-W. , author L. J. Hong , author G.-X. Jiang , author J. Luo . year 2025 . title Review of large-scale simulation optimization . journal Journal of the Operations Research Society of China , volume 13 , pages 688–722 . fan2025review

    work page 2025

  19. [19]

    , author S

    author Fourati, F. , author S. Kharrat , author V. Aggarwal , author M.-S. Alouini . year 2025 . title Every call is precious: Global optimization of black-box functions with unknown lipschitz constants . In booktitle International Conference on Artificial Intelligence and Statistics , pages 5176--5184 . organization PMLR . fourati2025every

    work page 2025

  20. [20]

    author Fu, M. C. year 2002 . title Optimization for simulation: Theory vs. practice . journal INFORMS Journal on Computing , volume 14 ( number 3 ), pages 192--215 . fu2002optimization

    work page 2002

  21. [21]

    , author X

    author Gong, X. , author X. Wang , author L. Zhou , author N. Geng . year 2022 . title Managing hospital inpatient beds under clustered overflow configuration . journal Computers & Operations Research , volume 148 , pages 106021 . gong2022managing

    work page 2022

  22. [22]

    , author M

    author Grill, J.-B. , author M. Valko , author R. Munos . year 2015 . title Black-box optimization of noisy functions with unknown smoothness . journal Advances in Neural Information Processing Systems , volume 28 . grill2015black

    work page 2015

  23. [23]

    author Hong, L. J. , author C. Li , author J. Luo . year 2020 . title Finite-time regret analysis of kiefer-wolfowitz stochastic approximation algorithm and nonparametric multi-product dynamic pricing with unknown demand . journal Naval Research Logistics (NRL) , volume 67 ( number 5 ), pages 368--379 . hong2020finite

    work page 2020

  24. [24]

    author Hong, L. J. , author B. L. Nelson . year 2007 . title Selecting the best system when systems are revealed sequentially . journal Iie Transactions , volume 39 ( number 7 ), pages 723--734 . hong2007selecting

    work page 2007

  25. [25]

    author Hong, L. J. , author B. L. Nelson . year 2009 . title A brief introduction to optimization via simulation . In booktitle Proceedings of the 2009 Winter simulation conference (WSC) , pages 75--85 . organization IEEE . hong2009brief

    work page 2009

  26. [26]

    author Hong, L. J. , author X. Zhang . year 2021 . title Surrogate-based simulation optimization . In booktitle Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications , pages 287--311 . publisher INFORMS . hong2021surrogate

    work page 2021

  27. [27]

    , author M

    author Hu, J. , author M. C. Fu . year 2025 . title On the convergence rate of stochastic approximation for gradient-based stochastic optimization . journal Operations research , volume 73 ( number 2 ), pages 1143--1150 . hu2024convergence

    work page 2025

  28. [28]

    , author M

    author Hu, J. , author M. C. Fu , author S. I. Marcus . year 2007 . title A model reference adaptive search method for global optimization . journal Operations research , volume 55 ( number 3 ), pages 549--568 . hu2007model

    work page 2007

  29. [29]

    , author C.-L

    author Jia, S. , author C.-L. Li , author Z. Xu . year 2020 . title A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port . journal Transportation Research Part B: Methodological , volume 142 , pages 174--196 . jia2020simulation

    work page 2020

  30. [30]

    , author Y

    author Jiang, H. , author Y. Shen , author Y. Li , author B. Xu , author S. Du , author W. Zhang , author C. Zhang , author B. Cui . year 2024 . title Openbox: A python toolkit for generalized black-box optimization . journal Journal of Machine Learning Research , volume 25 ( number 120 ), pages 1--11 . Jiang2024OpenBox

    work page 2024

  31. [31]

    , author O

    author Kaufmann, E. , author O. Capp \'e , author A. Garivier . year 2016 . title On the complexity of best-arm identification in multi-armed bandit models . journal The Journal of Machine Learning Research , volume 17 ( number 1 ), pages 1--42 . kaufmann2016complexity

    work page 2016

  32. [32]

    , author R

    author Kiatsupaibul, S. , author R. L. Smith , author Z. B. Zabinsky . year 2018 . title Single observation adaptive search for continuous simulation optimization . journal Operations research , volume 66 ( number 6 ), pages 1713--1727 . kiatsupaibul2018single

    work page 2018

  33. [33]

    , author J

    author Kiefer, J. , author J. Wolfowitz . year 1952 . title Stochastic estimation of the maximum of a regression function . journal The Annals of Mathematical Statistics , pages 462--466 . kiefer1952stochastic

    work page 1952

  34. [34]

    , author A

    author Kleinberg, R. , author A. Slivkins , author E. Upfal . year 2008 . title Multi-armed bandits in metric spaces . In booktitle Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 681--690 . kleinberg2008multi

    work page 2008

  35. [35]

    , author M

    author Larson, J. , author M. Menickelly , author S. M. Wild . year 2019 . title Derivative-free optimization methods . journal Acta Numerica , volume 28 , pages 287--404 . larson2019derivative

    work page 2019

  36. [36]

    , author P.-Y

    author Liu, S. , author P.-Y. Chen , author B. Kailkhura , author G. Zhang , author A. O. Hero III , author P. K. Varshney . year 2020 . title A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications . journal IEEE Signal Processing Magazine , volume 37 ( number 5 ), pages 43--54 . liu2...

    work page 2020

  37. [37]

    , author A

    author Locatelli, A. , author A. Carpentier . year 2018 . title Adaptivity to smoothness in x-armed bandits . In booktitle Conference on Learning Theory , pages 1463--1492 . organization PMLR . locatelli2018adaptivity

    work page 2018

  38. [38]

    , author N

    author Malherbe, C. , author N. Vayatis . year 2017 . title Global optimization of lipschitz functions . In booktitle International conference on machine learning , pages 2314--2323 . organization PMLR . malherbe2017global

    work page 2017

  39. [39]

    year 2014

    author Munos, R. year 2014 . title From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning . journal Foundations and Trends in Finance , volume 7 ( number 1 ), pages 1--129 . munos2014

    work page 2014

  40. [40]

    , author A

    author Nemirovski, A. , author A. Juditsky , author G. Lan , author A. Shapiro . year 2009 . title Robust stochastic approximation approach to stochastic programming . journal SIAM Journal on optimization , volume 19 ( number 4 ), pages 1574--1609 . nemirovski2009robust

    work page 2009

  41. [41]

    author Nemirovskij, A. S. , author D. B. Yudin . year 1983 . title Problem complexity and method efficiency in optimization . publisher Wiley-Interscience . nemirovskij1983problem

    work page 1983

  42. [42]

    , author B

    author Pichitlamken, J. , author B. L. Nelson , author L. J. Hong . year 2006 . title A sequential procedure for neighborhood selection-of-the-best in optimization via simulation . journal European Journal of Operational Research , volume 173 ( number 1 ), pages 283--298 . pichitlamken2006sequential

    work page 2006

  43. [43]

    year 2013

    author Shamir, O. year 2013 . title On the complexity of bandit and derivative-free stochastic convex optimization . In booktitle Conference on Learning Theory , pages 3--24 . organization PMLR . shamir2013complexity

    work page 2013

  44. [44]

    , author E

    author Shang, X. , author E. Kaufmann , author M. Valko . year 2019 . title General parallel optimization a without metric . In booktitle Algorithmic Learning Theory , pages 762--788 . organization PMLR . shang2019general

    work page 2019

  45. [45]

    year 2021

    author Singh, S. year 2021 . title Continuum-armed bandits: A function space perspective . In booktitle International Conference on Artificial Intelligence and Statistics , pages 2620--2628 . organization PMLR . singh2021continuum

    work page 2021

  46. [46]

    author Spall, J. C. year 2000 . title Adaptive stochastic approximation by the simultaneous perturbation method . journal IEEE transactions on automatic control , volume 45 ( number 10 ), pages 1839--1853 . spall2000adaptive

    work page 2000

  47. [47]

    author Tsybakov, A. B. year 2010 . title Introduction to Nonparametric Estimation . publisher Springer New York, NY . tsybakov2010

    work page 2010

  48. [48]

    , author L

    author Wang, T. , author L. J. Hong . year 2023 . title Large-scale inventory optimization: A recurrent neural networks--inspired simulation approach . journal INFORMS Journal on Computing , volume 35 ( number 1 ), pages 196--215 . wang2023large

    work page 2023

  49. [49]

    , author L

    author Wang, X. , author L. J. Hong , author Z. Jiang , author H. Shen . year 2023 . title Gaussian process-based random search for continuous optimization via simulation . journal Operations Research . wang2023gaussian

    work page 2023

  50. [50]

    , author S

    author Wang, Y. , author S. Balakrishnan , author A. Singh . year 2018 . title Optimization of smooth functions with noisy observations: Local minimax rates . journal Advances in Neural Information Processing Systems , volume 31 . wang2018optimization

    work page 2018

  51. [51]

    , author P

    author Yakowitz, S. , author P. L'ecuyer , author F. Vazquez-Abad . year 2000 . title Global stochastic optimization with low-dispersion point sets . journal Operations Research , volume 48 ( number 6 ), pages 939--950 . yakowitz2000global

    work page 2000

  52. [52]

    , author Y

    author Yu, Q. , author Y. Wang , author B. Huang , author Q. Lei , author J. D. Lee . year 2024 . title Stochastic zeroth-order optimization under strongly convexity and lipschitz hessian: minimax sample complexity . journal Advances in Neural Information Processing Systems , volume 37 , pages 99564--99600 . yu2024stochastic

    work page 2024

  53. [53]

    , author S

    author Zhou, E. , author S. Bhatnagar . year 2017 . title Gradient-based adaptive stochastic search for simulation optimization over continuous space . journal INFORMS Journal on Computing , volume 30 ( number 1 ), pages 154--167 . zhou2017gradient

    work page 2017