Fugu-MT 論文翻訳(概要): Product distribution learning with imperfect advice

論文の概要: Product distribution learning with imperfect advice

arxiv url: http://arxiv.org/abs/2511.10366v1
Date: Fri, 14 Nov 2025 01:47:30 GMT
ステータス: 翻訳完了
システム内更新日: 2025-11-14 22:53:22.827632
Title: Product distribution learning with imperfect advice
Title（参考訳）: 不完全なアドバイスによる製品流通学習
Authors: Arnab Bhattacharyya, Davin Choo, Philips George John, Themis Gouleakis,
Abstract要約: 未知分布からの i.d.samples が$P$ であることを考えると、分布学習の目標は、$P$ に近い分布のパラメータを復元することである。サンプル複雑性を持つTV距離$varepsilon$は、$tildeO(d1-/varepsilon2)$である。
参考スコア（独自算出の注目度）: 16.179400847403446
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Given i.i.d.~samples from an unknown distribution $P$, the goal of distribution learning is to recover the parameters of a distribution that is close to $P$. When $P$ belongs to the class of product distributions on the Boolean hypercube $\{0,1\}^d$, it is known that $Ω(d/\varepsilon^2)$ samples are necessary to learn $P$ within total variation (TV) distance $\varepsilon$. We revisit this problem when the learner is also given as advice the parameters of a product distribution $Q$. We show that there is an efficient algorithm to learn $P$ within TV distance $\varepsilon$ that has sample complexity $\tilde{O}(d^{1-η}/\varepsilon^2)$, if $\|\mathbf{p} - \mathbf{q}\|_1 < \varepsilon d^{0.5 - Ω(η)}$. Here, $\mathbf{p}$ and $\mathbf{q}$ are the mean vectors of $P$ and $Q$ respectively, and no bound on $\|\mathbf{p} - \mathbf{q}\|_1$ is known to the algorithm a priori.
Abstract（参考訳）: 未知分布からの i.d.~samples が$P$ であることを考えると、分布学習の目標は、$P$ に近い分布のパラメータを復元することである。 P$ が Boolean hypercube $\{0,1\}^d$ の積分布のクラスに属するとき、$Ω(d/\varepsilon^2)$ のサンプルは、全変量 (TV) 距離 $\varepsilon$ で$P$ を学ぶために必要であることが知られている。我々は、学習者が製品分布のパラメータを$Q$でアドバイスするときに、この問題を再考する。 P$をTV距離内で学習する効率的なアルゴリズムがあることが示される: $\tilde{O}(d^{1-η}/\varepsilon^2)$, if $\|\mathbf{p} - \mathbf{q}\|_1 < \varepsilon d^{0.5 - Ω(η)}$。ここで、$\mathbf{p}$ と $\mathbf{q}$ はそれぞれ$P$ と $Q$ の平均ベクトルであり、$\|\mathbf{p} - \mathbf{q}\|_1$ 上の有界な境界はアルゴリズム a に既知でない。

関連論文リスト

Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文参考訳（メタデータ） (2025-10-12T15:42:44Z)
New Algorithmic Directions in Optimal Transport and Applications for Product Spaces [5.9725566031600925]
アルゴリズムの観点から2つの高次元分布$mu,nu$ in$Rn$の最適輸送について検討する。実行時間は、$mu,nu$の完全な表現サイズではなく、次元に依存する。ガウス測度$varepsilon$の場合、ほとんどの$Phin$サンプルは距離$O(sqrtlog 1/varepsilon)$ in $poly(n/varepsilon)$にマッピングできる。
論文参考訳（メタデータ） (2025-09-25T19:58:06Z)
Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization [0.0]
本稿では、mathbbRl$における翻訳の$boldsymbolmuを推定し、mathbbR_++$パラメータにおける$sigmaを縮小する複雑性に焦点を当てる。 MLE(Maximum Likelihood Estimation)ではNPハードとなるが、$varepsilon$-approxs for arbitrary $varepsilon > 0$ in $textpoly left( frac1varepsilon )$ time が得られる。
論文参考訳（メタデータ） (2025-01-17T13:07:52Z)
On Learning for Ambiguous Chance Constrained Problems [2.7152798636894193]
この場合、$theta$のサンプルが$nu$から引き出されるサンプル問題により、元の問題は「適切に近似できる」ことが示される。また、この近似に関連するサンプルの複雑さ、すなわち$epsilon,delta>0$に対して$nu$から引かなければならないサンプルの数を導出する。
論文参考訳（メタデータ） (2023-12-31T17:25:43Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文参考訳（メタデータ） (2023-03-30T02:50:49Z)
Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文参考訳（メタデータ） (2021-08-19T16:16:48Z)
Self-training Converts Weak Learners to Strong Learners in Mixture Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文参考訳（メタデータ） (2021-06-25T17:59:16Z)
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [14.298220510927695]
古典的ChowLiuアルゴリズム(IEEE Trans.Inform.Theory, 1968)に対する有限サンプル保証を提供する。特定の木の$T$に対して、$widetildeO (|Sigma|2nvarepsilon-1)$の分布からのサンプルを$P$ over $Sigman$とすると、最も近いKL分岐を効率的に学習できる。
論文参考訳（メタデータ） (2020-11-09T02:08:56Z)
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)
Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文参考訳（メタデータ） (2020-04-13T08:06:29Z)

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

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