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

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

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

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

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.