Manuscript Psy01-A@1 · Psy01-A.tex · theorem · 94477fa3

Theorem: Ranking stability after an update

Stability, hard-mask discontinuity, and schedule dependence › Nested pruning and a quantitative learning-induced defect · lines 1418–1460 · proof included or linked

Psy01-A@1#thm:ranking, Psy01-A@1#eq:rankingstable, Psy01-A@1#eq:rankingcoarse

Back to manuscript

Let $x = H_{K_{e}} (w)$ , let $y = x + u$ be an update that respects the early mask, and let $k \leq K_{e}$ . If the eligible magnitude gap at the late cutoff is

γ = \abs x_{(k)} - \abs x_{(k + 1)} > 0

and

2 \norm u_{\infty} < γ,

then the selected late support is unchanged and

\norm H_{k} (y) - H_{k} (x)_{2} \leq \norm u_{2} .

Without a gap assumption, the always valid estimate is

\norm H_{k} (y) - H_{k} (x)_{2} \leq 2 \norm u_{2} + 2 \norm x - H_{k} (x)_{2} .

Proof. For an originally retained position and an originally excluded position, the magnitude ordering can change by at most $2 \norm u_{\infty}$ . The gap condition preserves every cross-cutoff ordering. On the common support the difference is the projection of $u$ , proving (eq:rankingstable).

For the second inequality, $H_{k} (y)$ is a best $k$ -term Euclidean approximation among eligible coordinates, so

\norm y - H_{k} (y)_{2} \leq \norm y - H_{k} (x)_{2} \leq \norm u_{2} + \norm x - H_{k} (x)_{2} .

Use the triangle inequality between $H_{k} (y), y, x, H_{k} (x)$ .

Displayed formulas in this passage

unlabeled · line 1423
$γ = \abs x_{(k)} - \abs x_{(k + 1)} > 0$
unlabeled · line 1427
$2 \norm u_{\infty} < γ,$
Psy01-A@1#eq:rankingstable · line 1431
$\norm H_{k} (y) - H_{k} (x)_{2} \leq \norm u_{2} .$
Psy01-A@1#eq:rankingcoarse · line 1436
$\norm H_{k} (y) - H_{k} (x)_{2} \leq 2 \norm u_{2} + 2 \norm x - H_{k} (x)_{2} .$
unlabeled · line 1453
$\norm y - H_{k} (y)_{2} \leq \norm y - H_{k} (x)_{2} \leq \norm u_{2} + \norm x - H_{k} (x)_{2} .$

Theorem: Ranking stability after an update

Displayed formulas in this passage

Nearby in this section