技術要約：容量制約のある遅延フィードバックを伴うオンライン凸最適化

1. 問題設定

本論文は、遅延フィードバックと限定的な追跡容量という2つの同時制約下におけるオンライン凸最適化 (OCO) および バンディット凸最適化 (BCO) を扱う。

標準的な遅延オンライン学習では、学習者は時刻 $t$ において行動 $x_t$ を選択し、損失 $f_t(x_t)$ を被るが、フィードバック（勾配またはスカラー損失）は時刻 $t + d_t$ にのみ受け取る。従来の文献では、学習者がフィードバックが到着するまで、保留中のすべてのラウンドを追跡するための無制限の容量を持っていると仮定している。しかし、実用的なシナリオ（例：限られたモニタリングリソースを持つ臨床試験）では、学習者が追跡できる保留中のラウンドの数は、容量 $C$ として定義される有界な数に制限される。もしあるラウンドが追跡されない場合、そのフィードバックは永久に失われる。

本論文では、これを以下のようなゲームとして定式化している：

• アドバーサリ（敵対者）は、凸損失 $f_t$ と遅延 $d_t$ を固定する。
• プレイヤーは、最大サイズ $C$ の追跡セット $S$ を維持する。
• 各ラウンドにおいて、プレイヤーは追跡中のラウンドをプリエンプト（破棄）するか、現在のラウンドを $S$ に追加することができる。
• ラウンド $s$ のフィードバックは、$s \in S$ である場合に限り、時刻 $s + d_s$ に観測される。
• 目標は、事後的に最良の固定行動 $x^*$ に対して、リグレット $R_T = \sum_{t=1}^T (f_t(x_t) - f_t(x^*))$ を最小化することである。

本論文では、遅延に関する2つの情報モデルを検討している：

1. 明示的（Clairvoyant）: 遅延 $d_t$ が予測時に既知である。
2. 半明示的（Semi-Clairvoyant）: 遅延は、標準的な遅延学習の設定と同様に、満了時（$t+d_t$）にのみ明らかになる。

2. 手法

著者らは、容量制約のある問題を、スケジューラとベース学習器の2つのコンポーネントに分解する還元ベースのアプローチを提案している。

2.1 還元フレームワーク

核心となるアイデアは、容量制約のある問題を、新しい**「遅延および重み付き」OCO**問題へと還元することである。

• スケジューラ: ラッパーアルゴリズムが追跡セット $S$ を管理する。これはプロキシ遅延スケジューリングメカニズムを使用する。各ラウンド $t$ について、スケジューラは分布 $D_t$ から「プロキシ遅延」$d'_t$ をサンプリングする。$d'_t \ge 0$ かつ容量に余裕がある場合、ラウンド $t$ は $S$ に追加される。フィードバックがまだ到着していない場合、時刻 $t + d'_t + 1$ に $S$ から削除される。
• 重要度重み付け: もしラウンド $s$ のフィードバックが観測された場合（すなわち、$s \in S$ かつ $d'_s \ge d_s$）、ラッパーは重要度重み $w_s = 1 / P(d'_s \ge d_s)$ を付与してベース学習器にフィードバックを転送する。フィードバックが失われた場合（容量飽和または早期のプロキシタイムアウトによる）、重みは0に設定される。
• ベース学習器: 学習器は、遅延および重み付きのフィードバックのストリームを受け取る。本論文では、この重み付き遅延ストリームを扱うために特別に設計されたアルゴリズムを導入している。

2.2 ベースアルゴリズム：DW-FTRL

本論文では、重み付き遅延設定のための2つのベースアルゴリズムを紹介している：

1. DW-FTRL (Delayed-Weighted Follow-the-Regularized-Leader): 1次（勾配）フィードバック用。観測されたすべてのラウンドからの重み付き勾配を集約した正則化目的関数を最小化することで、イテレートを更新する。
2. DW-FTBL (Delayed-Weighted Follow-the-Bandit-Leader): バンディット（スカラー損失）フィードバック用。標準的なシングルポイント勾配推定法（中心点を摂動させる手法）を使用するが、これを重み付き遅延フィードバックのストリームに適用する。

これらのベースアルゴリズムの理論的解析により、時間とともに変化する重みと、保留中の観測のバックログとの相互作用を明示的に考慮したリグレット境界が確立されている。主要な知見は、リグレットが、遅延が重複するラウンド間の重みのペアワイズな相互作用に依存することである。

2.3 プロキシ遅延スケジューラ

還元を機能させるためには、スケジューラは「真の遅延をカバーすること（フィードバックを観測すること）」と「容量飽和を避けること」という2つの相反する目標のバランスを取る必要がある。本論文では、2つの具体的なスケジューラを提案している：

