Sampling Bias and Convergence Conditions in Markov-Chain Optimization

How scenario visit frequencies determine the optimization direction, why one-step Markov samples are biased, and which cumulative-error bound yields convergence.

When a Markov chain selects scenarios for optimization, its stationary distribution determines the average direction being computed. To give high-cost scenarios more weight, one can design the chain to visit them more often. Having the desired stationary distribution does not, by itself, guarantee that a short run produces that average. If the design changes at every iteration, the accumulated effect of sampling bias also needs analysis.

1. Scenario visit frequencies and the average subgradient

Suppose a design x determines an investment cost f(x) and scenario operating costs Qi(x). There are m scenarios. To emphasize expensive scenarios, use the mellowmax objective at a fixed temperature w > 0:

Fw(x)=f(x)+Mw(x)Mw(x)=wlog(1m∑i=1mexp(Qi(x)w))

Here w is the temperature that divides cost. Assume the feasible design set X is nonempty, closed, and convex, and that f and each Qi are finite convex functions on a neighborhood of X, with the subgradients used below well defined. Mellowmax approximates the maximum scenario cost.

Let gf(x) and gi(x) be subgradients of investment and operating cost. Then

px(i)=exp(Qi(x)w)∑jexp(Qj(x)w)gw(x)=gf(x)+∑ipx(i)gi(x)∈∂Fw(x)

Evaluating every scenario may be expensive, which motivates using only the subgradient of a visited scenario. The frequency of those visits then determines the average direction.

Consider two scenarios at the current design. In this example, x is scalar and the investment-cost gradient is omitted.

Scenario Operating cost Gradient with respect to design
1 30 −10
2 10 +10

With w = 10, the desired weights and average direction are

px(1)=exp(3)exp(3)+exp(1)≈0.881,px(2)≈0.119gw(x)≈0.881(−10)+0.119(10)≈−7.62

An update in the negative-gradient direction increases x, locally reducing the cost of scenario 1, which currently has the higher cost.

Uniform sampling without reweighting gives

0.5(−10)+0.5(10)=0

so the two gradients cancel. More iterations estimate this different average more accurately; they do not recover the desired weighted sum.

At a fixed x, if the chain’s long-run visit frequencies are about 88.1% for scenario 1 and 11.9% for scenario 2, the simple average of visited gradients approaches −7.62. Visit frequency implements the weighting. For a Metropolis chain, iterations that reject a proposed move and remain in the same scenario must also be counted.

2. Stationary distributions and mixing rates

Write Px for the transition matrix at the current design. The stationarity condition is

pxPx=px

Starting with a scenario distributed according to px, one transition preserves that distribution. Whether a chain started from an arbitrary scenario approaches it is a separate question.

For example, if the transition matrix is the identity,

Px=I

the chain stays in its initial scenario forever. Every distribution is stationary, but a path trapped in one scenario cannot compute the desired weighted average.

Property to check What it establishes
px is stationary The transition preserves the target weights.
Irreducibility and other convergence conditions Long-run visit frequencies approach the target independently of the initial scenario.
Mixing rate How close the current-state distribution gets to the target within a finite number of transitions.

On a finite state space, irreducibility supports convergence of time averages along a sample path. Convergence of the state distribution at each time also requires aperiodicity. See Levin and Peres, Markov Chains and Mixing Times, Theorem 4.9 and Appendix C, for this distinction.

Updating the design also moves the target distribution px.

3. Design updates and tracking a changing distribution

A direct approach fixes x, runs the chain long enough to estimate the average subgradient, and then updates the design. Repeating this process after every design change can be expensive. An alternative alternates one scenario transition with one design update:

In+1∼Pxn(In,·)xn+1=ΠX[xn−αn+1(gf(xn)+gIn+1(xn))]

The first line makes one transition from the current scenario. The second updates the design using the visited scenario’s subgradient. The projection returns the result to X in Euclidean distance. The next iteration continues from the scenario just visited.

The scenario location is carried forward. Its old operating cost is not automatically valid: after the design changes, acceptance probabilities must use costs evaluated at the current design. One transition may require solving the operating problems for both the proposed and current scenarios.

Suppose the previous search was already close to its target distribution:

pxn=(0.88,0.12),pxn+1=(0.85,0.15)pxn+1=(0.12,0.88)

In the first line, a change from (0.88, 0.12) to (0.85, 0.15) leaves the previous search state a useful starting point. In the second line, the target flips to (0.12, 0.88), making the previously frequent scenario less important. Until the chain adapts, it may supply directions that poorly reflect the current design.

The chain’s speed of adaptation must therefore be considered together with the speed at which design updates move the target. If sampled subgradients are bounded by B and xn belongs to X, nonexpansiveness of projection gives

Zn+1:=gf(xn)+gIn+1(xn),‖Zn+1‖≤B‖xn+1−xn‖≤αn+1B

Smaller stepsizes limit design movement. At fixed w, a common Lipschitz bound on the operating costs also lets us control changes in the softmax weights through changes in the design. A small stepsize alone does not guarantee adequate tracking; the transition’s mixing properties must also be checked.

