論文の概要: Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue

• arxiv url: http://arxiv.org/abs/2607.22889v1
• Date: Fri, 24 Jul 2026 20:01:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:14.921227
• Title: Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue
• Title（参考訳）: 縮合したブール製品分布の効率的な学習 : 救助活動への影響
• Abstract要約: mathbbRn$ の自然パラメータ $z を、部分集合 $S に制約された独立標本から学ぶことは、高次元統計学における基礎的な挑戦である。 既存のパラメータ推定保証を太さ仮定で洗練し、前のサンプルの複雑さを$O( log n / 2)$ for $ell_infty$-recovery に改善し、未実行のミニマックスレートと一致させる。
• 参考スコア（独自算出の注目度）: 17.761018390014602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the natural parameters $z \in \mathbb{R}^n$ of discrete distributions $μ_z$ from independent samples constrained to a subset $S \subseteq \{0,1\}^n$ is a foundational challenge in high-dimensional statistics. Existing methods for efficiently estimating truncated Boolean product distributions, notably the work of [Fotakis et al' COLT'20, Algorithmica '22], require either strong local connectivity assumptions on $S$ -- a property denoted fatness -- or stringent anti-concentration assumptions and necessitate the total mass of the truncation set to be a constant with respect to $n$. Moreover, the results in [Fotakis et al' COLT'20, Algorithmica '22] suffer from sample complexities that scale as $Ω(2^n)$ if the mass of $S$ is exponentially small in $n$. In this work, we circumvent these limitations by analyzing the geometry of $S$ under the measure $μ_z$. We refine the existing parameter estimation guarantees under the fatness assumption, improving the prior sample complexity to $O( \log n / ε^2)$ for $\ell_\infty$-recovery, matching the untruncated minimax rate. We further generalize fatness using the notion of influence utilized in the analysis of Boolean functions and provide sufficient conditions for efficient inference. Notably, unlike previous work, our method does not require sampling at arbitrary parameterizations of the model. Lastly, we establish a theoretical lower bound demonstrating the sample complexity exhibits an intrinsic exponential dependence on the width of the model and the minimum distance between elements in the set.
• Abstract（参考訳）: 離散分布の自然パラメータ $z \in \mathbb{R}^n$ を、部分集合 $S \subseteq \{0,1\}^n$ に制約された独立標本から学ぶことは、高次元統計学における基礎的な挑戦である。 特に[Fotakis et al' COLT'20, Algorithmica '22] の作業では、(Fotakis et al' COLT'20, Algorithmica '22] は、$S$の強い局所接続仮定 -- 太さを表す性質 -- あるいは厳密な反集中仮定を要求し、truncation セットの総質量を$n$に対して一定に設定する必要がある。さらに、[Fotakis et al' COLT'20, Algorithmica '22] の結果は、$S$の質量が$n$で指数関数的に小さい場合、サンプル複雑度に悩まされる。 本研究では、これらの制限を、$μ_z$の測度で$S$の幾何学を解析することによって回避する。 我々は、太さ仮定の下で既存のパラメータ推定の保証を洗練し、前のサンプルの複雑さを$O( \log n / ε^2)$ for $\ell_\infty$-recovery に改善し、未解決のミニマックスレートと一致する。 さらに、ブール関数の解析に利用される影響の概念を用いて脂肪度を一般化し、効率的な推論に十分な条件を提供する。 特に,従来の研究と異なり,モデルの任意のパラメータ化においてサンプリングを行う必要はない。 最後に,標本の複雑さを示す理論的下界を確立し,モデルの幅と集合内の要素間の最小距離に固有の指数的依存性を示す。

関連論文リスト

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• Breaking the Finite-Sample Barrier in Entropy Coupling [9.251944578856843]
  限界に制約された観測の依存関係は、有限サンプル障壁を破る可能性がある。 我々は、この現象を、エントロピー結合$H(P|Q_1,dots,Q_m)$の導入によって定式化する。 分布マッチング表現学習とランダムネス抽出において,同じ枠組みが有限サンプル制限を定式化することを示す。
  論文  参考訳（メタデータ） (2026-05-15T17:39:57Z)
• Generalization Properties of Score-matching Diffusion Models for Intrinsically Low-dimensional Data [32.72306410557258]
  有限個のサンプルから未知分布の$$を学習するためのスコアベース拡散モデルの統計的収束について検討する。 以上の結果から,拡散モデルがデータ固有の幾何学に自然に適応していることが示唆された。 我々の理論は, 拡散モデルの解析を, GANと最適輸送で確立された急激なミニマックス速度で橋渡しするものである。
  論文  参考訳（メタデータ） (2026-03-04T03:59:02Z)
• Locally minimax optimal confidence sets for the best model [40.60301522036206]
  この論文は基本的な推論問題に取り組む:$P$ over $mathbbRd$ が未知の平均$boldsymbolmu$ である場合、$boldsymbolmu$ の最小成分に対応する指数に対する信頼セットを形成する必要がある。 我々は$d$が$n$でスケールするか、および$boldsymbolmu$の任意の関係によらず、妥当性を維持する「次元に依存しない」テストを提案する。
  論文  参考訳（メタデータ） (2025-03-27T16:06:07Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• A Finite Sample Complexity Bound for Distributionally Robust Q-learning [17.96094201655567]
  我々は,展開環境が訓練環境と異なる強化学習環境を考える。 ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。 これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
  論文  参考訳（メタデータ） (2023-02-26T01:15:32Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Efficient Parameter Estimation of Truncated Boolean Product Distributions [26.396901523831534]
  切り離されたサンプルからの学習の計算的および統計的複雑さが離散的な設定で検討されたのはこれが初めてである。 トラニケート集合が十分に太った場合, トラニケートされた試料から真の分布から試料を生成できることが示される。
  論文  参考訳（メタデータ） (2020-07-05T17:20:39Z)
• 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)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Optimal rates for independence testing via $U$-statistic permutation tests [7.090165638014331]
  独立分布と同一分布のペアが$sigma$-finiteで分離可能な測度空間で値を取る独立性テストの問題について検討する。 最初に、独立性の有効なテストはなく、$f: D(f) geq rho2 $ という形の代替と一様に一致していることを示す。
  論文  参考訳（メタデータ） (2020-01-15T19:04:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。