技术摘要：查询高效的结构化矩阵学习

问题陈述

本文研究了在仅能访问矩阵-向量乘法（matvec）查询的情况下，学习未知 $n \times n$ 矩阵 $A$ 的结构化近似的问题。学习者可以发出形式为 $x \to Ax$ 和 $x \to A^Tx$ 的查询，其中查询向量 $x$ 可以根据之前的响应进行自适应选择。

目标定义为问题 1：给定一个假设类（矩阵族）$\mathcal{F} \subset \mathbb{R}^{n \times n}$，寻找一个矩阵 $\tilde{B} \in \mathcal{F}$，使得：
$$\|A - \tilde{B}\|_F \leq \gamma \cdot \inf_{B \in \mathcal{F}} \|A - B\|_F$$
对于某个近似因子 $\gamma \geq 1$，并使用最少的 matvec 查询次数。这是一个“不可知”（agnostic）的设置，即不假设 $A$ 属于 $\mathcal{F}$ 或由 $\mathcal{F}$ 中的特定分布生成。

先前的研究主要集中在特定的结构化族（例如秩为 $k$ 的矩阵、稀疏矩阵、分层矩阵）上，并建立了查询复杂度界限，通常表明使用标准的草图（sketching）技术或向量-矩阵-向量（$x^T A y$）查询，只需 $O(\log |\mathcal{F}|)$ 次查询。本文旨在将这些结果推广到任意有限族，并确定 matvec 输出的多维特性（$Ax$ 是一个向量而非标量）是否允许比向量-矩阵-向量模型更优的查询复杂度。

方法论

1. 单侧基准（迭代细化）

作者首先分析了一种单侧算法（仅使用 $x \to Ax$），作为基准算法。该算法迭代地细化候选集 $\mathcal{C} \subseteq \mathcal{F}$：

1. 抽取一个具有 $\ell = O(\log \log |\mathcal{F}|)$ 列的随机草图矩阵 $\Pi$。
2. 计算 $Z = A\Pi$。
3. 剔除所有满足 $\|Z - B\Pi\|_F$ 显著大于最优误差界的 $B \in \mathcal{C}$。
4. 重复 $T = O(\log |\mathcal{F}| / \log \log |\mathcal{F}|)$ 次迭代。

这种方法实现了 $O(\log |\mathcal{F}|)$ 的查询复杂度，与已知于向量-矩阵-向量查询的界限一致。

2. 双侧模拟（核心创新）

其主要贡献在于一种利用 $A$ 和 $A^T$ 来实现近乎二次提升查询复杂度的算法，将对 $|\mathcal{F}|$ 的依赖从 $O(\log |\mathcal{F}|)$ 降低到 $\tilde{O}(\sqrt{\log |\mathcal{F}|})$。

该算法模拟了单侧迭代细化过程，但避免了在每一步中直接计算 $A\Pi$。相反，它先通过对 $A^T$ 进行 $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ 次查询来预计算左侧草图 $W = \Psi^T A$。在每次迭代中，它抽取一个右侧草图 $\Pi$，并尝试确定 $\Pi$ 是否是“有生产力的”（即是否能消除大部分坏候选者），而无需再次查询 $A$。

该模拟依赖于以下二分情况：

• 情况 1（有生产力的草图）： 如果随机草图 $\Pi$ 能够消除大量的候选者，算法则发出右侧查询 $A\Pi$ 以进行过滤。
• 情况 2（无生产力的草图）： 如果 $\Pi$ 几乎不能消除候选者，算法则使用预计算的左侧草图 $W$ 来寻找一个“代表性”矩阵 $R \in \mathcal{C}$，使得 $\|A\Pi - R\Pi\|_F$ 较小。这通过采样候选者并检查 $\|W\Pi - \Psi^T B \Pi\|_F$ 来完成。如果找到了代表性矩阵，算法就可以使用代理规则 $\|R\Pi - B\Pi\|_F$ 来过滤候选集，而无需实际计算 $A\Pi$。

为了处理候选集与左侧草图 $\Psi$ 之间的依赖关系，算法在每次迭代中抽取 $r = O(\log |\mathcal{F}|)$ 个右侧草图，并对可能产生的各种候选集进行并集界（union bound）处理，以确保左侧草图对所有潜在的代表性矩阵都是准确的。

