論文の概要: Reduced Label Complexity For Tight $\ell_2$ Regression
- arxiv url: http://arxiv.org/abs/2305.07486v1
- Date: Fri, 12 May 2023 13:56:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-15 12:50:05.589685
- Title: Reduced Label Complexity For Tight $\ell_2$ Regression
- Title(参考訳): ラベルの複雑さを減らした$\ell_2$回帰
- Authors: Alex Gittens and Malik Magdon-Ismail
- Abstract要約: データ$rm XinmathbbRntimes d$とラベル$mathbfyinmathbbRn$が与えられたら、目標は$mathbfw-mathbfyVert2$を見つけることである。
私たちは$mathbfy$に比例して$n/(d+sqrtn)$データポイントをスローアウトし、期待値に最適な$(1+d/n)$-approximationを行うアルゴリズムを提供します。
- 参考スコア(独自算出の注目度): 12.141102261633746
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given data ${\rm X}\in\mathbb{R}^{n\times d}$ and labels
$\mathbf{y}\in\mathbb{R}^{n}$ the goal is find $\mathbf{w}\in\mathbb{R}^d$ to
minimize $\Vert{\rm X}\mathbf{w}-\mathbf{y}\Vert^2$. We give a polynomial
algorithm that, \emph{oblivious to $\mathbf{y}$}, throws out $n/(d+\sqrt{n})$
data points and is a $(1+d/n)$-approximation to optimal in expectation. The
motivation is tight approximation with reduced label complexity (number of
labels revealed). We reduce label complexity by $\Omega(\sqrt{n})$. Open
question: Can label complexity be reduced by $\Omega(n)$ with tight
$(1+d/n)$-approximation?
- Abstract(参考訳): データ ${\rm x}\in\mathbb{r}^{n\times d}$ とラベル $\mathbf{y}\in\mathbb{r}^{n}$ が与えられたとき、目標は$\mathbf{w}\in\mathbb{r}^d$ で$\vert{\rm x}\mathbf{w}-\mathbf{y}\vert^2$ を最小化することである。
我々は、$\mathbf{y}$} に \emph{oblivious, $n/(d+\sqrt{n})$ データポイントをスローアウトし、期待値に最適な$(1+d/n)$-approximation を与える多項式アルゴリズムを与える。
モチベーションはラベルの複雑さを減らした(ラベルの数)厳密な近似である。
ラベルの複雑さを$\Omega(\sqrt{n})$で減らします。
オープンな質問:ラベルの複雑さを1+d/n)$-approximationで$\Omega(n)$に縮めることができるか?
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳(メタデータ) (2024-02-22T02:20:24Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。
mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
論文 参考訳(メタデータ) (2023-10-02T16:44:47Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳(メタデータ) (2023-04-10T05:52:38Z) - 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) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳(メタデータ) (2021-03-17T00:59:33Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳(メタデータ) (2021-03-10T07:33:03Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - 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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳(メタデータ) (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。