論文の概要: Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence
- arxiv url: http://arxiv.org/abs/2604.13414v1
- Date: Wed, 15 Apr 2026 02:32:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-16 20:38:32.356131
- Title: Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependence
- Title（参考訳）: マルコフ依存下での極小極小最適化とスペクトルルーティング
- Authors: Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma,
- Abstract要約: 主要声楽アンサンブルは、多種多様なほぼ独立した基礎学習者に対して平均化することにより、ばらつきの低減を実現する。
固定次元マルコフ集合における離散的な分類のために、この現象のミニマックス的特徴付けを行う。
合成マルコフ連鎖、2次元空間格子、128データセットのUCRアーカイブ、アタリDQNアンサンブルに関する実験は、理論的な予測を検証している。
- 参考スコア（独自算出の注目度）: 6.908972852063454
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Majority-vote ensembles achieve variance reduction by averaging over diverse, approximately independent base learners. When training data exhibits Markov dependence, as in time-series forecasting, reinforcement learning (RL) replay buffers, and spatial grids, this classical guarantee degrades in ways that existing theory does not fully quantify. We provide a minimax characterization of this phenomenon for discrete classification in a fixed-dimensional Markov setting, together with an adaptive algorithm that matches the rate on a graph-regular subclass. We first establish an information-theoretic lower bound for stationary, reversible, geometrically ergodic chains in fixed ambient dimension, showing that no measurable estimator can achieve excess classification risk better than $Ω(\sqrt{\Tmix/n})$. We then prove that, on the AR(1) witness subclass underlying the lower-bound construction, dependence-agnostic uniform bagging is provably suboptimal with excess risk bounded below by $Ω(\Tmix/\sqrt{n})$, exhibiting a $\sqrt{\Tmix}$ algorithmic gap. Finally, we propose \emph{adaptive spectral routing}, which partitions the training data via the empirical Fiedler eigenvector of a dependency graph and achieves the minimax rate $\mathcal{O}(\sqrt{\Tmix/n})$ up to a lower-order geometric cut term on a graph-regular subclass, without knowledge of $\Tmix$. Experiments on synthetic Markov chains, 2D spatial grids, the 128-dataset UCR archive, and Atari DQN ensembles validate the theoretical predictions. Consequences for deep RL target variance, scalability via Nyström approximation, and bounded non-stationarity are developed as supporting material in the appendix.
- Abstract（参考訳）: 主要声楽アンサンブルは、多種多様なほぼ独立した基礎学習者に対して平均化することにより、ばらつきの低減を実現する。
トレーニングデータが、時系列予測、強化学習(RL)リプレイバッファ、空間グリッドなどのマルコフ依存を示す場合、この古典的な保証は、既存の理論が完全に定量化されていない方法で低下する。
固定次元マルコフ集合における離散的な分類のためのこの現象のミニマックス的特徴付けと、グラフ正則部分クラスにおける速度に一致する適応アルゴリズムを提供する。
まず, 定常的, 可逆的, 幾何的エルゴード鎖に対する情報理論の下界を固定次元で確立し, 測定可能な推定器が$Ω(\sqrt{\Tmix/n})$よりも過大な分類リスクを達成できないことを示す。
すると、AR(1) の証人サブクラスにおいて、従属的一様バッグングは確率的に準最適であり、過大なリスクは$Ω(\Tmix/\sqrt{n})$で表され、$\sqrt{\Tmix}$アルゴリズム的ギャップを示すことが証明される。
最後に、依存グラフの実証的Fiedler固有ベクトルを介してトレーニングデータを分割し、ミニマックスレート$\mathcal{O}(\sqrt{\Tmix/n})$をグラフ正規部分クラス上の下階幾何学的カット項まで、$\Tmix$の知識なしに達成する。
合成マルコフ連鎖、2次元空間格子、128データセットのUCRアーカイブ、アタリDQNアンサンブルに関する実験は、理論的な予測を検証している。
虫垂の支持材料として、深部RL目標分散、Nyström近似によるスケーラビリティ、および有界非定常性が開発された。
関連論文リスト
- Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees [9.180350432640912]
連続時間マルコフ連鎖(CTMC)の定式化によるスコアベース離散拡散モデルのサンプリング効率について検討した。
一様離散拡散に対して、$$-leapingアルゴリズムは位数$tilde O(d/varepsilon)$の複雑さを達成することを示す。
離散拡散をマスキングするために,本質的な情報理論量によって収束率を制御した$$-leapingサンプルラを導入する。
論文 参考訳（メタデータ） (2026-02-16T18:48:17Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。
我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2026-01-03T04:50:21Z) - Phase-space entropy at acquisition reflects downstream learnability [54.4100065023873]
楽器分解位相空間に基づく取得レベルスカラー$S_mathcal B$を提案する。
本稿では, (S_mathcal B) が周期サンプリングの位相空間コヒーレンスを正確に同定できることを理論的に示す。
$|S_mathcal B|$は一貫してサンプリングジオメトリをランク付けし、トレーニングなしで下流での再構築/認識の困難を予測します。
論文 参考訳（メタデータ） (2025-12-22T10:03:51Z) - Beyond Isotonization: Scalable Non-Crossing Quantile Estimation via Neural Networks for Student Growth Percentiles [0.0]
学生成長パーセンタイル(SGP)は、アメリカ合衆国の国家評価システムで広く採用されており、独立した量子レグレッションとポストホック補正が採用されている。
我々は、このアプローチが基本的な方法論上の矛盾を含んでいることを実証する: 独立に見積もられた、潜在的に交差する量子化の間には、単調性が必要である。
ニューラルネットワークを用いたマルチクエンタイル回帰(NNQR)を実用的な代替手段として提案する。
論文 参考訳（メタデータ） (2025-10-25T19:39:07Z) - Anchor-MoE: A Mean-Anchored Mixture of Experts For Probabilistic Regression [0.0]
本稿では,確率的および点回帰の両方を扱うAnchored Mixture of Experts (Anchor-MoE)モデルを提案する。
Anchor-MoE がminimax-optimal $L2$ risk rate を達成することを示す。
RMSEとNLLの強いNGベースラインと一貫して一致または超える。
論文 参考訳（メタデータ） (2025-08-22T21:12:41Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Least Squares Regression with Markovian Data: Fundamental Limits and
Algorithms [69.45237691598774]
マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。
この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。
本稿では,経験的リプレイに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-16T04:26:50Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。