論文の概要: Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows
- arxiv url: http://arxiv.org/abs/2409.03980v1
- Date: Fri, 6 Sep 2024 02:01:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-09 16:58:39.074832
- Title: Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows
- Title（参考訳）: ネットワークフローのレンズによる任意サンプリングパターンによる入射行列推定
- Authors: Yudong Chen, Xumei Xi, Christina Lee Yu,
- Abstract要約: 行列補完は、観察されたエントリのスパースセットに基づいて、低ランク行列の欠落値を予測するタスクに取り組む。
観測パターンによって誘導される二部グラフのネットワークフローに基づく行列補完アルゴリズムを提案する。
この結果から,行列内の特定のエントリの回復に対する最小二乗誤差は,グラフ内の対応するエッジの有効抵抗に比例することを示した。
- 参考スコア（独自算出の注目度）: 9.631640936820126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Matrix completion tackles the task of predicting missing values in a low-rank matrix based on a sparse set of observed entries. It is often assumed that the observation pattern is generated uniformly at random or has a very specific structure tuned to a given algorithm. There is still a gap in our understanding when it comes to arbitrary sampling patterns. Given an arbitrary sampling pattern, we introduce a matrix completion algorithm based on network flows in the bipartite graph induced by the observation pattern. For additive matrices, the particular flow we used is the electrical flow and we establish error upper bounds customized to each entry as a function of the observation set, along with matching minimax lower bounds. Our results show that the minimax squared error for recovery of a particular entry in the matrix is proportional to the effective resistance of the corresponding edge in the graph. Furthermore, we show that our estimator is equivalent to the least squares estimator. We apply our estimator to the two-way fixed effects model and show that it enables us to accurately infer individual causal effects and the unit-specific and time-specific confounders. For rank-$1$ matrices, we use edge-disjoint paths to form an estimator that achieves minimax optimal estimation when the sampling is sufficiently dense. Our discovery introduces a new family of estimators parametrized by network flows, which provide a fine-grained and intuitive understanding of the impact of the given sampling pattern on the relative difficulty of estimation at an entry-specific level. This graph-based approach allows us to quantify the inherent complexity of matrix completion for individual entries, rather than relying solely on global measures of performance.
- Abstract（参考訳）: 行列補完は、観察されたエントリのスパースセットに基づいて、低ランク行列の欠落値を予測するタスクに取り組む。
観測パターンはランダムに均一に生成されるか、あるいは与えられたアルゴリズムに調整された非常に特殊な構造を持つとしばしば仮定される。
任意のサンプリングパターンに関しては、まだ理解にギャップがあります。
任意のサンプリングパターンが与えられた場合、観測パターンによって誘導される二部グラフのネットワークフローに基づく行列補完アルゴリズムを導入する。
加法行列に対して、私たちが使った特定の流れは、電気の流れであり、我々は、一致するミニマックス下界と共に、観測セットの関数として各エントリにカスタマイズされた誤差上界を確立する。
この結果から,行列内の特定のエントリの回復に対する最小二乗誤差は,グラフ内の対応するエッジの有効抵抗に比例することを示した。
さらに、我々の推定器は最小二乗推定器と同値であることを示す。
両方向の固定効果モデルに推定器を適用し,個々の因果効果と単位特異的・時間特異的な共同設立者を正確に推定できることを示す。
階数 1$ の行列に対して、サンプリングが十分に密度が高いときに最小値の最適推定を行う推定器を形成するために、エッジ不整合経路を用いる。
我々の発見は,ネットワークフローによってパラメータ化された新しい推定器のファミリーを導入し,与えられたサンプリングパターンがエントリ固有レベルでの相対的評価の難しさに与える影響を,きめ細やかかつ直感的に理解することを可能にする。
このグラフベースのアプローチにより、グローバルな性能測定にのみ依存するのではなく、個々のエントリに対する行列完備化の固有の複雑さを定量化することができる。
関連論文リスト
- Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information [3.9748528039819977]
本稿では,半教師付きモデルにおける雑音行列補完の統計的推測について検討する。
検討した文脈において,反復最小二乗(LS)推定手法を適用した。
提案手法は数回の反復しか必要とせず、結果として得られる低ランク行列と係数行列のエントリーワイズ推定器は正規分布を持つことが保証されている。
論文 参考訳（メタデータ） (2024-03-22T01:06:36Z) - Entry-Specific Bounds for Low-Rank Matrix Completion under Highly
Non-Uniform Sampling [10.824999179337558]
行列全体よりも小さい部分行列上で推定アルゴリズムを実行する方がよく、時には最適であることを示す。
我々の境界は、各エントリを局所的なサンプリング確率の関数として推定する難しさを特徴付ける。
論文 参考訳（メタデータ） (2024-02-29T23:24:43Z) - On the design-dependent suboptimality of the Lasso [27.970033039287884]
最小特異値が小さい場合、ラッソ推定器は、確実に最小値であることを示す。
我々の下限は、ラッソの全ての形態のまばらな統計的最適性を妨げるのに十分強い。
論文 参考訳（メタデータ） (2024-02-01T07:01:54Z) - Entrywise Inference for Missing Panel Data: A Simple and Instance-Optimal Approach [27.301741710016223]
停滞した採用によって引き起こされたパネルデータの欠落データバージョンに関連する推論的疑問を考察する。
我々は、予め特定されたカバレッジでエントリワイドな信頼区間を構築するためのデータ駆動方式を開発し、分析する。
我々は、欠落したエントリを推定する際に、そのエラーに非漸近的かつ高い確率境界を証明した。
論文 参考訳（メタデータ） (2024-01-24T18:58:18Z) - Matrix Completion from General Deterministic Sampling Patterns [28.116011361245224]
我々は、精度よく近似した低ランク行列完備問題の理論的保証を確立する。
観測グラフが十分に接続されており、類似ノード次数を持つため、このアルゴリズムが成功することを示す。
論文 参考訳（メタデータ） (2023-06-04T07:01:31Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳（メタデータ） (2020-07-16T13:27:47Z) - Learning Minimax Estimators via Online Learning [55.92459567732491]
確率分布のパラメータを推定するミニマックス推定器を設計する際の問題点を考察する。
混合ケースナッシュ平衡を求めるアルゴリズムを構築した。
論文 参考訳（メタデータ） (2020-06-19T22:49:42Z) - Asymptotic Analysis of an Ensemble of Randomly Projected Linear
Discriminants [94.46276668068327]
[1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。
我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。
また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
論文 参考訳（メタデータ） (2020-04-17T12:47:04Z) - Semiparametric Nonlinear Bipartite Graph Representation Learning with
Provable Guarantees [106.91654068632882]
半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。
提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。
我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
論文 参考訳（メタデータ） (2020-03-02T16:40:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。