論文の概要: Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression
- arxiv url: http://arxiv.org/abs/2009.03986v2
- Date: Tue, 24 Nov 2020 10:00:18 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-20 20:44:41.016210
- Title: Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression
- Title（参考訳）: スパース回帰における条件付き不一致と非近似サブセット選択
- Authors: Jianji Wang, Qi Liu, Shupei Zhang, Nanning Zheng, Fei-Yue Wang
- Abstract要約: 相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
- 参考スコア（独自算出の注目度）: 72.84177488527398
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given $m$ $d$-dimensional responsors and $n$ $d$-dimensional predictors,
sparse regression finds at most $k$ predictors for each responsor for linear
approximation, $1\leq k \leq d-1$. The key problem in sparse regression is
subset selection, which usually suffers from high computational cost. Recent
years, many improved approximate methods of subset selection have been
published. However, less attention has been paid on the non-approximate method
of subset selection, which is very necessary for many questions in data
analysis. Here we consider sparse regression from the view of correlation, and
propose the formula of conditional uncorrelation. Then an efficient
non-approximate method of subset selection is proposed in which we do not need
to calculate any coefficients in regression equation for candidate predictors.
By the proposed method, the computational complexity is reduced from
$O(\frac{1}{6}{k^3}+mk^2+mkd)$ to $O(\frac{1}{6}{k^3}+\frac{1}{2}mk^2)$ for
each candidate subset in sparse regression. Because the dimension $d$ is
generally the number of observations or experiments and large enough, the
proposed method can greatly improve the efficiency of non-approximate subset
selection.
- Abstract（参考訳）: m$ $d$-dimensional responsors と $n$ $ $d$-dimensional predictors が与えられたとき、スパースレグレッションは、線形近似に対する各responsor の最大$k$ の予測子、 $1\leq k \leq d-1$ を見つける。
スパース回帰の鍵となる問題は、通常高い計算コストに悩まされる部分集合の選択である。
近年,多くの改良された部分集合選択法が公表されている。
しかし、データ分析において多くの疑問に対して非常に必要となるサブセット選択の非近似法にはあまり注意が払われていない。
ここでは相関の観点からの疎回帰を考察し,条件付き不相関式を提案する。
次に, 回帰方程式の係数を候補予測器に対して計算する必要のない, 効率的な部分集合選択法を提案する。
提案手法により,sparse回帰の各候補部分集合に対して,計算複雑性を$o(\frac{1}{6}{k^3}+mk^2+mkd)$から$o(\frac{1}{6}{k^3}+\frac{1}{2}mk^2)$に削減する。
次元 $d$ は一般に観測や実験の数であり、十分大きいので、提案手法は非近似部分集合選択の効率を大幅に改善することができる。
関連論文リスト
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。
我々は,頑健な期待回帰(退職)を提案し,研究する。
提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
論文 参考訳（メタデータ） (2022-12-11T18:03:12Z) - Dimension free ridge regression [10.434481202633458]
我々は、リッジ回帰のバイアスとばらつきの観点から、すなわちデータ上のリッジ回帰を再考し、等価なシーケンスモデルのバイアスとばらつきの観点から、リッジ回帰のバイアスとばらつきを考察する。
新しい応用として、定期的に変化するスペクトルを持つヒルベルト共変量に対して、完全に明示的で鋭い尾根回帰特性を得る。
論文 参考訳（メタデータ） (2022-10-16T16:01:05Z) - Permuted and Unlinked Monotone Regression in $\mathbb{R}^d$: an approach
based on mixture modeling and optimal transport [4.924126492174802]
回帰関数の巡回的単調性の概念は、置換/無リンク回帰モデルにおける同定と推定に十分であることを示す。
我々は,Keefer-Wolfowitz に基づく,計算効率が良く,使いやすいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-10T18:37:59Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - 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) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。