論文の概要: Hardness and Algorithms for Robust and Sparse Optimization
- arxiv url: http://arxiv.org/abs/2206.14354v1
- Date: Wed, 29 Jun 2022 01:40:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-01 04:50:39.749856
- Title: Hardness and Algorithms for Robust and Sparse Optimization
- Title（参考訳）: ロバストおよびスパース最適化のためのハードネスとアルゴリズム
- Authors: Eric Price, Sandeep Silwal, Samson Zhou
- Abstract要約: スパース線形回帰やロバスト線形回帰といったスパース最適化問題に対するアルゴリズムと制限について検討する。
具体的には、スパース線型回帰問題は$k$-スパースベクトル$xinmathbbRd$を求め、$|Ax-b|$を最小化する。
頑健な線形回帰問題は、少なくとも$k$行を無視する集合$S$と、$|(Ax-b)_S|$を最小化するベクトル$x$を求める。
- 参考スコア（独自算出の注目度）: 17.842787715567436
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore algorithms and limitations for sparse optimization problems such
as sparse linear regression and robust linear regression. The goal of the
sparse linear regression problem is to identify a small number of key features,
while the goal of the robust linear regression problem is to identify a small
number of erroneous measurements. Specifically, the sparse linear regression
problem seeks a $k$-sparse vector $x\in\mathbb{R}^d$ to minimize $\|Ax-b\|_2$,
given an input matrix $A\in\mathbb{R}^{n\times d}$ and a target vector
$b\in\mathbb{R}^n$, while the robust linear regression problem seeks a set $S$
that ignores at most $k$ rows and a vector $x$ to minimize $\|(Ax-b)_S\|_2$.
We first show bicriteria, NP-hardness of approximation for robust regression
building on the work of [OWZ15] which implies a similar result for sparse
regression. We further show fine-grained hardness of robust regression through
a reduction from the minimum-weight $k$-clique conjecture. On the positive
side, we give an algorithm for robust regression that achieves arbitrarily
accurate additive error and uses runtime that closely matches the lower bound
from the fine-grained hardness result, as well as an algorithm for sparse
regression with similar runtime. Both our upper and lower bounds rely on a
general reduction from robust linear regression to sparse regression that we
introduce. Our algorithms, inspired by the 3SUM problem, use approximate
nearest neighbor data structures and may be of independent interest for solving
sparse optimization problems. For instance, we demonstrate that our techniques
can also be used for the well-studied sparse PCA problem.
- Abstract（参考訳）: スパース線形回帰やロバスト線形回帰といったスパース最適化問題のアルゴリズムと限界について検討する。
スパース線形回帰問題の目標は、少数の重要な特徴を特定することであるが、ロバストな線形回帰問題の目標は、少数の誤った測定値を特定することである。
特に、スパース線形回帰問題は、入力行列 $a\in\mathbb{r}^{n\times d}$ と対象ベクトル $b\in\mathbb{r}^n$ に対して、$k$-スパースベクトル $x\in\mathbb{r}^d$ を求める一方、ロバスト線形回帰問題は、最大 $k$ 行を無視するセット $s$ と $\|(ax-b)_s\|_2$ を最小化するベクトル $x$ を求める。
まず, [owz15] の作用に基づくロバスト回帰構築のための近似値のnp-hardnessであるbicriteria を示す。
さらに、最小重量$k$-clique予想からの還元により、頑健な回帰のきめ細かい硬さを示す。
正の面では、任意の精度の加算誤差を達成するロバスト回帰アルゴリズムを与え、細粒度ハードネス結果から下限と密接に一致するランタイムと、類似したランタイムでスパース回帰を行うアルゴリズムを使用する。
上界と下界の両方が、ロバストな線形回帰からスパース回帰への一般的な還元に依存している。
我々のアルゴリズムは3SUM問題にインスパイアされたもので、近傍のデータ構造に近く、スパース最適化問題の解法には独立した関心を持つ可能性がある。
例えば、我々の技術は、十分に研究されたスパースPCA問題にも利用できることを示した。
関連論文リスト
- Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。
我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
論文 参考訳（メタデータ） (2024-02-21T19:55:01Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sparse Mixed Linear Regression with Guarantees: Taming an Intractable
Problem with Invex Relaxation [31.061339148448006]
本稿では,ラベルのないデータセット上での疎混合線形回帰問題について検討する。
我々は、この難解な問題に対して、証明可能な理論的保証を持つ解をもたらす新しい凸緩和を提供する。
論文 参考訳（メタデータ） (2022-06-02T17:38:11Z) - Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
本稿では,リスト復号化可能な線形回帰問題について考察する。
我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
論文 参考訳（メタデータ） (2021-06-17T17:45:21Z) - Coordinate Methods for Matrix Games [41.821881312775496]
我々は,MathcalX max_yinmathY ytop A x$ の $min_x 形式の双線形サドル点問題を解くための主対座標法を開発した。
提案手法は,既存のサブ線形手法を,各項目の複雑性とサンプルの複雑さの観点から限界に推し進める。
論文 参考訳（メタデータ） (2020-09-17T17:55:03Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - 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) - Fractional ridge regression: a fast, interpretable reparameterization of
ridge regression [0.0]
リッジ回帰(RR)は、線形回帰における係数のL2-ノルムをペナライズする正規化手法である。
我々は、FRRを解くアルゴリズムと、Pythonのオープンソースソフトウェア実装を提供する。
論文 参考訳（メタデータ） (2020-05-07T03:12:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。