Constrained Learning with Universally Learnable Concept Classes

技術要約：普遍的に学習可能な概念クラスを用いた制約付き学習

1. 問題設定

本論文は、完全な非凸設定における無限次元仮説クラス上の制約付き統計的学習を扱う。目的は、主予測リスク $R_0(\phi)$ を、$m$ 個の制約 $R_i(\phi) \leq 0$ （$i=1, \dots, m$）の下で最小化することである。ここで、リスクは、異なるデータ分布 $D_i$ の下での、潜在的に非凸な損失汎関数の期待値である。

核心となる困難さは、実行可能な学習理論に求められる2つの要件間の構造的な緊張関係から生じる：

1. 強双対性（母集団レベル）： ラグランジュ双対問題が主制約問題を忠実に特徴付けること（双対ギャップがゼロであること）を保証するためには、仮説クラスは分解可能（decomposable）（可測なスプライシングに対して閉じていること）でなければならない。この性質は、ベクトル測量に対するリャプノフ凸性と関連しており、個々の汎関数が非凸であっても、到達可能なリスクベクトルの集合が凸であることを保証する。しかし、分解可能な空間（例：$L_p$ 空間）は、有限のデータから統計的な汎化性能（ラデマッハー複雑度の消失）を得るには大きすぎる。
2. 統計的汎化性能（経験レベル）： 有限のサンプルから学習可能であることを保証するためには、仮説クラスが制御された統計的複雑さ（例：減衰するラデマッハー複雑度）を持つ必要がある。再生核ヒルベルト空間（RKHS）のノルム球のような標準的な選択肢はこれを満たすが、これらは分解可能ではないため、サンプルサイズを増やしても制約違反をゼロにできない不可避な近似誤差（near-PACC結果）が生じる。

既存のアプローチは、単一の有限複雑度クラスを使用することで妥協することが多く、その結果、データが増えても消失しない残留誤差を伴う「near-PACC」の保証に留まっている。本論文は、このような不可避な残留誤差なしに、正確な、あるいは準正確な学習可能性を実現するために、この緊張関係を解消することを目指している。

2. 手法

著者らは、高密度RKHSクラスと双対経験的リスク最小化（DERM）を用いた可変複雑度フレームワークを提案している。

• 普遍的RKHS上の母集団問題： 母集団の制約問題は、分解可能なエンベロープ空間 $\mathcal{G}$（例：$L_p$ 空間）において稠密な普遍的RKHS $\mathcal{H}_K$ 上に設定される。$\mathcal{H}_K$ 自体は分解可能ではないが、$\mathcal{G}$ におけるその稠密性により、連続性の議論を通じて$\mathcal{G}$ から $\mathcal{H}_K$ へ強双対性の性質を転移させることが可能となる。
• 成長するノルム球を用いた経験的問題： 学習者は、サンプルサイズ $n$ とともに半径 $Q_n$ が増大する一連の閉じたノルム球 $B_{Q_n} = \{f \in \mathcal{H}_K : \|f\|_{\mathcal{H}_K} \leq Q_n\}$ 上で動作する。ここで、$Q_n \to \infty$ かつ $Q_n/\sqrt{n} \to 0$ となるように $Q_n$ を設定する。
  • これにより、探索空間は最終的にRKHSを網羅し（母集団解を捉える）、同時に、球 $B_{Q_n}$ の統計的複雑さ（ラデマッハー複雑度）は $O(Q_n/\sqrt{n})$ として消失し、一様収束を保証する。
• DERMアルゴリズム： 学習者は、非負の乗数に対して経験的双対関数を最大化し、次に現在の球 $B_{Q_n}$ 上で経験的ラグランジュ関数を最小化する。
• 実現可能性の分析： 非凸性により、ラグランジュ関数が下限を達成できなかったり、単一の予測器が双対劣微分を実現することを保証できなかったりするため、著者らは閉包–実現ギャップ（closure–realization gap） $\varepsilon^\star_\infty$ を導入している。この幾何学的定数は、双対関数の超微分と、RKHS内の予測器によって実現可能なリスクベクトルの集合との間の距離を測定する。

3. 主な貢献

1. 普遍的な（準）PACC学習可能性：
本論文は、アグノスティックな普遍的恐らく近似的に正しい制約付き（PACC）学習可能性を確立している。分布フリーのPAC学習とは異なり、ここでのサンプル複雑度は、RKHSの高次元の表現力ゆえに、基礎となる分布（具体的にはスレーター・マージンとティコノフ複雑度を通じて）に依存することが許容される。

