Train Faster, generalize better, Stability of stochastic gradient descent

Moritz Hardt, Benjamin Recht, Yoram Singer

Intro

我们的一个point是，任意一个模型如果使用SGM，都能在可以理解的时间范围内，达到非常小的generalization error。

存在某个位置的分布D over samples from some space Z。我们收到一个sample $$S=(z_1, ..., z_n)$$，从D中iid得到。目标是找到一个模型，能够得到非常小的risk

$$R[w] = \mathcal{E}_{z \sim D} f(w; z)$$

f是loss。

因为没法观测到真实的risk，所以使用sample-averaged proxy，也就是empirical risk

$$RS = \frac{1}{n} \sum{i=1}^n f(w; z_j)$$

当$$w=A(S)$$是被选作在data上的一个函数，而函数是randomized algorithm $$A$$，那么可以合理的考虑expected generalization error为

$$\epsilon{gen} = \mathbb{E}{S,A} [R_S[A(S)] - R[A(S)] ]$$