《Data Cleansing for Models Trained with SGD》笔记

[1] 在其 appendix B 中证 Lemma 7 时说由于 $\left(1-{\eta }_s\Lambda \right)I\prec Z_s\prec \left(1-{\eta }_s\lambda \right)I$，直接可得 (7) 式，这里对 lemma 7 的证明做注。

[1] 中相关定义： h j ( Λ ) ≤ ∥ Δ θ − j ∥ ≤ h j ( λ ) ( 7 ) Δ θ − j : = η π ( j ) ∣ S π ( j ) ∣ Z T − 1 Z T − 2 ⋯ Z π ( j ) + 1 g ( z j ; θ [ π ( j ) ] ) ( a ) h j ( a ) : = η π ( j ) ∣ S π ( j ) ∣ ∏ s = π ( j ) + 1 T − 1 ( 1 − η s a ) ∥ g ( z j ; θ [ π ( j ) ] ) ∥ ( b ) Z t : = I − η t H [ t ] H [ t ] : = 1 ∣ S t ∣ ∑ i ∈ S t ∇ θ 2 ℓ ( z i ; θ [ t ] ) ( b a t c h 平均 H e s s i a n ) g ( z ; θ ) : = ∇ θ ℓ ( z ; θ ) ( 梯度 ) hj(Λ)≤‖Δθ−j‖≤hj(λ)(7)Δθ−j:=ηπ(j)|Sπ(j)|ZT−1ZT−2⋯Zπ(j)+1g(zj;θ[π(j)])(a)hj(a):=ηπ(j)|Sπ(j)|T−1∏s=π(j)+1(1−ηsa)‖g(zj;θ[π(j)])‖(b)Zt:=I−ηtH[t]H[t]:=1|St|∑i∈St∇2θℓ(zi;θ[t])(batch平均Hessian)g(z;θ):=∇θℓ(z;θ)(梯度)

Δθ−j​hj​(a)Zt​H[t]g(z;θ)​hj​(Λ)≤∥Δθ−j​∥≤hj​(λ):= ​Sπ(j)​ ​ηπ(j)​​ZT−1​ZT−2​⋯Zπ(j)+1​g(zj​;θ[π(j)]):= ​Sπ(j)​ ​ηπ(j)​​s=π(j)+1∏T−1​(1−ηs​a) ​g(zj​;θ[π(j)]) ​:=I−ηt​H[t]:=∣St​∣1​i∈St​∑​∇θ2​ℓ(zi​;θ[t]):=∇θ​ℓ(z;θ)​(7)(a)(b)(batch平均Hessian)(梯度)​ 其中（几个此处出现了但不用管的量）：

• $S_t$ 表示第 t 步优化（即训练、梯度下降）的 mini-batch；
• ${\eta }_t$ 是此步的 learning rate；
• $\pi (j)$ 表示 instance $z_j$ 出现的那个 step（lemma 7 是用来证 theorem 5 & 6 的，而它们都是在 1 epoch 的情景下，每个 instance 只出现一次）；
• T 是一个 epoch 的 step 数。

[1] 中三个假设：

1. loss 函数 $l(z;\theta )$ 二阶可导，即 Hessian 存在；
2. $\exists \lambda ,\Lambda >0$，对 $\forall z,\theta$，有 $\lambda I\prec {\nabla }_{\theta }^2\ell (z;\theta )\prec \Lambda I$
3. ${\eta }_s\le 1/\Lambda$

其中 $\prec$ 的含义文章没解释。经查，它用在向量上表示 majorization^[2]，但第二条假设是用在矩阵上。经 [3] 评论提醒，可能指 Loewner 偏序^[4]：

• $A\succ B$ 表示 $A-B$ 正定
• $A⪰B$ 则表示 $A-B$ 半正定

(半)正定阵的相关内容可参考 [5,6]。[4] 用 >、$\ge$ 表示正定、半正定，[6] 则用 $\succ ,⪰$。正定阵是 Hermitian 阵^[7]的特例，是对对称矩阵^[8]来谈的，而 Hessian 矩阵^[9]（二阶导）是对称矩阵。

解释 lemma 7 的证明要用到正定阵的几点性质。若 A、B 都正定，则：

• $\forall x\ne 0,x^{T}Ax>0$（正定阵定义）
• A + B、ABA、BAB 都正定，若 AB = BA，则 AB 也正定；
• $A\succ B\wedge B\succ C\Rightarrow A\succ C$（传递性，证明见 [6]）

因为 (7) 是在讨论向量范数，就考察当 $A\succ B\succ 0$，对 $\forall x\ne 0$，$\Vert Ax\Vert$ 与 $\Vert Bx\Vert$ 的大小关系。为方便，转成平方（假设是向量二范数）：

