技術要約：クエリ効率的な構造化行列学習

問題設定

本論文は、未知の $n \times n$ 行列 $A$ に対し、行列ベクトル積（matvec）クエリのみへのアクセスが与えられた状況下で、その構造化近似を学習する問題を取り扱う。学習者は、以前の応答に基づいてクエリベクトル $x$ を適応的に選択できる形式のクエリ $x \to Ax$ および $x \to A^T 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$ である。この設定は「アグノスティック（agnostic）」であり、$A$ が $\mathcal{F}$ に属している、あるいは $\mathcal{F}$ 内の特定の分布から生成されているという仮定は置かない。

先行研究は、主に特定の構造化された族（例：ランク $k$、スパース、階層的行列）に焦点を当て、標準的なスケッチ手法やベクトル・行列・ベクトル（$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$ の両方を利用することで、クエリ複雑性を $\tilde{O}(\sqrt{\log |\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$ を使用して、$\|A\Pi - R\Pi\|_F$ が小さいような代表的な行列 $R \in \mathcal{C}$ を見つける。これは、候補をサンプリングし、$\|W\Pi - \Psi^T B \Pi\|_F$ をチェックすることによって行われる。代表的な行列が見つかれば、アルゴリズムは $A\Pi$ を一度も計算することなく、プロキシ・ルール $\|R\Pi - B\Pi\|_F$ を用いて候補集合をフィルタリングできる。

候補集合と左スケッチ $\Psi$ の間の依存関係を処理するために、アルゴリズムはイテレーションごとに $r = O(\log |\mathcal{F}|)$ 個の右スケッチを描画し、発生しうるすべての候補集合に対して和事象の境界（union bound）を用いることで、左スケッチがすべての潜在的な代表者に対して正確であり続けることを保証する。

3. 未知の最適誤差の取り扱い

アルゴリズムは当初、最適誤差 $\text{OPT} = \min_{B \in \mathcal{F}} \|A - B\|_F$ の上界 $M$ を必要とする。著者らは、以下の手順を含む二分探索アルゴリズム（Algorithm 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}$ に対して、$\|A - \tilde{B}\|_F \leq (3+\epsilon) \min_{B \in \mathcal{F}} \|A - B\|_F$ を満たす $\tilde{B} \in \mathcal{F}$ を高い確率で見つけるために、$\tilde{O}(\sqrt{\log |\mathcal{F}|}/\epsilon^2)$ 回の matvec クエリを使用するアルゴリズムが存在する。
• 定理 2（下界）： 一般的な有限な族に対して定数近似因子 $\gamma$ を解く問題 1 を解くアルゴリズムは、$\Omega(\sqrt{\log |\mathcal{F}|}/\log \gamma)$ 回の matvec クエリを必要とする。これにより、$\sqrt{\log |\mathcal{F}|}$ の依存性が、上界における $\log \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}|})$ で済む。
• バタフライ行列： 下界は、定数ランクのバタフライ行列（$\tilde{O}(n)$ のパラメータを持つ）に対して、$\tilde{O}(\sqrt{n})$ クエリが必要かつ十分であることを示唆しており、これは対数因子を除いて最良の既知の上界と一致する。

意義と主張

本論文は、特定の行列族を超えて、任意の有限および無限な族へと、構造化行列近似の研究を一般化するものである。その主な意義は以下の通りである：

1. 一般的な理論の確立： 監督学習における VC 次元に類似した、matvec モデルに適応した、仮説クラスのサイズ（または被覆数）に基づいてクエリ複雑性を特徴付けるフレームワークを提供すること。
2. 多次元出力の力の証明： $A$ と $A^T$ をクエリし、ベクトル出力を観察できる能力が、スカラー出力モデル（ベクトル・行列・ベクトル）と比較して、クエリ複雑性を根本的に減少させることを証明すること。
3. 境界のタイト性： 有限な族に対して $\tilde{O}(\sqrt{\log |\mathcal{F}|})$ という境界が、$\log \log$ 因子の差を除いて本質的に最適であることを示し、この一般的な設定における上界と下界のギャップを埋めること。

著者らは、現在の結果が定数倍の近似（$\gamma = 3+\epsilon$）を達成していることを指摘しており、同じクエリ複雑量で $(1+\epsilon)$ 近似を達成することは未解決の問題であるとしている。また、彼らのアルゴリズムは右側のクエリに対して適応性に依存しており、$\sqrt{\log |\mathcal{F}|}$ の境界を達成するために適応性が必須であることはまだ証明されていないことも強調している。