論文の概要: On Coresets For Regularized Regression
- arxiv url: http://arxiv.org/abs/2006.05440v3
- Date: Tue, 30 Jun 2020 08:43:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-23 14:37:50.220984
- Title: On Coresets For Regularized Regression
- Title（参考訳）: 正規化回帰のためのコアセットについて
- Authors: Rachit Chhaya, Anirban Dasgupta, Supratim Shit
- Abstract要約: 正規化された回帰版に対するコアセットのサイズを $|mathbfAx-mathbfb|_pr + lambda|mathbfx|_qs$ で解析する。
我々は、$r neq s$の場合、正規化回帰のコアセットが非正規化バージョンの最適コアセットよりも小さくなることを示す。
- 参考スコア（独自算出の注目度）: 8.965836729525394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the effect of norm based regularization on the size of coresets for
regression problems. Specifically, given a matrix $ \mathbf{A} \in
{\mathbb{R}}^{n \times d}$ with $n\gg d$ and a vector $\mathbf{b} \in
\mathbb{R} ^ n $ and $\lambda > 0$, we analyze the size of coresets for
regularized versions of regression of the form $\|\mathbf{Ax}-\mathbf{b}\|_p^r
+ \lambda\|{\mathbf{x}}\|_q^s$ . Prior work has shown that for ridge regression
(where $p,q,r,s=2$) we can obtain a coreset that is smaller than the coreset
for the unregularized counterpart i.e. least squares regression (Avron et al).
We show that when $r \neq s$, no coreset for regularized regression can have
size smaller than the optimal coreset of the unregularized version. The well
known lasso problem falls under this category and hence does not allow a
coreset smaller than the one for least squares regression. We propose a
modified version of the lasso problem and obtain for it a coreset of size
smaller than the least square regression. We empirically show that the modified
version of lasso also induces sparsity in solution, similar to the original
lasso. We also obtain smaller coresets for $\ell_p$ regression with $\ell_p$
regularization. We extend our methods to multi response regularized regression.
Finally, we empirically demonstrate the coreset performance for the modified
lasso and the $\ell_1$ regression with $\ell_1$ regularization.
- Abstract（参考訳）: 回帰問題に対するコアセットのサイズに対するノルムベース正規化の効果について検討する。
具体的には、行列 $ \mathbf{A} \in {\mathbb{R}}^{n \times d}$ に$n\gg d$ とベクトル $\mathbf{b} \in \mathbb{R} ^ n $ と $\lambda > 0$ が与えられたとき、形式 $\|\mathbf{Ax}-\mathbf{b}\|_p^r + \lambda\|{\mathbf{x}}\|_q^s$ の回帰の正規化バージョンに対するコアセットのサイズを分析する。
以前の研究は、リッジ回帰($p,q,r,s=2$)に対して、非正則化(すなわち最小二乗回帰(Avron et al))のコアセットよりも小さいコアセットが得られることを示した。
r \neq s$ の場合、正規化回帰のコアセットは、非正規化バージョンの最適コアセットよりも小さいサイズであることを示す。
よく知られたラスソ問題は、このカテゴリに該当するため、最小二乗回帰のコアセットよりも小さいコアセットを許さない。
我々は,lasso問題の修正版を提案し,最小二乗回帰よりも小さい大きさのコアセットを得る。
ラッソの修正版は、元のラッソと同様、溶液のスパース性も引き起こすことが実証的に示されている。
また、$\ell_p$レギュライゼーション付き$\ell_p$レグレッション用の小さなコアセットも取得します。
我々は手法を多応答正規化回帰に拡張する。
最後に、修正ラッソのコアセット性能と$\ell_1$レグレッションの$\ell_1$正規化を実証的に示す。
関連論文リスト
- Conditional regression for the Nonlinear Single-Variable Model [4.565636963872865]
F(X):=f(Pi_gamma):mathbbRdto[0,rmlen_gamma]$ ここで$Pi_gamma: [0,rmlen_gamma]tomathbbRd$と$f:[0,rmlen_gamma]tomathbbR1$を考える。
条件回帰に基づく非パラメトリック推定器を提案し、$one$-dimensionalOptimical min-maxレートを実現できることを示す。
論文 参考訳（メタデータ） (2024-11-14T18:53:51Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - In-Context Learning for Attention Scheme: from Single Softmax Regression
to Multiple Softmax Regression via a Tensor Trick [15.090593955414137]
本研究では,本研究における注意関係回帰のための2つの定式化に基づく文脈内学習について考察する。
我々の回帰問題は、ソフトマックス関連回帰に関する以前の研究と類似している。
論文 参考訳（メタデータ） (2023-07-05T16:41:01Z) - 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) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Hardness and Algorithms for Robust and Sparse Optimization [17.842787715567436]
スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
論文 参考訳（メタデータ） (2022-06-29T01:40:38Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。