Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
Abstract
Blind random search is a simple global optimization method that only requires the value of the loss function, without needing gradient information or an explicit loss model. However, its classical formulation assumes that the loss evaluation is noise-free, which limits its direct application to practical problems with noisy measurements. We extend blind random search by combining a vanishing acceptance threshold with the running average of noisy loss measurements. Under the stated assumptions, we prove that the proposed algorithm converges almost surely to the global minimizer. We further analyze the rate at which the loss at the current estimate approaches the minimum loss. For low-dimensional cases, we obtain an almost sure asymptotic upper bound on the difference between the two, and for high-dimensional cases, we prove that this difference, suitably scaled, has an exact Weibull limiting distribution.
Related
- Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
- Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
- The Minimum Number of Measurements for Almost-Everywhere Complex Phase Retrieval
- Almost sure upper bound for random multiplicative functions
- Almost everywhere convergence of mock Fourier series for the middle-fourth Cantor measure
BibTeX
@misc{zhou2026blind,
title = {{Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates}},
author = {Zixian Zhou and James C. Spall},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33302},
eprint = {2610.33302},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33302},
}
RIS
TY - UNPB
TI - Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
AU - Zixian Zhou
AU - James C. Spall
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33302
UR - https://arxiv.org/abs/2610.33302
AB - Blind random search is a simple global optimization method that only requires the value of the loss function, without needing gradient information or an explicit loss model. However, its classical formulation assumes that the loss evaluation is noise-free, which limits its direct application to practical problems with noisy measurements. We extend blind random search by combining a vanishing acceptance threshold with the running average of noisy loss measurements. Under the stated assumptions, we prove that the proposed algorithm converges almost surely to the global minimizer. We further analyze the rate at which the loss at the current estimate approaches the minimum loss. For low-dimensional cases, we obtain an almost sure asymptotic upper bound on the difference between the two, and for high-dimensional cases, we prove that this difference, suitably scaled, has an exact Weibull limiting distribution.
ER -