論文の概要: The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications
for Profile Maximum Likelihood
- arxiv url: http://arxiv.org/abs/2004.02425v1
- Date: Mon, 6 Apr 2020 06:40:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-16 06:27:23.454561
- Title: The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications
for Profile Maximum Likelihood
- Title（参考訳）: 低階行列のベーテとシンクホーンの永久数とプロファイル最大度との関係
- Authors: Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford
- Abstract要約: 我々はベーテとシンクホーンの永久体の近似の質に関する新しい限界を提供する。
先行研究における凸緩和とベーテ近似とシンクホーン近似との驚くべき関係を確立する。
- 参考スコア（独自算出の注目度）: 33.51964370430905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we consider the problem of computing the likelihood of the
profile of a discrete distribution, i.e., the probability of observing the
multiset of element frequencies, and computing a profile maximum likelihood
(PML) distribution, i.e., a distribution with the maximum profile likelihood.
For each problem we provide polynomial time algorithms that given $n$ i.i.d.\
samples from a discrete distribution, achieve an approximation factor of
$\exp\left(-O(\sqrt{n} \log n) \right)$, improving upon the previous best-known
bound achievable in polynomial time of $\exp(-O(n^{2/3} \log n))$ (Charikar,
Shiragur and Sidford, 2019). Through the work of Acharya, Das, Orlitsky and
Suresh (2016), this implies a polynomial time universal estimator for symmetric
properties of discrete distributions in a broader range of error parameter.
We achieve these results by providing new bounds on the quality of
approximation of the Bethe and Sinkhorn permanents (Vontobel, 2012 and 2014).
We show that each of these are $\exp(O(k \log(N/k)))$ approximations to the
permanent of $N \times N$ matrices with non-negative rank at most $k$,
improving upon the previous known bounds of $\exp(O(N))$. To obtain our results
on PML, we exploit the fact that the PML objective is proportional to the
permanent of a certain Vandermonde matrix with $\sqrt{n}$ distinct columns,
i.e. with non-negative rank at most $\sqrt{n}$. As a by-product of our work we
establish a surprising connection between the convex relaxation in prior work
(CSS19) and the well-studied Bethe and Sinkhorn approximations.
- Abstract（参考訳）: 本稿では、離散分布のプロファイルの確率、すなわち、要素周波数の多重集合を観測する確率を計算し、プロファイル最大確率(pml)分布、すなわち、最大プロファイルの確率の分布を計算する問題を考察する。
それぞれの問題に対して、多項式時間アルゴリズムは、離散分布から$n$ i.d.\サンプルを与え、$\exp\left(-O(\sqrt{n} \log n) \right)$の近似係数を達成し、多項式時間$\exp(-O(n^{2/3} \log n))$ (Charikar, Shiragur and Sidford, 2019) の多項式時間で達成可能な以前の最もよく知られた境界を改良する。
Acharya, Das, Orlitsky and Suresh (2016) の業績により、これはより広い範囲の誤差パラメータにおける離散分布の対称性に対する多項式時間普遍推定器を意味する。
我々は bethe and sinkhorn permanents (vontobel, 2012 and 2014) の近似のクオリティに関する新たな境界を提供することにより,これらの結果を達成する。
これらはそれぞれ$\exp(o(k \log(n/k)))$近似であり、非負のランクの行列は最大$k$であり、従来知られていた$\exp(o(n))$である。
PML 上の結果を得るためには、PML の目的が、ある Vandermonde 行列に $\sqrt{n}$ の異なる列、すなわち、非負のランクが $\sqrt{n}$ の値に比例するという事実を利用する。
我々の研究の副産物として、先行作業における凸緩和(css19)とよく研究されたベーテとシンクホーン近似との間に驚くべき関係が確立される。
関連論文リスト
- $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - Robust Mean Estimation Without Moments for Symmetric Distributions [7.105512316884493]
大規模な対称分布に対して、ガウス的設定と同じ誤差を効率的に達成できることが示される。
この最適誤差にアプローチする効率的なアルゴリズムの列を提案する。
我々のアルゴリズムは、よく知られたフィルタリング手法の一般化に基づいている。
論文 参考訳（メタデータ） (2023-02-21T17:52:23Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Approximating Pandora's Box with Correlations [14.284880952600995]
本稿では,次にどのボックスを訪問するかを適応的に選択できる最適ポリシーの近似の複雑さについて検討する。
本研究の主な成果は,一様決定木(UDT)問題に対するPBの近似保存等価性を確立することである。
また、より簡潔に値上の分布が$m$の積分布の混合として与えられる場合についても検討する。
論文 参考訳（メタデータ） (2021-08-30T03:32:16Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - List-Decodable Subspace Recovery: Dimension Independent Error in
Polynomial Time [5.812499828391904]
リスト化可能部分空間のリカバリにおいて、入力は$n$ポイント$alpha n$(ある$alpha ll 1/2$)の集合であり、それらは分布$mathcalD$から引き出される。
本研究は, より高速な固定ポリノミカルランニング時間を用いて, アンフェクタブルな集中防止誤差の3つの側面について, 結果を改善するものである。
論文 参考訳（メタデータ） (2020-02-12T18:30:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。