1. パレート・スケジューラ (Pareto Scheduler): 個々の遅延 $d_t$ に適応する。シフトされたパレート分布からプロキシ遅延をサンプリングし、追跡する確率を遅延に反比例させる。これは一般的な凸損失に適している。
2. ベルヌーイ・スケジューラ (Bernoulli Scheduler): 最大バックログ $\sigma_{max}$（任意の時刻における保留中の観測数の最大値）に合わせて調整される。プロキシ遅延として、確率 $p \approx C / \sigma_{max}$ で $\infty$ を、それ以外の場合は $-1$ をサンプリングする。これにより、一様重要度重みが得られ、強凸およびバンディット設定において強力な保証を得るための重要な特性となる。

3. 主な貢献

1. 容量制約付き OCO/BCO に対する初のリグレット保証: 本論文は、凸および強凸ドメインの両方において、1次フィードバックおよびバンディットフィードバックの両方に対する、容量制約付き遅延フィードバックのサブリニアなリグレット境界を初めて提供する。
2. 遅延および重み付き OCO フレームワーク: 新しい問題設定（遅延および重み付きフィードバック）を導入し、それに対する FTRL 変種を分析する。このフレームワークは、遅延を伴うスケールフリーなオンライン学習において独立した関心事である。
3. 統一されたプロキシ遅延スケジューリング: 著者らは従来のスケジューリングのアイデアを統合し、一様重みをもたらす新しいスケジューラ（ベルヌーイ）を導入し、強凸およびバンディット設定でより強力な保証を可能にした。
4. 未知のパラメータの処理: フレームワークは、半明示的モデル（予測時に遅延が未知）に対応しており、未知の $\sigma_{max}$ を事前知識なしで扱うためのダブリングトリックを使用している。

4. 主な結果

リグレット境界は、ホライゾン $T$、次元 $k$、総遅延 $d_{tot}$、最大バックログ $\sigma_{max}$、および容量 $C$ に依存する。

4.1 1次フィードバック (OCO)

• 凸損失: 容量 $C = \Omega(\log T)$ の場合、リグレットは対数因子を除いて最適な無制約遅延レートと一致する：
  $$\tilde{O}\left( G D \sqrt{d_{tot} + T} \right)$$
• 強凸損失: リグレットは以下の通りである：
  $$\tilde{O}\left( \frac{G^2}{\lambda} (\sigma_{max} + 1) \log T \right)$$
  これは、無制約の設定で見られる $\sigma_{max}$ に対する最適な依存関係と一致する。

4.2 バンディットフィードバック (BCO)

バンディットフィードバックの場合、容量制約は因子 $(1 + \sigma_{max}/C)$ を通じて次元依存項に影響を与える。

• 凸損失:
  $$\tilde{O}\left( GD \left( \sqrt{T \sigma_{max}} + T^{3/4} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/4} \sqrt{\nu k} \right) \right)$$
  ここで $\nu$ は関数値と勾配のスケール比である。境界は $C$ が減少するにつれて緩やかに悪化する。
• 強凸損失:
  $$\tilde{O}\left( \frac{G^2}{\lambda} \left( \sigma_{max} \log T + (T^2 \log T)^{1/3} \left(1 + \frac{\sigma_{max}}{C}\right)^{1/3} (\nu k)^{2/3} \right) \right)$$

重要な観察: $C \ge \sigma_{max}$ のとき、境界は無制約のレートを回復する。$C < \sigma_{max}$ のとき、リグレットは増加するが、依然としてサブリニアである。$\sigma_{max}$（ピーク同時実行数）への依存性は、キューイングのようなシステムにおいては $d_{max}$（最大遅延）への依存性よりも自然であることが示されている。

5. 意義と主張

本論文は、容量制約付き OCO および BCO のリグレット保証を導出した最初の論文であると主張している。その意義は以下の点にある：

• 理論と実務の架け橋: 無制限の容量を仮定する従来の遅延学習文献が無視してきた、追跡リソースが有限であるという現実的な制約に対処している。
• 遅延モデルの精緻化: 遅延が満了時にのみ明らかになる半明示的モデルを採用することで、本研究は、従来の「明示的」な仮定よりも、標準的な遅延学習やオンラインジョブスケジューリングの実態に近いものとなっている。
• 緩やかな劣化: 結果は、1次フィードバックについては対数的な容量（$C = \Omega(\log T)$）があれば標準的な遅延レートを回復できる一方で、バンディットフィードバックについては、容量がピークバックログを下回ると性能が緩やかに低下することを示している。
• 理論的新規性: 「遅延および重み付き」OCO 問題の導入と、重みと遅延の相互作用に関する具体的な FTRL 解析は、リソース制約下でのオンライン学習を分析するための新しいツールを提供している。

著者らは、凸バンディットフィードバックの境界が、無制約設定の最適な $\sqrt{d_{tot}}$ ではなく $\sqrt{T \sigma_{max}}$ でスケールすることに触れ、それでも $\sqrt{T d_{max}}$ に依存する従来の境界よりも改善されていると述べている。このギャップを埋めることが今後の課題であるとしている。また、彼らのモデルと有限バッファのキューイングシステムとの構造的な類似性は、さらなる探求に値すると示唆している。