Source-linked AI summary
Blind Random Search with Noisy Loss Measurements: Averaging, Thresholding, and Almost Sure Convergence
Zixian Zhou, Xintong Jiang
TL;DR
Noisy loss measurements can make an inferior candidate appear better, disrupting blind random search's monotonicity. The paper combines averaging and thresholding, reporting large reductions in terminal true-loss gaps while noting that empirical monotonicity is not itself a convergence proof or rate estimate.
Problem
Noisy objective measurements can make an inferior candidate appear better and break the monotonicity of blind random search.
Method
The proposed algorithm compares an averaged candidate loss with the current estimate and uses a threshold alongside averaging.
Results
99.79% reductions in median terminal true-loss gaps were obtained in both problems, while remeasurement reductions were 99.74% and 99.76%.
Takeaways & Limitations
The empirical finding that candidates increased the true loss is consistent with eventual monotonicity established in the convergence analysis.
Takeaways & Limitations
The empirical result is not a convergence proof or a rate estimate.
Abstract
from arXiv · showhide
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.
1 Introduction
Blind random search is useful when little objective information is available, but noisy measurements can make worse candidates appear better and destroy loss monotonicity. The paper combines increasing averaging, a vanishing positive threshold, and reused observations to recover eventual monotonicity and almost-sure convergence.
- Blind random search samples independently across the domain without adapting its sampling strategy to earlier information.This makes it useful when little exploitable objective information is available.
- In the noiseless setting, candidates are accepted only when their loss is lower, so current-estimate loss values are nonincreasing.
- Zero-mean measurement noise can make an apparent improvement conceal a true deterioration, allowing candidates with higher true loss to be accepted.The observation model is y(θ) = L(θ) + ϵ with E[ϵ] = 0.
- Averaging reduces loss-estimate variance, while thresholding requires observed improvement to exceed a positive margin and thereby reduces false acceptances.
- The proposed algorithm combines increasing averaging, a vanishing positive threshold, and accumulated measurements at the current estimate, while controlling the resulting selection bias.The paper shows that true loss is eventually nonincreasing and the search converges almost surely to the global optimum.
2 The Algorithm
The algorithm compares an averaged candidate loss with a pooled estimate at the current point, increases sample sizes, and couples them to a vanishing dynamic threshold. It reuses current-estimate measurements, accepting candidates only when the thresholded comparison succeeds.
- The comparison uses an averaged loss at the candidate point and a pooled loss estimate at the current estimate.Equation (1) defines this comparison rule.
- The algorithm initializes the current estimate with k0 observations and begins iterations from that sample size.
- At each search iteration, the candidate loss is averaged over observations before applying the acceptance rule.
- If a candidate is accepted, it becomes the new estimate and its averaged loss is stored; after rejection, one fresh observation is added to the current estimate.At iteration end, the current estimate's stored average contains exactly k + 1 observations.
- The method stores only the current estimate and pooled loss estimate rather than retaining every sampled point.
- Growing sample sizes are coupled with a vanishing threshold, creating the selection bias analyzed later.Unlike remeasurement methods, the algorithm reuses accumulated observations at the current estimate.
3 Convergence Analysis
The convergence analysis assumes separated minimizers and independent, identically distributed mean-zero subgaussian noise with fixed candidate-sampling distributions. Under these assumptions, the theorem establishes almost-sure convergence through uniform noise control, eventual monotonicity, and recurring acceptance of near-optimal candidates.
- Student's t noise with finite degrees of freedom is excluded because its polynomial tails violate the subgaussian tail bound.
- The analysis assumes a minimizer separated from all other points, which implies that the minimizer is unique.
- Noise observations are mutually independent and identically distributed, mean zero, and subgaussian with common variance proxy σ2.
- Candidate draws are independent across iterations and of measurement noise, with sampling distributions fixed in advance as functions of k.
- The proof controls comparison noise uniformly and shows that the current noise average converges to zero despite dependence on earlier acceptance decisions.
- The proof establishes eventual monotonicity of true loss, recurring near-optimal candidates, and their eventual acceptance, yielding an almost-sure convergence result.The argument is stated to hold almost surely unless otherwise noted.
Part I: Comparison noise and selection bias
Cumulative averaging creates a comparison between a fresh candidate average and a reused current average whose distribution is altered by past acceptances and rejections. Conditioning on acceptance therefore induces selection bias in the accepted candidate noise.
- Sample construction: At iteration k, the current estimate averages k accumulated measurements, while the candidate uses k + 1 new measurements.The candidate batch is independent and freshly sampled; the current sample is reused across comparisons.
- Comparison criterion: Each newly drawn measurement error is independent, identically distributed, and mean zero, but the decision combines true-loss change with the difference between noise averages.The acceptance test can therefore be affected by comparison noise even when individual errors are unbiased.
- Selection bias: Whenever acceptance has probability strictly between zero and one, the accepted candidate average has negative conditional mean despite zero unconditional mean.Selection favors candidate measurements with unusually low observed noise.
- Current-average dependence: The current average is not an ordinary centered average because it includes measurements retained from the latest accepted point and later rejection measurements.Its composition depends on the search history rather than only on independent fresh errors.
Part II: Realized sample decomposition
The realized current sample can be decomposed according to when the current estimate was established and how many later rejections added measurements at that estimate. Figure 1 represents these components as retained, rejection-added, and candidate measurements.
- Sample history: Let n_k denote the sample size when the current estimate was established; it equals the initialization size before the first acceptance and j + 1 after an acceptance at iteration j.This index identifies the measurements inherited from the most recently accepted point.
- Realized decomposition: The current average contains the measurements establishing the current estimate plus one additional measurement for each later rejection.The inherited block has weight n_k/k, while each rejection-added noise term has weight 1/k.
- Figure 1: Figure 1 uses blue for inherited measurements, yellow for later rejection measurements, green for candidate measurements, and red for the added post-rejection measurement.This color coding mirrors the algebraic decomposition of the realized sample.
- Acceptance update: If a candidate is accepted, its k + 1 measurements become the accumulated sample at the new current estimate.The next establishment index is then n_{k+1} = k + 1.
- Rejection update: If a candidate is rejected, the retained accumulated measurements remain and one new measurement is taken at the current estimate.The establishment index remains unchanged, n_{k+1} = n_k, and the new error is ζ_{k+1}.
Part III: Comparison bound for a deterministic history
The comparison bound handles the random history by first bounding decomposed averages for every deterministic possible establishment index and then substituting the index selected by the algorithm. Subgaussian concentration and Borel–Cantelli yield eventual control of the comparison noise.
- Decomposition: The decomposition separates the sample present when the current estimate was established from measurements added after subsequent rejections.This representation is used in the later comparison and convergence arguments.
- Deterministic history: For fixed deterministic (n, k), the decomposed current-noise term A_k(n) averages k independent noises and is subgaussian with variance proxy σ^2/k.The fresh candidate average is independent of A_k(n), so their difference is subgaussian with variance proxy 2σ^2/k.
- Random-history control: Because acceptance makes n_k random, the proof controls A_k(n) uniformly over deterministic n before substituting the algorithm-selected n_k.There are at most k possible values of n at iteration k.
- Fresh candidate concentration: The fresh candidate average is subgaussian with variance proxy σ^2/(k + 1), and its tail bound is summable in k.The proof applies Borel–Cantelli after combining the candidate and current-average bounds.
- Asymptotic bound: Almost surely, the comparison noise satisfies |D_k| ≤ τ_k for all sufficiently large k, with τ_k → 0.The summability argument leaves only finitely many exceptional iterations.
Part V: Eventual monotonicity
Once comparison noise is eventually bounded by the shrinking threshold, accepted updates cannot increase the true loss. The reachability argument also shows that candidates in any neighborhood S_{η/2} are generated infinitely often almost surely.
- Acceptance implication: If the acceptance test holds, the comparison identity gives Δ_k + D_k < −τ_k and sets the next estimate to the candidate.This links the noisy acceptance event to the true-loss increment and comparison noise.
- Eventual noise control: For all sufficiently large k, |D_k| ≤ τ_k, so the threshold controls the noise contribution in accepted comparisons.The bound follows from the eventual comparison-noise result.
- Reachability: Candidates in S_{η/2} are generated infinitely many times almost surely.The reachability argument uses divergent occurrence probabilities and the second Borel–Cantelli lemma.
Part VII: Eventual acceptance
Once the threshold vanishes, sufficiently accurate comparisons eventually accept a candidate from Sη/2 whenever the current estimate lies outside Sη, and this mechanism recurs infinitely often almost surely.
- Because τk → 0, the preceding acceptance argument applies for all sufficiently large k almost surely.
- If the current estimate is outside Sη and the comparison event holds, the candidate's loss gap satisfies ∆k < −η/2.
- The acceptance test then updates the estimate to θnew(k + 1) ∈ Sη/2 ⊂ Sη.
- Almost every sample path contains infinitely many indices where the required event and comparison condition hold.
Part VIII: Convergence
Applying the eventual-acceptance result across η = 1/m yields almost sure loss convergence, and Assumption A1 then gives almost sure convergence of the estimates to θ∗.
- Applying Part VII to η = 1/m and intersecting the resulting probability-one events extends the argument to all positive accuracy levels.
- The estimates satisfy L(ˆθk) → L(θ∗) almost surely.
- Under Assumption A1, the loss convergence implies ˆθk → θ∗ almost surely.
4 Numerical Experiments
The experiments compare the proposed averaging-and-thresholding method with remeasurement and naive blind random search under matched noisy-measurement budgets. Across quadratic and quartic problems, the controlled methods improve as budgets grow, generally outperform naive search, and achieve large terminal-gap reductions.
- Experimental setup: The experiments use two noisy test problems: a p = 2 quadratic and a p = 5 skewed quartic, with i.i.d. Gaussian measurement errors and uniform candidate sampling.The quadratic uses σ = 2, while the quartic uses σ = 3.
- Experimental setup: The proposed method, remeasurement benchmark, and naive search are compared under matched total measurement budgets rather than matched numbers of comparisons.The proposed method’s realized budget determines how many full comparisons the benchmark completes, while naive search uses exactly the same measurement count.
- Quadratic results: At small budgets on the quadratic problem, naive search initially performs better because one measurement per candidate permits broader exploration.At approximately 5.25 × 10^3 measurements, the proposed method, remeasurement benchmark, and naive method test 100, 71, and about 5,250 candidates, respectively.
- Quadratic results: As budgets increase, both controlled methods continue improving while naive search plateaus after retaining an unusually low noise-driven measurement.The proposed method generally attains the lower gap than the remeasurement benchmark.
- Largest-budget results: Across 400 largest-budget runs, none of 2,801 accepted updates increased the true loss, consistent with eventual monotonicity but not constituting a convergence proof or rate estimate.The controlled methods share averaging and thresholding and become much smaller than naive search’s gap as the budget grows.
5 Conclusions
The paper combines increasing averaging with a vanishing positive threshold to obtain almost-sure convergence and eventual monotonicity under noisy loss measurements. It also studies pooled comparisons, which reduce repeated measurements but introduce selection bias requiring additional control.
- Increasing averaging and a vanishing positive threshold yield almost-sure convergence to the global minimizer.
- The combined modifications make the true loss eventually nonincreasing almost surely despite measurement noise.
- Pooled comparisons use new candidate measurements against a pooled average at the current estimate instead of remeasuring the current estimate each time.This reduces repeated measurements at the current estimate.
- The convergence proof controls selection bias by obtaining a uniform bound over possible current noise averages before acceptance history selects the current estimate.
- Under matched total measurement budgets, pooled reuse performs similarly to the remeasurement benchmark and is generally somewhat better.
- Future work will examine more efficient averaging and threshold schedules and extensions to localized random search and other stochastic methods.