Result · GENERAL-SUPERGRADIENT-SCREENING
One supergradient principle screens moves safely
Proved herepublication: internal
Meaning
Concavity turns supergradients into upper bounds for finite objective changes.
Statement
For concave F and any supergradient G, exact finite relocation satisfies ΔF <= tr(GΔI)=α u_a^T G u_a-β u_b^T G u_b. Non-positive weighted tangent gain safely rejects the move.
criterion-generic safe pruning and sufficient stability certificate
Closest prior work
Nearest prior work
Relationships
Rests on
Enables
Open next door
- Quantitative A finite-geometry necessity boundOPEN-A-QUANTITATIVE-BOUND
- Characterize criteria with finite exchange => first-order geometryOPEN-CRITERION-CHARACTERIZATION
- Parameterized complexity of global finite D quantizationOPEN-D-PARAMETERIZED-COMPLEXITY
- Exact bit complexity of the variable-dimension tilt-DP dualOPEN-DS-TILT-DUAL-EXACT-COMPLEXITY
- Quantitative E necessity bound under spectral gapOPEN-E-SPECTRAL-GAP-BOUND
- Stronger branch-and-bound upper boundsOPEN-STRONGER-BB
- Stronger local neighborhoodsOPEN-STRONGER-LOCAL-NEIGHBORHOODS
Local graph
Proof
G2. General concavity/supergradient screening
For a concave criterion , let be any supergradient at the current information matrix. For an exact finite relocation
concavity gives
Therefore:
- if the weighted tangent gain is , the exact move cannot improve;
- weighted-tangent stability is a sufficient certificate of one-point exchange stability;
- expensive exact move evaluation can be restricted to screened-in candidates.
This applies to D, , A, and E (using a supergradient for E).
Measured audit: zero screening-direction violations in the reported randomized suites (including 4,886 D/A/ moves and the E suite).