CMP.6:4.4 - Establish what repeated updates imply
Select a progress argument appropriate to the state space and update:
| Available structure | What can be established | What remains to be supplied |
|---|---|---|
| A finite candidate set and strict improvement at every accepted change | Accepted 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 potential | At 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 relation | A 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 objective | Bounds 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 model | The 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.