論文の概要: Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures
- arxiv url: http://arxiv.org/abs/2201.09040v1
- Date: Sat, 22 Jan 2022 12:43:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-28 08:47:33.111214
- Title: Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures
- Title（参考訳）: 低ランクガウス混合系の最適推定と計算限界
- Authors: Zhongyuan Lyu and Dong Xia
- Abstract要約: 本稿では,各行列値の観測値に低ランク構造が植え付けられていることを前提として,低ランクガウス混合モデル(LrMM)を提案する。
一般に計算不可能な最大極大推定器の最小極大最適性を証明する。
以上の結果から,ミニマックス誤差率と統計的-計算的ギャップの相転移が明らかとなった。
- 参考スコア（独自算出の注目度）: 12.868722327487752
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Structural matrix-variate observations routinely arise in diverse fields such
as multi-layer network analysis and brain image clustering. While data of this
type have been extensively investigated with fruitful outcomes being delivered,
the fundamental questions like its statistical optimality and computational
limit are largely under-explored. In this paper, we propose a low-rank Gaussian
mixture model (LrMM) assuming each matrix-valued observation has a planted
low-rank structure. Minimax lower bounds for estimating the underlying low-rank
matrix are established allowing a whole range of sample sizes and signal
strength. Under a minimal condition on signal strength, referred to as the
information-theoretical limit or statistical limit, we prove the minimax
optimality of a maximum likelihood estimator which, in general, is
computationally infeasible. If the signal is stronger than a certain threshold,
called the computational limit, we design a computationally fast estimator
based on spectral aggregation and demonstrate its minimax optimality. Moreover,
when the signal strength is smaller than the computational limit, we provide
evidences based on the low-degree likelihood ratio framework to claim that no
polynomial-time algorithm can consistently recover the underlying low-rank
matrix. Our results reveal multiple phase transitions in the minimax error
rates and the statistical-to-computational gap. Numerical experiments confirm
our theoretical findings. We further showcase the merit of our spectral
aggregation method on the worldwide food trading dataset.
- Abstract（参考訳）: 構造行列-変量観測は、多層ネットワーク分析や脳画像クラスタリングといった様々な分野で頻繁に発生する。
このタイプのデータは実りある結果がもたらされる形で広範囲に調査されてきたが、統計的最適性や計算限界といった基本的な問題はほとんど未検討である。
本稿では,各行列値観測が低ランク構造を有することを前提として,低ランクガウス混合モデル(LrMM)を提案する。
下位の低ランク行列を推定するための最小限の下位境界が確立され、サンプルサイズと信号強度の全範囲が可能である。
情報理論的な極限や統計的極限と呼ばれる信号強度の最小条件の下では、一般に計算不可能である最大確率推定器の最小最適性が証明される。
信号が一定のしきい値(計算限界)よりも強い場合、スペクトル集約に基づく計算速度の速い推定器を設計し、そのミニマックス最適性を示す。
さらに, 信号強度が計算限界より小さい場合, 多項式時間アルゴリズムが基礎となる低次行列を一貫して復元できないことを示すために, 低次確率比フレームワークに基づくエビデンスを提供する。
その結果,minimaxエラー率と統計-計算間ギャップに複数の位相遷移が認められた。
数値実験により理論的な結果が確認された。
さらに,世界の食品取引データセットにおけるスペクトル集約法の有用性について述べる。
関連論文リスト
- Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Quantized Low-Rank Multivariate Regression with Random Dithering [23.81618208119832]
低ランク多変量回帰(LRMR)は重要な統計的学習モデルである。
基礎となる係数行列の推定に焦点をあてる。
我々は、ランダムディザリングを伴う均一な量子化、すなわち、量子化の前に適切なランダムノイズをデータに追加する。
制約付きラッソおよび正規化ラッソ推定器を提案し、非漸近誤差境界を導出する。
論文 参考訳（メタデータ） (2023-02-22T08:14:24Z) - Gaining Outlier Resistance with Progressive Quantiles: Fast Algorithms
and Theoretical Studies [1.6457778420360534]
任意の損失関数を強固化するために, 外部抵抗推定の枠組みを導入する。
通常のデータセットでは、データ再見積の回数を大幅に削減できるような、開始点の要件を緩和する新しい手法が提案されている。
得られた推定器は、必ずしも大域的でも大域的でもなくても、両方の低次元において最適性を楽しむことができる。
論文 参考訳（メタデータ） (2021-12-15T20:35:21Z) - Keep it Tighter -- A Story on Analytical Mean Embeddings [0.6445605125467574]
カーネル技術は、データサイエンスにおいて最も人気があり柔軟なアプローチの一つである。
平均埋め込みは、最大平均不一致(MMD)と呼ばれる分岐測度をもたらす。
本稿では,基礎となる分布の1つの平均埋め込みが解析的に利用可能である場合のMDD推定の問題に焦点をあてる。
論文 参考訳（メタデータ） (2021-10-15T21:29:27Z) - Near-optimal inference in adaptive linear regression [60.08422051718195]
最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。
我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。
我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
論文 参考訳（メタデータ） (2021-07-05T21:05:11Z) - Entropy Minimizing Matrix Factorization [102.26446204624885]
NMF(Nonnegative Matrix Factorization)は、広く使用されているデータ分析技術であり、多くの実際のタスクで印象的な結果をもたらしました。
本研究では,上述の問題に対処するために,EMMF (Entropy Minimizing Matrix Factorization framework) を開発した。
通常、外れ値が通常のサンプルよりもはるかに小さいことを考えると、行列分解のために新しいエントロピー損失関数が確立される。
論文 参考訳（メタデータ） (2021-03-24T21:08:43Z) - Over-the-Air Statistical Estimation [4.082216579462796]
2乗誤差損失下でのガウス多重アクセスチャネル(MAC)上の分散ミニマックス統計推定のためのスキームと下限について検討する。
物理層を用いた推定手法は,物理層抽象に依存したディジタルスキームによる推定誤差を大幅に低減することを示した。
論文 参考訳（メタデータ） (2021-03-06T03:07:22Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - All-or-nothing statistical and computational phase transitions in sparse
spiked matrix estimation [35.035853993422506]
スパース方式で近似メッセージパッシングアルゴリズムを解析する。
最小誤差と平均二乗誤差の位相遷移がすべて存在する。
スパース体制では、スパース回復が近似メッセージパッシングに困難であることを示す統計的-アルゴリズム的ギャップが分岐する。
論文 参考訳（メタデータ） (2020-06-14T18:38:34Z) - Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
我々は,人口レベルでのアルゴリズムの決定論的収束率と,$n$サンプルに基づく経験的対象に適用した場合の(不安定性)の間の相互作用に基づいて,統計的精度を得るフレームワークを開発する。
本稿では,ガウス混合推定,非線形回帰モデル,情報的非応答モデルなど,いくつかの具体的なモデルに対する一般結果の応用について述べる。
論文 参考訳（メタデータ） (2020-05-22T22:30:52Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。