随机一阶凸优化的复杂度下界
Published:
Paper Reading: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization
考虑随机凸优化问题
\[\begin{align*} \min_{x \in S} f(x). \end{align*}\]其中我们可以得到 $\nabla f(x)$ 的一个随机梯度估计，称为Oracle，我们希望知道需要多少Oracle的调用次数可以求解该问题。本文从信息论的角度出发，将其看出一个从观测到参数估计的问题，利用信息论的基本工具证明问题的复杂度下界。
Tools from Information Theory
为了本文的完备性，介绍一些信息论中的工具。
首先是Fano不等式，下面是并非最原始的紧的版本，但对于本文的证明已经足够。
假设 $X$ 服从于 $\mathcal{X}$ 上的均匀分布，给定一个马尔科夫链 $X \rightarrow Y \rightarrow \hat X $, 成立
\[\mathbb{P}(\hat X \ne X) \ge 1 - \frac{I(X;Y) + \log 2}{\log \vert \mathcal{X} \vert}.\]这说明如果 $X$ 和 $Y$ 的互信息不够大，将不能恢复出 $X$.
下一个工具是Gilbert-Varshamov bound，给出 $d$ 维超立方体中关于$l_1$ 距离的packing number。
对于 $d$ 维的超立方体 ${ 1,-1}^d$, 存在一个子集 $\mathcal{V}$, 其大小满足 $\vert \mathcal{V} \vert \ge \exp(d/8)$, 且该集合中的点都满足 $\Vert v - v’ \Vert_1 \ge d/2, \forall v,v’ \in \mathcal{V}$.
Lower Bound Constructions
Fano不等式给出了Testing 问题的下界，我们希望将优化问题转化为Testing问题。
我们定义函数的间隔为
\[\begin{align*} \rho(f,g) = \inf_{x \in S} [f(x) + g(x) - f^\ast - g^\ast]. \end{align*}\]我们构造一个packing $\mathcal{V}$, 对于集合中的每一个点 $v$, 构造一个函数 $f_v$, 这个函数集的最小间隔定义为 $ \rho = \inf_{v,v’ \in \mathcal{V}} \rho (f_v(x), f_{v’}(x))$.
根据定义，如果一个点 $x$ 为某个函数 $f$ 的 $\rho/3$-近似最优点，那么它将不可能是这个函数集中的其他函数的近似最优解：
\[\begin{align*} \rho \le f(x) - f^\ast + g(x) - g^\ast \le \frac{\rho}{3} + g(x) - g^\ast. \end{align*}\]我们取估计 $\hat v$ 为最优间隔最小的对应函数的下标，如果优化器能够有效地优化函数使得 $\mathbb{E}[f(x) - f^\ast] \le \rho /9$. 那么
\[\begin{align*} \mathbb{P} (\hat v \ne v) \le \mathbb{P}(f_{v}(x) - f_v^\ast \ge \rho/3) \le \frac{\mathbb{E}[f_v(x) - f_v^\ast]}{\rho /3} \le \frac{1}{3}. \end{align*}\]这可以保证错误率不超过 $1/3$.
下面我们定义困难函数，形如
\[\begin{align*} f_v(x) = \frac{1}{d} \sum_{i=1}^d \left( \frac{1}{2} + v_i \delta \right) f^+(x_i) + \left( \frac{1}{2} - v_i \delta \right) f^-(x_i). \end{align*}\]而随机梯度定义的方式是，首先从均匀分布中选择一个下标 $i$, 然后定义伯努利分布 $b_i \sim {\rm Ber}(0.5 + v_i \delta)$, 随机梯度为如下函数的梯度
\[\begin{align*} F_v(x) = b_i f^+(x_i) + (1-b_i) f^-(x_i). \end{align*}\]当满足 $\vert \partial f^+(x_i) / \partial x_i \vert \le 1$ 以及 $\vert \partial f^-(x_i) / \partial x_i \vert \le 1$ 的时候我们知道所给的随机函数为Lipschitz函数。
假定我们想要估计的参数为 $v^\ast$, 我们观测到了 $T$ 个随机变量，我们定义为 $(Y_t,U_t)$, 其中 $U_t$ 表示选择的随机下标， $Y_t$ 表示选择的随机伯努利变量。我们知道给定随机变量 ${(U_t,Y_t) }_{t=1}^{T}$ 之后，利用所给的优化器，我们选择优化其产生的 $f_v(x_T) - f_v(x_0)$ 最小的小标 $v$ 作为对真实参数的估计，这是一个从随机变量到估计的确定性函数，根据Fano不等式我们知道预测的错误率取决于packing set $\mathcal{V}$ 的大小以及互信息 $I(U_t,Y_t;v^\ast)$. 我们的packing set的大小根据Gilbert-Varshamov bound选取最大的大小，下面我们关注于处理互信息这一项。
首先根据每次 $t$ 之间的独立性，我们知道最终的互信息为每一时间点的互信息的 $T$ 倍。
我们知道 $U_t$ 与 $v^\ast$ 相互独立
\[\begin{align*} I(U_t,Y_t; v^\ast) &= I( Y_t; v^\ast \mid U_t) \\ &= \mathbb{E}_U [ {\rm KL}( \mathbb{P}_{Y,v^\ast \mid U} \Vert \mathbb{P}_{Y \mid U} \times \mathbb{P}_{v^\ast \mid U} )] \\ &= \mathbb{E}_U [ {\rm KL} (\mathbb{P}_{Y\mid v^\ast, U}\Vert \mathbb{P}_{Y \mid U}) ] \\ &\le \frac{1}{\vert \mathcal{V} \vert} \sum_{v \in \mathcal{V}} \mathbb{E}_U [{\rm KL} (\mathbb{P}_{Y \mid v^\ast, U} \Vert \mathbb{P}_{Y \mid v, U})] \\ &\le {\rm KL} ({\rm Ber}(0.5 + \delta) \Vert {\rm Ber}(0.5- \delta) ) \\ &\le 16 \delta^2, \end{align*}\]当 $\delta \le 1/4$ 时， 代入Fano不等式我们得到估计
\[\begin{align*} \mathbb{P} (\hat v \ne v) \ge 1 - \frac{16 T \delta^2 + \log 2}{d / 8}. \end{align*}\]因此当成功分辨出真实参数 $v^\ast$ 所需要的观测数目 $T = \Omega (d / \delta^2)$.
Convex Case
基于上述的证明框架，我们给出凸优化的结果。定义
\[\begin{align*} f^+(x_i) = \vert x_i - 0.5 \vert, \quad f^-(x) = \vert x_i + 0.5 \vert. \end{align*}\]对于这样所给出的函数 $f_v(x)$，容易验证其最小值点在 $x = 0.5 v$ 的时候取到，最小值为 $ 0.5 - \delta$.
我们选取 $S = { x \mid \Vert x \Vert_{\infty} \le 0.5 }$, 该集合 $S$ 包含了函数最小值。
下面计算分隔, 对于任意的 $v,v’ \in \mathcal{V}$,
\[\begin{align*} \rho(f_v, f_{v'}) & = \inf_{x \in S} [f(x) + g(x) - f^\ast - g^\ast] \\ &= \inf_{x \in S} \frac{1}{d} \sum_{i=1}^d \left( 1 + v_i \delta + v'_i \delta \right) f^+(x_i) + (1- v_i \delta -v_i' \delta) f^-(x_i) - (1- 2 \delta) \\ &= \inf_{x \in S} \frac{1}{d} \sum_{i: v_i \ne v_i'}^d (f^+(x_i) + f^-(x_i)) - (1- 2\delta) \\ &\ge \delta / 2. \end{align*}\]这就是说，如果优化器找到 $\epsilon$-最优解所需要的观测下界为 $\Omega(d \epsilon^{-2})$.
上述得到的Rate是紧的，由于可以被随机梯度下降达到。
值得注意的是，上述函数即使得到高阶导数，由于得到的信息并没有变多，仍然不可能改进上述界。
Strongly Convex Case
对于强凸函数，我们只需要将一次函数改为如下的二次函数：
\[\begin{align*} f^+(x_i) = (x_i - 0.5)^2, \quad f^-(x) = (x_i + 0.5)^2. \end{align*}\]对于这样所给出的函数 $f_v(x)$，容易验证其最小值点在 $x = \delta v$ 的时候取到，最小值为 $ 2 \delta (\delta+0.5) (\delta-0.5)$.
我们选取 $S = { x \mid \Vert x \Vert_{\infty} \le 0.5 }$, 该集合 $S$ 包含了函数最小值。
下面计算分隔, 对于任意的 $v,v’ \in \mathcal{V}$,
\[\begin{align*} \rho(f_v, f_{v'}) & = \inf_{x \in S} [f(x) + g(x) - f^\ast - g^\ast] \\ &= \inf_{x \in S} \frac{1}{d} \sum_{i=1}^d \left( 1 + v_i \delta + v'_i \delta \right) f^+(x_i) + (1- v_i \delta -v_i' \delta) f^-(x_i) - 2 (0.5 + \delta) (0.5- \delta) \\ &= \inf_{x \in S} \frac{1}{d} \sum_{i: v_i \ne v_i'}^d (f^+(x_i) + f^-(x_i)) - 2 (0.5 + \delta) (0.5- \delta) \\ &\ge \delta^2 / 2. \end{align*}\]这就是说，如果优化器找到 $\epsilon$-最优解所需要的观测下界为 $\Omega(d \epsilon^{-1})$.
但值得注意的是，上述函数的强凸系数为 $1/d$, 因此如果笔者理解准确的话，似乎并不能直接claim上述的rate是紧的。