静园5号院科研讲座:卡内基梅隆大学 David Woodruff 副教授谈子空间嵌入问题

 

  2019年8月8日,卡内基梅隆大学的 David Woodruff 副教授受邀访问北京大学前沿计算研究中心,并在静园五院做了题为“Tight Bounds For L1 Oblivious Subspace Embeddings”的主题报告,介绍了关于高维矩阵做子空间嵌入(Subspace Embedding)的工作。报告由中心讲席教授邓小铁老师主持,听众包括来自北京大学信息科学技术学院、数学学院等单位的师生。

 

  

  David Woodruff 副教授报告现场

 

  Woodruff 教授首先提到大家熟知的最小二乘回归问题:给定矩阵 A∈Rn×d,向量 b∈Rn,找到向量 x∈Rd 使得 |Ax-b|尽可能小。这一问题可以推广至任意 p 范数上,用于对 d 维数据做线性拟合。在现实生活中,数据量 n 远远大于 d,这使得这一情况值得被研究。对于最小二乘回归问题,我们知道这一问题的解可以被 x*=A-b 表示,其中 A是矩阵 A 的伪逆,这一问题的计算需要 O(nd2) 时间。这个时间量在现实生活中显得过高,一个处理办法是对这个问题做一些放缩,即允许求解近似最优,以及引入随机算法。这也引出了本次报告的核心问题:子空间嵌入。

 

  一个矩阵 S 被称作 p 范数子空间嵌入,如果对所有 x∈Rd,|Ax|p≤|SAx|p≤κ|Ax|p 以常数概率成立。而如果得到了这样一个子空间嵌入,解 p 范数回归问题的算法即可变为:对由 A 和 b 拼接得到的矩阵求子空间 [A b] 嵌入,再最小化 |SAx-Sb|p。以 L2 子空间嵌入为例,令 r=O(d/ϵ2),S 大小是 r×n,每个元素独立同分布于高斯分布 N(0,1/r) 的矩阵。可以通过网论证(Net Argument)和Johnson-Lindenstrauss (JL) 引理得知,S 是一个子空间嵌入,且是无依赖子空间嵌入(Oblivious Subspace Embedding, OSE),即和矩阵 A 的取值无关。然而这一方法的缺点是,矩阵 SA 的计算已经需要 O(nd2) 的时间,并没有从效率上得到提升。然而正是源于这样的想法,后续有研究成果对这一构造稍微做了一些改动:在 CountSketch 算法中,令 r=O(d22),S 矩阵在每一列随机选一个位置,并随机赋值为±1,矩阵其他位置均为0。可以证明对任意 x,以常数概率 |SAx|2=(1±ϵ)|Ax|会发生。注意到矩阵每列只有一个非0数的特点,我们知道 SA 的计算只需要 A 的 O(nnz(A)) 的时间,即和 A 的非零元素个数呈线性关系。同时,如果 S 每列只选一个非0值,即使想保证矩阵的秩,d的依赖也是紧的。而在 OSNAP 算法中,S 矩阵每列选 s=O(logd/ϵ) 个非0随机±1值,r=O(B d log d/ϵ2),可以证明这样的矩阵 S 也是子空间嵌入,而且对应的下界 r=Ω(B d2/ϵ )。

 

  而对于 L1 子空间嵌入问题,我们是否可以用类似的方法去做呢?Woodruff 教授这里回顾了 L2 子空间嵌入下用到的技术:JL引理(高斯分布引出的2-稳定(2-stable)版本),网论证。Woodruff 教授提到,这里可能我们需要1-稳定分布。无独有偶,柯西分布恰恰具有这一性质:a1C1+⋯+anCn≈|a|1C,其概率密度函数为 f(x)=1/(π(1+x2))。柯西分布的尾部可以被 Θ(1/x) 限定住,但这一尾部相对较大,对分析会带来一定困难。对于稠密柯西嵌入(Dense Cauchy Embedding),即嵌入中每个元素均为取自柯西分布的独立变量时,令 r="O(d" log⁡d),可以证明对所有 x,以常数概率 Ω(r)|Ax|1≤|SAx|1≤O(rd log⁡d)|Ax|会成立。下界的证明源自网论证和柯西下尾概率不等式,而上界的证明用到了 d 维子空间1范数下的一组基,先证明 |SU|1=O(rd log⁡rd) 以常数概率发生,进而 |SUx|1≤|SU|1|x|≤O(rd log⁡rd)|Ux|1。其中第一个不等式是 Holder不等式的应用。对于稀疏柯西嵌入(Sparse Cauchy Embedding),即其中每列只有一个非零值,独立同分布于一个柯西分布,令 r=O(d5 log5⁡d),可以证明对所有 x,以常数概率

  

  会成立,同样的,矩阵 SA 的计算时间为 O(nnz(A))。

  对于 L1无依赖子空间嵌入问题之前的结论,Woodruff 教授总结提炼出如下问题:

  Ω(d log⁡d) 的拉伸(distortion)是不是最优?能不能提出 (1+ϵ) 的拉伸?(如果是有依赖的版本,(1+ϵ) 的拉伸是可以做到的);

  是否能做到 r="O(d" log⁡d),拉伸为 O(d log⁡d) 的稀疏无依赖子空间嵌入?稀疏度和r的大小有没有什么权衡?

  

  Woodruff 教授及其合作者的最新论文对这些问题给出了解答:对于 1≤p<2,任意 p 范数 r 行的 OSE 的拉伸度为

  

  特别的,r=n 时,单位矩阵就是一个无拉伸的 OSE,p 趋向于2时,拉伸度趋向于 (1+ϵ)。而对于 p="1" 的情况,r=poly(d),n≫r 的时候,下界为 Ω(d log2⁡d),而稠密柯西嵌入和最优只差 O(log3d) 的因子。证明的大概思路基于Yao的最小最大原理(Yao's Minimax Principle):构造一组矩阵 A 的一个分布,并说明对任意嵌入 S,都有这样的下界。由于时间关系,Woodruff 教授没有仔细介绍这一构造和证明细节,具体内容可以参考他主页上的论文。

  

  Woodruff 教授最后提到一些公开问题:是否可以构造 L1 的 OSE,使得:1)用到  O(d2) 行,稀疏度为1,拉伸度为 O(d log⁡d)?2)用到 O(d logd) 行,稀疏度为 O(1),拉伸度为 O(d logd)?3)用到 O(2O(d)) 行,拉伸度为 O(1),或者证明更强的下界结论?而一个更有一般性的问题是,得到 1<p<2 的OSE的紧界。有听众问提问,为什么只关注 1<p<2?Woodruff 教授解释到,当然可以研究 p>2 的情况,但一般来说更高的 p 值意味着对离群的点更重视,在实际场景中不是那么适用。听众在报告中问了Woodruff 教授很多问题,Woodruff 教授均细心解答。报告结束后,Woodruff 教授继续和中心师生进行了深入交流。

 

  

  邓小铁教授与David Woodruff副教授合影