Manuscript Psy03-A@1 · Psy03-A.tex · theorem · b30eb6e9

Theorem: Local loss descent under an explicit repair budget

What structural repair can and cannot guarantee › A signed sparse-gradient guarantee · lines 873–911 · proof included or linked

Psy03-A@1#thm:descent, Psy03-A@1#eq:descent

Back to manuscript

Let $L (w)$ be differentiable on a neighborhood containing the update segment, and let its gradient be $L_{g}$ -Lipschitz there. Let $I$ be the inactive-coordinate set and $g = \nabla L (w)$ . Among updates supported in $I$ , using at most $k$ coordinates and satisfying $\norm δ_{2} \leq ε$ , the largest possible first-order loss decrease is

ε \norm g_{S}_{2},

where $S$ contains the $k$ largest $\abs g_{i}$ , $i \in I$ . If $g_{S} \neq = 0$ , the signed update

δ = - ε \frac{g _{S}}{\norm g _{S} _{2}}

satisfies

L (w + δ) - L (w) \leq - ε \norm g_{S}_{2} + \frac{L _{g} ε ^{2}}{2} .

Thus it strictly decreases loss when $0 < ε < 2 \norm g_{S}_{2} / L_{g}$ , for $L_{g} > 0$ .

Proof. For each support $S^{'}$ ,

- g \cdot δ \leq \norm g_{S^{'}}_{2} \norm δ_{2} .

The top-magnitude support maximizes the squared gradient norm. The signed update attains the first-order bound. Integration of the Lipschitz gradient along the segment gives

L (w + δ) \leq L (w) + g \cdot δ + L_{g} \norm δ_{2}^{2} /2.

Substitute the selected update.

Displayed formulas in this passage

unlabeled · line 881
$ε \norm g_{S}_{2},$
unlabeled · line 886
$δ = - ε \frac{g _{S}}{\norm g _{S} _{2}}$
Psy03-A@1#eq:descent · line 890
$L (w + δ) - L (w) \leq - ε \norm g_{S}_{2} + \frac{L _{g} ε ^{2}}{2} .$
unlabeled · line 901
$- g \cdot δ \leq \norm g_{S^{'}}_{2} \norm δ_{2} .$
unlabeled · line 907
$L (w + δ) \leq L (w) + g \cdot δ + L_{g} \norm δ_{2}^{2} /2.$

Theorem: Local loss descent under an explicit repair budget

Displayed formulas in this passage

Nearby in this section