• $\Vert Ax{\Vert }^2=x^T{A}^{T}Ax=x^T{A}^{2}x$（A、B 都是对称阵）
• $\Vert Bx{\Vert }^2=x^T{B}^{2}x$

那么： ∥ A x ∥ 2 − ∥ B x ∥ 2 = x T A 2 x − x T B 2 x = x T ( A 2 − B 2 ) x = x T ( A + B ) ( A − B ) x ‖Ax‖2−‖Bx‖2=xTA2x−xTB2x=xT(A2−B2)x=xT(A+B)(A−B)x

∥Ax∥2−∥Bx∥2​=xTA2x−xTB2x=xT(A2−B2)x=xT(A+B)(A−B)x​ 由前面正定阵性质：

• 因 A、B 都正定，所以 A + B 也正定；
• 条件已知 A - B 正定（$A\succ B$）；
• 因 (A + B)(A - B) = (A - B)(A + B) = $A^2-B^2$，所以 (A + B)(A - B) 也是正定。

所以 $\Vert Ax{\Vert }^2-\Vert Bx{\Vert }^2=x^T(A+B)(A-B)x>0$。这说明 $A\succ B\succ 0$ 的直观意义是 A 对向量的拉伸效果比 B 好，拉伸同一个向量 x，A 拉完比 B 拉完的向量范数更大（模更大，向量更长）。

有这个直观解释后回看 (7) 式证明。对比前面 $\Delta {\theta }_{-j}$ 和 $h_j(\cdot )$ 的定义（前文 (a)、(b) 式）可知 $h_j(\cdot )$ 是照着 $\Delta {\theta }_{-j}$ 的形式构造的，$h_j(\lambda )$ 就相当于把 $\Delta {\theta }_{-j}$ 中的各 $Z_s$ 换成相应的 $(1-{\eta }_s\lambda )I$ 再取范数。
∵ ∃ λ , Λ > 0 , ∀ z , θ , λ I ≺ ∇ θ 2 ℓ ( z ; θ ) ≺ Λ I H [ s ] : = 1 ∣ S s ∣ ∑ i ∈ S s ∇ θ 2 ℓ ( z i ; θ [ s ] ) ∴ λ I ≺ H [ s ] ≺ Λ I ∴ ( 1 − η s Λ ) I ≺ Z s = I − η s H [ s ] ≺ ( 1 − η s λ ) I ( c ) ∵\existλ,Λ>0,∀z,θ,λI≺∇2θℓ(z;θ)≺ΛIH[s]:=1|Ss|∑i∈Ss∇2θℓ(zi;θ[s])∴λI≺H[s]≺ΛI∴(1−ηsΛ)I≺Zs=I−ηsH[s]≺(1−ηsλ)I(c)

∵∴∴​∃λ,Λ>0,∀z,θ,λI≺∇θ2​ℓ(z;θ)≺ΛIH[s]:=∣Ss​∣1​i∈Ss​∑​∇θ2​ℓ(zi​;θ[s])λI≺H[s]≺ΛI(1−ηs​Λ)I≺Zs​=I−ηs​H[s]≺(1−ηs​λ)I​(c)​ 因为 $\forall x\ne 0,x^{T}Ix=x^{T}x>0$，所以单位阵 $I$ 正定；由前面第 3 条假设，$1-{\eta }_s\Lambda >0$，故 $x^T(1-{\eta }_s\Lambda )Ix>0$，所以 $(1-{\eta }_s\Lambda )I$ 正定；再由 ©，$Z_s$、$(1-{\eta }_s\lambda )I$ 都正定（传递性），于是可以套上面的直观解释：对向量的拉伸能力 $(1-{\eta }_s\Lambda )I$ 弱于 $Z_s$ 弱于 $(1-{\eta }_s\lambda )I$，所以同样是对 $g(z_j;{\theta }^{[s]})$ 进行（一系列）拉伸，再取范数，再带上前面的正常系数 $\frac{{\eta }_{\pi (j)}}{|S_s|}$，可得 (7)。

[10] 讲的文章也有用到 Loewner 偏序，且跟 [1] 是相关的文章。

References

1. (NIPS 2019) Data Cleansing for Models Trained with SGD - paper, code
2. Majorization
3. 矩阵论记号约定
4. Loewner order
5. 正定矩阵，正定矩阵
6. 半正定矩陣的偏序關係
7. Hermitian matrix
8. 对称矩阵，对称矩阵
9. Hessian matrix
10. 《Understanding Black-box Predictions via Influence Functions》笔记