Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
Abstract
Blind random search repeatedly draws a candidate point and replaces the current estimate whenever the candidate has a lower loss. In the absence of noise, the true loss is observed directly. It decreases strictly at every accepted update and is monotone nonincreasing over all iterations. Measurement noise can make a worse candidate appear better and thereby break this monotonicity. To recover almost sure convergence under noise, we incorporate averaging and thresholding into the original decision criterion. These two classical tools are coupled. As the sample sizes grow, the positive threshold shrinks at a matched rate. These modifications allow blind random search to recover eventual monotonicity of the true loss under noisy measurements and to converge almost surely.
Related
- Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates
- Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence
- Repeated averaging on expanders I: random d-regular graph
- Growing-time trace fluctuations and self-averaging form factors of Grover walks on random lifts
- Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis
BibTeX
@misc{zhou2026blind,
title = {{Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence}},
author = {Zixian Zhou and Xintong Jiang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04636},
eprint = {2609.04636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04636},
}
RIS
TY - UNPB
TI - Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
AU - Zixian Zhou
AU - Xintong Jiang
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04636
UR - https://arxiv.org/abs/2609.04636
AB - Blind random search repeatedly draws a candidate point and replaces the current estimate whenever the candidate has a lower loss. In the absence of noise, the true loss is observed directly. It decreases strictly at every accepted update and is monotone nonincreasing over all iterations. Measurement noise can make a worse candidate appear better and thereby break this monotonicity. To recover almost sure convergence under noise, we incorporate averaging and thresholding into the original decision criterion. These two classical tools are coupled. As the sample sizes grow, the positive threshold shrinks at a matched rate. These modifications allow blind random search to recover eventual monotonicity of the true loss under noisy measurements and to converge almost surely.
ER -