論文の概要: The Fine-Grained Hardness of Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2106.03131v1
- Date: Sun, 6 Jun 2021 14:19:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 18:34:57.123990
- Title: The Fine-Grained Hardness of Sparse Linear Regression
- Title（参考訳）: Sparse Linear Regression の微細結晶硬さ
- Authors: Aparna Gupte and Vinod Vaikuntanathan
- Abstract要約: この問題に対して、より優れたブルートフォースアルゴリズムは存在しないことを示す。
また,予測誤差が測定された場合,より優れたブラトフォースアルゴリズムが不可能であることを示す。
- 参考スコア（独自算出の注目度）: 12.83354999540079
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Sparse linear regression is the well-studied inference problem where one is
given a design matrix $\mathbf{A} \in \mathbb{R}^{M\times N}$ and a response
vector $\mathbf{b} \in \mathbb{R}^M$, and the goal is to find a solution
$\mathbf{x} \in \mathbb{R}^{N}$ which is $k$-sparse (that is, it has at most
$k$ non-zero coordinates) and minimizes the prediction error $||\mathbf{A}
\mathbf{x} - \mathbf{b}||_2$. On the one hand, the problem is known to be
$\mathcal{NP}$-hard which tells us that no polynomial-time algorithm exists
unless $\mathcal{P} = \mathcal{NP}$. On the other hand, the best known
algorithms for the problem do a brute-force search among $N^k$ possibilities.
In this work, we show that there are no better-than-brute-force algorithms,
assuming any one of a variety of popular conjectures including the weighted
$k$-clique conjecture from the area of fine-grained complexity, or the hardness
of the closest vector problem from the geometry of numbers. We also show the
impossibility of better-than-brute-force algorithms when the prediction error
is measured in other $\ell_p$ norms, assuming the strong exponential-time
hypothesis.
- Abstract（参考訳）: スパース線形回帰 (sparse linear regression) とは、設計行列 $\mathbf{a} \in \mathbb{r}^{m\times n}$ と応答ベクトル $\mathbf{b} \in \mathbb{r}^m$ が与えられるよく研究された推論問題であり、目的は、$k$-スパース(つまり、最大$k$非零座標を持つ)である解 $\mathbf{x} \in \mathbb{r}^{n}$ を見つけ、予測誤差 $||\mathbf{a} \mathbf{x} - \mathbf{b}|_2$ を最小化することである。
一方、問題は $\mathcal{NP}$-hard であることが知られており、$\mathcal{P} = \mathcal{NP}$ でない限り多項式時間アルゴリズムは存在しない。
一方、この問題の最もよく知られたアルゴリズムは、$N^k$の確率でブルートフォース探索を行う。
本研究では,細粒度複雑性の領域から重み付けされた$k$-clique 予想や,数幾何から最も近いベクトル問題の硬さなど,様々な一般的な予想のどれかのいずれかを仮定し,力より優れたアルゴリズムは存在しないことを示す。
また, 予測誤差が他の$\ell_p$ノルムで測定された場合, 強い指数時間仮説を仮定すると, 力より優れたアルゴリズムは不可能であることを示す。
関連論文リスト
- 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) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。
重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文 参考訳（メタデータ） (2023-10-18T10:56:57Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50: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) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
グリーンガードとロークリンの有名な高速多重極法における次元$dの指数的依存は改善できないことを示す。
これは高速多重極法について証明された最初の公式な制限である。
論文 参考訳（メタデータ） (2020-11-04T18:35:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。