光滑非凸优化的复杂度下界
Published:
Paper Reading: Complexity of Finding Statonary Points in One Dimension.
已知，对于$L$-光滑函数，梯度下降法可以在 $O(L \Delta \epsilon^{-2})$ 迭代次数内寻找到一个 $\epsilon$-稳定点（定义为梯度范数小于 $\epsilon$的点）, 其中 $\Delta:= f(x_0) - \inf_x f(x)$ 为初始的次优间隙。本文我们希望证明一个匹配的下界，说明梯度下降法的结果即使对于一维函数也不可能改进。
不失一般性，我们可以假设 $x_0 = 0$, 否则可以将函数平移为 $\hat f(x) = f(x - x_0)$. 进一步，我们可以仅仅考虑 $\Delta = L = 1$ 的简单情况。 如果对于该简单情况我们构造函数 $f$ 证明 $\Omega(\epsilon^{-2})$ 的复杂度下界， 否则我们可以考虑 $\hat f(x) = \Delta f( \sqrt{L} x / \sqrt{\Delta})$，这样会给出一个 $\Omega(L \Delta \epsilon^{-2})$ 复杂度下界。
对于算法询问的所有点 $x_1,\cdots,x_N$, 如果 $N = O(\epsilon^{-2})$, 我们将构造一个函数, 使得所有询问点的导数都为 $-\epsilon$. 我们将在区间 $[0,\epsilon^{-1}]$ 上定义函数，然后周期性延拓到整个定义域。注意到算法询问点将区间 $[0,\epsilon^{-1}]$ 拆分为多个小区间，但是至少有 $\Omega(\epsilon^{-2})$ 个区间长度至少为 $\Omega(\epsilon)$, 对于这些区间我们可以构造简单的分段二次函数使得函数上升并且区间端点的导数值仍然为 $-\epsilon$. 最后使得函数满足约束 $f(x_0) - \inf_x f(x) \le 1$.
具体来说，对于这些长度为 $l_i = x_{i+1} - x_i = \Omega(\epsilon)$ 的区间 $[x_i,x_{i+1}]$, 我们构造如下的函数：
\[\begin{align*} \Phi_i(x) =& - \epsilon (x- x_i) \\ & + \begin{cases} \dfrac{1}{2} ( x-x_i)^2, & x \in [x_i, x_i + l_i/2], \\ \dfrac{l_i^2}{8} + \dfrac{l_i}{2}(x - x_i - l_i/2) - \dfrac{1}{2} (x - x_i - l_i/2)^2, & x \in [x_i + l_i/2, x_{i+1}]. \end{cases} \end{align*}\]简单来说，由于最大的曲率由形如 $x^2/2$ 的成分给出，这样的函数最大的光滑性系数不超过1。我们将区间 $[x_i,x_{i+1}]$ 分为两段构造，前半段为开头向上的函数，满足曲率为 $1/2$, 这样的函数也即 $- \epsilon (x- x_i) + (x - x_i)^2/2$. 而区间的后后半是前半段函数的对称，使得其开头向下，并且在连接区光滑相连。这样构造后，函数满足端点处导数值都为 $-\epsilon$, 也即 $\Phi_i’(x_i) = \Phi_i’(x_{i+1}) = -\epsilon$. 通过计算，端点处的函数值为 $\Phi_i(x_i) = 0$ 和 $\Phi_i(x_{i+1}) = l_i(l_i/4- \epsilon)$. 如果区间的长度小于 $O(\epsilon)$, 我们将不能构造上述的分段二次函数，我们则简单的构造斜率为 $-\epsilon$ 的线性函数。最后，我们的函数为
\[\begin{align*} f(x) = \begin{cases} 1 - \epsilon x , & x \in (-\infty,0]; \\ f(x_i) - \epsilon (x - x_i), & x \in [x_i,x_{i+1}] ~ {\rm and} ~ l_i < 8 \epsilon; \\ f(x_i) + \Phi_i(x), & x \in [x_i,x_{i+1}] ~ {\rm and} ~ l_i \ge 8 \epsilon; \\ \cdots, & x \in [1/\epsilon,+\infty]. \end{cases} \end{align*}\]上面的函数在区间 $[0,1/\epsilon]$ 间遵循我们前文说的方式构造，而x轴负半轴部分简单地设置为过 $(0,1)$ 的斜率为 $-\epsilon$ 的线性函数。而在区间 $[1/\epsilon,+\infty]$ 上继续按照类似的方式构造。这样构造出来的函数对于算法苏哦有的查询都返回了一个非稳定点，我们最后只需要验证函数满足约束条件。由于 $f(0) = 1$, 我们下面将证明 $f(x) \ge 0$, 合起来就说明函数满足约束 $f(0) - \inf_x f(x) \le 1$。为了说明这一点，我们只需要对于区间 $[0,1/\epsilon]$ 证明，当算法的查询点个数小于 $\epsilon^{-2}/32$ 的时候，存在着很多长度大于 $\Omega(\epsilon)$ 的区间，这些区间可以使得函数总体呈现上升趋势，使得 $f(1/\epsilon) \ge f(0)$.
注意到函数在小区间内都呈现单调下降，但是总体下降量不会超过 $1$, 因此 $f(x) \ge 0$. 我们下面说明，所有的大区间加起来可以使得函数值上升超过1，从而抵消小区间的下降效果。定义 $I$ 为所有区间索引集合 $i \in [N]$ 使得 $l_i \ge 8 \epsilon$. 如果算法的查询点的总数小于 $\epsilon^{-2}/32$, 那么小区间的总体长度不超过 $\epsilon^{-1}/4$。由于我们考虑 $[0,\epsilon^{-1}]$ 的区间范围，这意味着大区间的总长度至少为 $3\epsilon^{-1}/4$, 也即：
\[\begin{align*} \sum_{i \in I} l_i \ge \frac{3}{4 \epsilon}. \end{align*}\]注意到在每一个大区间内，函数的上升量为 $\Phi_i(x_{i+1}) = l_i(l_i/4 - \epsilon)$. 由于 $l_i \ge 8 \epsilon$ 以及 $\vert I \vert \le \epsilon^{-2}/32$, 我们知道总上升量不小于
\[\begin{align*} \sum_{i \in I} l_i (l_i/4 - \epsilon) \ge \frac{1}{8} \sum_{i \in I} l_i^2 \ge \frac{1}{8 \vert I \vert} \left( \sum_{i \in I} l_i \right)^2 \ge 1. \end{align*}\]这就完成了 $f(0) - \inf_x f(x) \le 1$ 的证明，说明了 $\Omega(\epsilon^{-2})$ 的复杂度下界。