3. 处理未知的最优误差

算法最初需要最优误差 $\text{OPT} = \min_{B \in \mathcal{F}} \|A - B\|_F$ 的上界 $M$。作者提供了一个二分查找程序（算法 4）来进行如下操作：

1. 使用简单的草图算法计算一个粗略的初始界限 $M_{init}$。
2. 通过二分查找精细化该界限，将主双侧算法作为子程序来测试候选界限。
3. 以高概率实现 $(3+\epsilon)$ 近似。

4. 向无限族的扩展

利用覆盖数（covering number）论证，将针对有限族的结果扩展到无限族。对于具有覆盖数 $\Gamma_\alpha$ 的族，查询复杂度变为 $\tilde{O}(\sqrt{\log \Gamma_\alpha})$。具体而言，对于维度为 $q$ 的线性参数化族（例如带状矩阵、Toeplitz 矩阵、Hankel 矩阵），其覆盖数随 $q$ 缩放，从而导致查询复杂度为 $\tilde{O}(\sqrt{q})$。

关键结果

理论界限

• 定理 1（有限族上界）： 对于任何有限族 $\mathcal{F}$，存在一种算法，使用 $\tilde{O}(\sqrt{\log |\mathcal{F}|}/\epsilon^2)$ 次 matvec 查询，能以高概率找到 $\tilde{B} \in \mathcal{F}$，满足 $\|A - \tilde{B}\|_F \leq (3+\epsilon) \min_{B \in \mathcal{F}} \|A - B\|_F$。
• 定理 2（下界）： 任何为一般有限族解决问题 1 且具有常数近似因子 $\gamma$ 的算法，都需要 $\Omega(\sqrt{\log |\mathcal{F}|}/\log \gamma)$ 次 matvec 查询。这证明了上界中 $\sqrt{\log |\mathcal{F}|}$ 的依赖关系在忽略 $\log\text{-}\log$ 因子的情况下是紧确的。
• 推论 1（线性族）： 对于维度为 $q$ 的线性参数化族，可以用 $\tilde{O}(\sqrt{q})$ 次查询学习到近乎最优的近似。这改进了通过单侧草图或向量-矩阵-向量查询可实现的 $O(q)$ 界限。

具体改进

• 二次提升： 本研究证明了 matvec 查询（$x \to Ax$）相比于向量-矩阵-向量查询（$x^T A y$），在结构化矩阵学习中提供了近乎二次的优势。虽然向量-矩阵-向量查询需要 $O(\log |\mathcal{F}|)$ 次查询，但 matvec 查询仅需 $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ 次。
• 蝴蝶矩阵（Butterfly Matrices）： 下界意味着对于常秩蝴蝶矩阵（具有 $\tilde{O}(n)$ 个参数），$\tilde{O}(\sqrt{n})$ 次查询是必要且充分的，这与已知的最佳上界在对数因子范围内相匹配。

意义与主张

本文声称开启了对更广泛结构化矩阵近似的研究，超越了特定的矩阵族，转向任意有限及无限族。其主要意义在于：

1. 建立通用理论： 提供了一个框架，基于假设类的规模（或覆盖数）来表征查询复杂度，类似于监督学习中的 VC 维，但针对 matvec 模型进行了调整。
2. 展示多维输出的力量： 证明了通过查询 $A$ 和 $A^T$ 并观察向量输出的能力，可以实现与标量输出模型（向量-矩阵-向量）相比的查询复杂度的根本性降低。
3. 界限的紧密性： 证明了对于有限族，$\tilde{O}(\sqrt{\log |\mathcal{F}|})$ 界限在忽略 $\log\text{-}\log$ 因子时本质上是优化的，从而弥合了通用设定下的上界与下界之间的差距。

作者指出，目前的结果实现了常数因子近似（$\gamma = 3+\epsilon$），而以相同的查询复杂度实现 $(1+\epsilon)$ 近似仍是一个开放性问题。他们还强调，其算法依赖于右侧查询的自适应性，且实现 $\sqrt{\log |\mathcal{F}|}$ 界限对自适应性的必要性尚未得到证明。