2025.1.9 学习内容

《机器学习理论引导》第7章

• 基本概念（迭代优化算法，收敛率和迭代复杂度等价衡量算法性能）

• 确定优化：梯度下降

1.一般凸优化问题（凸函数）-收敛率 $O(1/T)$；

2.光滑强凸函数（任意点可构造一个二次函数作为上界）-收敛率 $O(1/{\beta}^T)$ 其中$\beta$>1 .

• 随机优化：随机梯度下降（相比于梯度下降，其不需要计算每一步$\nabla f(\omega)$的真实值，而是通过随机采样获得一个无偏估计值$g_t$）

1.凸函数-收敛率 $O(1/\sqrt{T})$；

2.$\lambda$强凸函数-阶段随机梯度下降-收敛率 $O(1/[{\lambda}T])$；

ps. 随机优化（SGD）每次迭代只需要处理一个或少量样本数据，适用于大规模数据集。随机优化里面的证明有点复杂，得再多看几遍，自己推导一下。

ps. 1. SGD中：随机梯度 $g_t$ 是梯度的无偏估计值即 $\mathbb{E}[g_t] = \nabla f(w_t)$；收敛目标是使得 $f(\bar{w}_T) \to f(w^*)$，误差减小到 $O(1/\sqrt{T})$；通过设定学习率 $\eta$，控制每一步如何利用当前梯度估计更新 $w_t$ 2. Bandit 中：奖励 $r(a)$ 是动作真实奖励的随机估计值即$\mathbb{E}[r(a)] = \mu(a)$，$\mu(a)$ 是真实期望奖励；收敛目标是使累积后悔 $\mathbb{E}[\text{Regret}_T]$ 控制在如$O(\sqrt{T})$ 这样的量级；利用如置信区间宽度控制探索与利用的平衡。

寻找收敛率的核心数学工具：Jensen 不等式、Hoeffding 不等式