PaperlayerView exact revision on arXiv

Source-linked AI summary

Blind Random Search with Noisy Measurements: Almost Sure Convergence and Convergence Rates

Zixian Zhou, James C. Spall

arXiv:2610.33302v1math.OCstat.ML

TL;DR

Blind random search can avoid gradient measurements, but its classical form assumes noise-free loss evaluations. This paper combines running averages with a vanishing acceptance threshold and proves almost sure convergence, with dimension-dependent rate results.

  • Problem

    Blind random search is useful when gradients are unavailable, but its classical formulation assumes noise-free loss measurements.

    Source: §I · p. 1

  • Method

    The algorithm combines running averages of noisy loss measurements with a vanishing acceptance threshold, adding one measurement at the current estimate after each rejection.

    Source: §I · p. 1, §V · p. 6

  • Results

    The algorithm converges almost surely to the global minimizer; low-dimensional cases have an almost sure asymptotic upper bound, while scaled high-dimensional suboptimality has a Weibull limit.

    Source: §V · p. 6

  • Takeaways & Limitations

    The rate results provide a basis for assessing the algorithm’s asymptotic convergence speed.

    Source: §V · p. 6

Abstract

from arXiv · show

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.

I. Introduction

The paper addresses blind random search when loss measurements are noisy, proposing running averages and a vanishing acceptance threshold. It establishes almost sure convergence and dimension-dependent convergence-rate results.

I. Introduction

  • Blind random search samples candidates independently without using past results, but can require many loss evaluations, especially in high dimensions.In its basic uniform-sampling form, it requires no tuning of algorithmic coefficients.Source: §I · p. 1
  • Noisy measurements can make a candidate appear better despite having higher true loss; prior comparison methods use averaging, thresholding, or both.Sequential methods may remeasure the current estimate at every iteration, increasing measurement cost; stored averages do not use a positive threshold.Source: §I · p. 1
  • The algorithm retains the current estimate’s running average, adds one measurement after each rejection, and uses a vanishing acceptance threshold.The paper also derives corresponding convergence rates.Source: §I · p. 1
  • Low-dimensional cases have an almost sure upper rate, while high-dimensional cases have an exact Weibull limit for the scaled suboptimality gap.The regime boundary depends on local loss growth and the sampling distribution.Source: §I · p. 2

II. The Algorithm

The algorithm modifies blind random search for noisy loss measurements by combining averages over increasing measurement counts with a vanishing threshold. It retains the current estimate and adds one measurement after a rejection.

II. The Algorithm

  • Initialization fixes k0 and an initial estimate, then averages k0 loss measurements at that estimate.The algorithm starts its iteration index at k0.Source: §II · p. 2
  • At iteration k, the candidate’s loss average uses k + 1 new measurements, and acceptance is determined using a vanishing threshold.The threshold uses the known sub-Gaussian scale parameter σ.Source: §II · p. 2
  • After acceptance, the candidate becomes the estimate and its measured average becomes the estimate’s running average.The algorithm then increases k by one and returns to the search step.Source: §II · p. 2
  • After rejection, the estimate stays unchanged and one additional loss measurement updates its running average.At the end of iteration k, the estimate’s average represents exactly k + 1 measurements.Source: §II · p. 2
  • The stated rates use iteration index k, while numerical comparisons use matched measurement budgets; the measurement count grows quadratically with K.Termination may use a predefined criterion such as a maximum number of noisy measurements.Source: §II · p. 2

III. Almost Sure Convergence and Rates

Under A1–A3, the algorithm converges almost surely to the global minimizer despite noisy loss measurements. Under the additional rate assumptions A4, its convergence behavior depends on the dimension relative to the local loss growth and sampling parameter γ.

Rate interpretation

  • Higher γ corresponds to more gradual loss growth near the minimizer; this helps sampling near-minimal-loss points, while the low-dimensional guaranteed rate is determined by the threshold.In high dimensions, the loss at the current estimate converges to the minimum more quickly; in low dimensions, changes in γ do not affect the guaranteed rate.Source: §III · p. 3

Almost sure convergence

  • The estimate converges almost surely to the global minimizer under A1–A3, retaining the convergence strength of noise-free blind random search [1, Thm. 2.1].The proof establishes eventual monotonicity of the loss and recurrent sampling near the minimizer.Source: §III · p. 3

