技術要約：オンライン実現可能回帰とReLUネットワークへの応用

問題設定

本論文は、確率的な仮定やマージン条件を一切課さない敵対的設定における、実現可能オンライン回帰（realizable online regression）を調査している。核心となる問題は、実現可能性（ターゲットとなる仮説 $h^* \in \mathcal{H}$ がラベルを完全に生成できること）が、いつホライゾンフリー（有限の）累積損失界を意味するかを決定すること、およびこの界を支配する複雑性パラメータを特定することである。

著者らはこれをオンライン分類と比較している。オンライン分類では、単純なパーセプトロンのようなクラスであっても、マージン仮定がない場合には無限の誤り界を持つことがある。しかし、回帰においては、実現可能性が（近似的な擬似距離のような）メトリック的損失の下で、有限の総損失を強制する場合がある。これは、分類問題が学習不可能である場合でも起こり得る。本研究は、近似三角形不等式（近似擬似距離）を満たす損失関数 $\ell$ に焦点を当てている。この条件は、仮説空間に大きなギャップがあるにもかかわらず、学習者が無視できるほどの損失で中間的なラベルを予測できてしまうような退化したシナリオを防ぐために必要である。

手法

本論文では、実現可能な最小最大累積損失を特徴付ける、Attiasら [2] によって導入された抽象的な次元であるスケールド・リトルトレディメンション（scaled Littlestone dimension） ($D_{\text{onl}}$) を上界付けるための、汎用的なポテンシャル法を導入している。

エントロピー・ポテンシャル・フレームワーク

$D_{\text{onl}}$ を直接計算することは困難な場合があるため、著者らは、誘導された上限擬似距離 $d_\ell(f, g) = \sup_{x} \ell(f(x), g(x))$ に関する仮説クラス $\mathcal{H}$ の被覆数に基づくダドリー型エントロピー積分を用いて、$D_{\text{onl}}$ を上界付けしている。

1. エントロピー・ポテンシャルの定義: 有限の直径を持つ仮説クラス $\mathcal{H}$ に対して、エントロピー・ポテンシャルは以下のように定義される：
   $$\Phi(\mathcal{H}) = \int_{0}^{\text{diam}(\mathcal{H})} \log_2 N(\mathcal{H}, \varepsilon) \, d\varepsilon$$
   ここで、$N(\mathcal{H}, \varepsilon)$ は $d_\ell$ に関する $\mathcal{H}$ の $\varepsilon$-被覆数である。

2. 主要定理: 著者らは、任意の $c$-近似擬似距離損失に対して、スケールド・リトルトレディメンションがエントロピー・ポテンシャルによって上界付けられることを証明している：
   $$D_{\text{onl}}(\mathcal{H}) \leq 4c \cdot \Phi(\mathcal{H})$$
   証明には、実現可能なスケールド・リトルトレディ・ツリーに対する**分岐限定（branch bound）**論法を用いている。各ノードにおけるバージョン空間を分析することで、近似三角形不等式により、$\varepsilon < \gamma/(2c)$ であるとき、いかなる $\varepsilon$-被覆もギャップ $\gamma$ を持つノードの子へと分割されることを示している。この「被覆の分割」をスケール間で積分することにより、任意の枝に沿った総ギャップが $\Phi(\mathcal{H})$ に比例して減少することを導き、枝に沿った総ギャップを $\Phi(\mathcal{H})$ で抑える。

3. 含意: もし $\mathcal{H}$ が多項式被覆数を持つ（すなわち、$N(\mathcal{H}, \varepsilon) \leq (A/\varepsilon)^p$）ならば、$\Phi(\mathcal{H}) < \infty$ となり、ホライゾンフリーな実現可能累積損失界が存在することを示唆する。

主要な貢献と結果

1. $\ell_q$ 損失下でのリプシッツ回帰

