Cost-sensitive spectral sampling algorithms for randomized block Kaczmarz methods

技術要約：ランダム化ブロック・カッツ法のためのコスト感受性スペクトル・サンプリング・アルゴリズム

問題提起
本論文は、一貫した線形システム $Ax=b$ を解くために用いられるランダム化ブロック・カッツ法（randomized block Kaczmarz methods）のオフライン設計問題を取り扱う。ランダム化ブロック・カッツ法は、方程式のブロックをランダムに選択して反復計算を行うが、その保証された収束率は、サンプリング分布に大きく依存する。実用上の重要な制約として、方程式の各ブロックは、メモリレイアウト、通信オーバーヘッド、あるいはブロックサイズに起因して、極めて異なる計算コストを発生させる可能性がある。

既存のアプローチは、ノルム比例型やパビング（paving）に基づくものなどのヒューリスティックを規定したり、現在の残差に適応したり、あるいはコストを考慮しない量量を最適化したりするものである。ここで扱われる具体的な問題は、許容されるブロックの固定された有限なカタログと、それに付随する正のコストが与えられたとき、どの静的な確率分布が、期待される計算量あたりの保証された指数的収束率を最大化するか、という点である。

手法および理論的枠組み
著者らは、各ブロック $B$ を、その行空間への直交射影 $P_B$ とコスト $c_B$ を用いて定式化することで、問題を形式化している。

1. ワーク正規化された証明（Work-Normalized Certificate）: 標準的な収束証明は、$A^T$ の値域に制限された期待射影 $H_p = \sum p_B P_B$ の最小固有値 $\mu(p)$ によって支配される。1ステップあたりの期待ワークは $\bar{c}(p) = \sum p_B c_B$ である。目的は、比率 $\eta(p) = \mu(p) / \bar{c}(p)$ を最大化することである。
2. 最適設計の定式化: 変数変換 $w_B = p_B / \bar{c}(p)$ を導入することで、問題は、コストでスケールされた射影の加重和 $G_B/c_B$（ここで $G_B$ は行空間に制限された射影）の最小固有値を最大化することへと変換される。これは、**コスト感受性E-最適設計問題（cost-sensitive E-optimal design problem）**として特定される。
3. 半正定値計画問題（SDP）: 問題は以下のSDPとして定式化される：
   $$\max t \quad \text{s.t.} \quad \sum w_B G_B \succeq t I_r, \quad \sum w_B c_B = 1, \quad w_B \ge 0$$
   ここで $r = \text{rank}(A)$ である。
4. 双対証明（Dual Certificate）: 本論文では、「ハード方向（hard-direction）」の証明を含む双対定式化を導出している。最適な値 $\eta^*$ は、トレース1の正定値行列 $Z$ に関する、カタログ全体の最大コスト正規化方向効率 $\langle G_B, Z \rangle / c_B$ の最小値である。これにより、任意の候補設計に対する厳密な事後的なギャップ（a posteriori gap）が得られる。
5. 疎なサポート（Sparse Support）: カラテオドリの定理に基づく定理により、高々 $r(r+1)/2 + 1$ 個のブロックをサポートとする最適設計が存在することが確立されている。

アルゴリズムによる貢献
本論文は、最適な静的分布を計算するための2つの証明付きアルゴリズムを提案している。

1. 厳密な交換法（Exact Exchange Method）: 小さなアクティブセットを維持する列生成スキームである。まず、候補となる分布と双対証明を見つけるために制限されたマスターSDPを解き、次に、新しいブロックを特定するために全カタログに対して「プライシング（価格設定）」ステップを実行し、証明を改善する。この手法は、厳密な最適化ギャップを提供する。
2. Frank-Wolfe型のスペクトル設計（Frank-Wolfe-type Spectral Design）: 射影のコスト正規化された凸包に適用される一次条件付き勾配法である。現在の最も弱い固有方向（最小固有値関数の劣勾配）に対して、最も高い方向効率を持つブロックを反復的に選択する。この手法は、制限されたSDPを解く必要がなく、ブロック選択とギャップの証明の両方に同じ量を用いる。

結果および診断テスト
本論文では、特定のメカニズムを分離するために、大規模なベンチマークではなく、診断的な数値テストを提示している。

• 冗長性（テストA）: いくつかの方向に対して多くの冗長なブロックが存在するカタログでは、一様サンプリングやノルムベースのサンプリングは、冗長性に確率質量を浪費するため性能が低い。スペクトル設計は、独立した方向へ質量を集中させ、証明を $(N+1)/2$ 倍改善する。
• コストの不均一性（テストB）: 安価な単一要素ブロックと高価な大きなブロックが存在する設定において、コストを無視したスペクトル設計（コストを無視したもの）は、高価なブロックを選択し、1イテレーションあたりの利得は高いものの、ワーク正規化された性能は低くなる。コスト感受性設計は、より安価なブロックを適切に選択し、目標誤差に達するまでの総ワークを大幅に減少させる。
• 疎な非対角ケース（テストC）: ブロックのサイズとコストが変化する（立方関数でモデル化された）疎な行列を用いた場合でも、コスト感受性設計は、一様、ノルムベース、およびコスト無視のスペクトル・ベースラインを再び上回った。20回の試行における観測された中央値のワークは、理論的なワーク正規化された証明によって予測された順序と密接に一致していた。

意義および主張
本論文は、既存のランダム化射影理論に対して補完的な視点を提供することを主張している。本論文は新しい射影ステップを導入したり、正確な平均二乗軌跡を最適化することを主張したりするものではない。その意義は以下の点にある：

• 形式的な特定: オフラインのブロック選択問題を、コスト感受性E-最適設計問題として明示的に特定したこと。
• 証明付きアルゴリズム: 静的な分布が、最適なワーク正規化された率にどれだけ近いかを定量化する、明示的な事後的証明（ギャップ）を備えた2つのアルゴリズムを提供したこと。
• 実用的な洞察: 行空間の情報が冗長である場合や、ブロックコストのバランスが崩れている場合に、標準的なヒューリスティック（一様、ノルムベース）が大幅に劣位となり得ることを示したこと。
• 適用範囲: 本手法は、ブロックカタログが多くの右辺ベクトルに対して再利用されるシナリオ、またはブロックコストが著しく異なるシナリオに最も適した、オフラインの静的なルールとして位置付けられている。これは、設計コストが解決コストを上回る単一解決シナリオのためのものではなく、また、異なるオンライン問題を解く適応的な残差ベースの手法に取って代わるものでもない。