Convergence proof

  • The proof handles selection bias by bounding comparison noise, then uses eventual monotonicity and repeated opportunities to sample near the minimizer to establish convergence.The algorithm updates its current loss average after rejection; its measurements are subject to the noise assumptions in A2.Source: §III · p. 3

Rate assumptions

  • Rate guarantees require A1–A4; A4 specifies local loss growth and near-minimizer sampling behavior, while A2 assumes centered i.i.d. sub-Gaussian measurement noise.The parameter γ must satisfy both parts of A4, and an incorrect γ can invalidate use of the rate theorem.Source: §III · pp. 2–3

Convergence rates

  • For p > 2γ, the suboptimality gap has an almost-sure asymptotic upper bound, whereas for p ≤ 2γ its scaled limit is Weibull with shape p/γ.The rate theorem also treats distance to the minimizer; the stated rate regime depends on dimension p relative to γ.Source: §III · pp. 3–4

IV. Numerical Experiments

The experiments compare running averages with resampling and naive search, then check the rate results on a photovoltaic model.

IV. Numerical Experiments

  • The experiments compare running averages with resampling and naive search.The photovoltaic model is used to check the rate results.Source: §IV · p. 5
  • The rate results are also checked on a photovoltaic model.Source: §IV · p. 5
  • The experimental plan first compares the search methods, then evaluates the rate results on the photovoltaic model.Source: §IV · p. 5

A. Convergence behavior and comparison with resampling

At the largest measurement budget, the proposed and resampling methods have lower median suboptimality gaps than naive search on both test losses. Both averaging methods continue improving as the budget grows, and none of 2801 accepted proposed updates increased true loss.

A. Convergence behavior and comparison with resampling

B. Photovoltaic example and convergence rates

The photovoltaic example applies the convergence and rate analysis to a model with a global power peak and an inferior local peak. Its simulations show a conservative low-dimensional bound and a high-dimensional empirical distribution close to the Weibull limit.

B. Photovoltaic example and convergence rates

  • For the photovoltaic model, the global peak is 100 W with L(θ∗) = 0, while the inferior local peak is 95 W.Minimizing the loss is equivalent to maximizing total power.Source: B. Photovoltaic example and… · p. 5
  • With γ = 2, µ = a = 1, and η0 = 1/4, the model satisfies A1–A4 and the estimate converges almost surely to θ∗.The stated setup uses k0 = 1, initial estimate −θ∗, and c = 3.Source: B. Photovoltaic example and… · p. 5
  • For 0 < η < 1/4, the sublevel set {L < η} is a ball of radius √η centered at θ∗ and contained in Θ.On this ball, the sampling probability is η^p/2 and L(θ) = ∥θ − θ∗∥², yielding γ = 2, µ = a = 1, and η0 = 1/4.Source: B. Photovoltaic example and… · pp. 5–6
  • For p = 2, Fig. 2 compares the median normalized suboptimality gap with the asymptotic upper bound 0.6, which the caption describes as conservative.The simulations use 512 independent replications per dimension.Source: Figure 2 · p. 6, B. Photovoltaic example and… · p. 6
  • At p = 6 and k = 10^6, the scaled-gap median is 0.84 versus the Weibull limit median of 0.885, with maximum empirical-CDF distance 0.057.The high-dimensional suboptimality gap decreases as k^-1/3, and the distance to the minimizer as k^-1/6.Source: B. Photovoltaic example and… · p. 6, Figure 2 · p. 6

V. Conclusions

The paper extends blind random search to noisy loss measurements by combining running averages with a decreasing acceptance threshold. Under the stated assumptions, the algorithm converges almost surely to the global minimizer, with different rate results for low and high dimensions.

V. Conclusions

  • The algorithm combines running averages of noisy loss measurements with a decreasing acceptance threshold and converges almost surely to the global minimizer.The paper proposes exploring this combination in local random search and simulated annealing as future work.Source: §V · p. 6
  • High dimensions yield a Weibull limit for the normalized suboptimality gap, while low dimensions yield an almost sure asymptotic upper bound that decreases to zero.The paper says these rates help engineers assess the algorithm’s asymptotic convergence speed.Source: §V · p. 6

Related papers

Loading 2610.33302v1…