ConvexOptimization

基本概念: 凸集合, 凸函数, 凹函数, 凸函数的一阶条件, 二阶条件, 保持凸性的数学操作(非负加权求和, 与仿射函数复合, 最大值或上确界), 对偶问题.

凸优化问题标准形式:
\begin{align}
\min_x\qquad & f_0(x)\\
s.t.\qquad & f_i(x)\leq0,\quad i=1,…,n\\
& a_i^Tx=b_i,\quad i=1,…,p
\end{align}
其中$f_0,f_1,…,f_n$是凸函数. 凸优化问题的任意一个局部最优解就是全局最优解.

凸优化最优解条件:
$$\nabla f_0(x^)^T(y-x^)\geq0,\quad\forall y\in\cal X$$
对于没有约束条件大的凸优化问题, 该条件可以退化为$\nabla f_0(x^*)=0$.

优化算法的收敛速率是和优化问题的性质密切相关, 对于一般的凸优化问题, 可以采用梯度下降达到$O(1/\sqrt T)$的收敛速率, 当函数为强凸时, 梯度下降的变种(epoch-GD)可以达到$O(1/T)$的收敛速率, 对于平滑函数, Nesterov的加速梯度下降可以达到$O(1/T^2)$的收敛速率, 当函数强凸且平滑时, 梯度下降可以达到线性收敛速率.

More info: Convex_optimization, Convex Optimization – Boyd and Vandenberghe

随机优化

样本平均近似(ERM)vs.随机近似(SGD)

完全信息在线学习

在线凸优化(OGD, ONS), OnlineToBatch

赌博机在线学习

多臂赌博机, 线性赌博机, 凸赌博机