論文の概要: Breaking the Finite-Sample Barrier in Entropy Coupling
- arxiv url: http://arxiv.org/abs/2605.16229v1
- Date: Fri, 15 May 2026 17:39:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.395346
- Title: Breaking the Finite-Sample Barrier in Entropy Coupling
- Title（参考訳）: エントロピー結合における有限サンプルバリアの破壊
- Authors: Shahab Asoodeh, Jun Chen,
- Abstract要約: 限界に制約された観測の依存関係は、有限サンプル障壁を破る可能性がある。
我々は、この現象を、エントロピー結合$H(P|Q_1,dots,Q_m)$の導入によって定式化する。
分布マッチング表現学習とランダムネス抽出において,同じ枠組みが有限サンプル制限を定式化することを示す。
- 参考スコア（独自算出の注目度）: 9.251944578856843
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Dependence among marginally constrained observations can break a finite-sample barrier. To formalize this phenomenon, we introduce the \emph{minimum list entropy coupling} $H(P\|Q_1,\dots,Q_m)$, the minimum conditional entropy $H(X|Y_1,\dots,Y_m)$ over all joint distributions with prescribed discrete marginals $X\sim P$ and $Y_i\sim Q_i$. Unlike classical formulations based on independent observations, our model allows $Y_1,\dots,Y_m$ to be arbitrarily dependent while keeping each marginal fixed. This enlarged coupling space reveals a sharp dichotomy: independent observations reduce residual uncertainty exponentially, whereas dependent observations can eliminate it exactly after finitely many samples. We characterize this zero-entropy regime through necessary and sufficient conditions and give concrete structural criteria under which it occurs. In particular, under mild support assumptions, zero entropy is achieved with $O(\log(1/P_{\min}))$ observations, where $P_{\min}$ is the minimum nonzero mass of $P$. We also develop a greedy algorithm with monotone approximation guarantees for computing $H(P\|Q_1,\dots,Q_m)$. Finally, we show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction, where zero entropy corresponds to exact recovery and exact extraction.
- Abstract（参考訳）: 限界に制約された観測の依存関係は、有限サンプル障壁を破る可能性がある。
この現象を形式化するために、最小条件付きエントロピー $H(X|Y_1,\dots,Y_m)$ を、所定の離散余区間が $X\sim P$ と $Y_i\sim Q_i$ を持つすべての関節分布に対して導入する。
独立観測に基づく古典的定式化とは異なり、我々のモデルは各辺の固定を保ちながらY_1,\dots,Y_m$を任意に依存させることができる。
独立な観測は残留不確実性を指数関数的に減少させるが、依存的な観測は有限個のサンプルの直後にそれを除去することができる。
我々は,このゼロエントロピー体制を必要かつ十分な条件で特徴付け,具体的構造基準を与える。
特に、弱い支持仮定の下では、0エントロピーは$O(\log(1/P_{\min})$観測によって達成され、$P_{\min}$は$P$の最小零質量である。
また、単調な近似を保証し、$H(P\|Q_1,\dots,Q_m)$を計算できるグリーディアルゴリズムを開発した。
最後に、分布マッチング表現学習とランダムネス抽出において、ゼロエントロピーが正確な回復と正確な抽出に対応する場合において、同じフレームワークが有限サンプル制限を定式化することを示す。
関連論文リスト
- Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
有限状態マルコフ鎖を$n$状態と遷移行列$P$で研究する。
すべての非退化モードが実周辺不変部分空間 $mathcalK(P)$ によってキャプチャされ、商空間 $mathbbRn/mathcalK(P) 上の誘導作用素が厳密に収縮し、ユニークな商解が得られることを示す。
論文 参考訳（メタデータ） (2026-01-31T02:57:01Z) - 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) - Precise Asymptotics of Bagging Regularized M-estimators [20.077783679095443]
我々は,アンサンブル推定器の正方形予測リスクを,正規化M値推定器のサブタグ化(サブサンプルブートストラップ集約)により特徴付ける。
我々の分析の鍵は、重なり合うサブサンプル上の推定値と残差との相関関係の結合挙動に関する新しい結果である。
サブサンプルサイズ,アンサンブルサイズ,正規化の併用最適化は,全データに対してのみ,正規化器の最適化を著しく上回る。
論文 参考訳（メタデータ） (2024-09-23T17:48:28Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Smooth min-entropy lower bounds for approximation chains [0.0]
簡単なエントロピー三角形の不等式を証明し、任意の補助状態の R'enyi エントロピーの観点から、状態の滑らかなミニエントロピーを有界にすることができる。
この三角形の不等式を用いて、様々なシナリオにおける近似鎖のエントロピーの観点から、状態の滑らかなミニエントロピーに対する下界を生成する。
論文 参考訳（メタデータ） (2023-08-22T18:55:16Z) - On counterfactual inference with unobserved confounding [36.18241676876348]
独立だが不均一な単位を持つ観測的研究を前提として、各単位の反実分布を学習することが目的である。
我々は、すべての$n$サンプルをプールして、すべての$n$パラメータベクトルを共同で学習する凸目的を導入する。
対数的ソボレフ不等式を満たすためにコンパクトに支持された分布に対して十分な条件を導出する。
論文 参考訳（メタデータ） (2022-11-14T04:14:37Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。