論文の概要: Optimal Estimator for Linear Regression with Shuffled Labels
- arxiv url: http://arxiv.org/abs/2310.01326v1
- Date: Mon, 2 Oct 2023 16:44:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-04 20:50:13.702883
- Title: Optimal Estimator for Linear Regression with Shuffled Labels
- Title（参考訳）: シャッフルラベルを用いた線形回帰の最適推定
- Authors: Hang Zhang and Ping Li
- Abstract要約: 本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
- 参考スコア（独自算出の注目度）: 17.99906229036223
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper considers the task of linear regression with shuffled labels,
i.e., $\mathbf Y = \mathbf \Pi \mathbf X \mathbf B + \mathbf W$, where $\mathbf
Y \in \mathbb R^{n\times m}, \mathbf Pi \in \mathbb R^{n\times n}, \mathbf X\in
\mathbb R^{n\times p}, \mathbf B \in \mathbb R^{p\times m}$, and $\mathbf W\in
\mathbb R^{n\times m}$, respectively, represent the sensing results, (unknown
or missing) corresponding information, sensing matrix, signal of interest, and
additive sensing noise. Given the observation $\mathbf Y$ and sensing matrix
$\mathbf X$, we propose a one-step estimator to reconstruct $(\mathbf \Pi,
\mathbf B)$. From the computational perspective, our estimator's complexity is
$O(n^3 + np^2m)$, which is no greater than the maximum complexity of a linear
assignment algorithm (e.g., $O(n^3)$) and a least square algorithm (e.g.,
$O(np^2 m)$). From the statistical perspective, we divide the minimum $snr$
requirement into four regimes, e.g., unknown, hard, medium, and easy regimes;
and present sufficient conditions for the correct permutation recovery under
each regime: $(i)$ $snr \geq \Omega(1)$ in the easy regime; $(ii)$ $snr \geq
\Omega(\log n)$ in the medium regime; and $(iii)$ $snr \geq \Omega((\log
n)^{c_0}\cdot n^{{c_1}/{srank(\mathbf B)}})$ in the hard regime ($c_0, c_1$ are
some positive constants and $srank(\mathbf B)$ denotes the stable rank of
$\mathbf B$). In the end, we also provide numerical experiments to confirm the
above claims.
- Abstract（参考訳）: 本稿では,シャッフルラベルを用いた線形回帰処理,すなわち $\mathbf Y = \mathbf \Pi \mathbf X \mathbf B + \mathbf W$, where $\mathbf Y \in \mathbb R^{n\times m}, \mathbf Pi \in \mathbb R^{n\times n}, \mathbf X\in \mathbb R^{n\times p}, \mathbf B \in \mathbb R^{p\times m}$, $\mathbf W\in \mathbb R^{n\times m}$について考察する。
観測値 $\mathbf y$ とセンシング行列 $\mathbf x$ を考えると、我々は$(\mathbf \pi, \mathbf b)$ を再構成する一段階推定器を提案する。
計算の観点からは、我々の推定器の複雑性は$o(n^3 + np^2m)$であり、これは線形代入アルゴリズム(例えば$o(n^3)$)と最小二乗アルゴリズム(例えば$o(np^2)の最大複雑性よりも大きい。
m)$。
統計的観点から、最小の$snr$要件を、未知、ハード、中、容易な4つのレギュレーションに分割し、各レギュレーションの下で正しい順列回復のための十分な条件を示す。
(i)$ $snr \geq \Omega(1)$ in the easy regime; $
(ii)$ $snr \geq \Omega(\log n)$ in the medium regime; and $
(iii)$ $snr \geq \omega((\log n)^{c_0}\cdot n^{{c_1}/{srank(\mathbf b)}}) hard regime (c_0, c_1$ はいくつかの正定数、$srank(\mathbf b)$ は$\mathbf b$ の安定ランクを表す)。
最後に,上記の主張を確認するための数値実験も実施する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。
グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
論文 参考訳（メタデータ） (2024-09-13T12:28:42Z) - Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Matrix Completion in Almost-Verification Time [37.61139884826181]
99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。
本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
論文 参考訳（メタデータ） (2023-08-07T15:24:49Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Beyond Independent Measurements: General Compressed Sensing with GNN
Application [4.924126492174801]
我々は、ノイズコーン観測からmathbbRn$の構造化信号$mathbfxを復元する問題を考察する。
実効的な$mathbfB$は測定値のサロゲートとして用いられる可能性がある。
論文 参考訳（メタデータ） (2021-10-30T20:35:56Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。