We consider the problem of rank-$1$ low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: $$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p} , $$ where $\|M\|_{\mathcal{S}_p}$ denotes the $\ell_p$ norm of the singular values of $M$. Given $\varepsilon>0$, our goal is to output a unit vector $v$ such that $$ \|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I - u u^\top)\|_{\mathcal{S}_p}. $$ Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal number of matrix-vector products for Spectral ($p=\infty$), Frobenius ($p=2$) and Nuclear ($p=1$) LRA. In particular, for Spectral LRA, we show that any algorithm requires $\Omega\left(\log(n)/\varepsilon^{1/2}\right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods [MM15, BCW22]. Our lower bound addresses Open Question 1 in [Woo14], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1.2 in [BCW22]. Next, we show that for any fixed constant $p$, i.e. $1\leq p =O(1)$, there is an upper bound of $O\left(\log(1/\varepsilon)/\varepsilon^{1/3}\right)$ matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the $O\left(\log(n/\varepsilon)/\varepsilon^{1/3}\right)$ bound recently obtained in [BCW22], and matches their $\Omega\left(1/\varepsilon^{1/3}\right)$ lower bound, to a $\log(1/\varepsilon)$ factor.


翻译:在矩阵-向量乘积模型下,我们考虑了在各种Schatten范数下的秩为1的低秩近似问题:$$ \min_{\|u\|_2=1} \|A (I - u u^\top)\|_{\mathcal{S}_p} , $$ 其中 $\|M\|_{\mathcal{S}_p}$ 表示 $M$ 的奇异值的 $\ell_p$ 范数。给定 $\varepsilon>0$,我们的目标是输出一个单位向量 $v$,使得 $$ \|A(I - vv^\top)\|_{\mathcal{S}_p} \leq (1+\varepsilon) \min_{\|u\|_2=1}\|A(I - u u^\top)\|_{\mathcal{S}_p}. $$ 我们的主要结果显示,对于谱($p=\infty$),弗罗贝尼乌斯($p=2$)和核($p=1$)LRA,Krylov方法(几乎)实现了信息理论上的最优矩阵-向量乘积数量。尤其是,对于谱LRA,我们展示了任何算法都需要 $\Omega\left(\log(n)/\varepsilon^{1/2}\right)$ 矩阵-向量乘积,这与Krylov方法 [MM15, BCW22] 获得的上界完全匹配。我们的下界回答了 [Woo14] 中的开放问题1,为鉴别谱LRA算法缺乏进展提供了证据,并解决了[BCW22]中的开放问题1.2。接下来,我们展示,对于任何固定常数 $p$,即 $1\leq p=O(1)$,都存在 $O\left(\log(1/\varepsilon)/\varepsilon^{1/3}\right)$ 的矩阵-向量乘积上界,这意味着复杂度不随输入大小而增长。这改进了最近在[BCW22]中获得的 $O\left(\log(n/\varepsilon)/\varepsilon^{1/3}\right)$ 上界,并匹配了他们的 $\Omega\left(1/\varepsilon^{1/3}\right)$ 下界,还少了一个 $\log(1/\varepsilon)$ 的因子。

0
下载
关闭预览

相关内容

南大《优化方法 (Optimization Methods》课程,推荐!
专知会员服务
77+阅读 · 2022年4月3日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
NeurIPS 2021 | 用简单的梯度下降算法逃离鞍点
专知会员服务
23+阅读 · 2021年12月6日
专知会员服务
12+阅读 · 2021年10月12日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
【文本生成现代方法】Modern Methods for Text Generation
专知会员服务
43+阅读 · 2020年9月11日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
RL解决'LunarLander-v2' (SOTA)
CreateAMind
62+阅读 · 2019年9月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
百闻不如一码!手把手教你用Python搭一个Transformer
大数据文摘
18+阅读 · 2019年4月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
VIP会员
相关VIP内容
南大《优化方法 (Optimization Methods》课程,推荐!
专知会员服务
77+阅读 · 2022年4月3日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
NeurIPS 2021 | 用简单的梯度下降算法逃离鞍点
专知会员服务
23+阅读 · 2021年12月6日
专知会员服务
12+阅读 · 2021年10月12日
专知会员服务
76+阅读 · 2021年3月16日
专知会员服务
50+阅读 · 2020年12月14日
【文本生成现代方法】Modern Methods for Text Generation
专知会员服务
43+阅读 · 2020年9月11日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
RL解决'LunarLander-v2' (SOTA)
CreateAMind
62+阅读 · 2019年9月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
百闻不如一码!手把手教你用Python搭一个Transformer
大数据文摘
18+阅读 · 2019年4月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员