• 正確な学習可能性： $\varepsilon^\star_\infty = 0$ の場合（例：双対微分可能性の下）、学習者は正確な実現可能性と最適性を達成する。
• 準PACC学習可能性： $\varepsilon^\star_\infty > 0$ の場合、学習者は $\varepsilon^\star_\infty$ と等しい残留誤差内で最適性と実現可能性を達成する。極めて重要な点は、この残留誤差は問題の幾何学的な固有特性であり、固定されたモデリングの選択によるアーティファクトではなく、良好な条件下では消失することである。

2. プライマル達成を伴わない実現可能性証明：
完全な非凸領域では、制約付き主問題に達成された解が存在しない場合がある。本論文は、DERMの出力が、たとえプライマル最小化器が存在しないと仮定しても、漸近的に実現可能であり、$\varepsilon^\star_\infty$ まで準最適であることを証明している。これは、レヴィン–バラディエールの超微分の表現を用いた双対側からの変分議論を通じて達成される。

3. 明示的な統計的レート：
著者らは、最適値を学習するための明示的な多項式サンプル閾値を導出している。彼らは、$\varepsilon$-最適ラグランジュ・レベルセットに到達するために必要な最小限のRKHSノルムとして定義されるティコノフ複雑度 $T^\varepsilon_n$ を導入した。正則化パスに関する標準的なソース条件の下で、彼らは $T^\varepsilon_n$ が有限であることを示し、$O(\varepsilon^{-\max\{4, 2(1-\beta)/\beta\}})$（ここで $\beta$ はソース条件を特徴付ける）のサンプル複雑度を導出した。

4. 普遍的フレームワークの必要性：
本論文は、普遍的RKHSの無制限の容量により、彼らの設定の非制約的な特殊化においては、分布フリーのサンプル閾値が存在しないことを証明している。したがって、普遍的学習フレームワーク（レートが分布に依存する）は、単に便利なだけでなく、大きな仮説クラスに対する双対アルゴリズムにとって**規範的（canonical）**なものである。

4. 主な結果

• 定理1： 成長するノルム球を持つ高密度RKHS上のDERMは、普遍的にPACC学習可能であることを確立している。
  • (i) 明示的な閾値を伴う、最適値の正確な学習可能性。
  • (ii)–(v) 閉包–実現ギャップ $\varepsilon^\star_\infty$ によって制御される実現可能性および準最適性の保証。
  • (vi) $\varepsilon^\star_\infty = 0$ の時の正確なPACC学習可能性。
• 系1： ソース条件の下での明示的な多項式サンプル複雑度の境界を提供する。
• 補題1： 閉包–実現ギャップを特徴付け、双対関数が最適点において微分可能であれば、それが消失することを示す。

5. 意義と主張

本論文は、母集団レベルの強双対性（分解性を要求）と有限サンプルでの汎化性能（低複雑度を要求）の間の根本的な構造的緊張関係を解決すると主張している。普遍的RKHSの分解可能なエンベロープにおける稠密性を活用することで、著者らは、ノルム球の制限を通じて統計的制御を維持しながら、大きな空間の正確な双対性を継承できることを示している。

その意義は、「不可避な残留誤差を伴うnear-PACC結果」を超えた点にある。本論文は、従来の残留誤差は固定されたパラメトリック近似のアーティファクトであったのに対し、彼らの残留誤差（$\varepsilon^\star_\infty$）は問題自体の幾何学的定数であり、良好な幾何学の下では証明可能に消失するものであると論じている。これは、不均質な分布の下で制約の実現可能性を保持できない可能性のある凸サーロゲートに頼ることなく、非凸設定（例：公平性や安全性の制約を伴うディープラーニング）における制約付き学習の理論的基礎を提供するものである。

著者らが認める限界事項：

• 実現可能性のために必要な回復条件（仮定5）は、正確な領域（$\varepsilon^\star_\infty=0$）においては一般的な基準によって検証される。
• 実現可能性に関するアグノスティックな主張はこの仮定に依存しているが、値の学習は達成フリー（attainment-free）である。
• DERMの手順は理想化されたアルゴリズムの仕様であり、実用的なプライマル・デュアル・スキームの計算実装と収束については今後の課題とされている。
• 明示的なレートはソース条件に依存している。これがない場合、閾値は有限であるが非明示的である。