After a single transition, In+1 is generally not an exact draw from pxn. Thus Zn+1 cannot be treated as a conditionally unbiased SGD estimator. Convergence analysis must control how this discrepancy affects the whole sequence of updates.

4. Distance bounds with sampling error

Assume a minimizer exists at the fixed w and choose a comparison point:

x⋆∈argminx∈XFw(x),Fw⋆:=Fw(x⋆)

Euclidean projection gives the one-step inequality

‖xn+1−x⋆‖2≤‖xn−αn+1Zn+1−x⋆‖2=‖xn−x⋆‖2−2αn+1Zn+1⊤(xn−x⋆)+αn+12‖Zn+1‖2

A sufficiently positive inner product in the middle term contributes to reducing squared distance. With an exact subgradient, convexity directly connects that inner product to the objective gap:

zn∈∂Fw(xn)zn⊤(xn−x⋆)≥Fw(xn)−Fw⋆

The actual Zn+1 contains information from only one scenario, so this inequality cannot be applied to it directly. Define a scenario-specific cost difference

ri(x):=Qi(x)−Qi(x⋆)

An individual ri(x) may be negative because x⋆ need not minimize every scenario separately. Define the sampling error as the visited scenario’s cost difference minus its average under the target distribution:

en+1:=rIn+1(xn)−∑ipxn(i)ri(xn)

If In+1 were drawn exactly from pxn conditional on the history, this error would have zero conditional mean. For one Markov transition, writing ℱ for the history gives, in general,

𝔼[en+1|ℱn]=∑i(Pxn(In,i)−pxn(i))ri(xn)≠0

This conditional mean depends on the history and can be zero. The sampling error is a scalar defined from cost differences.

Convexity of the investment and scenario costs gives

Zn+1⊤(xn−x⋆)≥f(xn)−f(x⋆)+rIn+1(xn)

Viewed as a convex function of the cost vector, mellowmax has gradient px. Its supporting-hyperplane inequality at the current cost vector yields

∑ipx(i)[Qi(x)−Qi(x⋆)]≥Mw(x)−Mw(x⋆)

The weighted cost difference upper-bounds the difference in mellowmax values, allowing it to be combined with the preceding scenario-wise lower bound. For log-sum-exp convexity and the supporting-hyperplane inequality, see Boyd and Vandenberghe, Convex Optimization, Chapter 3.

Substituting the definition of the sampling error gives

Zn+1⊤(xn−x⋆)≥Fw(xn)−Fw⋆+en+1

A large negative en+1 means the visited scenario reports a smaller cost difference than the target-weighted average. This weakens the lower bound supporting distance reduction.

5. Bounding cumulative sampling error

Insert the inner-product lower bound and the bound B on Zn+1 into the distance inequality:

Dn:=‖xn−x⋆‖22αn+1[Fw(xn)−Fw⋆]≤Dn−Dn+1+αn+12B2−2αn+1en+1

The right side contains the reduction in squared distance, a quadratic term from taking a finite step, and the contribution of sampling error. Summing over iterations telescopes the distance terms:

∑n=0N−1(Dn−Dn+1)=D0−DN≤D0

For a fixed initial design, taking expectations gives

2∑n=0N−1αn+1𝔼[Fw(xn)−Fw⋆]≤D0+B2∑n=0N−1αn+12+𝔼[−2∑n=0N−1αn+1en+1]

Each en+1 need not be zero. It is enough to bound the final cumulative-error term so that it grows sufficiently slowly relative to the sum of stepsizes.

For example, suppose one can prove that finite nonnegative constants C0 and C1, independent of N, satisfy

𝔼[−2∑n=0N−1αn+1en+1]≤C0+C1∑n=0N−1αn+12

Proving this bound requires conditions on mixing of the design-dependent transitions, regularity with respect to design changes, and the stepsizes. The constants may depend on the fixed w, the problem, and the chain.

A Poisson-equation decomposition is one way to obtain such a bound. It expresses the centered cost differences through an equation involving the transition operator, then uses bounds and regularity of its solution to control the cumulative error.

6. Expected objective error of the averaged design

Define the stepsize-weighted average of the pre-update designs:

x¯N:=∑n=0N−1αn+1xn∑n=0N−1αn+1

Positive stepsizes and convexity of X keep this average feasible. Convexity of Fw, together with the cumulative-error bound, gives

𝔼[Fw(x¯N)]−Fw⋆≤D0+C0+(B2+C1)∑n=0N−1αn+122∑n=0N−1αn+1

We can now compare the growth of the numerator and denominator. For example,

αn+1=an+1,a>0∑n=0N−1αn+1≍N,∑n=0N−1αn+12≍logN

where ≍ denotes the same order of growth in N. Holding w and the associated constants fixed yields

𝔼[Fw(x¯N)]−Fw⋆=O(logNN)→0

This rate applies to the expected objective error of the averaged design at a fixed temperature. It does not establish cost reduction at each iteration or convergence of the last design itself. Approximation error relative to the original maximum-cost problem, and changes in mixing as w decreases, require separate analysis.