論文の概要: Optimal Sketching Bounds for Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2304.02261v1
- Date: Wed, 5 Apr 2023 07:24:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-06 13:20:45.050466
- Title: Optimal Sketching Bounds for Sparse Linear Regression
- Title(参考訳): Sparse Linear Regressionのための最適スケッチ境界
- Authors: Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris
Schwiegelshohn, David P. Woodruff
- Abstract要約: 我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
- 参考スコア(独自算出の注目度): 116.30196615349226
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study oblivious sketching for $k$-sparse linear regression under various
loss functions such as an $\ell_p$ norm, or from a broad class of hinge-like
loss functions, which includes the logistic and ReLU losses. We show that for
sparse $\ell_2$ norm regression, there is a distribution over oblivious
sketches with $\Theta(k\log(d/k)/\varepsilon^2)$ rows, which is tight up to a
constant factor. This extends to $\ell_p$ loss with an additional additive
$O(k\log(k/\varepsilon)/\varepsilon^2)$ term in the upper bound. This
establishes a surprising separation from the related sparse recovery problem,
which is an important special case of sparse regression. For this problem,
under the $\ell_2$ norm, we observe an upper bound of $O(k \log (d)/\varepsilon
+ k\log(k/\varepsilon)/\varepsilon^2)$ rows, showing that sparse recovery is
strictly easier to sketch than sparse regression. For sparse regression under
hinge-like loss functions including sparse logistic and sparse ReLU regression,
we give the first known sketching bounds that achieve $o(d)$ rows showing that
$O(\mu^2 k\log(\mu n d/\varepsilon)/\varepsilon^2)$ rows suffice, where $\mu$
is a natural complexity parameter needed to obtain relative error bounds for
these loss functions. We again show that this dimension is tight, up to lower
order terms and the dependence on $\mu$. Finally, we show that similar
sketching bounds can be achieved for LASSO regression, a popular convex
relaxation of sparse regression, where one aims to minimize
$\|Ax-b\|_2^2+\lambda\|x\|_1$ over $x\in\mathbb{R}^d$. We show that sketching
dimension $O(\log(d)/(\lambda \varepsilon)^2)$ suffices and that the dependence
on $d$ and $\lambda$ is tight.
- Abstract(参考訳): 我々は,$\ell_p$ ノルムや,ロジスティック損失や relu 損失を含むヒンジ様損失関数の幅広いクラスから,様々な損失関数の下での $k$-sparse 線形回帰に対する不明瞭なスケッチについて検討する。
スパース $\ell_2$ のノルム回帰では、_\theta(k\log(d/k)/\varepsilon^2)$行を持つ斜めスケッチの上に分布があり、定数係数に密着している。
これは$\ell_p$ に拡張され、上界に$o(k\log(k/\varepsilon)/\varepsilon^2)$項を追加する。
これは、スパース回帰の重要な特別なケースである関連するスパース回復問題との驚くべき分離を確立する。
この問題に対して、$\ell_2$ のノルムの下では、$o(k \log (d)/\varepsilon + k\log(k/\varepsilon)/\varepsilon^2)$ の上限を観測し、スパースリカバリがスパースレグレッションよりも厳密にスケッチしやすいことを示した。
スパースロジスティックおよびスパースReLU回帰を含むヒンジ様損失関数のスパース回帰に対して、$O(\mu^2 k\log(\mu n d/\varepsilon)/\varepsilon^2)$ rows suffice, $\mu$は損失関数の相対的な誤差境界を得るために必要となる自然な複雑性パラメータであることを示す最初のスケッチ境界を与える。
再び、この次元は厳密で、より低い順序項と$\mu$への依存であることが示される。
最後に、類似のスケッチ境界は、スパース回帰の一般的な凸緩和であるLASSO回帰に対して達成できることを示し、ここでは、$\|Ax-b\|_2^2+\lambda\|x\|_1$ over $x\in\mathbb{R}^d$ を最小化する。
スケッチ次元 $o(\log(d)/(\lambda \varepsilon)^2)$ suffices と $d$ と $\lambda$ への依存が密であることを示す。
関連論文リスト
- 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) - Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic
Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。
また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。
我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文 参考訳(メタデータ) (2023-03-31T18:12:33Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳(メタデータ) (2023-02-01T05:22:40Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - L1 Regression with Lewis Weights Subsampling [10.796388585158184]
Lewisの重みに従って$X$からサンプリングし、経験的最小化器を出力すると、1-delta$$$mの確率で成功することを示す。
また、対応する$Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$も与えます。
論文 参考訳(メタデータ) (2021-05-19T23:15:00Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳(メタデータ) (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。