CMP.6 - Derive an Iterative Computational Update from Local Information

Type: Method Status: Usable, evolving Normativity: Normative

CMP.6:1 - Problem frame

Use this when a desired result is hard to construct directly, but the current candidate reveals a computable improvement: a beneficial local replacement, a derivative, a violated condition or feedback about a proposed change. You need to turn that information into an update rule and determine what repeated updates can establish.

This is an algorithmic design problem. It occurs in discrete local search, iterative equation solving, optimization and learning procedures. The input need not be numerical: swapping two choices or changing one symbol can be the available operation. The difficulty is connecting an accessible local signal to a useful change of the whole candidate.

The gain is an executable update, an appropriate step or acceptance rule, and a stopping or progress account suited to the requested result. The reader needs to follow the candidate’s admissible changes and comparisons. Differentiation is a prerequisite only for the derivative-based branch; MATH.10 supplies the corresponding mathematical variation.

Use a direct construction when it already gives the required result affordably. An existing iterative method can also be used directly when its hypotheses fit. This pattern is needed when the update or its justification must be constructed or changed.

CMP.6:2 - Problem

How can local information generate an admissible sequence of computational changes with a justified improvement or termination claim, without confusing local progress, convergence and the original objective?

A direction that improves an infinitesimal model may fail at a finite step. A locally unchangeable candidate may still be globally poor. An indefinitely improving sequence may never return the finite answer its recipient needs.

CMP.6:3 - Forces

CMP.6:4 - Solution

Choose the comparison → construct the available changes → derive a useful update → control its extent → establish progress → return the result at its supported scope.

CMP.6:4.1 - State the candidate, criterion and wanted conclusion

Describe the current candidate x, its admissible set and the result wanted. A criterion J(x) can measure an objective, a residual or a potential used to establish progress. State which it is. A potential that decreases helps analyze the algorithm; its relation to the recipient’s requested answer still needs to be established.

Separate possible conclusions: one improved candidate, no improving change in a specified neighborhood, a point meeting a residual tolerance, a global optimum, or a sequence converging under stated conditions. Select the useful conclusion now rather than automatically pursuing the strongest one.

When the iteration serves a model or learner, retain its target through C.29.2 and the relevant modeling or learning method. Optimization error, error in the subject model and performance on later cases are different questions.

CMP.6:4.2 - Construct local changes and their obtainable consequences

Specify what may change at one step. Examples include flipping one binary choice, exchanging two assignments, updating a coordinate, adding a vector direction or replacing a violated part of a construction. MATH.10 supplies the comparison under admissible variation; the present task is to obtain a useful change by a finite computation.

Determine what information is available about a proposed change:

• a directly computed difference in J;
• a local approximation, such as a derivative or a small model of the objective;
• a response or estimate obtained from samples or feedback.

Choose a procedure that uses this information. A discrete local search can examine neighbor changes and select one with positive gain. A smooth minimization can use a negative gradient. A coordinate method can solve a smaller update problem while holding other coordinates fixed. A residual correction needs a relation showing how that correction changes the residual or another progress measure.

If obtaining the direction calls another hard problem, include its algorithm and cost or accept an approximate direction with an appropriate result condition. Writing an argmin expression identifies the desired update; it does not automatically supply an algorithm for obtaining it.

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, distinguish realized change from a conditional or expected improvement claim. 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.4 - Establish what repeated updates imply

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

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.

CMP.6:4.5 - Choose a stopping test that supports the receiving answer

Derive the test from the wanted conclusion. Exhausting a discrete neighborhood establishes local optimality for that neighborhood. A residual threshold answers a residual question; a condition or error bound is needed to convert it into distance from a solution. Small successive changes can result from a tiny step even while the candidate remains poor.

For a constrained optimum, the full gradient need not vanish. Use the absence of a feasible improving variation, a suitable projected update or the relevant constrained condition. Report that condition at the scope it establishes.

When time runs out, return the best admissible candidate or current approximation together with any supported bound. A tolerance or resource limit belongs to the use that needs the result.

CMP.6:4.6 - Revisit the source of a failed improvement

When the step fails, locate whether the direction, extent, feasibility repair, feedback or assumed relation to the objective changed. Revise that part. If local moves repeatedly stop at unsatisfactory candidates, enlarge or change the neighborhood, restart from another candidate, use CMP.4 to explore alternatives or obtain a bound through CMP.5.

Compare alternatives by the quality and cost relevant to the receiving use, using the existing characterization and improvement methods. Faster iteration is valuable only in relation to the result it obtains.

CMP.6:5 - Archetypal Grounding

CMP.6:5.1 - Construct a discrete local-improvement algorithm

Partition the vertices of an undirected graph into two groups to maximize the total nonnegative weight of edges crossing between groups. Start with any partition. At a vertex v, let I(v) be the weight of its edges to vertices in the same group and C(v) the weight to vertices in the other group. Flipping v changes the cut value by I(v)-C(v).

Compute these differences and flip a vertex whenever its difference is positive. Each flip is an admissible partition change and strictly increases the criterion. Because there are finitely many partitions, the algorithm eventually reaches one with I(v)≤C(v) at every vertex.

At this stopping state, C(v) is at least half the incident weight at v. Summing over vertices counts every cut edge twice, so the cut value is at least half the total graph weight. The total graph weight bounds any cut, giving a factor-two bound relative to the maximum cut. This is a property derived from the chosen neighborhood and nonnegative weights, rather than an assertion that every local optimum is globally optimal.

