Fugu-MT 論文翻訳(概要): On Computing Total Variation Distance Between Mixtures of Product Distributions

論文の概要: On Computing Total Variation Distance Between Mixtures of Product Distributions

arxiv url: http://arxiv.org/abs/2605.03839v1
Date: Tue, 05 May 2026 15:05:49 GMT
ステータス: 翻訳完了
システム内更新日: 2026-05-06 19:35:43.991688
Title: On Computing Total Variation Distance Between Mixtures of Product Distributions
Title（参考訳）: 製品分布の混合量間の総変動距離の計算について
Authors: Weiming Feng, Yucheng Fu, Minji Yang, Anqi Zhang,
Abstract要約: 本研究では,n$次元離散領域上の2種類の積分布間の総変動距離を近似する問題について検討する。このクラスに対して、時間における全変動距離を正確に計算する決定論的アルゴリズムを与える。
参考スコア（独自算出の注目度）: 7.048905632889667
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the problem of approximating the total variation distance between two mixtures of product distributions over an $n$-dimensional discrete domain. Given two mixtures $\mathbb{P}$ and $\mathbb{Q}$ with $k_1$ and $k_2$ product distributions over $[q]^n$, respectively, we give a randomized algorithm that approximates $d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)$ within a multiplicative error of $(1\pm \varepsilon)$ in time $\mathrm{poly}((nq)^{k_1+k_2},1/\varepsilon)$. We also study the special case of mixtures of Boolean subcubes over $\{0,1\}^n$. For this class, we give a deterministic algorithm that exactly computes the total variation distance in time $\mathrm{poly}(n,2^{O(k_1+k_2)})$, and show that exact computation is $\#\mathsf{P}$-hard when $k_1+k_2=Θ(n)$.
Abstract（参考訳）: 我々は,n$次元離散領域上の2種類の積分布間の総変動距離を近似する問題について検討した。 $\mathbb{P}$ と $\mathbb{Q}$ と $k_1$ と $k_2$ の積分布をそれぞれ$[q]^n$ とすると、$d_{\mathrm{TV}}\left({\mathbb{P}},{\mathbb{Q}}\right)$ を乗法誤差の$(1\pm \varepsilon)$ で近似するランダム化アルゴリズムが与えられる。また、Boolean subcubes の$\{0,1\}^n$ の混合物の特別な場合についても検討する。このクラスに対して、時間$\mathrm{poly}(n,2^{O(k_1+k_2)})$の総変動距離を正確に計算する決定論的アルゴリズムを与える。

関連論文リスト

Product distribution learning with imperfect advice [16.179400847403446]
未知分布からの i.d.samples が$P$ であることを考えると、分布学習の目標は、$P$ に近い分布のパラメータを復元することである。サンプル複雑性を持つTV距離$varepsilon$は、$tildeO(d1-/varepsilon2)$である。
論文参考訳（メタデータ） (2025-11-13T14:44:46Z)
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文参考訳（メタデータ） (2025-10-12T15:42:44Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文参考訳（メタデータ） (2024-02-06T15:39:09Z)
Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
論文参考訳（メタデータ） (2023-11-22T04:34:09Z)
SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文参考訳（メタデータ） (2023-10-18T10:56:57Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Additive estimates of the permanent using Gaussian fields [0.0]
本稿では,M$M$実行列$A$から加法誤差までの永久性を推定するランダム化アルゴリズムを提案する。我々は$mathrmperm(A)$を$epsilonbigg(sqrt32Mprod2M_i=1 C_iibigg)$の加算誤差に時間内に見積もることができる。
論文参考訳（メタデータ） (2022-12-20T22:13:42Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文参考訳（メタデータ） (2022-06-17T17:55:43Z)
Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。 3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文参考訳（メタデータ） (2021-10-05T09:33:49Z)
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)

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