凸函数：最小二乘，岭回归，逻辑回归…
更新规则：
w
i
+
1
=
w
i
−
α
i
d
f
d
w
(
w
i
)
w_{i+1} = w_i - α_i\frac{df}{dw}(w_i)
wi+1=wi−αidwdf(wi)
-dw : 斜率的负数，决定更新的方向
如果 -dw > 0 则往左走
如果 -dw < 0 则往右走
α ： 步长
公式推导：
Loss :
f
(
x
)
=
∣
∣
w
x
−
y
∣
∣
2
2
f(x) = ||wx - y||^2_2
f(x)=∣∣wx−y∣∣22
求导：
d
f
d
w
(
w
)
=
2
∣
∣
w
x
−
y
∣
∣
2
\frac{df}{dw}(w) = 2||wx-y||_2
dwdf(w)=2∣∣wx−y∣∣2
梯度更新：
w
i
+
1
=
w
i
−
α
∣
∣
w
x
−
y
∣
∣
w_{i+1} = w_i - α||wx -y||
wi+1=wi−α∣∣wx−y∣∣
α i = α n i α_i = \frac{α}{n\sqrt{i}} αi=niα
α : 常量
n : 训练集数量
i : iteration 迭代次数
随着迭代次数增加，步长越来越小。
w
i
+
1
=
w
i
−
α
i
∑
j
=
1
n
(
w
i
T
x
(
j
)
−
y
(
j
)
)
x
(
j
)
w_{i+1} = w_i - α_i\sum^n_{j=1}(w^T_ix^{(j)} - y^{(j)})x^{(j)}
wi+1=wi−αij=1∑n(wiTx(j)−y(j))x(j)
空间复杂度： O(nk)
随机样本计算梯度，如果全部样本都计算梯度，计算量过大
w
i
+
1
=
w
i
−
α
i
(
w
i
T
x
(
j
)
−
y
(
j
)
)
x
(
j
)
w_{i+1} = w_i - α_i(w^T_ix^{(j)} - y^{(j)})x^{(j)}
wi+1=wi−αi(wiTx(j)−y(j))x(j)
空间复杂度： O(k) 【取消了sum】
w
i
+
1
=
w
i
+
α
i
▼
f
j
(
w
i
)
w_{i+1} = w_i + α_i▼f_j(w_i)
wi+1=wi+αi▼fj(wi)
j 表示随机抽取的样本
w i + 1 = w i − α i ∑ j ∈ B n ( w i T x ( j ) − y ( j ) ) x ( j ) w_{i+1} = w_i - α_i\sum^n_{j∈B}(w^T_ix^{(j)} - y^{(j)})x^{(j)} wi+1=wi−αij∈B∑n(wiTx(j)−y(j))x(j)
只计算最小batch的梯度更新