Jump to text
On this page
Copy and source
Published source confirmed at last check

Source changed 2026-11-18 22:51:26 UTC · snapshot created 2026-11-18 22:54:45 UTC · last check 2026-11-18 22:54:38 UTC

CMP.6:4.3 - Make the finite update admissible and useful

For discrete replacements, compute the whole finite difference when it is affordable. Apply only changes that retain the required constraints, or pair the change with a specified repair whose effect is included in the comparison.

For a direction d, construct x'=x+η*d with step size η. The local information must support that finite change. A known upper model can determine a suitable step; otherwise a trial-and-reduction rule can search for a step whose observed effect supports acceptance. Include every trial evaluation in the cost.

For example, suppose a differentiable minimizing objective satisfies

J(x+s)≤J(x)+grad J(x)·s+(L/2)*||s||²

on the relevant region, with known L>0. Choosing s=-grad J(x)/L gives

J(x+s)≤J(x)-||grad J(x)||²/(2L).

This derives a finite descent step from a bound on the local model’s error. When that bound is unavailable, an adaptive step rule needs its own termination or acceptance conditions. One unsuccessful trial can justify reducing or changing the step; it does not establish that the direction never helps.

For constrained problems, use an admissible parameterization, projection or other constraint-preserving update. Reestablish the progress account for that update. Simply clipping a coordinate can change the original unconstrained argument.

With noisy feedback, first choose what the next action must establish. A comparison of two fixed candidates can support accepting a particular change; a noisy direction can instead support progress in expectation over a sequence. These require different constructions. Repeating a measurement or taking a larger sample is useful only when the additional information changes the step or its warranted use. A deterministic monotone-descent statement cannot be inferred from a noisy sign alone.

CMP.6:4.3.1 - Decide a proposed change from uncertain comparisons

For minimization, fix the current candidate x and one admissible proposal y while collecting evidence about Delta=J(y)-J(x). Construct observations whose mean is that difference. For example, if J(x)=E[l(x,Z)] and both candidates can be evaluated on a fresh case Z, use Y=l(y,Z)-l(x,Z). This paired difference retains the same target; its variance can differ from that of two independently estimated means. An observation of only the chosen action’s consequence does not supply the unchosen value: obtain a compatible observation or estimation procedure before using this construction. MMP.7 supplies a missing account of the observation law.

Use CMP.9 to obtain an interval [a_n,b_n] for Delta with the error guarantee needed by the decision. For a fixed sample count, use its fixed-count construction. For repeated inspection, use its simultaneous intervals or another bound valid at the chosen stopping time. Known bounds on Y, independence and a stable target are conditions of that particular construction, not conclusions obtained from the sample itself.

Choose a useful decrease threshold tau >= 0 before inspecting the comparison. Accept y when b_n < -tau; on the interval’s coverage event, this establishes J(y)<J(x)-tau. If a_n >= -tau, this comparison rules out a decrease greater than tau. Otherwise it is unresolved: obtain further information when worthwhile, try another proposal, or retain x with that unresolved comparison. A time limit supplies a finite return without pretending that an inconclusive test rejected the proposal.

Repeated adaptation needs error control across comparisons as well as within each comparison. Number proposed comparisons j=1,2,…, assign failure budgets delta_j=delta/(j*(j+1)), and let CMP.9 construct a simultaneous interval using delta_j for each. Choose that comparison’s candidates from the earlier history, then collect fresh observations satisfying its stated law conditional on that history. The conditional failure bound is at most delta_j; summing these bounds gives probability at least 1-delta that all comparisons used in the adaptive sequence are covered. Reusing observations to select the proposal and then treating them as fresh comparison evidence needs a different valid argument.

On this joint event, every accepted move decreases the same J. A finite candidate set cannot revisit a candidate through such moves. This does not guarantee that each noisy comparison resolves in finite time, especially at equality. A tau-local conclusion additionally needs every neighbor’s comparison to rule out a decrease greater than tau at the returned candidate, or a bound covering the remaining neighbors. Without that coverage, return an improved candidate and the unresolved alternatives. A changed objective, admissible set or feedback law reopens the affected comparisons.

CMP.6:4.3.2 - Construct progress from a noisy direction

When checking each move costs too much, a stochastic update can trade that per-move claim for an expected result. Derive the trade-off from the information supplied. Consider an unconstrained differentiable J with the upper model above and a lower bound J_low. Let H_t denote all information available before drawing feedback at iteration t, including x_t. Suppose an obtainable gradient estimate g_t satisfies

E[g_t | H_t]=grad J(x_t) and E[||g_t-grad J(x_t)||^2 | H_t] <= v.

The first condition concerns the current candidate and its history; an estimate unbiased only before adaptive selection is insufficient. Derive the conditions from the feedback mechanism or use a justified supplier. For example, uniform independent sampling of component gradients from a fixed finite average has the required mean. For an expected loss, interchanging differentiation and expectation needs its own conditions. An empirical variance is not automatically a valid bound v.

Choose a fixed step 0<eta<=1/L and compute x_(t+1)=x_t-eta*g_t. Substituting this step into the upper model and taking conditional expectations gives

E[J(x_(t+1)) | H_t] <= J(x_t) - eta*||grad J(x_t)||^2 + (L*eta^2/2)*E[||g_t||^2 | H_t]

<= J(x_t) - (eta/2)*||grad J(x_t)||^2 + (L*eta^2/2)*v.

Here E[||g_t||^2 | H_t] <= ||grad J(x_t)||^2+v; the zero conditional mean of the error removes its cross term. The term involving v allows for noise in the descent estimate. A realized update can increase J, and the displayed bound need not certify expected decrease close to a stationary point.

For T such updates, sum the inequalities and use the lower bound. With a known D >= J(x_0)-J_low, the result is

(1/T)*sum_(t=0)^(T-1) E[||grad J(x_t)||^2] <= 2*D/(eta*T) + L*eta*v.

This is a finite stationarity result, not a global-optimum or distance-error guarantee. For a positive epsilon, to request an expected squared gradient norm at most epsilon^2, choose eta<=1/L and, when v>0, eta<=epsilon^2/(2*L*v); choose an integer T>=max(1,4*D/(eta*epsilon^2)). Return x_R for an index R chosen uniformly from 0,…,T-1 independently of the update randomness. Its expected squared gradient norm equals the average bounded above. CMP.9’s reservoir construction can retain one such iterate without storing the whole trajectory. Selecting the last iterate or the smallest noisy observation does not inherit this particular bound.

If b conditionally independent estimates at the same current candidate each have the stated conditional mean and error second moment at most sigma^2, their average has v<=sigma^2/b. Compare a smaller step and more iterations with a larger batch and its extra work; count all Tb gradient observations, not only updates. A batch chosen adaptively using its own observed errors needs an argument preserving the assumed mean and second-moment bound. Known L, D and v give the displayed budget; if they are unavailable, this formula does not invent them. Use a qualified estimate for an exploratory run, a supported bound, or the comparison route above according to the receiving claim.

A constraint-preserving parameterization can make this construction applicable to its unconstrained parameters, with J and L expressed there. Arbitrary clipping or projection does not preserve the displayed derivation; use the corresponding constrained progress result. If feedback has a conditional bias, retain its extra inner-product term in the first inequality or repair the estimator. More samples of the same biased signal do not restore the omitted zero-mean condition.