論文の概要: Active Sampling for Linear Regression Beyond the $\ell_2$ Norm
- arxiv url: http://arxiv.org/abs/2111.04888v1
- Date: Tue, 9 Nov 2021 00:20:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-10 23:21:46.469527
- Title: Active Sampling for Linear Regression Beyond the $\ell_2$ Norm
- Title（参考訳）: $\ell_2$ Normを超える線形回帰のためのアクティブサンプリング
- Authors: Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
- Abstract要約: 対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
- 参考スコア（独自算出の注目度）: 70.49273459706546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study active sampling algorithms for linear regression, which aim to query
only a small number of entries of a target vector $b\in\mathbb{R}^n$ and output
a near minimizer to $\min_{x\in\mathbb{R}^d}\|Ax-b\|$, where $A\in\mathbb{R}^{n
\times d}$ is a design matrix and $\|\cdot\|$ is some loss function.
For $\ell_p$ norm regression for any $0<p<\infty$, we give an algorithm based
on Lewis weight sampling that outputs a $(1+\epsilon)$ approximate solution
using just $\tilde{O}(d^{\max(1,{p/2})}/\mathrm{poly}(\epsilon))$ queries to
$b$. We show that this dependence on $d$ is optimal, up to logarithmic factors.
Our result resolves a recent open question of Chen and Derezi\'{n}ski, who gave
near optimal bounds for the $\ell_1$ norm, and suboptimal bounds for $\ell_p$
regression with $p\in(1,2)$.
We also provide the first total sensitivity upper bound of
$O(d^{\max\{1,p/2\}}\log^2 n)$ for loss functions with at most degree $p$
polynomial growth. This improves a recent result of Tukan, Maalouf, and
Feldman. By combining this with our techniques for the $\ell_p$ regression
result, we obtain an active regression algorithm making $\tilde
O(d^{1+\max\{1,p/2\}}/\mathrm{poly}(\epsilon))$ queries, answering another open
question of Chen and Derezi\'{n}ski. For the important special case of the
Huber loss, we further improve our bound to an active sample complexity of
$\tilde O(d^{(1+\sqrt2)/2}/\epsilon^c)$ and a non-active sample complexity of
$\tilde O(d^{4-2\sqrt 2}/\epsilon^c)$, improving a previous $d^4$ bound for
Huber regression due to Clarkson and Woodruff. Our sensitivity bounds have
further implications, improving a variety of previous results using sensitivity
sampling, including Orlicz norm subspace embeddings and robust subspace
approximation. Finally, our active sampling results give the first sublinear
time algorithms for Kronecker product regression under every $\ell_p$ norm.
- Abstract（参考訳）: 対象ベクトル $b\in\mathbb{R}^n$ の少数のエントリのみを問合せし、近小数点を $\min_{x\in\mathbb{R}^d}\|Ax-b\|$ に出力する線形回帰のアクティブサンプリングアルゴリズムについて検討する。
任意の$0<p<\infty$ に対して$\ell_p$ のノルム回帰に対して、lewisの重みサンプリングに基づくアルゴリズムを与え、$(1+\epsilon)$ の近似解を$\tilde{o}(d^{\max(1,{p/2})}/\mathrm{poly}(\epsilon))$ のクエリで出力する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
その結果、chen と derezi\'{n}ski は、$\ell_1$ のノルムに対してほぼ最適境界を与え、$p\in(1,2)$ で$\ell_p$ の回帰に対して準最適境界を与えた。
また、多項式成長度が最大となる損失関数に対して、最初の全感度上限である$o(d^{\max\{1,p/2\}}\log^2 n)$を提供する。
これはTukan、Maalouf、Feldmanの最近の結果を改善する。
これを $\ell_p$ 回帰結果の手法と組み合わせることで、 $\tilde O(d^{1+\max\{1,p/2\}}/\mathrm{poly}(\epsilon))$ クエリのアクティブ回帰アルゴリズムが得られ、Chen と Derezi\'{n}ski の別のオープンな質問に答える。
ハマー損失の重要な特別な場合に対して、我々はさらに $\tilde O(d^{(1+\sqrt2)/2}/\epsilon^c)$ と $\tilde O(d^{4-2\sqrt 2}/\epsilon^c)$ の非活性サンプル複雑性へのバウンドを改善し、クラークソンとウッドラフによるハマー回帰に対する以前の$d^4$バウンドを改善する。
我々の感度境界はさらに意味を持ち、orliczノルム部分空間埋め込みやロバスト部分空間近似など、感度サンプリングを用いて様々な結果を改善する。
最後に、我々のアクティブサンプリング結果は、$\ell_p$ノルムごとにクロネッカー積回帰に対する最初の部分線形時間アルゴリズムを与える。
関連論文リスト
- Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。
また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
論文 参考訳（メタデータ） (2024-06-01T07:03:40Z) - Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank
Approximation [23.06440095688755]
ニューラルネットワークを圧縮する一般的な手法は、完全に接続された層(または埋め込み層)に対応する行列$AinmathbbRntimes d$の$k$-rank $ell$近似$A_k,2$を計算することである。
ここで$d$は層内のニューロンの数、$n$は次のニューロンの数、$A_k,2$は$O(n+d)k)$メモリに格納できる。
これ
論文 参考訳（メタデータ） (2020-09-11T20:21:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。