随机零阶凸优化的复杂度下界
Published:
Paper Reading: Optimal rates for zero-order convex optimization: the power of two function evaluations
在上一篇博文 随机凸优化的复杂度下界 中，我们讨论了随机一阶凸优化的复杂度下界，在本文中我们考虑一个更困难的情况。当我们只能得到函数值的估计，而不能得到导数信息，这也称为零阶优化。问题为
\[\begin{align*} \min_{x \in S} f(x). \end{align*}\]Lower Bound Function
我们在 $d$ 维的超立方体中均匀选择 $v \in {-1,1 }^d$.
给定 $v$, 我们定义函数 $f_v(x) = \delta \langle x, v \rangle$, 其中参数 $\delta$ 的具体取值将在后面确定， 定义域为 $S = {x \mid \Vert x \Vert \le 1 }$.
我们定义随机函数 $F_V(x) = \langle x, V \rangle$, 其中 $V \sim \mathcal{N}(\delta v, \sigma^2 I_d)$.
我们考虑的算法迭代 $t$ 次，每次Oracle会产生一个随机向量 $V_t$, 算法给出至多两个点的询问 $(x_1^{(t)},x_2^{(t)})$, Oracle返回对应的随机函数的取值. 这里允许同时访问两个点的原因是实际中零阶优化器通常基于使用差分逼近导数的思想，因此需要同时访问两个点的函数值。
Analysis
对于一阶算法复杂度下界的分析框架，需要证明两件事情，
- 一是所构造的函数集合满足一定的间隔
- 二是计算我们构造的Oracle给出的互信息上界
当函数间隔足够大，一个优化算法将可以成功区分出不同的函数，但另一方面根据信息论，当互信息不够大时候不可能区分出真正的参数，那么上述分析就可以给出优化算法的下界。
很自然地我们想要套用上述的分析框架，但笔者曾经尝试过，似乎只能得到和一阶情况相同的下界，而无法得到关于维度的依赖。
下面我们采用原文的分析，直接使用Lecum不等式考虑每一个维度，而非Fano不等式。
选定真实参数 $v^\ast$, 记 $W_t = \begin{bmatrix} x_1^{(t)} \ x_1^{(t)} \end{bmatrix}$, 观测值为 $Y_t = W_t V_t$， 其中 $V_t \sim \mathcal{N}(\delta v^\ast, \sigma^2 I_d)$
算法的输出为 $(Y_1,\cdots,Y_T)$ 到一个输出值 $\hat X$ 的映射，作为最优点 $x^\ast$ 的估计，给定 $v \in \mathcal{V}$, 我们知道
\[\begin{align*} f_v(\hat X) - f_v^\ast &= \delta \left( \sqrt{d}- \sqrt{\sum_{j=1}^d\mathbb{I}[{\rm sign}(\hat X_j) = {\rm sign} (x^\ast_j)]} \right) \\ &\ge \frac{\delta}{2\sqrt{d}} \left(d - \sum_{j=1}^d\mathbb{I}[{\rm sign}(\hat X_j) = {\rm sign}(x^\ast_j)] \right) \\ &= \frac{\delta}{2\sqrt{d}}\sum_{j=1}^d \mathbb{I}[{\rm sign}(\hat X_j) \ne {\rm sign}(x^\ast_j)]. \end{align*}\]因此我们可以得到Minimax Rate的下界为
\[\begin{align*} \inf_{\mathcal{A}} \sup_{v} \mathbb{E} [ f_v(\hat X) - f_v^\ast] \ge \inf_{\hat X} \frac{\delta}{2 \sqrt{d}} \sum_{j=1}^d\mathbb{P}({\rm sign}(\hat X_j) \ne {\rm sign}(x_j^\ast)) \end{align*}\]其中概率的随机性来自于 $v$ 的随机性， 来自 $d$ 维超立方体上的均匀分布。
对于任意的算法 $\mathcal{A}$, 我们知道
\[\begin{align*} \mathbb{P}({\rm sign}(\hat X_j) \ne {\rm sign}(x_j^\ast)) &= \frac{1}{2} \mathbb{P}({\rm sign}(\hat X_j) = 1 \mid {\rm sign}(x_j^\ast) =-1) + \frac{1}{2} \mathbb{P}({\rm sign}(\hat X_j) =-1 \mid {\rm sign}(x_j^\ast)= 1) \\ &= \frac{1}{2} \mathbb{P}({\rm sign}(\hat X_j) = 1 \mid v_j^\ast =1) + \frac{1}{2} \mathbb{P}({\rm sign}(\hat X_j) =-1 \mid v_j^\ast= -1) \\ & \ge \frac{1}{2}\left( 1 - \Vert P_{+j} - P_{-j} \Vert_{TV} \right). \end{align*}\]其中最后一步使用了Lecum不等式，由 TV距离的定义得到，其中 $P_{+j}$ 与 $P_{-j}$ 分别表示给定 $j$ 的前提下 $Y_1,\cdots,Y_T$ 的分布，给定了该分布后，我们知道$\hat X$ 为关于 $Y_1,\cdots,Y_T$ 的确定函数。将上式关于 $j$ 求和并且利用Cauchy-Schwartz不等式，有
\[\begin{align*} \sum_{j=1}^{d} \mathbb{P}({\rm sign}(\hat X_j) \ne {\rm sign}(x_j^\ast)) &\ge \frac{1}{2} \sum_{j=1}^{d} \left( 1 - \Vert P_{+j} - P_{-j} \Vert_{TV} \right) \\ &\ge \frac{d}{2} \left( 1 - \frac{1}{\sqrt{d}} \sqrt{\sum_{j=1}^d \Vert P_{+j} - P_{-j} \Vert_{TV}^2}\right) \end{align*}\]下面我们处理TV距离这一项。利用Pinsker不等式以及KL距离的联合凸性，
\[\begin{align*} \Vert P_{+j} - P_{-j} \Vert_{TV}^2 &\le \frac{1}{2} {\rm KL}(P_{+j} \Vert P_{-j} ) \le \frac{1}{2 \vert \mathcal{V \vert}} \sum_{v \in \mathcal{V}} {\rm KL}(P_{v,+j} \Vert P_{v,-j} ) , \end{align*}\]其中 $P_{v,+j}$ 与 $P_{v,-j}$ 分别表示给定 $v$ 下 $Y_t$ 的分布，但是第 $j$ 个分量的取值强制设置为给定值。
上面的 $P_{v,+j}$ 与 $P_{v,-j}$ 是关于所有观测 ${ Y_t}_{t=1}^T$ 的分布， 下面我们利用KL距离的链式法则，将其拆开
\[\begin{align*} &\quad {\rm KL}(P_{v,+j} \Vert P_{v,-j} ) \\ &= \sum_{t=1}^T {\rm KL} (P_{v,+j}^t \mid Y_1,\cdots,Y_{t-1} \Vert P_{v,-j}^t \mid Y_1, \cdots,Y_{t-1}), \end{align*}\]其中 $P_{v,+j}^t \mid Y_1,\cdots,Y_{t-1}$ 为给定之前观测值的前提下并且$v^\ast =v$ 但强制第 $j$ 个分量为 $1$ 的前提下， 关于 $Y_t$ 的分布。
当算法确定的时候 , $W_t$ 是关于 $Y_{1},\cdots,Y_{t-1}$ 的确定性函数， 因此给定 $Y_{1},\cdots,Y_{t-1}$ 的前提下，$Y_t$的分布由 $V_t$ 唯一确定。根据 $V_t$ 的生成方式，我们可以得知 $Y_t \mid Y_1,\cdots, Y_{t-1} \sim \mathcal{N}(W_t \delta v , \sigma^2 W_tW_t^\top)$. 其中 $v$ 分别为 $v_+^\ast$ 或者 $v_{-}^\ast$, 分别表示 $v^\ast$ 但是强制第 $j$ 个分量为 $1/-1$ 的向量。
此时上述的KL距离可以根据正态分布的距离公式给出，
\[\begin{align*} &\quad {\rm KL} (P_{v,+j}^t \mid Y_1,\cdots,Y_{t-1} \Vert P_{v,-j}^t \mid Y_1, \cdots,Y_{t-1}) \\ &= \frac{\delta^2}{2 \sigma^2} (v_{+}^\ast - v_{-}^\ast)^\top W_t^\top (W_tW_t^\top)^{-1} W_t (v_{+}^\ast - v_{-}^\ast) \\ &\le \frac{2 \delta^2}{\sigma^2} W_{t,j}^\top (W_tW_t^\top)^{-1} W_{t,j}. \end{align*}\]其中 $W_{t,j} = \begin{bmatrix} x_{1,j}^{(t)} \ x_{1,j}^{(t)} \end{bmatrix} $ 为 $2\times 1$ 的向量，上述用到了 $v_{+}^\ast$ 以及 $v_{-}^\ast$ 仅在第 $j$ 个分量有区别的性质。
对 $j$ 求和，得到
\[\begin{align*} &\quad \sum_{j=1}^d {\rm KL} (P_{v,+j}^t \mid Y_1,\cdots,Y_{t-1} \Vert P_{v,-j}^t \mid Y_1, \cdots,Y_{t-1}) \\ &\le \frac{2 \delta^2}{\sigma^2} \sum_{j=1}^d W_{t,j}^\top (W_tW_t^\top)^{-1} W_{t,j} \\ &= \frac{2 \delta^2}{\sigma^2} (W_tW_t^\top)^{-1} \sum_{j=1}^d W_{t,j} W_{t,j}^\top \\ &= \frac{2 \delta^2}{\sigma^2} (W_tW_t^\top)^{-1} W_t W_t^\top \\ &= \frac{2 \delta^2}{\sigma^2}. \end{align*}\]在链式法则中将所有 $T$ 项加起来，我们得到最终的 KL距离，我们一步步代入之前的得到的不等式，有
\[\begin{align*} &\quad \inf_{\mathcal{A}} \sup_{v} \mathbb{E} [ f_v(\hat X) - f_v^\ast] \\ &\ge \frac{\sqrt{d} \delta}{4} \left( 1 - \frac{1}{\sqrt{d}} \sqrt{\sum_{j=1}^d \Vert P_{+j} - P_{-j} \Vert_{TV}^2}\right) \\ &\ge \frac{\sqrt{d} \delta}{4} \left( 1 - \frac{1}{\sqrt{d}} \sqrt{\frac{1}{2 \vert \mathcal{V \vert}}\sum_{j=1}^d \sum_{v \in \mathcal{V}} {\rm KL}(P_{v,+j} \Vert P_{v,-j} )}\right) \\ &\ge \frac{\sqrt{d} \delta}{4} \left( 1 - \frac{1}{\sqrt{d}} \sqrt{\frac{1}{2 \vert \mathcal{V \vert}}\sum_{j=1}^d \sum_{v \in \mathcal{V}} \sum_{t=1}^T {\rm KL} (P_{v,+j}^t \mid Y_1,\cdots,Y_{t-1} \Vert P_{v,-j}^t \mid Y_1, \cdots,Y_{t-1}) {\rm KL}(P_{v,+j} \Vert P_{v,-j} )}\right) \\ &\ge \frac{\sqrt{d} \delta}{4} \left( 1 - \frac{\delta \sqrt{T}}{\sigma \sqrt{d}}\right) \end{align*}\]下面我们选择 $\sigma, \delta$ 的取值。回忆我们定义的随机函数 $F_V(x) = \langle x, V \rangle$, 其中 $V \sim \mathcal{N}(\delta v, \sigma^2 I_d)$.
我们希望随机函数满足Lipschitz性质，由于 $\Vert x \Vert \le 1$, 我们只需要
\[\begin{align*} \mathbb{E} \Vert V \Vert^2 = d (\delta^2 + \sigma^2) \le 1. \end{align*}\]我们取 $ \delta = \epsilon / (4 \sqrt{d})$ 以及 $ \sigma = 1 / (4 \sqrt{d})$, 当 $\epsilon \le 1$ 的时候随机函数满足Lispchitz性质。
根据我们的下界不等式，对于任意的 $ \frac{\delta \sqrt{T}}{\sigma \sqrt{d}} \le \frac{1}{2}$ 我们都有下界
\[\begin{align*} \inf_{\mathcal{A}} \sup_{v} \mathbb{E} [ f_v(\hat X) - f_v^\ast] \ge \epsilon /2. \end{align*}\]换句话说，想要优化该函数必须要有
\[\begin{align*} T \ge \frac{\sigma^2 d}{4 \delta^2} = \Omega \left( \frac{d}{\epsilon^2} \right). \end{align*}\]注意到该上界可以被基于差分的零阶方法达到，因此这是一个紧的界。