高阶凸优化的复杂度下界简证
Published:
Paper Reading: Oracle Complexity of Second-Order Methods for Smooth Convex Optimization.
在上一期blog中，我们介绍了一个 $p$阶算法，可以对于凸优化问题取得 $\mathcal{O}(\epsilon^{-2/(3p+1)})$ 的收敛率。在本文我们进一步证明一个下界，说明这个结果是不可改进的。
我们曾经在很早之前 介绍过 一阶算法的最优复杂度下界, 为 $\Omega(\epsilon^{-1/2})$. 本文的结果事实上推广了上述构造，得到一个 $\Omega(\epsilon^{-2/(3p+1)})$ 的下界。
用 $x_{[i]}$ 来表示向量 $x$ 的第 $i$ 个坐标分量。对于任意给定的迭代次数 $T$, 我们考虑如下 $f_T: R^T \rightarrow R$ 的 函数
\[\begin{align*} f_T(x) = \frac{1}{T^{3 (p+1)/2}} \left( \frac{1}{p+1}\left( \sum_{i=1}^{T-1} \left \vert (x_{[i]} - x_{[i-1]}) T^{3/2} \right \vert^{p+1} + \left \vert x_{[T]} T^{3/2} \right \vert^{p+1} \right) - T^{3/2} x_{[1]} \right) \end{align*}\]容易验证该函数是凸的，而且 $p$ 阶导数应该满足 $\mathcal{O}(1)$-Lipschitz 连续。换元，令
\[\begin{align*} y = T^{3/2} (x_{[1]} - x_{[2]}, x_{[2]} - x_{[3]}, \cdots, x_{[T]} ). \end{align*}\]求导并且令其等于0。我们知道最优点处的 $y^\ast$ 应该为全 $1$ 向量。因此， $x^\ast$ 应该满足如下公差为 $-1$ 的等差数列
\[\begin{align*} x^\ast = (T, T-1, \cdots, 1) / T^{3/2}. \end{align*}\]注意到最小点 $x^\ast$ 满足条件 $\Vert x^\ast \Vert = \mathcal{O}(1)$. 并且代入后可以得到函数的极小值为
\[\begin{align*} f_{T}^\ast = \frac{1}{T^{3 (p+1)/2}} \left( \frac{T}{p+1} - T \right) = - \frac{(p-1)}{(p+1)T^{(3p+1)/2}}. \end{align*}\]对于任意从 $0$ 出发的进行不超过 $T$ 次迭代的 $p$ 阶算法，我们考虑将其优化函数 $f_{2T}$. 注意到由于函数的链式构造 （也即仅有相邻两个坐标相连），进行张量步运算的 $p$ 阶算法每次只能激活至多一个坐标（也即将一个新的坐标从零值变为非零值）。进行 $T$ 次迭代以内，由于从 $T+1$ 开始的坐标都为 $0$, 算法至多能取得与优化函数 $f_T$ 一样的效果，那么函数算法返回的点 $\hat x$ 成立
\[\begin{align*} f_{2T}(\hat x) - f_{2T}^\ast \ge f_T^\ast - f_{2T}^\ast = \Omega( T^{-(3p+1)/2} ). \end{align*}\]证毕。