CMP.6:11 - SoTA-Echoing

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

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

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

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