マルコフ依存下における多数決アンサンブルの分光ルーティングとミニマックス最適性

要旨: 多数決アンサンブルは、多様で、概ね独立な基となる学習器（base learners）にわたって平均化することで、分散低減を達成します。学習データがマルコフ従属性を示す場合、たとえば時系列予測、強化学習（RL）のリプレイバッファ、空間グリッドのような設定では、この古典的な保証が、既存の理論が十分に定量化できていない形で劣化します。本研究では、固定次元のマルコフ設定における離散分類について、この現象のミニマックス的な特徴づけを与えます。また、グラフ正則（graph-regular）な部分クラスに対して、その率（rate）に一致する適応型アルゴリズムも提案します。まず、固定された周辺次元（ambient dimension）における定常・可逆・幾何学的にエルゴード的な（geometrically ergodic）鎖について、情報理論に基づく下界を確立し、測定可能な推定器（measurable estimator）が超過分類リスク（excess classification risk）を
\Omega(\sqrt{\Tmix/n}) より良くすることはできないことを示します。次に、この下界の構成を支えるAR(1)の目撃（witness）部分クラスにおいて、従属性に依存しない一様バギング（uniform bagging）が、超過リスクが
\Omega(\Tmix/\sqrt{n}) 以下で抑えられる形で証明可能に劣適（suboptimal）であることを示し、さらに
\sqrt{\Tmix} のアルゴリズムギャップを明らかにします。最後に、
\emph{適応スペクトルルーティング（adaptive spectral routing）}を提案します。これは、依存関係グラフの経験的フィードラー固有ベクトル（empirical Fiedler eigenvector）により訓練データを分割し、
\Tmix の知識なしに、グラフ正則部分クラス上で低次の幾何学的カット項（lower-order geometric cut term）まで含めてミニマックス率
\mathcal{O}(\sqrt{\Tmix/n}) を達成します。合成マルコフ鎖、2次元空間グリッド、128データセットのUCRアーカイブ、Atari DQNアンサンブルに関する実験により、理論予測が検証されます。深層強化学習における目標の分散（target variance）への帰結、Nystr"om近似によるスケーラビリティ、ならびに有界な非定常性（bounded non-stationarity）については、付録の補足資料として展開します。