Regular Tree Search for Simulation Optimization

• URL: http://arxiv.org/abs/2506.17696v1
• Date: Sat, 21 Jun 2025 12:07:01 GMT
• Title: Regular Tree Search for Simulation Optimization
• Authors: Du-Yi Wang, Guo Liang, Guangwu Liu, Kun Zhang,
• Abstract summary: We propose a class of random algorithms, called Regular Tree Search, which integrates adaptive sampling with partitioning the search space.<n>We prove global convergence under sub-Gaussian noise, based on assumptions involving the optimality gap, without requiring continuity of the objective function.
• Score: 5.54189661879098
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Tackling simulation optimization problems with non-convex objective functions remains a fundamental challenge in operations research. In this paper, we propose a class of random search algorithms, called Regular Tree Search, which integrates adaptive sampling with recursive partitioning of the search space. The algorithm concentrates simulations on increasingly promising regions by iteratively refining a tree structure. A tree search strategy guides sampling decisions, while partitioning is triggered when the number of samples in a leaf node exceeds a threshold that depends on its depth. Furthermore, a specific tree search strategy, Upper Confidence Bounds applied to Trees (UCT), is employed in the Regular Tree Search. We prove global convergence under sub-Gaussian noise, based on assumptions involving the optimality gap, without requiring continuity of the objective function. Numerical experiments confirm that the algorithm reliably identifies the global optimum and provides accurate estimates of its objective value.

Related papers

• Decision Tree Induction Through LLMs via Semantically-Aware Evolution [53.0367886783772]
  We propose an evolutionary optimization method for decision tree induction based on genetic programming (GP)<n>Our key innovation is the integration of semantic priors and domain-specific knowledge about the search space into the algorithm.<n>This is operationalized through novel genetic operators that work with structured natural language prompts.
  arXiv  Detail & Related papers  (2025-03-18T12:52:03Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• Sample-and-Bound for Non-Convex Optimization [18.30858789210194]
  We propose new sampling methods for non-dimensional objective optimization that adapts Monte Carlo benchmarks to improve efficiency. We evaluate the proposed high-order baseline and competitive benchmarks algorithms aggressively.
  arXiv  Detail & Related papers  (2024-01-09T20:45:47Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• CITS: Coherent Ising Tree Search Algorithm Towards Solving Combinatorial Optimization Problems [0.0]
  This paper proposes a search algorithm by expanding search space from a Markov chain to a depth limited tree based on SA. At each iteration, the algorithm will select the best near-optimal solution within the feasible search space by exploring along the tree in the sense of look ahead' Our results show that above the primals SA and CIM, our high-level tree search strategy is able to provide solutions within fewer epochs for Ising formulated NP-optimization problems.
  arXiv  Detail & Related papers  (2022-03-09T10:07:26Z)
• Optimal Survival Trees [2.7910505923792637]
  We present a new Optimal Survival Trees algorithm that leverages mixed-integer optimization (MIO) and local search techniques to generate globally optimized survival tree models. We demonstrate that the algorithm improves on the accuracy of existing survival tree methods, particularly in large datasets.
  arXiv  Detail & Related papers  (2020-12-08T09:00:57Z)
• From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering [33.000371053304676]
  We present the first continuous relaxation of Dasgupta's discrete optimization problem with provable quality guarantees. We show that even approximate solutions found with gradient descent have superior quality than agglomerative clusterings. We also highlight the flexibility of HypHC using end-to-end training in a downstream classification task.
  arXiv  Detail & Related papers  (2020-10-01T13:43:19Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.