论文标题
动态痕量估计的最佳查询复杂性
Optimal Query Complexities for Dynamic Trace Estimation
论文作者
论文摘要
我们考虑到在动态设置中准确痕迹估计所需的矩阵向量查询数量的问题，在该动态设置中，我们的基础矩阵正在缓慢变化，例如在优化过程中。具体而言，对于任何$ m $ $矩阵$ a_1，...，a_m $，连续差异为schatten- $ 1 $ norm by $α$，我们提供了一个新颖的二进制树求和程序，同时估计所有$ m $ traces traces traces tem $δ$ tif $δ$失败的可能性，并带有$δ$ take $δ$ take potivalibality of $ x α\ sqrt {\ log（1/δ）}/ε+ m \ log（1/δ）\ right）$，改善了从dharangutte and Musco中对$α$和$δ$的依赖性（Neurips，2021）。我们的过程在$ a_i $上没有其他规范界限，可以推广到$ p $ -th schatten norm in [1,2] $中的$ p \，其复杂性为$ \ widetilde {o} \ left（mα\ left（mα\ left） \ log（1/δ）\ right）$。 通过对高斯矩阵的通信复杂性和信息理论分析的新颖降低，我们为所有相关参数（包括故障概率）提供了匹配的下限，以进行静态和动态痕量估计。我们的下限（1）给出了Hutchinson在矩阵 - 矢量产品模型中具有Frobenius Norm误差的第一个紧密界限，即使在静态设置中，（2）是动态痕量估计的第一个无条件下限，解决了先前工作的开放问题。
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly, such as during an optimization process. Specifically, for any $m$ matrices $A_1,...,A_m$ with consecutive differences bounded in Schatten-$1$ norm by $α$, we provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $ε$ error with $δ$ failure probability with an optimal query complexity of $\widetilde{O}\left(m α\sqrt{\log(1/δ)}/ε+ m\log(1/δ)\right)$, improving the dependence on both $α$ and $δ$ from Dharangutte and Musco (NeurIPS, 2021). Our procedure works without additional norm bounds on $A_i$ and can be generalized to a bound for the $p$-th Schatten norm for $p \in [1,2]$, giving a complexity of $\widetilde{O}\left(m α\left(\sqrt{\log(1/δ)}/ε\right)^p +m \log(1/δ)\right)$. By using novel reductions to communication complexity and information-theoretic analyses of Gaussian matrices, we provide matching lower bounds for static and dynamic trace estimation in all relevant parameters, including the failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation, resolving open questions of prior work.
