Run this notebook online: or Colab:

# 11.4. 随机梯度下降¶

%load ../utils/djl-imports


## 11.4.1. 随机梯度更新¶

(11.4.1)$f(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n f_i(\mathbf{x}).$

$$\mathbf{x}$$的目标函数的梯度计算为

(11.4.2)$\nabla f(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\mathbf{x}).$

(11.4.3)$\mathbf{x} \leftarrow \mathbf{x} - \eta \nabla f_i(\mathbf{x}),$

(11.4.4)$\mathbb{E}_i \nabla f_i(\mathbf{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\mathbf{x}) = \nabla f(\mathbf{x}).$

NDManager manager = NDManager.newBaseManager();

// Sample once from a normal distribution
public float getRandomNormal(float mean, float sd) {
return manager.randomNormal(mean, sd, new Shape(1), DataType.FLOAT32).getFloat();
}

float eta = 0.01f;
Supplier<Float> lr = () -> 1f; // Constant Learning Rate

BiFunction<Float, Float, Float> f = (x1, x2) -> x1 * x1 + 2 * x2 * x2; // Objective

BiFunction<Float, Float, Float[]> gradf = (x1, x2) -> new Float[]{2 * x1, 4 * x2}; // Gradient

Function<Float[], Float[]> sgd = (state) -> {
Float x1 = state[0];
Float x2 = state[1];
Float s1 = state[2];
Float s2 = state[3];

Float g1 = g[0];
Float g2 = g[1];

g1 += getRandomNormal(0f, 0.1f);
g2 += getRandomNormal(0f, 0.1f);
Float etaT = eta * lr.get();
return new Float[]{x1 - etaT * g1, x2 - etaT * g2, 0f, 0f};
};


Tablesaw not supporting for contour and meshgrids, will update soon


Fig. 11.4.1 Contour Gradient Descent with Constant Learning Rate.

## 11.4.2. 动态学习率¶

(11.4.5)\begin{split}\begin{aligned} \eta(t) & = \eta_i \text{ if } t_i \leq t \leq t_{i+1} && \text{分段常数} \\ \eta(t) & = \eta_0 \cdot e^{-\lambda t} && \text{指数衰减} \\ \eta(t) & = \eta_0 \cdot (\beta t + 1)^{-\alpha} && \text{多项式衰减} \end{aligned}\end{split}

int ctr = 1;

Supplier<Float> exponential = () -> {
ctr += 1;
return (float)Math.exp(-0.1 * ctr);
};

lr = exponential; // Set up learning rate

Tablesaw not supporting for contour and meshgrids, will update soon


Fig. 11.4.2 Contour Gradient Descent with Exponential Learning Rate.

int ctr = 1;

Supplier<Float> polynomial = () -> {
ctr += 1;
return (float)Math.pow(1 + 0.1 * ctr, -0.5);
};

lr = polynomial; // Set up learning rate

Tablesaw not supporting for contour and meshgrids, will update soon


Fig. 11.4.3 Contour Gradient Descent with Polynomial Learning Rate.

## 11.4.3. 凸目标的收敛性分析¶

(11.4.6)$\mathbf{x}_{t+1} = \mathbf{x}_{t} - \eta_t \partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x}),$

(11.4.7)$R(\mathbf{x}) = E_{\boldsymbol{\xi}}[f(\boldsymbol{\xi}, \mathbf{x})]$

(11.4.8)\begin{split}\begin{aligned} &\|\mathbf{x}_{t+1} - \mathbf{x}^*\|^2 \\ =& \|\mathbf{x}_{t} - \eta_t \partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x}) - \mathbf{x}^*\|^2 \\ =& \|\mathbf{x}_{t} - \mathbf{x}^*\|^2 + \eta_t^2 \|\partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x})\|^2 - 2 \eta_t \left\langle \mathbf{x}_t - \mathbf{x}^*, \partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x})\right\rangle. \end{aligned}\end{split}

(11.4.9)$\eta_t^2 \|\partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x})\|^2 \leq \eta_t^2 L^2.$

(11.4.10)$f(\boldsymbol{\xi}_t, \mathbf{x}^*) \geq f(\boldsymbol{\xi}_t, \mathbf{x}_t) + \left\langle \mathbf{x}^* - \mathbf{x}_t, \partial_{\mathbf{x}} f(\boldsymbol{\xi}_t, \mathbf{x}_t) \right\rangle.$

