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

Source changed 2026-11-18 21:11:39 UTC · snapshot created 2026-11-18 21:12:35 UTC · last check 2026-11-18 22:45:10 UTC

CMP.6:4.4 - Establish what repeated updates imply

Select a progress argument appropriate to the state space and update:

Available structureWhat can be establishedWhat remains to be supplied
A finite candidate set and strict improvement at every accepted changeAccepted changes cannot revisit a candidate, so only finitely many can occur.A terminating way to find or rule out the next improving change, and a useful bound on the search cost.
A decreasing nonnegative integer potentialAt most its initial value many decreases of at least one.The potential’s encoded magnitude can be large, and one iteration may be expensive.
A contraction or another quantitative convergence relationA finite error bound after a chosen number of updates.A way to compute the required update and connect that error to the requested result.
A descent estimate with a bounded-below objectiveBounds on accumulated improvement and, under appropriate assumptions, stationarity measures.Convergence to one point or global optimality requires its own additional conditions.
A conditional mean and second-moment bound for a noisy direction, with the smooth upper modelThe finite expected stationarity bound in :4.3.2.A warranted feedback law, admissible updates, step and sampling cost, and the stated output selection.

Use MATH.20 for the bound and MATH.21 for the convergence construction when needed. If each step improves but there is no useful stopping guarantee, return that limited procedure or change the method. Equal-value moves need their own cycle handling; strict-improvement reasoning does not cover them.