論文の概要: Nonparametric Matrix Estimation with One-Sided Covariates
- arxiv url: http://arxiv.org/abs/2110.13969v1
- Date: Tue, 26 Oct 2021 19:11:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-28 13:09:53.388991
- Title: Nonparametric Matrix Estimation with One-Sided Covariates
- Title(参考訳): 片側共変量を用いた非パラメトリック行列推定
- Authors: Christina Lee Yu
- Abstract要約: mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。
我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
- 参考スコア(独自算出の注目度): 5.457150493905064
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Consider the task of matrix estimation in which a dataset $X \in
\mathbb{R}^{n\times m}$ is observed with sparsity $p$, and we would like to
estimate $\mathbb{E}[X]$, where $\mathbb{E}[X_{ui}] = f(\alpha_u, \beta_i)$ for
some Holder smooth function $f$. We consider the setting where the row
covariates $\alpha$ are unobserved yet the column covariates $\beta$ are
observed. We provide an algorithm and accompanying analysis which shows that
our algorithm improves upon naively estimating each row separately when the
number of rows is not too small. Furthermore when the matrix is moderately
proportioned, our algorithm achieves the minimax optimal nonparametric rate of
an oracle algorithm that knows the row covariates. In simulated experiments we
show our algorithm outperforms other baselines in low data regimes.
- Abstract(参考訳): データセット $x \in \mathbb{r}^{n\times m}$ がスパーシティ $p$ で観測され、$\mathbb{e}[x]$, ここで$\mathbb{e}[x_{ui}] = f(\alpha_u, \beta_i)$ のある保留滑らかな関数 $f$ を推定したいとする行列推定のタスクを考える。
我々は、行 covariates $\alpha$ が観測されないが、列 covariates $\beta$ が観測されるような設定を考える。
本稿では,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析手法を提案する。
さらに,行列が適度に比例すると,行の共変量を知っているオラクルアルゴリズムの極小最適非パラメトリックレートが達成される。
シミュレーション実験では,本アルゴリズムが低データ領域の他のベースラインよりも優れていることを示す。
関連論文リスト
- Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳(メタデータ) (2024-06-01T07:33:41Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳(メタデータ) (2023-06-06T22:35:16Z) - Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time [8.808780937701522]
我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
論文 参考訳(メタデータ) (2023-02-21T23:49:36Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳(メタデータ) (2022-06-10T17:38:18Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Optimal Exact Matrix Completion Under new Parametrization [0.0]
適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。
対象行列を正確に復元する行列補完アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-06T18:31:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。