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.