著者らは、$[-1, 1]^d$ 上の $L$-リプシッツ関数クラス $\mathcal{H}_L$ に対し、損失 $\ell_q(y, y') = |y - y'|^q$ を適用している。彼らは、$q$ と次元 $d$ の関係に基づく鋭い相転移を確立した：

• 学習可能な領域 ($q > d$): エントロピー・ポテンシャルは有限である。最小最大実現可能累積損失は $\Theta_{d,q}(L^d)$ である。著者らは、リプシッツ包絡線（下界および上界）に基づく効率的な決定論的プロパー・アルゴリズムを提供し、これがこの界を達成することを示す。
• 学習不可能な領域 ($q \leq d$): エントロピー・ポテンシャルは発散する。
  • $q < d$ の場合、最小最大累積損失はホライゾン $T$ に対して多項式的に増大する。
  • $q = d$ の場合、損失は $T$ に対して対数的に増大する。
  • いずれの場合も、$D_{\text{onl}}(\mathcal{H}_L) = \infty$ である。
• 漸近的学習可能性: 任意の連続な損失 $\ell$ （ただし $\ell(y,y)=0$）について、リプシッツ関数に対しては、総累積損失が有限であるかどうかにかかわらず、瞬時損失 $\ell(\hat{y}_t, y_t)$ が $t \to \infty$ として 0 に収束することを示す。

2. 有界 $k$-ReLU ネットワーク

本論文では、二乗損失を用いた、$[-1, 1]^d$ 上の有界 $k$-ReLU ネットワークのクラス $\mathcal{H}_{k,d}$（有界な重みを持つ $k$ 個の ReLU の和）を研究している。

• 回帰と分類の分離:
  • 分類: 0/1 損失の下では、$\mathcal{H}_{2,1}$（2つの隠れニューロン、1次元入力）に対して実現可能なオンライン分類は不可能である。なぜなら、有界な重みを用いてもリトルトレディメンションが無限になるためである。
  • 回帰: 二乗損失の下では、実現可能なオンライン回帰は有限の総損失を許容する。
• 上界:
  • 累積損失 $O(k^2 \log^4 d) = \tilde{O}(k^2)$ を持つ（情報理論的な）オンライン・アルゴリズムが存在する。
  • 単一の ReLU ($k=1$) の場合、次元 $d$ に依存せず $O(1)$ の累積損失を実現する効率的なアルゴリズムが存在する。
• 下界:
  • $\Omega(k^2 \log(d/k^2))$ の下界が証明されており、$k$ と $\log d$ への依存関係が必要であることを示している。
• 計算量的な困難性:
  Gap-ETH 仮定に基づき、著者らは $k \geq 2$ において、蓄積された損失 $e^{o(d)}$ を $d$ に関する多項式時間で達成する効率的なプロパー・オンライン学習者の存在を否定している。これは、情報理論的には有限の損失が可能であっても、プロパー学習者として効率的に計算することは困難である可能性を示唆している。

3. 深層ネットワークへの一般化

これらの結果は、深さ $L$、幅 $k$ のネットワークへと拡張される。最小最大実現可能二乗累積損失は $\tilde{O}(k^L)$ と示され、$d/k^L \to \infty$ のとき、$\Omega(k^L \log(d/k^L))$ の一致する下界が得られる。

意義と主張

本論文は、実現可能性が、アグノスティック（agnostic）な設定と比較して、オンライン学習の景観を根本的に変えることを主張している。具体的には：

1. 複雑性の尺度としてのメトリック・エントロピー: 著者らは、近似擬似距離の下での実現可能オンライン回帰において、メトリック・エントロピー（エントロピー・ポテンシャル $\Phi$ を通じて）が、$D_{\text{onl}}$ の十分かつ多くの場合においてタイトなプロキシ（代理指標）であることを確立した。これにより、抽象的な次元が扱いにくい場合に、具体的で計算可能なツールを提供している。
2. 非パラメトリック回帰における相転移: 本研究は、非パラメトリック・リプシッツ回帰がホライゾンフリーとなる正確な条件 ($q > d$) を特定しており、これは分類や $q \leq d$ の回帰の学習不可能性と鋭い対照をなしている。
3. ニューラルネットワークの学習可能性: 本論文は、ReLU ネットワークにおける分類と回帰の顕著な分離を強調している。有界な ReLU ネットワークは、分類の設定では学習不可能（リトルトレディメンションが無限）であるが、回帰の設定では有限の累積損失を許容する。しかし、この学習可能性には注意が必要である。$k \geq 2$ の場合、プロパー学習者によってこれを効率的に達成することは、計算量的に困難である可能性が高い。
4. 限界: 著者らは、エントロピー・ポテンシャルによる上界が常にタイトであるとは限らないことを指摘している。すなわち、$\Phi(\mathcal{H}) = \infty$ であるが $D_{\text{onl}}(\mathcal{H}) < \infty$ となるクラスが存在する。したがって、$\Phi$ は完全な特性化ではなく、明示的な上界のサロゲート（代用物）として機能する。

本研究は、最新のオンライン次元理論 [2] に依拠しており、確率過程（ダドリー積分）の手法を敵対的オンライン設定に適応させている。その際、実現可能性の仮定があるため、逐次的なチェイニング（sequential chaining）ではなく、標準的な被覆（covers）を用いている。