スケッチングによる連合学習型線形文脈バンディットのスケーリング
arXiv cs.LG / 2026/5/4
📰 ニュースDeveloper Stack & InfrastructureModels & Research
要点
- 本論文は、特徴量次元 d が大きい連合学習型文脈線形バンディットで、既存手法が計算・通信の点でスケールしにくい理由（各ラウンドあたり O(d^3) の行列式計算と O(d^2) のパラメータ送信）を扱います。
- Federated Sketch Contextual Linear Bandits（FSCLB）を提案し、SVDとスケッチングにより行列式の直接計算を回避することで、各ラウンドの計算量を O(d^3) から O(l^2 d)（スケッチサイズ l<d）へ削減します。
- さらに double-sketch 戦略により通信コストも削減し、アップロード/ダウンロード費用を O(d^2) から O(l d) へ下げます。
- 非同期の連合学習条件やローカルの増分を壊し得る単純なスケッチ統合を避けるため、通信判定では共分散行列ではなくスケッチ行列を用いることで問題を解決します。
- 理論的には後悔（regret）の上界を示し、合成データと実データの実験では、計算・通信コストを90%以上削減しつつ累積報酬の低下はごくわずかであることを示します。
