随机一阶凸优化的复杂度下界
Published:
Paper Reading: Information-Based Complexity, Feedback and Dynamics in Convex Programming [TIT’11]
考虑随机凸优化问题
\[\begin{align*} \min_{x \in S} f(x). \end{align*}\]其中我们可以得到 $\nabla f(x)$ 的一个随机梯度估计，称为Oracle，我们希望知道需要多少Oracle的调用次数可以求解该问题。本文从信息论的角度出发，将其看出一个从观测到参数估计的问题，利用信息论的基本工具证明问题的复杂度下界。
我们将一个算法流程定义为和Oracle的交互过程，每次算法根据所有的历史信息采用一个确定性映射询问点 $X_t$, 然后Oracle会返回对应的随机梯度记作为 $Y_t$. 这样算法运行 $T$ 步后产生了一个随机序列 $(X_1,Y_1,\cdots,X_T,Y_T)$. 对于随机一阶算法，我们限制Oracle满足无偏性以及方差有界性，也即
\[\begin{align*} \mathbb{E}[Y_t \vert X_t] = \nabla f(X_t), \quad {\rm and} \quad \mathbb{E} [ \Vert Y_t - \nabla f(X_t) \Vert^2 \vert X_t ] \le \sigma^2. \end{align*}\]Tools from Information Theory
为了本文的完备性，介绍一些信息论中的工具。
Fano’s Inequality
首先是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
下一个工具是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}$.
Reduction to Hypothesis Testing
下界证明的一个核心的思路是将优化问题规约为一个假设检验问题，然后利用信息论/统计中已有的工具给出紧的下界。我们会定义一列函数 ${ f_0, \cdots, f_{N-1} }$, 说明一个好的优化算法需要可以在给定的复杂度内辨识出对应的函数。
“好”的算法定义为，对于任意一个函数，都可以以概率至少 $1-\delta$ 确保输出一个解$\epsilon$-近似解 $X_{T+1}$ 满足 $f(X_{T+1}) - f^\ast \le \epsilon$, 其中 $f^\ast := \min_{x \in S} f(x)$.
我们希望我们构造的函数列尽可能难以辨识。这里“难”辨识定义为函数在空间内的距离应该尽量大，使得算法一旦优化了函数1，就难以优化函数2. 为了数学上进行刻画，我们需要为函数配备一个距离 $d(\cdot,\cdot)$ 满足
\[\begin{align*} d(f,g) \ge 2 \epsilon ~~ {\rm and} ~~ f(x) - f^\ast < \epsilon \Longrightarrow g(x) - g^\ast > \epsilon. \end{align*}\]环境每次在算法运行之前为预先均匀地选择函数 $i \in {0,\cdots,N-1 }$. 我们将这个随机变量定义为 $M$, 我们的目的是把 $M$ 恢复出来。 我们定义下面这个自然的估计量
\[\begin{align*} \hat M_T(X_1,Y_1,\cdots,X_T,Y_T, X_{T+1}) = \arg \min_{i = 0,\cdots,N-1} f_i(X_{T+1}) - f_i^\ast. \end{align*}\]定义好了所需要的所有的准备内容后，我们下面的引理说的是: 如果我们构造出的函数列满足
\[\begin{align*} d(f_i,f_j) \ge 2 \epsilon, \quad \forall i \ne j. \end{align*}\]那么
\[\begin{align*} I(M;\hat M_T) \ge (1- \delta) \log N - \log 2, \end{align*}\]其中 $I(M;\hat M_T)$ 为估计量与真实值之间的互信息。我们并不给出证明，因为事实上该结果可以用Fano不等式直接得到。
Information Bounds
本节我们给出算法运行 $T$ 步后关于互信息的上界，这样结合上一节的结果就可以给出复杂度下界。
出于方便我们定义 $X_{1:t} = (X_1,\cdots,X_t)$.注意到 $\hat M_T$ 是关于 $(X_{1:T},Y_{1:T})$ 的确定性映射，根据数据处理不等式以及KL散度/互信息的链式法则，我们可以得到
\[\begin{align*} I(M;\hat M_T) \le \sum_{t=1}^T I(M; Y_t \vert X_{1:t}, Y_{1:t-1}). \end{align*}\]进而，经过一些计算 （详见原文 Lemma 4 以及不等式 (31)), 最终可以得到文章称为 Information Radius bound的不等式：
\[\begin{align*} I(M; \hat M_T) \le T \max_{i,j} \sup_{x \in S} D( P_{T \vert M=i, X=x} \Vert P_{Y \vert M = j, X=x}), \end{align*}\]其中 $D(\cdot \Vert \cdot)$ 表示两个分布之间的KL散度。我们考虑一种可能最简单的随机梯度的情况，也即给随机梯度加上正态噪声 $Y \vert X = \nabla f(X) + Z$, 其中 $Z \sim \mathcal{N}(0,\sigma^2 I_d/d)$. 代入正态分布之间的KL散度的显示解，我们可以得到
\[\begin{align*} I(M; \hat M_T) \le \frac{d T}{2 \sigma^2} \max_{i,j} \sup_{x \in S} \Vert \nabla f_i(x) - \nabla f_j(x) \Vert^2. \end{align*}\]到了这里，下面两个章节的结论基本就水到渠成了。在下面我们会考虑用上述的框架证明Lipschitz函数以及强凸函数的复杂度下界。
Lower Bound for Lipschitz Functions
根据Gilbert-Varshamov bound, 我们可以取 $d$ 维单位超立方体上一个大小为 $N> 2^{d/8}$ 的 $d/2$-packing ${v_0,\cdots,v_{N-1} }$ 满足
\[\begin{align*} \Vert v_i - v_j \Vert^2 \ge d/2, \quad \forall i \ne j. \end{align*}\]考虑 $S$ 为以原点为中心半径为 $R$ 的球，我们希望定义在 $S$ 上的一列$L$-Lipschitz函数，满足两两之间很难辨认, 我们选择函数为关于 $R v_i / \sqrt{d}$ 的距离函数，定义为
\[\begin{align*} f_i(x) = \beta \Vert x / R - v_i / \sqrt{d} \Vert. \end{align*}\]那么每一个函数 $f_i$ 的极小值点为 $x_i^\ast = v_i / \sqrt{d}$. 我们简单将距离函数选择为 $d(f_i, f_j)= \epsilon \sqrt{8 / d} \Vert v_i - v_j \Vert$. 我们知道这样选取后的距离函数对任意 $i \ne j$ 一定满足 $d(f_i, f_j) \ge 2 \epsilon$. 下面我们需要它满足距离函数的第二个要求，通过观察不等式
\[\begin{align*} f_j(x) - f_j^\ast =& \beta \Vert x / R - v_j / \sqrt{d} \Vert \\ \ge& (\beta/ \sqrt{d}) \Vert v_i - v_j \Vert - \beta \Vert x / R - v_i / \sqrt{d} \Vert \\ =& (\beta/ \sqrt{d}) \Vert v_i - v_j \Vert - (f_j(x) - f_j^\ast) \\ =& \frac{\beta d(f_i,f_j)}{\sqrt{8} \epsilon} - (f_j(x) - f_j^\ast) \\ \ge& \frac{\beta}{\sqrt{2}} - (f_j(x) - f_j^\ast). \end{align*}\]可以发现我们只需要选取 $\beta$ 满足 $\beta \ge \sqrt{8} \epsilon$ 即可。为了保证函数为 $L$-Lipschitz, 只要选择 $\beta \le L R$ 即可。注意到对于所有 $i$ 都成立 $\Vert \nabla f_i(x) \Vert \le \beta / R$. 我们代入之前的结果可以得到
\[\begin{align*} T \ge \frac{\sigma^2 R^2(( 1-\delta) (d/8) - \log 2)}{8 d \beta^2}. \end{align*}\]当选择 $\beta \asymp \epsilon$, 我们得到了下界 $\Omega(\sigma^2 R^2 \epsilon^{-2})$.
Lower Bound for Strongly Convex Functions
与上一节相同，我们选择相同的 packing ${v_0,\cdots,v_{N-1}}$ 以及定义域 $S$, 令 $\beta \le 1$, 然后定义如下的二次函数：
\[\begin{align*} f_i(x) = \frac{\mu}{2} \Vert x / R - \beta v_i/ \sqrt{d} \Vert^2. \end{align*}\]上述函数一定满足 $\mu$-强凸的假设。对于上述函数，我们将距离函数也对应地选择为二次函数 $d(f_i,f_j) = 2 (\epsilon / d) \Vert v_i - v_j \Vert^2$. 类似地，我们知道这样选取后的距离函数对任意 $i \ne j$ 一定满足 $d(f_i, f_j) \ge 2 \epsilon$. 下面我们需要它满足距离函数的第二个要求，通过观察不等式
\[\begin{align*} f_j(x) - f_j^\ast =& \frac{\mu}{2} \Vert x / R - \beta v_j / \sqrt{d} \Vert^2 \\ \ge& \frac{\mu \beta^2}{4 d} \Vert v_i - v_j \Vert^2 - \frac{\mu}{2} \Vert x / R - \beta v_i / \sqrt{d} \Vert^2 \\ =& \frac{\mu \beta^2 ~d(f_i,f_j)}{8 \epsilon} - (f_j(x) - f_j^\ast) \\ \ge& \frac{\mu \beta^2}{4} - (f_j(x) - f_j^\ast). \end{align*}\]可以发现我们需要选择 $\mu \beta^2 \ge 8 \epsilon$ 即可。注意到
\[\begin{align*} \Vert \nabla f_i(x) - \nabla f_j(x) \Vert^2 \le (\mu^2 \beta^2 / d) \Vert v_i - v_j \Vert^2 \le 4 \mu^2 \beta^2. \end{align*}\]因此，我们代入之前的结果就得到了
\[\begin{align*} T \ge \frac{\sigma^2 (( 1-\delta) (d/8) - \log 2)}{8 d \mu^2 \beta^2}. \end{align*}\]当选择 $\beta \asymp \sqrt{\epsilon / \mu}$, 我们得到了下界 $\Omega(\sigma^2 / (\mu \epsilon))$.
Extension to SZO with One-Point Feedback
文章的结果也可以推广到随机零阶优化的设定，也即 Stochastic Zeroth-order Optimization (SZO). 此时每次oracle返回一个随机的函数值估计，在这种情况下，使用完全类似的证明可以得到如下的下界：
对于$L$-Lipschitz函数 ($L>1$)，下界为 $\Omega(d \sigma^2 R^2 \epsilon^{-2})$.
对于$\mu$-强凸函数，下界为 $\Omega( d \sigma^2 / ( R^2 \mu \epsilon))$.
我们做一些简单的评论：首先可以发现对应的下界都乘了 $d$ 倍，这是因为对于函数值我们可以直接施加 $\sigma^2$ 的噪声，但是对于梯度我们只能施加 $\sigma^2/d$ 的噪声才能使得整个随机梯度向量的方差控制在 $\sigma^2$ 以内。其次，强凸情况下关于定义域大小 $R$ 的依赖并不紧，这是因为下界构造使用了二次函数，其函数值的大小依赖于 $R$. 这可能需要使用更巧妙的构造解决。