Research map / Learning theory and algorithms / Combinatorial and search optimization
Sample-and-Bound for Non-convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MCIR, an MCTS-based sampling method for non-convex global optimization that uses interval-bound lower bounds, volume-aware UCT, and Hessian/gradient-based node learning, evaluated against sampling and tree-search baselines on synthetic, bound-constrained, and neural-network-derived benchmarks.
Problem
Global optimization of high-dimensional non-convex functions with known analytic form, where branch-and-bound partition trees grow exponentially with dimension and pure sampling methods struggle to converge.
Approach
Adapts MCTS by replacing visitation-count UCB with interval-arithmetic lower bounds and box-volume terms, grows the tree by sampling rather than fixed partitions, and inserts a Newton-style node learned from averaged gradient and Hessian information attached to the root.
Key results
- On Michalewicz-200d, MCIR reaches -172.58 ± 2.84 versus DA's -199.14 and Gurobi's -202.46, so it is not best across all tasks.
- On Biggsbi1-1000d, MCIR reaches 1.0101 ± 0.0001 versus DIRECT's 1.6592 and DE's 56.17 among the baselines reported.
- On NN-Michalewicz-100d, MCIR reaches -17.51 ± 0.01, the best among reported methods, versus DA's -14.65 and TuRBO's -15.10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MCIR instead of CMA | Ackley optimization · Ackley-50d | best objective value: $0.0000 \pm 0.0000$ -> $0.6245 \pm 0.7649$ | Hurt |
| Use MCIR instead of CMA | Ackley optimization · Ackley-100d | best objective value: $0.0000 \pm 0.0000$ -> $0.0000 \pm 0.0000$ | No clear effect |
| Use MCIR instead of CMA | Ackley optimization · Ackley-200d | best objective value: $0.0000 \pm 0.0000$ -> $0.5135 \pm 1.0270$ | Hurt |
| Use MCIR instead of Dual Annealing | Levy optimization · Levy-50d | best objective value: $0.0000 \pm 0.0000 $ -> $5.5889 \pm 1.9306 $ | Hurt |
| Use MCIR instead of Gurobi | Levy optimization · Levy-100d | best objective value: $-0.0000 \pm 0.0000 $ -> $9.1970 \pm 1.4018 $ | Hurt |
| Use MCIR instead of Gurobi | Levy optimization · Levy-200d | best objective value: $-0.0002 \pm 0.0000 $ -> $20.5379 \pm 4.1395 $ | Hurt |
| Use MCIR instead of Gurobi | Michalewicz optimization · Michalewicz-50d | best objective value: $-49.8521 \pm 0.0000 $ -> $-48.0423 \pm 0.7511 $ | Hurt |
| Use MCIR instead of Gurobi | Michalewicz optimization · Michalewicz-100d | best objective value: $-100.5415 \pm 0.0000 $ -> $-91.9268 \pm 1.0598 $ | Hurt |
| Use MCIR instead of Gurobi | Michalewicz optimization · Michalewicz-200d | best objective value: $-202.4635 \pm 0.0000 $ -> $-172.5783 \pm 2.8443 $ | Hurt |
| Use MCIR instead of DIRECT | Biggsbi1 optimization · Biggsbi1-1000d | best objective value: $1.6592 \pm 0.0000 $ -> $1.0101 \pm 0.0001 $ | Helped |
| Use MCIR instead of Differential Evolution | Harkerp optimization · Harkerp-100d | best objective value: $-0.7887 \pm 0.0738 $ -> $-0.9256 \pm 0.0017 $ | Helped |
| Use MCIR instead of CMA | Watson optimization · Watson-31d | best objective value: $0.0000 \pm 0.0000$ -> $0.0023 \pm 0.0018 $ | Hurt |
Surprising findings
- CMA-ES reaches near-zero error on Ackley-50d/100d/200d and Watson-31d, outperforming MCIR on those tasks.
- Gurobi finishes in one function evaluation and attains the best value on several Michalewicz and Levy instances, reporting an anomalous negative Levy value.
Limitations
- Requires access to the analytic form of the objective for interval bounds and derivatives, so it does not apply to black-box problems.
- Interval and Hessian computations add overhead; the authors note reducing numerical overhead as future work.
- Performance depends on hyperparameters (C_lb, C_v, C_x, child count, local optimizer budget) and is sensitive to local optimizer settings; neural-network objectives lack Hessian information (ReLU).
Experimental setup
Datasets: Levy Ackley Michalewicz Biggsbi1 Harkerp Watson
Benchmarks: Ackley Levy Michalewicz Biggsbi1 Harkerp Watson one-layer ReLU neural network objectives
Metrics: best-found objective value (mean ± std over 5 seeds) time to best point number of samples to best point
Baselines: basinhopping differential evolution dual annealing DIRECT CMA-ES TuRBO LaMCTS Gurobi
Builds on: Monte Carlo Tree Search UCT L-BFGS-B LaMCTS
Closest papers by meaning
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.89)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- An Online Adaptive Sampling Algorithm for Stochastic Difference-of-convex Optimization with Time-varying Distributions (ICML 2025 · similarity 0.87)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.86)
- Optimizing Posterior Samples for Bayesian Optimization via Rootfinding (ICLR 2025 · similarity 0.86)
- Monte Carlo Tree Search in the Presence of Transition Uncertainty (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.