Result · SOFT-ASSIGNMENT-GRADIENT

Soft assignments have an exact gradient

Proved herepublication: internal

Meaning

An exact gradient supports optimization of the randomized-assignment information objective.

Statement

For differentiable F with G=∇F(I_soft), ∂F/∂r_ib=w_i(2 s_i^T G μ_b-μ_b^T G μ_b), equivalent up to a bin-independent term to negative squared G-distance.

Relationships

Rests on

Soft assignments are an actual randomized quantizerSOFT-RANDOMIZED-FIM

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
Stronger branch-and-bound upper boundsOPEN-STRONGER-BB
Stronger local neighborhoodsOPEN-STRONGER-LOCAL-NEIGHBORHOODS

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

S2. Exact soft-assignment gradient

For differentiable $F$ , $G=\nabla F(I_{\rm soft})$ ,

\boxed{ \frac{\partial F}{\partial r_{ib}} =w_i(2s_i^\top G\mu_b-\mu_b^\top G\mu_b). }

Up to a bin-independent term this is negative squared $G$ -distance to the centroid.

From Randomized and soft quantizers · chapter contents