Part A - Construct an algorithm
CMP.1 - Solve One Problem through Another or Transfer a Limit (Computational Reduction)
Type: Method Status: Stable Normativity: Normative
CMP.1:1 - Problem frame
Use this pattern when an unfamiliar computational problem might be solved through another problem, or when you need to determine what an assumed solver would make possible. The useful connection must turn admitted inputs into usable queries and recover the answer required by the original question.
Start by naming the problem to be answered and the problem whose solver will be used. Construct a conversion on one revealing input and say how each possible solver answer returns to the first problem. A working conversion, a failed return condition or a correctly directed impossibility consequence is a useful first result.
A computational reduction from A to B is an effective way to solve A using a solver for B. The single-query reduction below constructs a query and an answer-recovery procedure; an adaptive reduction can choose its next query from an earlier answer. The reader needs elementary algorithms, finite representations, function composition and arguments about termination. The graph example explains its representation and assumes a suitable shortest-path solver. The undecidability example uses the stated halting result as a mathematical premise.
Use an available solver directly when its admitted inputs and answers already fit the question. C.29.2 supplies ordinary computational formulation. The present method develops the missing reduction and what follows from it. Approximate, randomized or physically realized computations require the corresponding answer and resource guarantees when they enter this connection.
CMP.1:2 - Problem
Two problems can have similar names or output shapes while admitting different inputs or requiring different guarantees. A conversion can lose the distinction that determines the answer, create a target input outside the solver’s domain, or leave no effective way to recover the original output.
A reduction can also be used backwards. Solving A through B supplies an A-solver when B is solvable; a known impossibility for A then constrains B. Reversing that implication can rule out a useful algorithm without justification.
The task is to construct the connection, establish its answer relation and effective execution, and carry only the consequence that its direction and resource conditions support.
CMP.1:3 - Forces
| Force | Tension |
|---|---|
| Reusing a solver and preserving the question | The solver may answer a translated problem while the original output or a negative case remains unresolved. |
| Mathematical definition and effective construction | A conversion can be well defined while computing it requires the answer being sought. |
| Computability and resource use | An effective reduction can create instances too large for the intended budget. |
| General limit and restricted use | A universal impossibility can coexist with algorithms for a narrower input class or a weaker answer. |
CMP.1:4 - Solution
Local mantra: specify both answers; construct the queries; recover every relevant answer; establish direction and cost; use the consequence; revise the changed condition.
CMP.1:4.1 - Specify the two problems and the intended conclusion
Call A the problem to be answered through B. State each problem’s admitted inputs and required outputs. An output might be a value, a satisfying witness, a decision including negative cases, or an approximation with a stated guarantee. Choose the forms needed.
For a decision problem, write A(x) for the proposition to be decided on input x. A solver must return a correct yes or no and terminate on every admitted input. If a proposed procedure only eventually confirms positive cases, retain that different capability in the problem statement.
For a witness problem, let Ans_A(x,y) mean that y is an acceptable answer for x. Specify what the procedure should do when no witness exists if that case is admitted. Use C.29.2 when the answer, representation or available elementary operations still need formulation.
Name the intended use of the reduction: build an algorithm from an available solver, transfer a known impossibility, or derive a resource consequence. This selects what effectiveness, return and cost arguments are needed.
CMP.1:4.2 - Construct a query from the available input and operations
Build a terminating procedure f that maps each admitted A-input x to an admitted B-input f(x). Work from the information present in x and the operations available to the conversion.
A useful way to begin is to identify what a B-instance must represent about x. Construct its components and relations, then retain any additional information needed for answer recovery. When the input contains a program, a conversion can assemble a new program description with that program embedded in it. Constructing the description and executing the embedded program are different operations.
Check the solver’s input conditions. A graph procedure accepting only nonnegative edge weights cannot be used unchanged when the conversion creates negative edges. A procedure specified for finite explicit inputs needs a suitable finite representation.
If producing f(x) assumes an answer to A(x) that the available operations do not obtain, the proposed conversion has not supplied the reduction. Replace that assumption with an effective construction from the available input, or retain it as the unresolved computational contribution. When obtaining the answer during conversion is effective, include that work in the cost and usefulness comparison.
CMP.1:4.3 - Construct answer recovery and establish correctness
For a single-query witness reduction, give a recovery procedure r(x,z). For every admitted x and every answer z the B-solver is permitted to return, establish:
Ans_B(f(x),z) implies Ans_A(x,r(x,z)).
The recovery must terminate under those conditions. Include negative outcomes, failure reports or approximation bounds when the A-contract needs them. A single fortunate B-answer is insufficient if the solver may validly return another answer that the recovery cannot use.
For a yes/no-preserving decision reduction, establish both directions:
A(x) iff B(f(x)).
Then the B-answer is the A-answer. If recovery reverses or otherwise changes the returned answer, state that rule and prove the resulting correspondence. For example, one positive implication alone leaves the no branch undecided.
When several queries are needed, construct the calling algorithm. State how a returned answer determines the next query and retained state, why every query is admitted, and why correct target answers lead to termination with the required A-answer. An adaptive reduction is a procedure using the solver, rather than one fixed input map.
Compose reductions by composing their conversions and recovery procedures. Intermediate answers must satisfy the next procedure’s conditions. MATH.17 and MATH.18 support the mathematical composition and interpretation questions; the present work additionally establishes effective execution under the selected computational model.
CMP.1:4.4 - Follow the direction of the consequence
For an established reduction from A to B:
- A suitable B-solver, together with the reduction, gives a suitable A-solver.
- If no such A-solver can exist under the stated model and guarantee, no B-solver with the assumed capability can exist.
Write the constructed A-procedure before using the second conclusion. It shows what the assumed B-solver would enable and where the contradiction arises.
Keep the scope of a limit. An impossibility for a total decision procedure on an unrestricted input class leaves other questions open: positive-case recognition, bounded execution, a restricted class, or a different computational model. Choose an alternative only when it supplies a useful answer for the work. The finite-state return in :5.2 shows such a change.
For a complexity consequence, use a reduction with the required resource bound. An unboundedly expensive input conversion supplies no efficient A-algorithm merely because B has one.
CMP.1:4.5 - Derive the cost that can change the choice
When cost matters, include input conversion, query size, solver calls and answer recovery under a named computational model. If conversion costs T_f(n), its output has size at most m(n), B costs T_B(m(n)), and recovery costs T_r(n,m(n)) including the returned answer size relevant to it, the one-query construction has the corresponding total bound:
T_A(n) <= T_f(n)+T_B(m(n))+T_r(n,m(n)).
If the answer size is not bounded through these arguments, include it explicitly. For several queries, sum the costs of their construction, calls and recovery, including any adaptive work between calls. Analyze peak simultaneous storage separately from total work.
The representation matters. A quantity written with n bits can have a value exponential in n; enumerating that many states changes the cost claim. Exact rational operations also have costs depending on operand length when bit complexity is the model.
Use the result to choose or reject the reduction for the current resources. Another solver, a smaller representation or a different computational construction can preserve the answer while changing cost. C.29.2 supplies the surrounding resource and accuracy formulation.
CMP.1:4.6 - Return a usable construction or a bounded limit
For solver reuse, return the input construction, solver conditions, recovery and relevant cost. A user should be able to follow an input through to its original answer.
For a limit, return the reduction argument, its computational assumptions and the excluded guarantee. Use that result to revise the question or allocation of work. A failed implementation attempt supplies neither this limit nor a reason to stop searching for a valid reduction.
When the input class, answer guarantee, representation or available solver changes, revisit the affected connection. Retain the earlier consequence for the conditions under which it was established.
CMP.1:5 - Archetypal Grounding
CMP.1:5.1 - Solve difference constraints through a graph problem
The input is a finite set of variables and inequalities of the form:
x_v <= x_u+w(u,v),
with rational weights. The required answer is an assignment satisfying all inequalities or a correct infeasibility report.
Construct a directed graph with one vertex per variable and an edge u to v of weight w(u,v) for each inequality. Add a new source s with a zero-weight edge to every variable vertex. Use a solver that permits negative edge weights and returns either shortest-path distances from s or a reachable negative cycle.
A negative cycle proves infeasibility: sum its inequalities. Every variable cancels, leaving 0 <= sum of cycle weights, which is false for a negative total.
If there is no negative cycle, all vertices are reachable from s and their shortest distances are finite. For every edge, the shortest-path condition gives:
d(v) <= d(u)+w(u,v).
Thus x_v=d(v) recovers a satisfying assignment. This proves the required return for either solver outcome.
For example, take x_b<=x_a+3, x_c<=x_b-2 and x_a<=x_c+1. Distances (d(a),d(b),d(c))=(-1,0,-2) satisfy all three. If the final bound changes to x_a<=x_c-2, the directed cycle has weight 3-2-2=-1 and proves infeasibility.
For n variables and m inequalities, construction adds n+1 vertices and m+n edges. Reading or assembling those lists and copying back an assignment takes O(n+m) operations under the explicit-graph model. Add the selected solver’s cost on that graph and the rational-arithmetic costs appropriate to the representation.
The graph is a computational construction for the given inequalities. If those inequalities describe schedules, flows or another subject, their physical or organizational adequacy is a further modeling question. The reduction has established the answer for the supplied mathematical constraints.
CMP.1:5.2 - An event decider would decide halting
A team asks for a procedure that always decides whether an arbitrary deterministic program with unbounded working memory will eventually emit a designated event. The input is a finite program description, its finite initial data and the event to be recognized. The guarantee includes terminating with “no” for a program that never emits it.
Use the halting problem as A: given a program P and input x, decide whether P(x) terminates. Under the ordinary Turing-computable model, no total algorithm decides this for all programs and inputs.
Construct a program Q with x and P’s description included. Q simulates P on x, suppresses the simulated program’s output, and emits the designated event if and when the simulation halts. The description of Q is obtained by placing the supplied data inside this fixed wrapper; constructing it does not run P(x).
If P(x) halts, Q emits. If P(x) does not halt, Q never reaches its emitting step. A supposed total event-decider applied to Q would therefore decide A in both cases. This contradicts the halting result, so the requested universal event-decider is unavailable under these assumptions.
The direction matters: halting was reduced to event decision. The argument constructed a halting decider from the assumed event decider.
Now change the admitted system to a fully represented deterministic finite-state machine with effective transitions and a decidable emitted-event label on each transition. Starting from its initial state, follow transitions while remembering visited states. Return yes upon the event; return no if the machine halts without it or repeats a state before emitting it. At most the number of reachable states can be visited before such repetition or termination. Determinism and complete state make the future repeat as well.
This supplies a usable decision procedure for the changed class. If an environment can add unrepresented inputs or the “state” omits a changing counter, restore those inputs or state before applying this finite-state result. C.29.2 and A.3.3.TR supply that formulation work. The original universal impossibility and this restricted procedure remain compatible.
CMP.1:5.3 - A small description can create an expensive search
An input describes b Boolean state variables. A conversion that explicitly constructs every possible state may produce 2^b vertices. Even a solver linear in the resulting graph size then gives an exponential dependence on b.
The construction may still be effective and useful for small b. For a larger budget-constrained use, keep the original answer condition and seek a representation or method that avoids explicit expansion, or derive a suitable restriction of reachable states. Include the cost of expanding the input when comparing the complete procedures.
CMP.1:5.4 - Recover a witness through adaptive decision queries
The required answer is the lexicographically least satisfying assignment of a Boolean circuit C on n ordered input bits, or UNSAT. An available solver decides whether a supplied circuit has any satisfying assignment and terminates on either answer.
First query C. A negative answer gives UNSAT. After a positive answer, retain a prefix with a satisfying extension. Try its next bit as 0 and query the circuit with that prefix fixed. Keep 0 if the answer is yes; otherwise keep 1. The retained prefix still has a satisfying extension. After n bit choices it is a complete satisfying assignment; preferring 0 at each position makes it the least one.
For C(a,b,c)=(a or b) and (not a or c), the answers are:
C: yes -> prefix 0: yes -> prefix 00: no -> prefix 010: yes.
The recovered answer is 010. For circuit size N, copying each restricted circuit takes O(N) work. There are at most n+1 calls, giving total work bounded by (n+1)T_B(O(N))+O(nN+n) and sequential-call space O(N+n+S_B(O(N))).
If the solver only recognizes satisfiable inputs and may diverge otherwise, the query at prefix 00 can fail to return. This construction then lacks its required guarantee. Obtain a total decider or use finite enumeration, whose worst-case work is O(2^n N).
CMP.1:6 - Bias-Annotation
The solver’s familiar name can draw attention away from its admitted inputs and returned guarantees. Follow the conversion and recovery, including the negative branch the original problem requires.
An impossibility argument can also be overextended. Keep its input class, computational model and answer guarantee visible, then examine a changed useful question at those same points. A resource estimate is conditional on the representation used.
CMP.1:7 - Conformance Checklist
For the reduction being used:
- Both problems have stated admitted inputs and required answers.
- The conversion is effective from the supplied input and produces admitted queries.
- Every solver outcome relied on by the construction has an effective recovery with the required guarantee.
- The correctness argument covers the needed directions and termination conditions.
- The consequence follows the direction of the constructed solver reuse.
- A resource claim includes conversion, calls, recovery and relevant representation sizes.
- The result supplies an algorithm, a useful restricted alternative or a limit with a specific effect on the next move.
CMP.1:8 - Common Anti-Patterns and How to Avoid Them
Assuming an unavailable answer to construct the query. A wrapper program can be constructed without running the program it contains, as in :5.2. Identify that effective construction. If choosing the wrapper requires an answer that the available operations cannot obtain, the conversion remains unresolved.
Using only the successful branch. Finding an emitted event confirms a positive case. The universal decision request also requires a terminating negative answer, which simulation alone leaves unresolved.
Reversing the reduction. Write the A-procedure using the B-solver before transferring an impossibility or an algorithm. Its calls determine the direction.
Hiding conversion cost behind the solver’s bound. Explicit expansion of b bits into 2^b states dominates the use in :5.3. Include the created instance and its storage in the resource argument.
CMP.1:9 - Consequences
An unfamiliar problem can acquire a usable algorithm through a constructed connection to another. The same form of reasoning can establish a limit by showing what an assumed solver would imply.
The construction must cover its converted inputs, recovered answers and resource costs. A new solver or representation can improve it; a changed answer guarantee or input class can invalidate only part of its earlier use.
CMP.1:10 - Architectural Rationale
Effective conversion and answer recovery make reduction a computational method. Mathematical correspondence supplies the relevant implication, while computability and cost determine whether the connection can be used under the stated conditions.
Solver reuse and impossibility belong together because the latter follows by assuming and then constructing the former. State which guarantee the assumed solver would transfer and in which direction. The shortest-path and program-wrapper cases demonstrate different uses of that shared method.
C.29.2 already supplies the computational question, representation and ordinary progress account. This pattern develops a missing reduction, its answer relation and the consequence of an available or assumed solver. More specialized algorithm constructions can supply the conversion or the target solver.
CMP.1:11 - SoTA-Echoing
Erickson’s Undecidability notes, §§7.4-7.5 and 7.9-7.10, supply a foundational account of effective program construction and the direction of reduction arguments. The adopted contribution is the explicit construction that turns an assumed solver into another solver. The event-wrapper example here uses the halting result under its stated computational model.
Erickson’s Shortest Paths supplies the directed-graph and negative-cycle machinery used in the solver-reuse case. The recovered inequalities and their infeasibility argument explain what that machinery answers in the source problem.
A direct algorithm is preferable when conversion adds effort without improving the needed result. When a reduction is useful, the choice among ordinary computability, bounded-resource, approximate or randomized reductions follows the answer guarantee being transferred. A preserved decision alone leaves an approximation ratio, probability or practical runtime to its corresponding argument.
CMP.1:12 - Relations
- C.29.2 specifies computational answers, representation, progress, accuracy and resources.
- C.29 establishes a subject correspondence when the computational problem describes something beyond the mathematical construction.
- MATH.17 and MATH.18 develop operations on operations, interpretations and their preserved consequences.
- MATH.4 and MATH.12 supply induction and constructive argument methods when the reduction needs them.
- A.3.3.TR recovers state and continuation distinctions, including those needed by finite-state restrictions.
- C.39 and C.40 help develop a missing computational way or explore alternatives when a construction remains unresolved.
CMP.1:End
CMP.2 - Derive a Recursive Procedure from a Problem Decomposition
Type: Method Status: Stable Normativity: Normative
CMP.2:1 - Problem frame
Use this when you can state the answer required from a finite input, but a procedure for obtaining it is missing or unaffordable. Parts of the task resemble the whole, or a transformation produces another instance whose answer could help. You need to choose those subproblems and determine what they must return.
A practitioner may recognize a recursive formula yet be unable to turn an unfamiliar problem into one. A common difficulty appears at recombination: each part returns a correct answer to its own question, but those answers omit information needed for the whole. Another appears at progress: a call changes its input without bringing computation closer to a return.
The gain is a recursive procedure with usable base cases, a reason its calls return, a justified way of combining their results and an initial account of its cost. The reader needs to follow finite case distinctions, functions and a simple inductive argument. MATH.4 can supply that argument; C.29.2 supplies the relation between a computational answer and the question it is meant to settle.
Use a suitable existing procedure directly when it already answers the question within the available resources. This method develops recursion for obtaining a finite answer. A server, stream or other intentionally continuing process needs a progress condition appropriate to that behavior.
CMP.2:2 - Problem
How can one discover a recursive algorithm whose subproblems are obtainable, whose answers suffice to reconstruct the requested result, and whose unfolding has an acceptable cost?
Choosing a familiar equation or writing a self-call does not settle those questions. The designer must connect the meaning of a subproblem to the operation that uses its answer.
CMP.2:3 - Forces
| Force | What must be reconciled |
|---|---|
| Small subproblems and sufficient answers | A short returned value can omit the boundary information needed for recombination. |
| Natural structure and useful decomposition | Following input syntax makes some arguments easy; a different split may reduce work or expose the needed result. |
| Generality and effective choice | A mathematical existence argument can leave the next branch or object unavailable to computation. |
| Progress and branching | Every call may become smaller while their number grows too quickly. |
| Simple cost model and actual representation | Counting additions can hide copying, growing integers or expensive access. |
| Reuse and changed questions | A summary adequate for one result may discard information needed by a later result. |
CMP.2:4 - Solution
State the answer → propose smaller questions → derive the join → strengthen what must be returned → establish return → compare the work.
CMP.2:4.1 - Fix the question and the available operations
Describe an input x, the information available about it, and what a returned answer must allow its recipient to do. Asking for an optimum value, one attaining object, or every attaining object gives different result requirements. State the empty and degenerate cases when they belong to the input family.
List the operations available on this input: inspect a constructor, split an interval, compare keys, compute a remainder, test a condition, or call a supplied procedure. A proposed step such as “choose the correct partition” remains a construction task until the partition can be obtained.
For example, maximum segment sum on a sequence of integers asks for a contiguous nonempty segment with largest sum. Returning its sum answers a value query; locating the segment also requires endpoints. Permitting the empty segment changes the base case and the answer on an all-negative input.
CMP.2:4.2 - Choose a decomposition by asking how answers would join
Take a representative input and suppose that selected smaller questions have been answered correctly. Try to construct the answer for this input from those returned values. This local design question avoids having to unfold the entire recursion while inventing it.
Useful proposals include removing one element, splitting into balanced parts, following the constructors of a structured input, or transforming the input while decreasing another measure. The last case includes Euclid’s replacement of a pair by a divisor and remainder. Input size need not decrease in every component.
For each proposal, account for every form a valid answer can take. If a sequence is split into left and right parts, an optimal contiguous segment lies wholly on one side or crosses the boundary. The crossing case shows what the two recursive answers must supply.
Keep the proposal that makes the join both justified and obtainable. If the only available join searches the original problem again, change the subproblem question, retain more information, or try another decomposition.
CMP.2:4.3 - Strengthen the returned result when the join needs more
Write the join using named values. Each value must come from the input, a smaller answer or an available local operation. A missing value identifies a specific revision of the subproblem, rather than a reason to discard recursion as a whole.
For maximum segment sum, the best segment on each side is insufficient: a crossing segment uses a suffix of the left side and a prefix of the right. Let each nonempty part return four quantities:
T: the sum of the whole part;P: the largest sum of a nonempty prefix;S: the largest sum of a nonempty suffix;B: the largest sum of a nonempty contiguous segment.
For a left summary L and right summary R, construct:
T = L.T + R.T
P = max(L.P, L.T + R.P)
S = max(R.S, R.T + L.S)
B = max(L.B, R.B, L.S + R.P)
The alternatives in each maximum come from the possible locations of the corresponding segment. To return a segment, carry the endpoints attaining each selected prefix, suffix and best segment. Choose a consistent rule for ties when only one witness is wanted.
This is the algorithmic use of strengthening an inductive result in MATH.4. The additional design decision is what summary enables an affordable join for the chosen problem decomposition. Further questions may require a different summary.
CMP.2:4.4 - Supply base cases and a decreasing measure
Give a direct result for each case on which recursion stops. Then show that every recursive call reaches such a case after finitely many steps. A nonnegative integer that strictly decreases is often enough. A finite input constructor or a well-founded ordering can supply the same argument when one numerical size is awkward.
For the segment procedure, a singleton v returns (v,v,v,v). Split every longer interval into two nonempty shorter intervals. Its length decreases along every call path. This also explains why an empty interval needs its own convention or must be excluded before calling the procedure.
For nonnegative integers with b>0, Euclid’s call (a,b) → (b,a mod b) decreases the second component because 0≤a mod b<b. The first component may increase relative to its old value; it is the selected measure that must decrease. At b=0, return a, with the intended convention for (0,0) fixed separately.
When a termination checker fails, inspect which decrease is absent from its account. A supplied difference, lexicographic measure or invariant may express the progress already present in the procedure. If progress is missing, repair the procedure or weaken its claimed result. A small successful run alone does not establish return on every allowed input.
CMP.2:4.5 - Establish the result and expose its computational cost
Use the base and smaller-call assumptions to establish the returned property. Recombination must work for every smaller answer allowed by its specification, including the selected tie behavior. When deriving a program from an existing proof, MATH.12 recovers the operations hidden in that proof.
Count the subcalls and local work. A recurrence for mathematical values and a recurrence for computational cost answer different questions. For balanced segment splitting with interval views, constant-cost arithmetic and the four-value join, the work satisfies W(n)=W(floor(n/2))+W(ceil(n/2))+O(1), giving O(n) operations. Sequential depth-first evaluation retains O(log n) summaries on its call stack. Copying each subarray instead adds work at each level; growing integer values also change the cost per addition.
If equal subproblems recur, CMP.3 can identify and share them. If the decomposition generates alternatives that can be ruled out, CMP.4 can construct those exclusions. If representation dominates the cost, compare the access and update operations before replacing the mathematical construction.
CMP.2:4.6 - Use the result and revisit the assumption that changed
Run a small case through the complete procedure, including the use of its returned answer. Change one condition that stresses the construction: empty input, a boundary case, a different output request or a resource limit. Follow the affected base, join and progress arguments.
The result may be a working procedure, an unaffordable but informative construction, or a located missing operation. Use that difference to choose the next algorithmic move. Formal proof or additional testing is chosen for the uncertainty that matters to the receiving use.
CMP.2:5 - Archetypal Grounding
CMP.2:5.1 - A join that initially loses the answer
For [-2,3,-1,4,-5], split into [-2,3,-1] and [4,-5]. Their best sums are 3 and 4. Keeping only those values would miss the crossing segment [3,-1,4], whose sum is 6.
The strengthened summaries are L=(0,1,2,3) and R=(-1,4,-1,4), ordered as (T,P,S,B). The join yields (-1,4,1,6). With attaining endpoints retained, it returns the segment from the second through fourth element. The user can now obtain the segment rather than merely knowing its value.
Changed condition: suppose the wanted segment may contain at most two elements. The former crossing winner has length three. The four maxima have discarded the sums of shorter candidate suffixes and prefixes. Add prefix and suffix results indexed by permitted length, combine only lengths whose sum is at most two, and keep the same restriction on internal best segments. In this case the answer becomes 4, attained by [4]. For a general limit k, a straightforward join over length pairs costs O(k²); the resource consequence can justify a different algorithm. Reusing the old four-value join would silently answer the earlier question.
CMP.2:5.2 - A subproblem obtained by a transformation
To compute gcd(48,18), replace the pair by (18,12), then (12,6), then (6,0), and return 6. The equality gcd(a,b)=gcd(b,a mod b) follows because a common divisor of either pair divides both entries of the other pair. The remainder operation and decreasing second component turn that equality into a returning procedure.
If the next use also needs coefficients u,v with u*a+v*b=gcd(a,b), the returned number alone is insufficient. Suppose the smaller call supplies d=u'*b+v'*r, with r=a-q*b. Substitution gives d=v'*a+(u'-q*v')*b; return the updated coefficients too. For the original pair, 6=(-1)*48+3*18. The same recursive decomposition supports a stronger output through a changed join.
CMP.2:6 - Bias-Annotation
Familiar syntax can make one decomposition appear inevitable. Compare its join and cost with another plausible decomposition when those differences can change the choice. Conversely, an elegant asymptotic bound can hide operations that the representation in use makes expensive.
A successful example demonstrates the construction and can expose a missing case. The general result depends on the base, joining and progress arguments, with any additional assurance selected for the intended use.
CMP.2:7 - Conformance Checklist
- The input and wanted result distinguish a value from any witness or continuation information that is needed.
- Each subproblem is constructible from available data, and its returned specification supplies the join.
- The base cases cover the stopping situations; every recursive path has the stated progress toward one of them.
- The join preserves the answer property, including boundaries and the chosen treatment of ties.
- The cost account includes branching, recombination and representation costs material to the decision.
- A changed requirement is followed through the returned information and affected clauses before the procedure is reused.
CMP.2:8 - Common Anti-Patterns and How to Avoid Them
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Return only the final scalar from each part | The segment example loses crossing answers. Derive the join and retain the boundary summaries it consumes. |
| Treat a changed input as a smaller input | Calls can continue indefinitely. State a well-founded decrease and check every recursive branch against it. |
| Treat termination as affordability | An exponential call tree can terminate correctly. Count calls and local work; share repeated subproblems when useful. |
| Keep the old summary after changing the question | A length constraint or witness request can be lost. Reconstruct what the new join needs and revise the affected result. |
CMP.2:9 - Consequences
The method makes recursive algorithm design available as a sequence of inspectable choices. It exposes a useful link between mathematical construction and algorithmics: strengthening what a subproblem returns can make a previously unavailable or costly computation possible.
The resulting algorithm need not be the fastest one. Its explicit subproblem and join create opportunities for sharing, new representations, parallel execution or replacement by another algorithm. Those improvements retain their own correctness and resource questions.
CMP.2:10 - Architectural Rationale
Subproblem meaning, recombination, progress and cost belong together because changing one can force a change in the others. Starting from a recursive syntax would obscure the discovery of the required question and summary. Starting from an induction proof alone can leave the effective decomposition and cost unresolved.
MATH.4 supplies witness construction by induction; MATH.12 supplies extraction from a proof. This pattern constructs and compares recursive obtaining procedures, including decompositions that do not follow the input’s constructors. CMP.3 changes how repeated calls are evaluated without silently changing what they ask. C.29.2 retains the common computational formulation and its connection to the receiving question.
CMP.2:11 - SoTA-Echoing
Erickson, Algorithms, chapter 1 develops recursion through reductions to simpler instances and separate correctness and running-time arguments. Adopt the local design question about a correct smaller answer; adapt it by making the information required at the join explicit and testing a changed output request. A remembered recurrence alone supplies less help when the decomposition itself is missing.
For the construction in :4.2–4.5, an available recurrence or input-structural split is the simpler alternative when it already returns enough information for the join and meets the cost requirement. Strengthening a subanswer is worth its extra work when that simpler return loses the requested result, as the four-value segment construction and coefficient-returning divisor procedure demonstrate. Reconsider this choice when a different output, representation or competing decomposition changes either sufficiency or total cost.
The current Lean reference on recursive definitions distinguishes structural recursion, well-founded measures and forms of partial or continuing behavior. Adopt the distinction between a missing syntactic decrease and an absent termination argument. Formal encoding can check a consequential or difficult construction; its additional work is unnecessary for simply exploring a decomposition.
CMP.2:12 - Relations
- C.29.2 - Computational Formulation: supplies the requested computational result, elementary operations and connection to use.
- CMP.1: supplies reuse through an effective reduction; recursion constructs the repeated same-family reduction and its return.
- MATH.4 and MATH.12: supply inductive construction and the obtaining operations recoverable from proof.
- CMP.3: shares repeated calls and chooses their evaluation and storage; CMP.4 handles exclusions among alternative extensions.
- MATH.20: supplies bounds used when comparing cost or consequences. The general resource and portfolio methods choose among the constructed alternatives.
CMP.2:End
CMP.3 - Share and Schedule Repeated Subcomputations
Type: Method Status: Stable Normativity: Normative
CMP.3:1 - Problem frame
Use this when a procedure repeatedly obtains the same intermediate answer, or retains so many intermediate values that it cannot finish within the available memory. You need to determine which work can be shared, when to perform it, and what to retain for later use.
The situation occurs in dynamic programming, symbolic evaluation, database computations, program analysis and differentiation of computational graphs. The repeated unit is a subcomputation with stated inputs and a needed result. Similar-looking calls may still require different answers because their data, assumptions or effects differ.
The gain is an evaluation procedure that performs less repeated work or fits the available storage while preserving the requested answer. The reader needs to understand a function call and a directed dependency graph; the graph is explained here as a set of intermediate results with arrows from each prerequisite to its consumer. CMP.2 can supply the original recursive procedure.
Direct recomputation is often best for a cheap, seldom-repeated operation. Apply this method when sharing or storage choices can change the feasibility or cost of the computation. A changing environment requires the meaning of reuse to be established before previous results are used.
CMP.3:2 - Problem
How can repeated computations be identified and reorganized without merging cases that need different answers, using an evaluation order and storage policy that support the requested result?
“Cache the answer” leaves three questions open: what counts as the same question, which answers must already be available, and whether the retained information suffices for the eventual output.
CMP.3:3 - Forces
| Force | What must be reconciled |
|---|---|
| Sharing and distinctions | A coarse reuse key saves work but can conflate different continuations. |
| Demand and predictable order | Computing only requested states avoids unused work; a regular order can simplify access and scheduling. |
| Time and storage | Retaining values avoids computation but can exhaust memory or increase data movement. |
| Value and witness | A small working table can retain the optimum value while losing the path attaining it. |
| Reuse and change | An answer remains usable only while the data and conditions on which it depends still apply. |
| Mathematical equality and execution effects | Repeating a pure calculation and repeating an observation or state change can produce different behavior. |
CMP.3:4 - Solution
Name the repeated question → retain its determining information → expose dependencies → choose evaluation order → choose retained values → recover the required output.
CMP.3:4.1 - State what a subcomputation means
Describe the result of one subcomputation as a function of its inputs and fixed environment. Include every condition that can change the returned answer or its use. A pair of sequence indices identifies an edit-distance subproblem only within specified sequences, edit operations and costs.
For optimization, distinguish the best remaining value from accumulated cost already incurred. If two histories lead to the same remaining problem but have different past costs, share the remaining answer and combine it with each history’s cost. Merging the complete histories may lose a better total. When history changes the allowed future choices, retain that history information in the state.
This question is also useful before an implementation exists: identify the small family of questions that many possible constructions would ask. A recursion tree can then be designed around those questions instead of optimized after the fact.
CMP.3:4.2 - Define reuse by the answer the continuation needs
Choose a representation of subproblem identity, often called a key. Equal keys must imply interchangeable answers for the intended continuation. The key can contain input values, an immutable object’s identity, a data revision, parameters and relevant assumptions. A cache local to one fixed computation may keep some of these implicit in its scope.
MATH.2 supplies the reasoning behind an identification: the operation used after identification must give the same required result whichever representative was used. An implementation also needs an effective way to recognize the keys. A hash narrows candidates; resolve collisions before treating different data as identical.
Distinguish completed answers from computations that have merely begun. Reading an unfinished entry as a result can introduce circular reasoning. In parallel evaluation, decide whether repeated demand waits for one producer or safely computes another copy; preserve the meaning of completion in either case.
For an operation with effects, state what reuse preserves. Replacing two reads of a changing sensor by one stored reading changes the observation sequence. Drawing again and reusing the same sample can give different dependence between the two results. Sharing a pure calculation on an already obtained reading or sample can be valid. Select the intended operation before choosing the reuse rule.
CMP.3:4.3 - Construct the dependency graph and an evaluation order
For each distinct subproblem, identify which other results are needed to obtain its answer. Make the direction from prerequisite to consumer explicit. Count distinct states and the work needed to combine each state’s prerequisites and alternatives; the number of states alone does not establish the total cost.
If dependencies are acyclic, two standard constructions are available:
| Construction | How it obtains results | Useful condition |
|---|---|---|
| Memoized evaluation | On a call, return a completed stored answer if present; otherwise obtain prerequisites, compute the result and store it. | Only part of the possible graph is expected to be reached. |
| Ordered table evaluation | Obtain a topological order, in which prerequisites precede their consumers, and compute states in that order. | The needed state region and dependency order are known and regular access helps. |
These methods can be combined by regions. Independent ready states can also be evaluated concurrently, provided the sharing and combination operations preserve the result.
A directed cycle prevents this simple ordering. Determine whether it is an erroneous recursive dependency, a finite-horizon problem missing its horizon coordinate, or a genuine fixed-point problem. For a genuine cycle, provide the iteration, ordering or other solving method and its result conditions. Adding memoization alone does not solve mutually dependent equations.
CMP.3:4.4 - Retain what remains live, and recompute selectively
A value is live along an execution path while a later operation on that path still needs it. Find its last consumer, including any use in reconstructing the requested output. The storage can be reused after its last use. A live value can also be discarded earlier if it can be obtained again when needed at an acceptable cost and with the required meaning.
Compare full retention, a moving set of recent values, and selected stored checkpoints from which intervening work is recomputed. Include key storage, lookup, copying, arithmetic size and transfer costs when they can change the choice. The mathematical dependency graph can be unchanged while these execution costs differ substantially.
Recomputation must reproduce the needed value from retained inputs and conditions. If it repeats an external effect or uses changed data, its meaning needs separate treatment. A stored checkpoint is useful only if it contains enough information to restart that part of the computation.
CMP.3:4.5 - Recover the value, witness or continuation actually requested
For each return, ask what the recipient must obtain. A dynamic program may return only an optimum value, one attaining sequence of choices, a count, or all attaining sequences. Store a selected predecessor when one witness is required, retain all relevant alternatives when their multiplicity matters, or provide an additional reconstruction procedure.
A small table is not automatically a complete answer. Sometimes an extra pass or a recursive split reconstructs a witness using less storage than retaining all predecessors. Include that work in the cost comparison.
When inputs or requirements change, identify the affected dependencies. Invalidate or recompute their consumers, or show that the changed information cannot alter those results. Choose the simplest reuse boundary that pays for itself; rebuilding a small calculation can be cheaper than maintaining fine-grained dependencies.
CMP.3:4.6 - Compare the resulting procedure with the original
Evaluate one complete use under both procedures and follow a changed condition that can break the proposed identification or storage policy. Check returned content as well as operation counts. The method’s result is the changed computation and its resource consequence.
Use C.11.DUA when deciding whether another measurement, argument or experiment would change the choice. A theoretical bound can guide an initial implementation; actual resource observations can select among alternatives whose constant factors or memory behavior matter.
CMP.3:5 - Archetypal Grounding
CMP.3:5.1 - Obtain a sequence-editing answer without expanding repeated calls
Let D(i,j) be the smallest number of unit-cost insertions, deletions and substitutions transforming the first i characters of fixed sequence A into the first j characters of fixed sequence B. Matching characters cost zero. Then:
D(0,j) = j
D(i,0) = i
D(i,j) = min(D(i-1,j)+1,
D(i,j-1)+1,
D(i-1,j-1) + (0 if A[i]=B[j] else 1))
Here character positions start at 1. Each alternative identifies the last edit or match. Removing it leaves the corresponding smaller problem; adding it to a best smaller answer supplies a candidate for the whole prefix. Thus the minimum covers the possible last steps.
Naively unfolding this recurrence repeatedly requests the same prefix pairs. Within one fixed pair of sequences and one cost rule, use (i,j) as the key. Dependencies have smaller i+j, so increasing rows and then columns gives a valid order.
For A=CAB and B=AB, the complete table is:
| Prefix of A | Empty | A | AB |
|---|---|---|---|
| Empty | 0 | 1 | 2 |
| C | 1 | 1 | 2 |
| CA | 2 | 1 | 2 |
| CAB | 3 | 2 | 1 |
The result is 1; deleting the initial C attains it. There are (m+1)(n+1) states for lengths m,n, with constant work per interior state under constant-cost character comparison and small-integer arithmetic. Full retention uses O(mn) cells. If only the distance is required, the preceding and current row suffice, giving O(n) working cells.
Changed output: the recipient now needs an edit script. The final distance and two surviving rows do not supply the deleted path. One repair stores a minimizing predecessor for each cell and traces back from (m,n). Another computes forward and backward costs to a middle row, chooses a column minimizing their sum, and recursively reconstructs the two halves. Every edit path crosses that row, which justifies the split. This second construction exchanges recomputation for storage; CMP.2 supplies the recursive decomposition. Neither choice alters the meaning of an allowed edit.
Changed reuse scope: for A=CB, B=AB, the value at (2,2) is 1; for A=CA, B=AB, it is 2. A global cache keyed only by (i,j) would conflate them. Restrict the cache to a fixed input pair or include the input identity and relevant conditions.
CMP.3:5.2 - Share an expression while preserving its interpretation
For f(x,y)=(x+y)*(x+y)+(x+y), build one node t=x+y with three uses, then obtain t*t+t. With x=2,y=3, the result is 30. This replaces three additions of x+y by one and shares its stored value until the final addition.
If y changes to 4, t and its consumers must change; the result becomes 42. If each occurrence instead meant “read the next measurement and add x,” the shared expression would change the computation’s meaning. The subproblem must be a fixed pure addition of supplied values for this identification to hold.
In differentiation of a longer expression graph, intermediate values may be needed again in reverse order. Keeping all of them can exceed memory. Retain selected restart values and recompute intervening pure operations when needed, comparing the extra work with reduced storage. This applies the same method to a different receiving algorithm.
CMP.3:6 - Bias-Annotation
Visible repetition can encourage indiscriminate caching. The profitable unit may instead be a larger common subproblem, or no shared unit at all when lookup costs dominate. A small count of stored cells can also hide large objects, metadata and movement between memory levels.
Results obtained from fixed data invite overgeneralization to changing environments. State where a key’s omitted parameters are held fixed, and revisit that boundary when the result is reused elsewhere.
CMP.3:7 - Conformance Checklist
- The repeated question and its determining data are recoverable from the key and its stated scope.
- Equal keys justify the required reuse, including relevant effects, randomness and changed inputs.
- Dependencies determine an evaluation order, or a separate method resolves the genuine cycles.
- Completed results are distinguished from work still being evaluated.
- Storage and recomputation choices preserve the final value, witness or continuation that is required.
- The resource comparison counts relevant transitions, arithmetic, access and storage as well as states.
- The changed-condition use follows the dependency or output requirement that changed.
CMP.3:8 - Common Anti-Patterns and How to Avoid Them
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Key a subproblem by its position across changing inputs | The edit-distance example reuses an answer to another question. Bind the key to the input and conditions or narrow the cache’s lifetime. |
| Treat an in-progress entry as an answer | A cyclic dependency can return unsupported content. Keep completion explicit and supply the appropriate cycle-solving method. |
| Discard predecessors while promising a witness | The optimum value remains but the attaining object cannot be returned. Retain choices or construct a reconstruction pass. |
| Share effects as if they were pure calculations | Observations, updates or random dependence can change. Identify the fixed data calculation that is interchangeable. |
CMP.3:9 - Consequences
Many repeated call trees become a much smaller graph of distinct questions. Evaluation order and retention become design choices, making time, memory and output reconstruction comparable.
The transformation creates responsibilities for identity and change. Its benefit depends on repetition, graph size and access costs; a dependency graph can itself be enormous. A correct shared computation can still be unaffordable, which may call for a changed representation, approximation or problem formulation.
CMP.3:10 - Architectural Rationale
Identity, dependencies, evaluation and lifetime form one method because changing the result being shared can alter all four. Separating “add a cache” from the required continuation would hide the main correctness question. Including selective recomputation prevents storage minimization and computation minimization from being treated as the same objective.
The mathematical identification is supplied by MATH.2, the subproblem construction by CMP.2, and common computational formulation by C.29.2. This pattern supplies the algorithmic reorganization. It can serve numerical, symbolic and learning procedures.
CMP.3:11 - SoTA-Echoing
Erickson, Algorithms, chapter 3 develops memoization, deliberate evaluation order, space saving and reconstruction of sequence-editing answers. Adopt the progression from a meaningful recurrence to distinct subproblems and their evaluation. Extend the identity question explicitly to changing inputs and effectful operations. The CAB example is a small independent derivation of that general design approach.
Hirschberg’s linear-space reconstruction is a historical counterexample to the assumption that reconstructing a sequence requires retaining a complete table. Its middle-split method also applies to edit paths. Adopt reconstruction as a choice between storage and additional calculation. Compare the costs for the input representation and machine in use.
Current JAX checkpointing documentation shows the same storage/recomputation choice in automatic differentiation. Adopt its substantive distinction between saved intermediates and recomputed pure operations. Compiler behavior and hardware costs affect the best schedule; a particular library interface is an example of realization rather than a prerequisite of this method.
The working choice in :4.3–4.5 is between retaining all needed intermediate answers, recomputing them when requested, and retaining selected answers from which others can be reconstructed. Full retention is simpler when memory is ample and reconstruction would dominate. Recalculation avoids maintaining entries whose results are cheap or rarely reused. Selective retention pays extra scheduling or reconstruction work when it preserves the required answer under a tighter memory limit; the edit-script construction supplies one such choice. Reconsider it when effects change which calls can be shared, the recipient needs a different witness, readout costs change, or a competing reconstruction method improves the same resource trade-off.
CMP.3:12 - Relations
- CMP.2: constructs the subproblems and their combination; this method changes how repeated questions are evaluated.
- MATH.2: supplies identification under operations; A.3.3 helps restore state information when equal retained states allow different continuations.
- C.29.2: supplies computational result and resource conditions. C.29.3 applies when realization changes the relevant execution assumptions.
- MMP.8: supplies information restrictions for adaptive choices; a computation used to obtain such a policy must preserve the observations and history on which its choices depend.
- C.11.DUA: selects additional checking or measurement for a decision that could change, including the value of further optimization.
CMP.3:End
CMP.4 - Construct Computational Search with Justified Exclusions
Type: Method Status: Stable Normativity: Normative
CMP.4:1 - Problem frame
Use this when an answer must be constructed by choosing among alternatives, direct enumeration is too costly, and information about a partial choice can eliminate some of its completions. You need a search procedure that saves work while retaining the answers its recipient needs.
Examples include finding an assignment satisfying constraints, selecting a best combination, constructing a counterexample and exploring possible program states. The general difficulty is deciding which alternatives may be omitted. A promising search order can find an answer quickly while providing no reason to exclude the alternatives visited later.
The gain is a search with explicit coverage, useful exclusion rules and a result that remains interpretable if computation is interrupted. The reader needs finite sets, logical conditions and inequalities; MATH.20 supplies a more developed bound argument. C.29.2 supplies the wanted computational answer.
Use direct construction or enumeration when it already solves the problem at acceptable cost. Heuristic search is also useful when a good candidate is enough. Justify exclusions against the requested result. A satisfactory candidate can suffice without a proof of global optimality.
CMP.4:2 - Problem
How can a procedure omit whole sets of candidates and still return a valid witness, a justified optimum or a warranted statement that no required answer exists?
The exclusion must concern every relevant completion represented by the omitted branch. Failure of one attempted completion or poor predicted performance alone does not establish that result.
CMP.4:3 - Forces
| Force | What must be reconciled |
|---|---|
| Coverage and early progress | Broad exploration retains alternatives; informed order may obtain a useful witness sooner. |
| Cheap and strong exclusions | A weak inexpensive bound can save more total work than a costly tight bound. |
| One answer and all answers | A rule preserving one optimum can discard other attaining objects. |
| Current candidate and remaining possibility | A feasible result establishes what can be done; a branch bound constrains what remains possible. |
| Reuse and assumptions | A learned conflict can remain useful across branches but fail after constraints change. |
| Return time and strength of conclusion | An interrupted search can still supply a candidate and a bound, while exhaustion supports a stronger conclusion. |
CMP.4:4 - Solution
Represent the alternatives → cover them by extensions → derive exclusions → choose exploration order → retain the remaining possibility → return the supported answer.
CMP.4:4.1 - Define a partial choice and its completions
State what constitutes a complete candidate, when it is admissible, and which result is wanted: one witness, a best value and witness, every optimum, a count, or a counterexample. For optimization, state the criterion and its direction.
Choose a representation s of partial choices. Explain which complete candidates it represents and what information is still undecided. Include past choices when they change future feasibility or cost. If several histories have the same remaining question, CMP.3 can share that question while preserving the history-dependent contribution.
Construct extensions that cover the relevant completions. Binary inclusion/exclusion, a variable’s remaining values and legal next transitions are common forms. Overlap is permitted for finding one witness but can duplicate results; counting and enumeration need a way to handle it. A symmetry reduction needs an account of which answers it identifies and whether the recipient accepts that identification.
CMP.4:4.2 - Derive an exclusion that applies to the entire branch
Select a reason for omitting s according to the result required:
| Reason | Required argument | What it allows |
|---|---|---|
| Infeasibility | No completion of s can satisfy the original conditions. | Discard s when looking for admissible answers. |
| Bound | Every completion has a value no better than a bound compared with an already admissible answer. | Discard s for the corresponding optimization conclusion. |
| Dominance | Another retained choice supplies an admissible answer at least as good for every continuation that matters. | Omit dominated work while retaining the stated result. |
| Equivalent completions | A retained representative accounts for the answers required from s. | Share or omit duplicate work with the appropriate treatment of identity and multiplicity. |
Construct these arguments from the constraints and the partial state. Propagating a choice can shrink the permitted values of other variables; an empty remaining domain then excludes that branch. A bound may come from relaxing the remaining problem through CMP.5. Dominance must include future possibilities, not merely compare the current partial scores.
For a maximization problem, let L be the value of the best admissible candidate already obtained, often called the incumbent. Let U(s) be at least as large as the value of every admissible completion of s. If one optimum is required, U(s)≤L permits exclusion. If every attaining candidate is required, equality can still contain needed answers; use U(s)<L for this bound-based exclusion and preserve the attaining alternatives.
For minimization, reverse the bound directions: a lower bound on every completion is compared with the cost of a known feasible candidate. A candidate score and a bound on all completions have different roles even when their numerical values coincide.
CMP.4:4.3 - Reuse consequences within their conditions
When a conflict occurs, identify which partial assignments and original conditions imply it. A smaller conflicting subset can exclude the same combination elsewhere, saving repeated discovery. Apply the learned consequence only where those conditions hold.
Keep its scope simple enough to use. A consequence of the fixed problem can be retained throughout that search. A consequence relying on a temporary assumption applies only under that assumption, unless the assumption is retained in the learned condition. After a constraint or domain change, revisit consequences depending on it.
An observation that a branch was unpromising can guide ordering. Turning it into an exclusion requires the corresponding all-completions argument or an explicitly weaker heuristic conclusion. This is particularly relevant when a learned model proposes branches or estimates their value.
CMP.4:4.4 - Choose the exploration order for the next useful result
Maintain the unprocessed partial states. Depth-first exploration retains relatively little state; an order based on bounds can tighten the remaining optimum range; a feasibility heuristic can obtain an incumbent early. Choose according to the result and resources needed now.
At each selected state, propagate applicable conditions, apply a useful exclusion, return or improve a complete admissible candidate, or generate covering extensions. A finite search space and complete processing support eventual exhaustion. In an infinite space, eventual discovery additionally depends on how branches are scheduled; repeatedly expanding one branch can leave an existing witness unvisited.
Compare the cost of an exclusion with the work it is likely to avoid. It can be rational to skip a difficult bound and explore the branch.
CMP.4:4.5 - Preserve the meaning of bounds during computation
A mathematical bound must retain its direction in the arithmetic that computes it. For a maximizing search, an upper bound rounded downward without justification may exclude a better answer. Conservative rounding, interval bounds or a justified rational calculation can preserve the exclusion. A score predicted by a model is an estimate unless a suitable bound property has been established.
Use stronger arithmetic or independent checking where an erroneous exclusion could alter a consequential result. Ordinary exploratory search can instead keep a borderline branch or report a qualified result. C.11.DUA selects that extra work by its possible effect on the receiving decision.
Keep a bound for the unprocessed work, including a state whose expansion is interrupted. For maximization with an incumbent L, the whole optimum is at most max(L, max U(s)) over the states still pending. The incumbent supplies a lower bound. If a pending state lacks an upper bound, a finite global upper bound is not yet supplied by this account.
CMP.4:4.6 - Return the strongest result actually obtained
On finding a witness, return it with the meaning of its admissibility. For optimization, include its objective value and any remaining bound that the recipient needs. On complete exhaustion, sound exclusions and covering extensions justify optimality if a feasible answer was found, or absence of a feasible answer if none was found.
On interruption, return the available candidate and unresolved possibility. “No witness found within this run” is useful information but does not establish that no witness exists. If the recipient requested only a satisfactory candidate, finding one can finish the work before the search is exhausted.
Use an initial and changed-condition case to check which conclusion the recipient can use. Changing an output from one optimum to all optima, or changing a domain, directly tests the exclusion’s scope.
CMP.4:5 - Archetypal Grounding
CMP.4:5.1 - Select a best subset and interpret an interrupted search
Choose a subset of three items within capacity 5. Their (weight,value) pairs are A=(4,7), B=(3,5) and C=(2,3). Values and weights are positive integers. A partial state fixes which items are included or excluded; the next undecided item supplies the two covering extensions.
An initial candidate {A} is admissible with value 7. To bound the root, allow fractions of items. Filling by value per weight takes A and one third of B, giving 7+5/3=26/3. To establish that this is an upper bound, let a, b and c be the selected fractions. For 0≤a,b,c≤1 and 4a+3b+2c≤5,
7a+5b+3c=(5/3)*(4a+3b+2c)+a/3-c/3≤25/3+1/3=26/3.
The displayed fill attains the bound. Every integral subset is included in this relaxed set, so it too has value at most 26/3. Since integral subset values are integers, 8 is also a valid upper bound.
If the run is interrupted here, it has established 7≤optimum≤8, together with candidate {A}. It has not established optimality of A.
In the include-A branch, neither B nor C can also fit, so its best completion is A with value 7. In the exclude-A branch, B and C fit together and give 8. This meets the global upper bound, establishing that {B,C} is optimal. The algorithm obtained both a usable subset and a stopping reason.
Changed output: add an item D=(5,8) and ask for all optimal subsets. Once {B,C} has value 8, pruning a branch with upper bound 8 could lose the distinct answer {D}. Retain equality branches, or use a separate enumeration phase constrained to the established optimum value. The former “one optimum” exclusion answers a different request.
CMP.4:5.2 - Use a conflict, then revise its assumptions
Three tasks A, B and C must occupy slots 0 or 1. Every pair conflicts, so conflicting tasks must use different slots. After choosing A=0, propagation forces B=1 and leaves C with no allowed slot. The branch is infeasible. Choosing A=1 gives the symmetric conflict. Exhausting these two A choices proves that no assignment exists under these constraints.
If a third slot 2 becomes available, the earlier impossibility no longer applies. The construction A=0, B=1, C=2 is feasible. An implementation reusing conflicts learned under the two-slot domain must retain or reconsider that domain assumption. Searching faster with an obsolete conflict would prevent the useful new answer.
CMP.4:6 - Bias-Annotation
An early good answer can make unvisited alternatives seem irrelevant. That is a valid stopping choice when the recipient needs only a satisfactory candidate; it does not itself justify an optimum claim. Conversely, insisting on exhaustion can waste resources after further improvement no longer matters.
Examine a bound’s direction and scope. The relevant distinction is what the bound establishes about possible completions, including the arithmetic and assumptions used to obtain it.
CMP.4:7 - Conformance Checklist
- Partial states have a stated meaning and their extensions cover the answers that must be retained.
- Each exclusion applies to every relevant completion represented by the omitted state.
- The use of equality, symmetry, dominance and duplicates matches the request for one answer, all answers or a count.
- The incumbent is admissible; each bound has the correct direction and computational support for its use.
- Learned consequences retain assumptions that limit their reuse.
- Interrupted work remains represented in the pending possibility, and the returned conclusion matches what was completed.
- Additional pruning or assurance work is chosen for its useful effect.
CMP.4:8 - Common Anti-Patterns and How to Avoid Them
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Exclude a branch because one completion failed | Another completion may work. Derive a conflict applying to the entire represented set or continue branching. |
| Use a predicted score as a bound | A better answer may be discarded. Keep the prediction as an ordering heuristic unless its bound property is established. |
| Prune ties while enumerating all optima | Distinct attaining answers disappear, as in the added-D case. Retain equality branches or use a separate complete enumeration. |
| Report interruption as impossibility | Unvisited alternatives remain. Return the candidate, remaining bounds and the limit on the conclusion. |
| Reuse a conflict after its domain changes | A newly feasible answer can be excluded. Reconsider the consequence with its original conditions. |
CMP.4:9 - Consequences
The search can avoid large parts of a combinatorial space and still support a precise result. If a run stops early, report what the search established and what remains possible. Include any bounds that matter to the recipient.
Exclusions may be weak, expensive or scarce, and the remaining space may still grow exponentially. A changed formulation, relaxation, shared subproblem or weaker requested conclusion can then be the next useful move.
CMP.4:10 - Architectural Rationale
Coverage and exclusion are complementary: a complete branching scheme loses its guarantee if an unsupported pruning rule is added, while sound pruning cannot recover alternatives that the branching never represented. Exploration order is kept separate because it can improve time to a witness without changing which branches are valid to omit.
MATH.20 supplies the mathematical bound. CMP.5 constructs a relaxed problem that can provide one; CMP.3 can share repeated remaining questions. This pattern combines such contributions into the algorithmic construction and interpretation of search. C.40 concerns broader exploration and further problem development; its interests and stepping stones need not be reducible to a fixed search objective.
CMP.4:11 - SoTA-Echoing
Erickson, Algorithms, chapter 2 develops recursive exploration of choices. Adopt the separation between a partial choice, its extensions and the recursively obtained answer. The present synthesis adds the result-sensitive treatment of branch bounds, interrupted search and changed assumptions.
The primary report The SCIP Optimization Suite 10.0 describes current mathematical-programming search and a numerically rigorous mode combining rational and directed-rounding computation. Adopt its substantive lesson that a bound’s mathematical direction must survive its computation. The additional cost and supported problem classes limit when that mode is appropriate. This pattern neither requires a solver certificate for ordinary search nor treats a floating-point estimate as an unconditional exclusion.
For :4.2–4.6, compare justified exclusions with simpler exhaustive exploration and heuristic ordering alone. A bound is useful when the branches it safely avoids repay the work of obtaining and maintaining it, or when its conclusion settles the task before exhaustion. If finding a satisfactory candidate is enough, cheap ordering can win without proving a stronger bound. Retain ordinary conservative arithmetic when it supports the required comparison; rational or directed-rounding machinery is useful only when its added cost buys a consequential warranted exclusion. Reopen this selection when the requested output, admitted assumptions, cost of bounds or evidence for their soundness changes. In particular, asking for every optimum changes the usefulness of equality bounds.
CMP.4:12 - Relations
- C.29.2: states the wanted computational answer and its resource conditions.
- CMP.2: supplies recursive decomposition; CMP.3 identifies repeated remaining subproblems and schedules their evaluation.
- CMP.5 and MATH.20: construct useful relaxed bounds and justify the corresponding inequalities.
- MMP.10: supplies the admissible problem when search serves a modeled subject question.
- C.11.DUA: guides the value of further exploration, stronger bounds or additional checking.
- C.40: supports the wider development of alternatives and problems, including situations in which the search space or objective itself is being changed.
CMP.4:End
CMP.5 - Bound an Optimum or Recover a Feasible Candidate through a Relaxed Problem
Type: Method Status: Stable Normativity: Normative
CMP.5:1 - Problem frame
Use this when an optimization problem is difficult to solve directly, but weakening some of its restrictions or costs gives a more accessible problem. Its solution may help construct a candidate for the original problem, or bound how much better the current candidate could become.
The situation occurs in combinatorial selection, scheduling, routing, program synthesis and continuous optimization. A relaxed solution can make an inaccessible search informative, but it may violate the original conditions. For example, fractional choices are useful for reasoning about an indivisible selection even though the fractions cannot be implemented as that selection.
The gain is a useful bound, a recovered admissible candidate, or both, together with a reason they apply to the original question. The reader needs feasible sets, an objective and inequalities. MATH.20 supplies further bound reasoning; a solver for the selected relaxed problem may be obtained as a separate contribution.
Use an available direct method when it already produces the needed result at acceptable cost. Approximation alone does not make a problem a relaxation: this method needs the correspondence and inequality that support its bound. A good heuristic can still be used without that bound, with its result stated accordingly.
CMP.5:2 - Problem
How can solving an easier problem help obtain or assess an answer to the original one, without treating the easier problem’s admissibility or optimum as the original result?
The designer must construct both directions of use: how original candidates are represented in the relaxed problem, and how the relaxed output yields a bound or a candidate that the original recipient can use.
CMP.5:3 - Forces
| Force | What must be reconciled |
|---|---|
| Easy and informative relaxation | Removing many restrictions may simplify solution but leave a weak bound or hard recovery. |
| Relaxed value and admissible candidate | The easier optimum can be unobtainable under the original conditions. |
| Solver effort and useful improvement | Tightening a bound can cost more than exploring or using the current candidate. |
| Recovery and lost quality | Rounding or repair can restore feasibility while worsening the objective. |
| Mathematical and computed bounds | Approximate optimization and arithmetic can weaken or invalidate a claimed bound direction. |
| One criterion and several interests | A scalar optimization result answers its stated criterion; other objectives retain their own comparison. |
CMP.5:4 - Solution
State the original problem → construct the easier comparison → obtain its informative result → recover an admissible answer → bound the loss → choose the next use.
CMP.5:4.1 - State what the original candidate must satisfy
Name the original feasible set F, objective f, and whether it is minimized or maximized. Include the conditions that make a candidate usable in the receiving activity. An abstract numerical optimum can leave implementation, uncertainty or other subject conditions outside this particular problem; keep that boundary visible through C.29 and MMP.10.
State what would change the present decision: a better candidate, an infeasibility conclusion, a bound on possible improvement, or an answer within a given tolerance. This selects how much work to spend on the relaxation and recovery.
If several criteria matter, use the existing characterization and Pareto methods to preserve their trade-offs. The scalar constructions below address the chosen optimization question.
CMP.5:4.2 - Construct the relaxation and derive the bound direction
For minimization, give a relaxed feasible set R, objective g, and a way of representing each x in F by i(x) in R, such that g(i(x))≤f(x). Where minima exist, this yields min_R g≤min_F f. For maximization, use the reversed objective inequality so that the relaxed optimum is an upper bound on the original optimum.
Common constructions include:
| Construction | Why the comparison can hold | Main design risk |
|---|---|---|
| Drop a constraint or allow fractions instead of integral choices | Every original feasible point remains available with the same objective. | The relaxed optimum may be far from any original feasible candidate. |
| Make transitions or costs more permissive | Every original path remains represented at no greater cost in a minimizing problem. | The relaxed route may use operations forbidden in the original problem. |
| Replace a coupling constraint by a multiplier term | The signed term gives a bound on the objective for original feasible points, while the relaxed computation may separate into smaller problems. | A wrong sign or an unsupported minimizing step reverses or loses the bound. |
For the last construction, consider minimization with constraint h(x)≤0. For λ≥0, f(x)+λ*h(x)≤f(x) on original feasible points. Minimizing this expression over a larger, simpler set therefore supplies a lower bound if that minimum is obtained or bounded from below. The returned point can violate h(x)≤0; its usefulness as a bound does not make it an admissible answer.
Choose a relaxation by both its solving cost and its receiving use. A tighter mathematical description can be computationally worse, or make recovery harder. Existing portfolio and improvement methods can compare several candidate relaxations.
CMP.5:4.3 - Obtain a result with the strength its next use requires
Select an obtaining procedure for the relaxed problem. It may return an optimum, a candidate with a bound, a dual bound, or a heuristic estimate. Retain that distinction when using the result.
For minimization, a feasible relaxed point with value P gives an upper bound on the relaxed minimum. It does not by itself give a lower bound on the original minimum. To support such a lower bound, obtain the relaxed optimum or another justified lower bound L, for example from a feasible dual construction. MATH.20 supplies the bound argument; the relevant solver or proof supplies its computed value.
With an original feasible candidate of value C, the useful comparison is L≤original optimum≤C. A relaxed candidate’s value P may lie on either side of the original optimum. Keep it separately when it guides recovery.
Check the computational bound direction when rounding, stopping tolerances or incomplete solving can change an exclusion or conclusion. A conservative weaker bound can be preferable to an expensive stronger one. C.11.DUA selects extra computation or assurance according to its possible effect.
CMP.5:4.4 - Construct an admissible original candidate
Give an effective recovery operation when a candidate is needed. Rounding, selecting a subset, scheduling fractional allocations, repairing violated conditions or searching near the relaxed answer can serve this role. Test the original conditions after recovery and explain why the operation preserves or restores them.
Rounding upward can violate a capacity limit, while rounding downward can leave coverage incomplete. Derive the direction and any subsequent repair from the constraints.
Track objective change through recovery. If every recovered candidate has cost at most α times an attained minimizing relaxation value R*, then C≤α*R*≤α*original optimum for nonnegative costs and the stated approximation factor. If the relaxed solver returns only a feasible value P, the first inequality may still hold with P, but the comparison to the original optimum needs a separate bound on P or a direct comparison of C with a justified lower bound.
Recovery can fail or produce no better candidate. Retain an already admissible better candidate. A useful bound alone can still guide search or show that further improvement is too small to matter.
CMP.5:4.5 - Return to the original problem and choose the next move
Return the recovered candidate under its original conditions and the bound that applies to the original objective. For minimization, an additive gap C-L bounds how much the candidate can still improve. A ratio uses additional conditions, such as a positive denominator; a zero or negative lower bound does not support a generic ratio claim.
Use the result to adopt the candidate, stop at an adequate gap, guide a branch of CMP.4, tighten the relaxation, revise recovery or choose a different algorithm. The stronger relaxation is worthwhile only if its expected contribution warrants the extra work.
When the question or allowed operations change, recheck the representation i, bound direction and recovery. A bound from a more restrictive former problem may cease to constrain the new one. A bound that remains valid may also become too weak to be useful.
CMP.5:5 - Archetypal Grounding
CMP.5:5.1 - Recover indivisible choices from a fractional solution
In weighted vertex cover, a graph represents pairs that must be covered. Selecting a vertex covers its incident edges and incurs nonnegative cost w(v). The original problem minimizes sum w(v)*z(v) with z(v) equal to 0 or 1 and z(u)+z(v)≥1 on every edge.
Allow 0≤z(v)≤1 instead. Every integral cover remains feasible, so the fractional minimum is a lower bound. Obtain a fractional solution x and select every vertex with x(v)≥1/2. Each edge has an endpoint at least one half, so the selected vertices cover every edge. This derives feasibility of the rounding rule.
For each selected vertex, w(v)≤2*w(v)*x(v). Summing over selected vertices, and using nonnegative weights for the remaining terms, gives C≤2*sum w(v)*x(v). If x attains the fractional minimum, the recovered cover costs at most twice the original optimum. A merely feasible fractional point gives the displayed cost comparison but does not alone establish that approximation factor.
Consider a triangle with unit vertex costs. Setting every fractional value to one half gives value 1.5. Adding the three edge inequalities gives 2*sum x(v)≥3, proving that 1.5 is the fractional minimum. Threshold rounding selects all three vertices with cost 3. Removing one vertex leaves a valid cover with cost 2, improving the initial candidate. Original costs are integers, so the lower bound 1.5 also implies an original cost of at least 2. The recovered cover is therefore optimal for this instance.
Changed constraint: add “select at most one vertex.” The fractional vector with all values one half violates this new constraint, and the recovered two-vertex cover is also inadmissible. If the cardinality constraint is deliberately dropped in the relaxation, 1.5 can remain a lower bound for feasible original solutions, but it provides no feasible cover. On a triangle one selected vertex always leaves the opposite edge uncovered, so the new original problem is infeasible. The previous recovery rule cannot be reused as a solution.
CMP.5:5.2 - Use a relaxed answer as a search bound
A robot moves on the finite grid with coordinates 0≤x≤2, 0≤y≤1. It can move one horizontal or vertical step at unit cost. The task is to go from (0,0) to (2,0); cell (1,0) is blocked.
Ignore blocked cells in the relaxed problem. The distance is abs(dx)+abs(dy), here 2. Every permitted original route is also a relaxed route with the same cost, so 2 is a lower bound. The straight relaxed route is unusable. An admissible detour through (0,1),(1,1),(2,1) costs 4, giving an initial comparison 2≤optimum≤4.
CMP.4 can use the relaxed remaining distance at each partial route, together with the distance already traveled. Alternatively, the blocked direct row implies that a valid route must include an upward and a downward move in addition to two horizontal moves, proving a lower bound of 4. That stronger argument closes this small case. The admissible detour supplies a route. The relaxed distance supplies a bound.
Changed operations: allow diagonal moves at unit cost. The earlier Manhattan distance can overestimate: reaching (1,1) from (0,0) can cost 1 rather than 2. Relax the new movement problem instead. With unrestricted unit-cost horizontal, vertical and diagonal moves, max(abs(dx),abs(dy)) is the distance and supplies the corresponding lower bound. Rebuild the bound using the allowed moves.
CMP.5:6 - Bias-Annotation
An elegant relaxed formulation can redirect effort toward solving the surrogate problem ever better while original feasibility remains unresolved. Keep the recipient’s candidate or decision in view when choosing solver effort and recovery.
The word “bound” can also conceal a direction error. A convenient relaxed candidate is informative, but its objective value carries only the inequalities established for it. Calling a result approximate does not remove the need to state which conclusion the approximation supports.
CMP.5:7 - Conformance Checklist
- The original feasible candidates, objective and useful next decision are stated.
- Every original candidate has the required representation in the relaxed problem, with the inequality in the needed direction.
- The relaxed solver’s returned candidate, optimum, bound or estimate is used at its actual strength.
- Recovery is effective and its feasibility is established under the original conditions when an original candidate is promised.
- Loss through relaxation, incomplete solution and recovery is kept distinguishable where it affects the conclusion.
- Any additive or multiplicative comparison has its required sign and denominator conditions.
- A changed constraint or operation is followed through the relaxation and recovery before their result is reused.
CMP.5:8 - Common Anti-Patterns and How to Avoid Them
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Use a feasible relaxed objective as a minimizing lower bound | It can exceed the original optimum. Obtain an optimum, a dual lower bound or another justified bound. |
| Return the relaxed point as the original answer | Fractions or forbidden transitions can make it unusable. Construct and check recovery under the original conditions. |
| Round without examining the constraint | Coverage or capacity can fail. Derive the rounding direction and repair from the constraint. |
| Reuse the old relaxation after adding allowed operations | A former lower bound can become an overestimate, as with diagonal moves. Rebuild the problem comparison. |
| Tighten a bound after the decision is settled | Additional optimization consumes resources without changing the next action. Stop or redirect effort according to the receiving use. |
CMP.5:9 - Consequences
A difficult problem can yield useful information and better candidates before it can be solved directly. Bounds can support early stopping, guide search and distinguish an unattained relaxed ideal from an original feasible result.
Weak relaxation or costly recovery can limit the gain. The method exposes these limitations as choices that can be changed: which conditions are relaxed, what result the easier solver supplies, and how the original candidate is reconstructed.
CMP.5:10 - Architectural Rationale
The method joins two constructions that are often separated: making an easier problem informative and making its result usable in the original problem. Keeping recovery beside the bound prevents an easier optimum from replacing the task that motivated it.
MMP.10 supplies the formulated feasible problem when it arises from modeling; MATH.20 supplies mathematical inequalities. CMP.5 contributes the algorithmic construction of a relaxed obtaining problem and its recovery operation. CMP.4 can consume the bound without requiring a recovered candidate from every branch. Approximate subject models and general surrogate selection retain their own correspondence and portfolio methods.
CMP.5:11 - SoTA-Echoing
Williamson and Shmoys, The Design of Approximation Algorithms, especially the introductory rounding constructions and later linear-programming methods, develops the link between relaxation, recovery and approximation bounds. Adopt the obligation to construct both feasibility and objective comparison. The triangle is a small worked instance of the familiar cover construction; its simple instance-specific optimality does not generalize to every graph.
The primary SCIP 10.0 report adds a current computational consideration: relaxed bounds used in optimization can require rational or directed-rounding support to retain their direction. Adopt that consideration where the conclusion depends on it. A cheap conservative bound or direct candidate can be preferable to the additional solving and certification work.
The connection with relaxed path costs shows another use of the same construction. Here recovery is a separate route search, while the relaxed result supplies an optimistic cost.
For :4.2–4.5, compare relaxation and recovery with a direct algorithm, a cheaper feasible-candidate heuristic, and an already available valid bound. Prefer the lighter construction when it supplies the required candidate or comparison. Solving a relaxation more accurately is worthwhile when a tighter bound changes the search or when its recovered candidate improves the original result enough to repay the effort. Recovery can instead lose feasibility or too much objective value, as the changed cover case shows. Reconsider the selection when a new feasible-set relation, recovery guarantee, competing construction or resource limit changes that trade-off.
CMP.5:12 - Relations
- MATH.20: supplies the bound and inequality reasoning; MMP.10 supplies the feasible problem in a modeled receiving use.
- CMP.1: transfers answers through effective problem reductions. The present relaxation can instead preserve a one-sided bound and require separate candidate recovery.
- CMP.4: uses relaxed bounds to exclude or prioritize search branches and to describe remaining improvement.
- C.29 and C.29.2: preserve the relation between the original subject question and the computational result being returned.
- C.11.DUA and the general characterization, Pareto and improvement methods: guide comparison of solver effort, candidate quality and further work.
CMP.5:End
CMP.6 - Derive an Iterative Computational Update from Local Information
Type: Method Status: Stable 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
| Force | What must be reconciled |
|---|---|
| Cheap information and useful direction | A local signal is accessible but can omit interactions determining the effect of a change. |
| Large progress and model validity | A large step may save iterations or leave the region where its prediction applies. |
| Feasibility and improvement | An improving unconstrained move can violate the original conditions. |
| Local and global conclusions | A local stopping test needs additional structure to establish a global optimum. |
| Iteration count and work per iteration | A stronger update may require more information or computation. |
| Computed and receiving criteria | Decreasing a surrogate or training loss can leave the intended use unchanged or worse. |
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 conclusion the work needs now.
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, 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.
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.
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.
For noisy comparisons, distinguish a resolved interval test from an exhausted sampling budget. For stochastic directions, the fixed budget in :4.3.2 supports its expected result for the selected output, not an observed certificate for a particular last iterate. An additional assessment can supply a different result when its cost is justified; keep the assessment conditions separate from the update samples used to select that result.
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.
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:5.3 - Change from exact information to noisy feedback
Keep J(x)=(x-3)^2, but replace the exact derivative by g(x)=2*(x-3)+zeta, where each fresh zeta independently equals -2 or 2 with equal probability. Its conditional mean is the derivative and its error variance is 4. With eta=1/4, the error e=x-3 becomes e'=e/2-zeta/4, so
E[e'^2 | e] = e^2/4+1/4.
At e=0, either outcome increases J from zero to 1/4. A claim that every accepted stochastic step improves J would therefore be false. Repetition obeys E[e_T^2]=4^(-T)*e_0^2+(1/3)*(1-4^(-T)): the noise contribution remains near 1/3. More iterations with the same step cannot give an arbitrarily small mean squared error.
Average b fresh gradient estimates at the current x before each update. The noise term becomes 1/(4*b), giving
E[e_T^2]=4^(-T)*e_0^2+(1/(3*b))*(1-4^(-T)).
For x_0=0, the receiving requirement E[e_T^2]<=0.1 is met by b=4 and T=5: the bound is 9/1024+(1/12)*(1023/1024), about 0.092041. This uses 20 gradient observations. Unlike the general stationarity result, this quadratic recurrence directly supports the last iterate’s squared-error claim; its special structure supplies that stronger result. A larger batch, a smaller step or another justified construction can compete on total work.
Change the feedback condition. Suppose the signal becomes g(x)=2*(x-3)+1+zeta. Its mean is the derivative plus 1. The same update now centers on x=2.5, not x=3. Even unlimited averaging removes only zeta’s variation, leaving squared error 1/4 at that center. If the offset 1 is known from a valid calibration, subtract it before updating and recover the earlier argument. If it is unknown, obtain its relation to the target or return the unresolved bias; choosing a smaller sampling error does not repair the target.
The comparison route supports a different receiving choice. Suppose a current candidate and one proposal can be compared through fresh bounded loss differences in [-1,1]. A valid simultaneous interval [-0.18,-0.04] permits the proposal for tau=0.02; [-0.05,0.03] leaves that comparison unresolved; [-0.01,0.08] rules out a decrease greater than 0.02. If further proposals are selected from these results, apply the per-comparison budgets in :4.3.1. A fixed-count interval repeatedly inspected until it favors a proposal does not supply the same claim.
CMP.6:6 - Bias-Annotation
A familiar update formula can displace the question of which local information is 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
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Turn an improving direction into an arbitrary finite step | The quadratic example can oscillate or diverge. Derive step extent or supply an adaptive rule with stated conditions. |
| Stop solely because successive values barely change | A tiny step can hide a large unresolved error. Connect the stopping quantity to the result by a bound. |
| Demand zero full gradient at a constrained optimum | The interval example is optimal with a nonzero derivative. Use feasible variations or the appropriate projected condition. |
| Infer global optimality from a local stop | The neighborhood may miss a better distant candidate. Derive a global comparison or retain the local conclusion. |
| Treat finite termination as a useful runtime bound | The finite state space or potential may be enormous. Account for encoded magnitude and work per step. |
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. Locating the failure can show which part of the formulation needs revision.
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.
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.
For noisy feedback, :4.3.1 composes CMP.9’s intervals with a finite-change decision and an error budget across adaptive proposals. It is the appropriate alternative when the receiving work needs a warranted decision about each accepted change. Its sampling can be expensive or leave equality unresolved. In :4.3.2, adapt the conditional expected-decrease argument and finite stationarity bound of Bottou, Curtis and Nocedal, sections 4.1 and 4.3 to obtain an executable noisy-direction procedure and its budget. This established mathematical line trades per-step improvement for an expected finite-output result. Exact information remains the simpler choice when it is affordable. Larger batches, better estimators or variance-reduction methods deserve comparison when they improve the same requested result per total work. A changed conditional mean, variance bound, feasible region or output selection reopens the affected argument.
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.
- CMP.9: constructs estimates and intervals for noisy comparisons, and a uniform retained iterate when the expected-output argument needs one; MMP.7 supplies a missing observation law.
- C.11.DUA and the general improvement methods: select the value of additional computation, information or a more costly update.
CMP.6:End
CMP.7 - Construct a Learner from Examples and Feedback
Type: Method Status: Stable Normativity: Normative
CMP.7:1 - Problem frame
Use this when examples or feedback are available and the required rule for further cases is missing, or an existing learning procedure must be changed for a different target, kind of feedback or resource limit. You need to construct the procedure that obtains the rule, rather than leave “learn the model” as an unexplained operation.
The situation occurs when learning a classifier, estimating a response, constructing a surrogate, discovering a program or updating a policy. The output may be a symbolic rule, a function represented by weights, a distribution or a retained set of candidate rules. Its required form follows from the intended use.
The gain is a learning procedure with explicit inputs, selection or update operations and a learned result that can be applied at its warranted scope. The reader needs functions, finite examples and a loss or another stated comparison. Probabilistic guarantees require the corresponding additional probability model.
Use an existing rule directly when it already serves the purpose. Use an established learner when its inputs, target, restrictions and costs fit. This pattern is needed when those choices or their connection to further use must be constructed or revised. Explaining a learned rule and teaching a person to apply it are distinct tasks, supplied by the explanation and development methods when required.
CMP.7:2 - Problem
How can a computation turn examples and feedback into a useful rule for further cases, with a clear distinction between fitting the observed examples, obtaining the rule affordably and justifying its further use?
Many rules can agree on the available examples and disagree elsewhere. Faster optimization can obtain one of them more accurately while leaving that disagreement unresolved.
CMP.7:3 - Forces
| Force | What must be reconciled |
|---|---|
| Expressive rules and learnability | A large rule family can represent more targets while requiring more information or search. |
| Available feedback and target use | Recorded labels or rewards may differ from the response the recipient needs. |
| Fit and generalization | Low loss on used examples leaves questions about unseen cases and changed conditions. |
| Statistical and computational efficiency | A class can be learnable in principle while obtaining its selected rule remains unaffordable. |
| Stability and adaptation | Retaining past information helps under stable conditions but can obstruct a changed target. |
| Point prediction and retained ambiguity | One chosen answer is convenient; unresolved alternatives can matter to the next action. |
CMP.7:4 - Solution
State the further use → identify available feedback → restrict the rule family → construct selection or update → establish its result → apply and revise.
CMP.7:4.1 - State what a further application must obtain
Describe the input on which the learned rule will be used, the required response and the loss or gain that matters. Include the region, population, time or interaction conditions when they change that meaning. A rule predicting an observed label, a latent property and the consequence of an intervention answers different questions.
Separate the learning algorithm from the learned rule. In a batch setting, write A(S)=h_S: algorithm A consumes the examples S and returns rule h_S. A later application computes h_S(x) on a new input x. In an online setting, the learner also carries state and updates it as feedback arrives. The cost of obtaining a rule and the cost of applying it may favor different constructions.
State whether the recipient needs one rule, a set of alternatives, an uncertainty statement or an action selected from predictions. The output type changes what the learner must retain. A rule can be useful under a qualified assumption without an unconditional guarantee over all possible inputs.
CMP.7:4.2 - Recover the examples and feedback actually available
Identify the supplied inputs, labels, rewards, demonstrations or other observations and how they were obtained. For missing labels, delayed feedback, selection effects or dependence between examples, state what the learning procedure can observe. MMP.7 supplies the probability model of recorded data when such a model is needed.
Choose the feedback regime before deriving the update. In supervised learning, the supplied target response can evaluate a candidate prediction directly. In bandit feedback, only the consequence of a chosen action is observed; an update requiring all unchosen consequences is unavailable. A self-produced label remains the output of another rule and can propagate its errors.
State which conditions are fixed during the learning claim. Independent examples from one distribution, an arbitrary sequence generated by one stable target rule, and a changing target support different arguments. Data rows alone do not supply any of these assumptions.
CMP.7:4.3 - Construct the rule family and inductive restriction
Choose a family H of candidate rules and a representation in which they can be compared or updated. It may contain thresholds, programs, trees, parameterized functions or another suitable construction. Give the operations needed to apply a rule and obtain its response.
The restriction expresses which unobserved continuations the learner will consider plausible. It can come from subject structure, invariances, a simplicity preference, regularization or a previously learned representation. State the basis and the limit of the restriction. Choosing a rule family is an inference commitment, not merely a software parameter.
MMP.11 can supply a subject-grounded function family. For a surrogate, state the source responses and input region that the learned rule must serve. This pattern supplies the algorithmic way of obtaining a member or a supported collection of members from examples. If no candidate can serve the target, improve the family or representation rather than trying to optimize within it indefinitely.
CMP.7:4.4 - Give an effective selection or update procedure
Choose how data and feedback change the candidate:
| Construction | Effective operation | Principal condition |
|---|---|---|
| Select from a finite family | Evaluate each rule on the relevant examples and select by the stated criterion, with an explicit treatment of ties. | The family and evaluations must be affordable. |
| Retain consistent candidates | Remove rules contradicted by newly observed feedback; use or combine the survivors. | Every observed label used for elimination must agree with one fixed target rule in the initial family. |
| Optimize a parameterized criterion | Construct updates or search using CMP.6 or CMP.4, including initialization, constraint handling and stopping. | Optimization progress and the meaning of the learning criterion both need their stated conditions. |
For empirical risk minimization, a typical criterion is the average loss L_S(h)=(1/n)*sum loss(h(x_i),y_i). Regularization or another restriction can change the criterion. An argmin expression specifies the desired rule; the learner needs a procedure for obtaining it, including what it does when the minimum is not obtained or several rules tie.
Look for shared work and useful ordering. For thresholds, sorting examples once can let successive threshold scores be updated from counts rather than reevaluated on the whole dataset. CMP.3 supplies sharing when its identity conditions hold. For a parameterized learner, compare the work of one update, the updates needed and the later cost of applying the result.
CMP.7:4.5 - Establish the learning result at the strength available
Distinguish three results:
- Obtaining: the algorithm returns the stated rule or collection under its inputs and computational limits.
- Fit or update performance: the returned rule achieves the stated empirical criterion, or the online procedure has the stated behavior on feedback.
- Further-use performance: a bound, comparison, assumption or observation supports the response on the receiving cases.
Prove or check only the result needed for the use, with additional work selected through C.11.DUA. For example, a finite fixed H with a realizable target and independent examples from the receiving distribution permits a sample-based generalization argument. A finite online candidate family can instead support a mistake bound for an arbitrary sequence under a stable realizable target; independent sampling is then unnecessary for that bound.
In a statistical argument, retain the class, loss range, dependence and selection conditions used by the theorem. Repeatedly choosing rules against the same assessment examples changes what that assessment supports. In a changed environment, all historical observations need not have the same relevance to the future query.
When available examples leave candidates disagreeing at a consequential input, return that ambiguity or choose a rule under an explicit selection basis. Obtaining an additional response is one possible move, not a default obligation. Compare its likely effect with the cost of asking, delaying or acting under the remaining uncertainty.
CMP.7:4.6 - Apply the result and revise the part that fails
Use the learned output on the intended further case. A discrepancy can come from the rule family, data law, target definition, optimization, representation or application. Follow the dependency that failed rather than reflexively requesting more training examples or more optimization steps.
If the target changes over time, choose a forgetting, reweighting, windowing or adaptation procedure together with the relation to the new target. C.11.DUA helps decide whether a discrepancy warrants more examples or a changed procedure; the common portfolio methods can retain several useful rules. This pattern constructs the learning operation used in that arrangement.
Return the learned rule, its application method, the conditions material to its use and the narrow reason for reopening it.
CMP.7:4.7 - Train a primer for a fixed responder
Use this when a capable responder can produce worthwhile alternatives, yet direct requests repeatedly elicit similar answers. Keep a direct request and an adequate hand-written prompt as baselines. The adjustable component is a policy that writes an additional prompt, the primer. The original task and primer go to the fixed responder. Its response is what the recipient uses.
During training, sample several primers per task and several responses to each primer. Evaluate their quality, their difference from a declared reference collection and diversity among responses. Use the responses to give credit to the policy that produced each primer. Keep the responder fixed during that update. On held-out tasks, apply the trained primer policy and the same responder. For comparison with direct generation and the adequate hand-written prompt, give each task the same reference collection and acceptance criteria. Keep responses that meet both the quality criterion and the required difference from that collection, then count the semantically distinct responses among those retained. Report quality losses that matter to the recipient. Use comparable sampling budgets. Count policy training, responder samples, scoring and both calls at use. If an adequate supplied primer still fails, examine the responder’s capability. A search over prompt text through an API is another implementation with its own update and cost.
Albalak et al. used a reference set fixed before training. A distance from that set can reward repeated discoveries made after it was frozen. For a claim about continuing novelty, retain a common comparable set of tasks and update each practice’s own history under a stated rule. At each observation, establish how many different responses meet both its quality and novelty criteria. Compare those results and their costs under the same task conditions. Distances from different histories express different comparisons. Use a shared reference as well when the judgement requires novelty relative to the same prior collection. The extra cost of two-stage generation can make direct generation preferable for the intended use.
CMP.7:4.8 - Generate with restricted topic knowledge and refine with a knowledgeable model
Use this when familiar answers dominate and there is a way to assess proposals that depart from them. Specify which knowledge is restricted in the generator and how to check the restriction. Retain its ability to express a coherent proposal. In D’Ambrosio et al., filtering topic material during training and continued training that induces partial forgetting were distinct interventions. Delaying access to documents or asking a knowledgeable model to simulate unfamiliarity makes a different intervention. Keep a knowledgeable generator as a comparator.
Give the original task and the initial proposal to a knowledgeable reviser. Ask it to preserve the proposal’s distinctive idea while correcting errors or supplying missing conditions. Retain both versions. Examine what survived, then assess originality, fitness for use and feasibility separately. A replacement idea can enter a new branch. An incoherent initial proposal, an idea lost during revision and a preserved but infeasible idea call for changes to different components. Compare the complete arrangement with direct expert generation and with knowledgeable generation given the same revision and assessment budget. Count model preparation, generation, revision, judging and the cost of testing a proposal.
The experiments used model judgements of proposals. A feasibility judgement can select a trial. Feasibility in the intended practice needs its own demonstration. The study found no scoring advantage in neuroevolution at 1B or backpropagation at 7B under the reported conditions. Check the intended domain and the generator’s capacity before paying for training.
CMP.7:4.9 - Train a function while changing its internal representation
Use this when current predictions fit but later changes or generalization matter, and the learner’s internal computation can be examined and changed. Define the next task and any earlier responses that must survive. Compare ordinary training and an adequate familiar regularizer under stated budgets. Decide whether you need generalization to new inputs, adaptation within the present family, retention through an update or learning a new family. These require different observations.
A Unified Factored Organizer (UFO) is a low-capacity nonlinear autoencoder used during training. Choose the primary network’s internal quantities, such as node activations or attention weights, and normalize them across the training batch by component. For intracomponent regularization, each vector records one component’s responses at fixed input positions. Preserve those positions across batches. In the reported finite-domain experiment, absent inputs occupy zero-filled positions and contribute no reconstruction loss. Reordering a minibatch must preserve which input each position denotes. An intercomponent vector records one input’s responses across a layer’s fixed components. For attention, identify heads and query/key positions consistently. The reported fixed-length sequences preserve these roles; variable lengths require a further construction. Choose coordinates and storage that are feasible for the domain. Train the primary network on task loss plus a weighted reconstruction loss. Hold the organizer’s parameters fixed in that update while passing the gradient through it. In a separate update, keep the primary network fixed. Within each intracomponent vector, select the lowest-error entries. For intercomponent regularization, select the lowest-error complete vectors within each layer. The organizer receives the complete vectors; selection determines which reconstruction errors contribute to its update. Specify the selection rule and how the reconstruction weight increases from its initial value. The primary network can then perform the task without running the organizer.
Compare the ability to solve the declared next task, retention of protected responses, successful runs and total training cost, including the organizer, its activations and both updates. A reduction in steps to a threshold can still be costly per step. Reconstruction loss alone cannot establish the ability to learn a different family. Sheppard et al. give the training construction and its experimental conditions. Lehman and Stanley separately compare how compatible and incompatible changes and the size of an update affect retention. Use a change whose required effect you can identify to decide whether the next intervention belongs in the representation, the update or the new training task.
CMP.7:5 - Archetypal Grounding
CMP.7:5.1 - Construct a batch selector and expose an unresolved continuation
On nonnegative integer inputs, consider the two rules f(x)=x and g(x)=x mod 2. The supplied examples are (0,0) and (1,1). Both rules have zero squared loss on those examples.
A learner can evaluate both rules and return the minimizing set {f,g}. The returned set retains the ambiguity. It can also return one rule under a declared preference, but the zero training loss alone gives no reason to prefer f over g at input 2. Their predictions there are 2 and 0.
Suppose the receiving task needs a prediction at 2 and an additional observed response is available for a cost that could be justified. If that response is 2, the same selection procedure prefers f; if it is 0, it prefers g. If the observation is not worth obtaining, use a selected rule under the remaining assumption or retain both possible responses for the downstream decision. Better minimization of the original two-example loss cannot distinguish them.
Changed response: suppose the response at 2 is 1. Neither rule fits all three observations. Revisit the two-rule family or the assumption of deterministic noiseless responses. Repeatedly fitting the original family more accurately cannot create the absent continuation.
CMP.7:5.2 - Construct an online learner and derive its mistake bound
Let H be a finite family of binary prediction rules and suppose one fixed rule in H gives every true label that will arrive. Retain the set V of rules consistent with all labels seen so far. On a new input, predict the majority label among rules in V, using a fixed tie rule. After receiving the true label, remove the rules that predicted otherwise.
On each mistaken prediction, at least half of V is removed. The true rule remains, so after M mistakes 1≤|H|/2^M, giving M≤log2|H|. This establishes a bound on mistakes for an arbitrary input sequence under the stable-realizable-target assumption. It does not require independent random examples. Evaluating all survivors on each input costs up to |H| rule evaluations; the mistake guarantee alone does not make an enormous family affordable.
For a concrete instance, let inputs be integers 0 through 4 and let H contain six threshold rules h_t(x)=1 if x≥t else 0, for t=0,...,5. Break ties by predicting 1. At input 2, three rules predict each label, so predict 1. If the true label is 0, retain thresholds 3, 4 and 5. At input 3, the majority now predicts 0; if the true label is 1, retain only threshold 3. The two mistakes are within floor(log2 6)=2; subsequent predictions follow h_3 correctly as long as the assumed target remains h_3.
Changed feedback: a later example gives label 1 at input 2. It contradicts the previously received label at 2. Eliminating the last rule would leave an empty set. The stable noiseless-target premise has failed: retain the discrepancy and choose a treatment for noise or change, such as weighting errors or using a recent-data learner. The earlier mistake proof cannot be carried through that change unchanged.
CMP.7:6 - Bias-Annotation
Training loss and benchmark performance are visible and easy to optimize. The recipient may instead need a response in a different region or after an intervention. Keep that target explicit so that improving the visible criterion does not silently replace it.
A broad function class or large pretrained model can hide a strong inductive restriction in its representation, training history and obtaining procedure. The relevant question is which continuations it favors and how that choice fits the receiving use.
CMP.7:7 - Conformance Checklist
- The future application, output type and relevant loss or gain are recoverable.
- Available examples and feedback match the operations the learner performs.
- The candidate family or other inductive restriction has a stated basis and boundary.
- Selection or update is effective, with tie, failure and stopping behavior specified.
- Obtaining, fit and further-use claims retain their distinct conditions.
- Statistical or online guarantees use the sampling, target and class assumptions they require.
- A contradictory or changed case leads to the relevant data, family, target or update revision rather than automatic extra training.
CMP.7:8 - Common Anti-Patterns and How to Avoid Them
| Misstep exposed by the method | Consequence and repair |
|---|---|
| Use zero training error as a prediction argument | Identity and parity agree on the examples but disagree at 2. Retain the ambiguity or supply the selection basis relevant to further use. |
| Treat an optimization formula as the learning algorithm | The chosen rule can remain unobtainable. Supply effective selection or update with its computational cost. |
| Use feedback that the agent never receives | A bandit update can silently assume labels for unchosen actions. Match the operation to the actual observation regime. |
| Keep eliminating candidates after the fixed-target premise fails | The threshold example leaves no survivor. Revise the treatment of noise or change and its result conditions. |
| Assume more data or computation always resolves the failure | An inadequate family or wrong target can survive both. Locate the changed dependency before choosing more work. |
CMP.7:9 - Consequences
Learning becomes an explicit algorithmic contribution: a reader can say what is supplied as feedback, how it changes a candidate, what rule is obtained and how that rule is used. The construction can be delegated or changed without leaving an unexplained “learn” step between modeling and computation.
The method can also expose a limit that further optimization cannot remove. New information, a better family, another target or a different receiving decision may be needed. The result remains useful when it identifies that choice without demanding unnecessary evidence.
CMP.7:10 - Architectural Rationale
The learning algorithm and learned rule must remain distinct because their costs, inputs and failure modes differ. Inductive restriction belongs with the algorithm’s construction: without it, agreement on examples leaves the future rule unspecified. Base the performance argument on the feedback and use in question.
MMP supplies data and subject-model accounts. CMP.4 and CMP.6 supply effective search or update; CMP.7 assembles those contributions into a learner. Further model assessment, explanation, development and portfolio choice use their existing methods.
CMP.7:11 - SoTA-Echoing
Shalev-Shwartz and Ben-David, Understanding Machine Learning, chapters 2-5 and 21, supplies empirical selection, inductive restriction and online learning under different information assumptions. For a manageable finite family with a stable realizable target, adopt majority-and-elimination over choosing an arbitrary consistent rule when mistake reduction matters: one mistaken arbitrary choice may remove only one rule, while a mistaken majority removes at least half. Include the extra work of evaluating the surviving rules and counting their predictions. When enumeration is unaffordable or feedback is noisy, this finite-family construction requires replacement or qualification.
For a large parameterized family, Bottou, Curtis and Nocedal supplies optimization procedures and separates their error from statistical error. Adopt an affordable update through CMP.6 when direct rule enumeration fails; retain the unclosed generalization question after numerical progress.
For changing environments, Han, Huang and Wang, Model Assessment and Selection under Temporal Distribution Shift develops adaptive recent-history comparison instead of treating all historical assessment data as equally representative. Adopt reconsideration of data relevance and the selected assessment window when time changes the target. The benefit trades reduced historical mismatch against fewer effective observations and depends on the paper’s assessment conditions; it is not a guarantee under arbitrary unobserved change.
Revisit the learning construction when the assumed feedback ceases to be available, the target or admissible family changes, or another obtaining procedure improves the required result at comparable resources. Revisit only the affected selection, update or performance argument.
CMP.7:12 - Relations
- C.29.2: supplies computational formulation and application conditions; C.11.DUA selects worthwhile additional information or computation.
- MMP.7: supplies the law of recorded data when probabilistic inference is used; MMP.11 can supply the subject response family.
- CMP.4, CMP.6 and CMP.3: supply search, updates and reusable intermediate work for obtaining the rule.
- C.2.8, EXD and the development DPFs: address what a reader or learner must understand or acquire when using and explaining the resulting method.