(11.4.11)$\|\mathbf{x}_{t} - \mathbf{x}^*\|^2 - \|\mathbf{x}_{t+1} - \mathbf{x}^*\|^2 \geq 2 \eta_t (f(\boldsymbol{\xi}_t, \mathbf{x}_t) - f(\boldsymbol{\xi}_t, \mathbf{x}^*)) - \eta_t^2 L^2.$

(11.4.12)$E\left[\|\mathbf{x}_{t} - \mathbf{x}^*\|^2\right] - E\left[\|\mathbf{x}_{t+1} - \mathbf{x}^*\|^2\right] \geq 2 \eta_t [E[R(\mathbf{x}_t)] - R^*] - \eta_t^2 L^2.$

(11.4.13)$\|\mathbf{x}_1 - \mathbf{x}^*\|^2 \geq 2 \left (\sum_{t=1}^T \eta_t \right) [E[R(\mathbf{x}_t)] - R^*] - L^2 \sum_{t=1}^T \eta_t^2.$

(11.4.14)$\bar{\mathbf{x}} \stackrel{\mathrm{def}}{=} \frac{\sum_{t=1}^T \eta_t \mathbf{x}_t}{\sum_{t=1}^T \eta_t}.$

(11.4.15)$E\left(\frac{\sum_{t=1}^T \eta_t R(\mathbf{x}_t)}{\sum_{t=1}^T \eta_t}\right) = \frac{\sum_{t=1}^T \eta_t E[R(\mathbf{x}_t)]}{\sum_{t=1}^T \eta_t} = E[R(\mathbf{x}_t)],$

(11.4.16)$\sum_{t=1}^T \eta_t E[R(\mathbf{x}_t)] \geq \sum_{t=1}^T \eta_t E\left[R(\bar{\mathbf{x}})\right].$

(11.4.17)$\left[E[\bar{\mathbf{x}}]\right] - R^* \leq \frac{r^2 + L^2 \sum_{t=1}^T \eta_t^2}{2 \sum_{t=1}^T \eta_t},$

## 11.4.4. 随机梯度和有限样本¶

(11.4.18)$P(\mathrm{choose~} i) = 1 - P(\mathrm{omit~} i) = 1 - (1-1/n)^n \approx 1-e^{-1} \approx 0.63.$

(11.4.19)${n \choose 1} \frac{1}{n} \left(1-\frac{1}{n}\right)^{n-1} = \frac{n}{n-1} \left(1-\frac{1}{n}\right)^{n} \approx e^{-1} \approx 0.37.$

## 11.4.5. 小结¶

• 对于凸问题，我们可以证明，对于广泛的学习率选择，随机梯度下降将收敛到最优解。

• 对于深度学习而言，情况通常并非如此。但是，对凸问题的分析使我们能够深入了解如何进行优化，即逐步降低学习率，尽管不是太快。

• 如果学习率太小或太大，就会出现问题。实际上，通常只有经过多次实验后才能找到合适的学习率。

• 当训练数据集中有更多样本时，计算梯度下降的每次迭代的代价更高，因此在这些情况下，首选随机梯度下降。

• 随机梯度下降的最佳性保证在非凸情况下一般不可用，因为需要检查的局部最小值的数量可能是指数级的。

## 11.4.6. 练习¶

1. 尝试不同的随机梯度下降学习率计划和不同的迭代次数进行实验。特别是，根据迭代次数的函数来绘制与最佳解$$(0, 0)$$的距离。

2. 证明对于函数$$f(x_1, x_2) = x_1^2 + 2 x_2^2$$而言，向梯度添加正常噪声等同于最小化损失函数$$f(\mathbf{x}, \mathbf{w}) = (x_1 - w_1)^2 + 2 (x_2 - w_2)^2$$，其中$$\mathbf{x}$$是从正态分布中提取的。

3. 比较随机梯度下降的收敛性，当你从$$\{(x_1, y_1), \ldots, (x_n, y_n)\}$$使用替换方法进行采样时以及在不替换的情况下进行采样时

4. 如果某些梯度（或者更确切地说与之相关的某些坐标）始终比所有其他梯度都大，你将如何更改随机梯度下降求解器？

5. 假设是$$f(x) = x^2 (1 + \sin x)$$$$f$$有多少局部最小值？你能改变$$f$$以尽量减少它需要评估所有局部最小值的方式吗？