Fugu-MT 論文翻訳(概要): Reduced Label Complexity For Tight $\ell

論文の概要: 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)$に縮めることができるか?

関連論文リスト

Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
本研究では, 対向分布シフトの存在下でのL2$損失に対して, 単一ニューロンを学習する問題について検討した。ベクトルベクトル二乗損失を$chi2$divergenceから$mathcalp_0$に近似するアルゴリズムを開発した。
論文参考訳（メタデータ） (2024-11-11T03:43:52Z)
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)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
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)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。