矩阵博弈的复杂度下界
Published:
Paper Reading: The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria.
本文我们考虑建立如下单纯形矩阵博弈的优化复杂度下界：
\[\begin{align*} \max_{w \in W} \min_{p \in \Delta^n} p^\top A w = \max_{w \in W} \min_{l \in [n]} (Aw)_l. \end{align*}\]这包含了很多基础性的问题。例如 (1) 当集合 $W$ 为单位范数球，等价于感知器问题，可以视作为一个最简单的单层神经网络。此时 $A$ 为数据集，$w$ 为线性模型的参数，求解上述问题等价于求解一个间隔最小的线形分类器；（2）当集合 $W$ 也为单纯形，等价于双玩家零和博弈问题，其中矩阵 $A$ 表示两个玩家不同对策的收益矩阵，求解上述问题等价求解两个玩家混合随机策略的Nash均衡点。我们将问题（1）和（2）分别称为 $\ell_2$/单纯形-问题和 单纯形/单纯形问题。
下面，我们采用一个证明框架，给出上述设定 (1) 和设定 (2) 的复杂度下界。我们定义的oracle复杂度为矩阵乘法的次数，其中包括了左乘操作 $Aw$ 或者右乘操作 $p^\top A$.
Lower Bound for Problem (1)
The Construction
对于一个给定的算法，我们考虑如下高维函数构造, 其中$\alpha, \beta$ 为待定参数。首先初始化 $v_0 = \alpha 1$，然后对于随后的 $T+1$ 次迭代，对于算法如下的对抗oracle。
- 计算算法的查询点 $p_t$ 和 $w_t$.
- 选择 $u_t$ 为正交于向量组 $u_1,\cdots,u_{t-1}, w_1,\cdots,w_t$ 的一个单位向量。
- 抽取独立的标准高维高斯向量 $\xi_t$, 然后令 $v_t$ 为 $\beta \xi_t$ 到向量组 $v_0,\cdots,v_{t-1},p_1,\cdots,p_t$ 补空间的正交投影。
- 令 $A_t = \sum_{j=1}^t (v_{j-1} - v_j) u_j^\top$ 并且返回oracle为 $p_t^\top A_t$ 以及 $A_t w_t$.
容易注意到根据构造，上述等价于给出了一个困难的例子，其中矩阵 $A$为
\[\begin{align*} A = \sum_{t=1}^T (v_{t-1} - v_t) u_j^\top + v_T u_{T+1}^\top. \end{align*}\]上述构造中的正交性可以保证每次迭代 $t$ 返回oracle $p_t^\top A$ 以及 $A w_t$ 只依赖于直到迭代 $t$ 中所拥有的部分知识即可。
下面用上述构造给出在假设 $\max_{l \in [n]} \Vert A_l \Vert \le 1$ 下寻找一个 $\epsilon$ 解的 $\tilde{\Omega}(\epsilon^{-2/3})$ 的复杂度下界。我们将证明拆分成如下三个步骤。
Step I: Seperator Exists
我们希望我们构造的例子存在一个线性分类器。我们选择单位向量 $\bar w = \frac{1}{\sqrt{T+1}} \sum_{t=1}^{T+1} u_t$. 对于这个平均的向量，成立
\[\begin{align*} &\max_{w: \Vert w \Vert \le 1}\min_{p \in \Delta^n} p^\top A w \ge \min_{p \in \Delta^n} p^\top A \bar w = \frac{\alpha}{\sqrt{T+1}}. \end{align*}\]Step II: Algorithm Returns a Non-Separator
上一步我们证明了一个近似分类器的存在，但下一步我们证明我们的构造可以保证算法无法返回一个分类器。根据构造，我们有
\[\begin{align*} A w_{T+1} =& \sum_{t=1}^T (v_{t-1} - v_t) u_t^\top w_{T+1}. \end{align*}\]定义 向量 $r = (r_0,\cdots,r_T)$ 满足 $r_0 = u_1^\top w_{T+1}$, $r_T = u_T^\top w_{T+1}$, 以及对于其他的 $t$ 有 $r_t =u_t^\top w_{T+1} - u_{t+1}^\top w_{T+1}$. 因此，可以将上式重写为
\[\begin{align*} A w_{T+1} =& r_0 v_0 - \sum_{t=1}^T r_t v_t \\ =& \alpha r_0 1 - \beta \sum_{t=1}^T r_t (I - M_t M_t^\top ) \xi_t \\ =& \alpha r_0 1 - \beta \left( \sum_{t=1}^T r_t \xi_t - \sum_{t=1}^T r_t M_t M_t^\top \xi_t \right), \end{align*}\]其中我们定义 $M_t$ 为向量组 $v_0,\cdots,v_{t-1},p_1,\cdots,p_t$ 的正交基。为了分析 $\min_{p \in \Delta^n} A w_{T+1} = \min_{l \in [n]}（A w_{T+1})_l$ 的大小，我们使用高维概率的集中不等式。为了便于理解，我们给出直觉上大致的估计而非完全严谨的证明，详细的推导可以见原论文。
首先我们对向量 $\sum_{t=1}^T r_t \xi_t$ 的每一个维度分别应用Hoeffding集中不等式可以知道其每一个维度都将集中在 $\Vert r_{1:T} \Vert$ 附近。而对于向量 $\sum_{t=1}^T r_t M_t M_t^\top \xi_t$ 由于投影的存在，事实上可以证明当维度足够高 (文中选择了 $n = \Omega(T^2)$ ) 的时候，该向量最小的一项应当小于 $\Vert r_{1:T} \Vert$。 因此，遵循我们上述的直觉，我们可以证明高概率下一定有：
\[\begin{align*} \min_{l \in [n]}(A w_{T+1})_l \le \alpha r_0 - \frac{\beta}{4} \Vert r_{1:T} \Vert, \end{align*}\]其中常数 $1/4$ 是由于使用集中不等式的误差导致。回顾向量 $r$ 的定义，我们定义新的向量组 $x_t = u_t w_{T+1}$, 那么可以将上面的不等式重写为
\[\begin{align*} \min_{l \in [n]}(A w_{T+1})_l \le \alpha x_0 - \frac{\beta}{4} \sqrt{ \sum_{t=1}^{T=1} (x_j - x_{j+1})^2 + x_{T^2} }. \end{align*}.\]上式子是否为负事实上可以通过定义一个三对角矩阵 $M$ 的正定性来得到, 业绩分析什么时候成立 $x^\top M x \ge 0$. 经过简单的分析我们可以知道，当 $\alpha = O(\beta / \sqrt{T})$ 的时候，可以保证上式右端项为父，因此算法一定不能返回一个线性分类器，并且结合第一步，我们知道
\[\begin{align*} \max_{w: \Vert w \Vert \le 1}\min_{l \in [n]}(A w)_l - \min_{l \in [n]}(A w_{T+1})_l \ge \frac{\alpha}{\sqrt{T+1}}. \end{align*}\]Step III: Bounded Norm
最后一步，我们验证构造满足矩阵 $A$ 的范数有界条件, 容易根据集中不等式得到
\[\begin{align*} \max_{l \in [n]} \Vert A_l \Vert = \tilde{O}( \alpha + \beta \sqrt{T}). \end{align*}\]An $\tilde{\Omega}(1/T^{3/2})$ Lower Bound
最后，我们选取合适的参数 $\alpha, \beta$ 得到最终的复杂度下界。为了保证 $\max_{l \in [n]} \Vert A_l \Vert \le 1$，我们需要选择 $\alpha = O(1)$ 以及 $\beta = \tilde{O}(1/\sqrt{T})$. 为了保证第二步中的条件成立，我们需要选择 $\alpha = O(\beta/ \sqrt{T}) =\tilde{O}(1/T)$. 最终我们知道给出的下界为
\[\begin{align*} \Omega\left( \frac{\alpha}{\sqrt{T}} \right) = \tilde{\Omega}\left( \frac{1}{T^{3/2}} \right). \end{align*}\]Lower Bound for Problem (2)
本节，我们采用类似的构造，证明关于问题(2) 的复杂度下界。
A Reduction
首先，我们证明，任意求解单纯形/单纯形博弈问题的算法，都可以求解如下的 $\ell_1$/单纯形-矩阵博弈问题：
\[\begin{align*} \max_{w: \Vert w \Vert_1 \le 1} \min_{p \in \Delta^n} p^\top A w = \max_{w: \Vert w \Vert_1 \le 1} \min_{l \in [n]} (Aw)_l. \end{align*}\]给定一个收益矩阵为 $A \in \mathbb{R}^{n \times d}$ 的 $\ell_1$/单纯形-矩阵博弈问题的实例，我们可以用如下的方式调用收益矩阵为 $(A;-A) \in \mathbb{R}^{n \times 2d}$ 一个单纯形/单纯形博弈问题的求解器进行求解。每次我们从求解器中获得询问点 $p \in \mathbb{R}^d$ 和 $(w^+,w^-) \in \mathbb{R}^{2n}$, 然后返回oracle为 $p^\top A$ 以及 $A(w^+ - w^-)$. 进行 $T+1$ 次迭代后，我们最后输出点 $p_{T+1}$ 以及 $w_{T+1} = w_{T+1}^+ - w_{T+1}^-$ 满足 $\Vert w_{T+1} \Vert \le \Vert w_{T+1}^+ \Vert + \Vert w_{T+1}^- \Vert_1 = 1$. 我们可以证明上述这个归约给出了一个相同效率的单纯形/单纯形问题的求解器，推导如下:
\[\begin{align*} & \max_{\Vert w \Vert_1 \le 1} \min_{p \in \Delta^n} p^\top A w - \min_{p \in \Delta^n} p_{T+1}^\top Aw_{T+1} \\ = & \max_{w \in \Delta^{2d}} \min_{p \in \Delta^n} p^\top A (w^+ - w^-) - \min_{p \in \Delta^n} p_{T+1}^\top A(w_{T+1}^+ - w_{T+1}^-). \end{align*}\]上式做左端项代表$\ell_1$/单纯形问题解的逼近程度，而右端项是我们上述算法给出的关于单纯形/单纯形问题解的逼近程度。等号成立的原因是：关于$\ell_1$/单纯形问题的解 $w^\ast$ 一定满足 $\Vert w^\ast \Vert_1$，而此时将 $w^\ast$ 的负元素和非负元素的绝对值分开，得到的向量 $(w^+, w^-)$ 一定满足 $(w^+, w^-) \in \Delta^{2d}$.
The Construction
经过上述分析，我们知道如果一个算法可以求解单纯形/单纯形问题，那么也可以在相同的时间内求解 $\ell_1$/单纯形问题。因此，为了构造单纯形/单纯形问题的复杂度下界，只需要构造 $\ell_1$/单纯形问题的复杂度下界即可。由之前关于问题（1）的构造启发，我们进行简单的修改得到如下构造：首先初始化 $v_0 = \alpha 1$，然后对于随后的 $T+1$ 次迭代，对于算法如下的对抗oracle。
- 计算算法的查询点 $p_t$ 和 $w_t$.
- 取独立的标准高维高斯向量 $\xi_t’$, 然后令 $u_t$ 为$\xi_t’$ 到向量组 $u_1,\cdots,u_{t-1}, w_1,\cdots,w_t$ 补空间的正交投影，后并且归一化使得模长为1的向量。
- 抽取独立的标准高维高斯向量 $\xi_t$, 然后令 $v_t$ 为 $\beta \xi_t$ 到向量组 $v_0,\cdots,v_{t-1},p_1,\cdots,p_t$ 补空间的正交投影。
- 令 $A_t = \sum_{j=1}^t (v_{j-1} - v_j) u_j^\top$ 并且返回oracle为 $p_t^\top A_t$ 以及 $A_t w_t$.
注意到只有步骤2进行了修改，目的是为了使用集中不等式来满足矩阵 $A$ 的每个元素有界的条件。
Step I: Seperator Exists
类似地，我们可以证明存在一个线性分类器。我们选择单位向量 $\bar w = \frac{1}{\Vert \sum_{t=1}^{T+1} u_t \Vert_1} \sum_{t=1}^{T+1} u_t$. 对于这个平均的向量，成立
\[\begin{align*} &\max_{w: \Vert w \Vert_1 \le 1}\min_{p \in \Delta^n} p^\top A w \ge \min_{p \in \Delta^n} p^\top A \bar w = \frac{\alpha}{\Vert \sum_{t=1}^{T+1} u_t \Vert_1} \ge \frac{\alpha}{\sqrt{d}\Vert \sum_{t=1}^{T+1} u_t \Vert_2} = \frac{\alpha}{\sqrt{d(T+1)}}. \end{align*}\]Step II: Algorithm Returns a Non-Separator
由于之前分析中的第二步只依赖于 $u_t$ 正交于向量组 $u_1,\cdots,u_{t-1}, w_1,\cdots,w_t$，之前的分析仍然成立。回顾之前的结论，我们知道当 $\alpha = O(\beta / \sqrt{T})$ 的时候，可以保证上式右端项为父，因此算法一定不能返回一个线性分类器，并且结合第一步，我们知道
\[\begin{align*} \max_{w: \Vert w \Vert \le 1}\min_{l \in [n]}(A w)_l - \min_{l \in [n]}(A w_{T+1})_l \ge \frac{\alpha}{\sqrt{d(T+1)}}. \end{align*}\]Step III: Bounded Elements
在这一步中，我们利用高维高斯分布的集中不等式，证明构造的矩阵 $A$ 中每一个元素都有界。根据矩阵 $A$ 的定义以及三角不等式，我们可以得到
\[\begin{align*} \max_{i,j} \vert A_{i,j} \vert \le \left \vert \sum_{t=1}^T (v_{t-1,i} - v_{t,i}) u_{t,j} \right \vert + \vert v_{T,i} \vert \vert u_{T+1,j} \vert. \end{align*}\]当给定向量组 $v_0,\cdots, v_T$ 的前提下，向量 $u_t$ 作为球面上的均匀分布，我们知道其满足次高斯范数为 $O(1/d)$ 的次高斯分布。因此根据次高斯随机变量和的集中不等式，我们可以得到以高概率成立
\[\begin{align*} \left \vert \sum_{t=1}^T (v_{t-1,i} - v_{t,i}) u_{t,j} \right \vert = \tilde{O} \left( \sum_{t=1}^T (v_{t-1,i} - v_{t,i})^2/d \right). \end{align*}\]再对右端项利用Young氏不等式，得到
\[\begin{align*} \left \vert \sum_{t=1}^T (v_{t-1,i} - v_{t,i}) u_{t,j} \right \vert = \tilde{O} \left( \frac{\alpha^2+\sum_{t=1}^T v_{t,i}^2}{d} \right). \end{align*}\]下面，注意到 $v_{t,i} \mid v_{0,i}, \cdots, v_{t-1,i}$ 服从于方差小于 $\beta^2$ 的高斯分布，我们利用鞅差序列的集中不等式，可以得到以高概率成立着
\[\begin{align*} \left \vert \sum_{t=1}^T v_{t,i}^2 \right \vert = \tilde{O} \left( \beta^2 T \right) \end{align*}\]因此我们知道以高概率成立
\[\begin{align*} \max_{i,j} \vert A_{i,j} \vert = \tilde{O} \left( \alpha / \sqrt{d} + \beta \sqrt{T/d} \right). \end{align*}\]An $\tilde{\Omega}(1/T^{3/2})$ Lower Bound
最后，我们选取合适的参数 $\alpha, \beta$ 得到最终的复杂度下界。为了保证 $\max_{i,j} \vert A_{i,j} \vert \le 1$，我们需要选择 $\alpha = O(\sqrt{d})$ 以及 $\beta = \tilde{O}(\sqrt{d/T})$. 为了保证第二步中的条件成立，我们需要选择 $\alpha = O(\beta/ \sqrt{T}) =\tilde{O}(\sqrt{d}/T ))$. 最终我们知道给出的下界为
\[\begin{align*} \Omega\left( \frac{\alpha}{\sqrt{dT}} \right) = \tilde{\Omega}\left( \frac{1}{T^{3/2}} \right). \end{align*}\]