Result · GENERAL-SUPERGRADIENT-SCREENING

One supergradient principle screens moves safely

Proved herepublication: internal

Read the proof and evidence →

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

Local graph
Local map of Concavity/supergradient finite-move screening1 prerequisites to the left, 5 results it enables or questions it raises to the right, 0 boundary cases below.Exact weighted rank-two relocationExact weighted rank-t…Safe A tangent screeningSafe A tangent screen…Safe D tangent screeningSafe D tangent screen…Safe Ds tangent screeningSafe Ds tangent scree…Safe E supergradient screeningSafe E supergradient…Weighted tangent stability implies exchange stabilityWeighted tangent stab…Concavity/supergradient finite-move screeningConcavity/supergradie…
Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

G2. General concavity/supergradient screening

For a concave criterion FF, let GG be any supergradient at the current information matrix. For an exact finite relocation

ΔI=αuaua⊤−βubub⊤,\Delta I=\alpha u_au_a^\top-\beta u_bu_b^\top,

concavity gives

ΔF≤tr⁡(GΔI)=αua⊤Gua−βub⊤Gub.\boxed{ \Delta F \le \operatorname{tr}(G\Delta I) = \alpha u_a^\top Gu_a- \beta u_b^\top Gu_b. }

Therefore:

  • if the weighted tangent gain is ≤0\le0, 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, DsD_s, A, and E (using a supergradient for E).

Measured audit: zero screening-direction violations in the reported randomized suites (including 4,886 D/A/DsD_s moves and the E suite).


From First-order and finite screening · chapter contents