論文の概要: Learning Distributions from Multiple Data Providers
- arxiv url: http://arxiv.org/abs/2607.24732v1
- Date: Mon, 27 Jul 2026 17:57:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:15.549292
- Title: Learning Distributions from Multiple Data Providers
- Title（参考訳）: 複数のデータプロバイダから分散を学習する
- Abstract要約: 本研究では,制約条件付きサンプルを用いた分布学習のスタイリングモデルについて検討する。
学習性は$mathscrS$に関連付けられた共起グラフによって管理される。
PAC学習の最適なサンプル複雑性は、ほぼ線形から二次まで様々である。
- 参考スコア（独自算出の注目度）: 13.95037228126825
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution $p$ on a finite domain $[n]$. The learner is given a fixed family of queryable sets $\mathscr{S} \subseteq 2^{[n]}$, and each query to $S \in \mathscr{S}$ returns an independent sample from the conditional distribution $p(\cdot \mid S)$. Learnability is governed by the co-occurrence graph associated with $\mathscr{S}$: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity $\widetilde O(n^2/ε^2)$, and this bound is tight in the worst case. On the other hand, if $[n]$ is queryable then ordinary sampling improves the bound to $Θ(n/ε^2)$, and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on $\mathscr S$ under which the optimal complexity is nearly linear, $\widetilde Θ(n/ε^2)$, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every $α\in (1,2)$, there exists a query family with optimal PAC rate $\widetilde Θ(n^α/ε^2)$.
- Abstract（参考訳）: 異種および重なり合うデータ提供者からの学習を動機として,制約条件付きサンプルからの分布学習のスタイリングモデルについて検討する。
目的は、未知の分布$p$を有限領域$[n]$で学習することである。
学習者は、クエリ可能な集合の固定されたファミリー$\mathscr{S} \subseteq 2^{[n]}$を与えられ、各クエリに対して$S \in \mathscr{S}$は条件分布$p(\cdot \mid S)$から独立したサンプルを返す。
学習性は$\mathscr{S}$に関連付けられた共起グラフによって管理される。
このグラフがターゲットサポートに接続されている場合、ポイントワイドの一貫性が達成できる。
PAC学習は、共起グラフが完成すれば可能である。
PAC学習の最適なサンプル複雑性は、ほぼ線形から二次まで様々である。
完全共起グラフを持つ全てのクエリ族は、サンプル複雑性$\widetilde O(n^2/ε^2)$を認め、最悪の場合、この境界は厳密である。
一方、$[n]$ がクエリ可能であれば、通常のサンプリングは$(n/ε^2)$ へのバウンドを改善し、全ての集合がクエリ可能であってもさらに改善することはできない。
より一般に、階層的可視性は、最適複雑性がほぼ線形である$\mathscr S$上の十分構造的条件として、対の問い合わせ族を正準例として、$\widetilde >(n/ε^2)$とみなす。
最後に、線型と二次の間の多項式率の全範囲は達成可能であり、すべての$α\in (1,2)$に対して、最適なPACレートが$\widetilde >(n^α/ε^2)$のクエリ族が存在する。
関連論文リスト
- Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
論文 参考訳（メタデータ） (2026-04-17T14:47:52Z) - High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。
我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文 参考訳（メタデータ） (2026-02-01T17:05:31Z) - Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。
一定の正則性特性を満たす有限範囲の良好なMIMに着目する。
ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
論文 参考訳（メタデータ） (2025-02-13T17:37:42Z) - One-Shot Learning for k-SAT [2.6293381978389787]
我々は、$k$-SATのワンショット学習が、満足度しきい値を大きく下回っていることを示す。
学習アルゴリズムの解析を単純化し、$d$のより強いバウンダリを$beta$で取得する。
論文 参考訳（メタデータ） (2025-02-10T23:56:08Z) - Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Learning and Covering Sums of Independent Random Variables with
Unbounded Support [4.458210211781738]
独立整数値確率変数の和 $X = X_1 + cdots + X_n$ を非有界、あるいは無限なサポートでカバーし、学習する問題について検討する。
我々は、$X_i$sの集合的サポートの最大値が、必ずしも$X$を学習する際のサンプルの複雑さに現れることを示した。
論文 参考訳（メタデータ） (2022-10-24T15:03:55Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - On the Parameterized Complexity of Polytree Learning [4.060731229044571]
データサイエンスの基本的な課題は、観測データからベイズネットワークを学ぶことである。
textscPolytree Learningは3n cdot |I|mathcalO(1)$ timeで解けることを示す。
論文 参考訳（メタデータ） (2021-05-20T11:29:12Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。