For a four-cycle with unit weights, start with all vertices in one group. Flipping vertex 1 produces a cut of value 2. Flipping the opposite vertex 3 produces value 4, which is optimal because all four edges cross. Only incident edges need updating after each flip. Finite termination alone does not make the general algorithm polynomial in the encoded input size; the number and cost of flips require a further account.

Changed condition: allow negative edge weights. Take four vertices with weights -3 on edges 1-2 and 3-4, and weight 1 on the four edges between those pairs. With all vertices in one group, each single flip changes the cut by -1, so the algorithm stops at value 0. Moving the pair {1,2} together to the other group produces value 4. Finite termination survives, but the former factor-two guarantee fails. A two-vertex neighborhood opens an improving move; its cost and eventual quality need their own comparison.

CMP.6:5.2 - Derive a step and change its constrained stopping condition

Minimize J(x)=(x-3)² over real x. Its derivative is 2(x-3). The update x'=x-2η(x-3) multiplies the error x-3 by 1-2η. Thus 0<η<1 contracts its magnitude; with η=1, the error oscillates without decreasing.

Choose η=1/4. From x=0, the iterates are 1.5, 2.25, 2.625, ...; the objective values are 9/4, 9/16, 9/64, .... After k steps from the initial point, the distance to 3 is 3/2^k. A requested distance at most epsilon therefore has a directly computable iteration bound. This example establishes the update through its algebra rather than through a generic instruction to repeat until the values seem stable.

Changed constraint: require 0≤x≤1. Projection of the same proposed first step onto this interval gives x=1. Further projected steps remain at 1. The derivative there is -4, so a full-gradient-zero stopping test would never recognize the constrained optimum. Every feasible point in the interval has J(x)≥4=J(1), establishing the result. The changed feasible set requires a changed stopping argument, even though a related update can still be used.

CMP.6:6 - Bias-Annotation

A familiar update formula can displace the question of which local information is actually available. A gradient-based method, for example, needs a computable gradient or a justified estimate; a symbolic derivative on paper can still leave costly evaluation.

Visible improvement can also be mistaken for sufficient progress. Retain the relation between the improved criterion and the requested result, including the distinction between a finite-state termination argument and an affordable run.

CMP.6:7 - Conformance Checklist

• The candidate, admissible changes, comparison criterion and requested conclusion are stated.
• The local information and the operation obtaining an update are available under the stated inputs.
• The finite step or replacement has the required feasibility and improvement account.
• Repetition has the claimed termination, convergence or limited progress conditions.
• The stopping test supports the wanted answer rather than merely detecting small changes.
• The cost comparison includes direction construction, trials, state updates and consequential arithmetic or information costs.
• A changed condition is followed through the update and its result claim before reuse.

CMP.6:8 - Common Anti-Patterns and How to Avoid Them

CMP.6:9 - Consequences

The designer obtains a rule that makes a next computational change from available information and can explain what repeated use achieves. The method connects discrete improvement, continuous optimization and feedback-driven updates through their progress arguments without identifying their different guarantees.

It can also reveal that the available local information is insufficient. A new neighborhood, stronger model, additional observation or different algorithm may be required. The explicit failure locus makes that revision smaller than replacing the entire computational formulation.

CMP.6:10 - Architectural Rationale

Update construction, finite-step control and stopping belong together because each changes what the algorithm can return. MATH.10 derives conditions from variations and MATH.21 constructs objects through convergence. CMP.6 supplies the effective rule, its repeated execution and the finite answer required from it.

CMP.5 can furnish a bound or an easier update subproblem; CMP.4 explores alternative candidates. CMP.7 can use the update to construct a learner, while keeping optimization progress distinct from performance on further cases. These are complementary algorithmic methods rather than one universal optimizer.

CMP.6:11 - SoTA-Echoing

Williamson and Shmoys, The Design of Approximation Algorithms, chapter 2 and later local-search constructions, derives global comparisons from specified local neighborhoods. Adopt that style of argument rather than equating local improvement with global success. The cut example makes the neighborhood and nonnegative-weight assumption explicit; a more powerful neighborhood can require more work per update.

Bottou, Curtis and Nocedal, Optimization Methods for Large-Scale Machine Learning develops obtaining procedures, step control and the distinction among optimization and statistical errors. Adopt the error-bound-to-update construction and the accounting for inexact information. Its smooth and stochastic analyses have stated assumptions; they do not govern every discrete or learned update.

For the smooth branch, compare a preset step with the upper-model or trial-controlled construction in :4.3 using the same available objective and derivative operations. A known useful L makes the derived step inexpensive; without that information, trial control spends extra evaluations to avoid an unsupported finite step. The quadratic case exhibits a concrete failure of a preset value. Retain a fixed step when its bound already supports the required result; choose trial control when its information gain warrants those evaluations. Under noisy feedback, that deterministic comparison must be replaced by the corresponding stochastic conditions.

For a finite discrete neighborhood, direct gain calculation may be simpler than fitting a continuous model. The cut example derives both update and guarantee from those discrete gains. Revisit the chosen direction, acceptance or stopping rule when feedback, admissible moves or a required progress bound changes, or when another construction obtains the same required result at lower total cost.

CMP.6:12 - Relations

• C.29.2: states the obtaining task, operations and resource conditions.
• MATH.10: constructs admissible variations; MATH.20 supplies bounds; MATH.21 supplies convergence and finite-approximation reasoning.
• CMP.4 and CMP.5: can provide alternative exploration, a relaxed update problem or a useful comparison bound.
• CMP.7: uses updates in a learning algorithm while retaining a separate account of further-case performance.
• C.11.DUA and the general improvement methods: select the value of additional computation, information or a more costly update.

CMP.6:End