Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulation
Not on the map. Why?
Abstract (arXiv)
Gradient-based optimization methods are commonly used to identify local optima in high-dimensional spaces. When derivatives cannot be evaluated directly, stochastic estimators can provide approximate gradients. However, these estimators' perturbation-based sampling of the objective function introduces variance that can lead to slow convergence. In this paper, we present dimensional peeking, a variance reduction method for gradient estimation in discrete optimization via simulation. By lifting the sampling granularity from scalar values to classes of values that follow the same control flow path, we increase the information gathered per simulation evaluation. Our derivation from an established smoothed gradient estimator shows that the method does not introduce any bias. We present an implementation via a custom numerical data type to transparently carry out dimensional peeking over C++ programs. Variance reductions by factors of up to 7.9 are observed for three simulation-based optimization problems with high-dimensional input. The optimization progress compared to three meta-heuristics shows that dimensional peeking increases the competitiveness of zeroth-order optimization for discrete and non-convex simulations.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 13 of its 38 references that are in the map. First posted on arXiv 21 Jan 2026.
Builds on
13 of 38 references.
References · 13
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
- 2019CityFlow: A Multi-Agent Reinforcement Learning Environment for Large Scale City Traffic Scenariocited by 115
- 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
- 2022Automatic Differentiation of Programs with Discrete Randomnesscited by 29
- 2021Zeroth order optimization with orthogonal random directionscited by 21
- 2016ASTRO-DF: A Class of Adaptive Sampling Trust-Region Algorithms for Derivative-Free Stochastic Optimizationcited by 7
- 2022Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Boundscited by 7
- 2022Differentiable Physics Simulations with Contacts: Do They Have Correct Gradients w.r.t. Position, Velocity and Control?cited by 7
- 2023Smoothing Methods for Automatic Differentiation Across Conditional Branchescited by 7
- 2020Gradient-based Algorithms for Convex Discrete Optimization via Simulationcited by 5
- 2024Generalizing Stochastic Smoothing for Differentiation and Gradient Estimationcited by 4
Built on by
Not cited yet.