論文の概要: Semi-Random Sparse Recovery in Nearly-Linear Time
- arxiv url: http://arxiv.org/abs/2203.04002v1
- Date: Tue, 8 Mar 2022 10:56:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-09 14:20:04.821243
- Title: Semi-Random Sparse Recovery in Nearly-Linear Time
- Title（参考訳）: ほぼ線形時間における半ランダムスパース回復
- Authors: Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian
- Abstract要約: 生成モデル変更に対する高速スパース回収アルゴリズムの脆性について検討する。
提案手法は,半ランダム生成モデルに基づく証明可能な保証付き高速反復法とは異なる。
半ランダムモデルに対して確実に堅牢なスパースリカバリの幾何学に適合した新しい反復法を設計する。
- 参考スコア（独自算出の注目度）: 37.61139884826181
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sparse recovery is one of the most fundamental and well-studied inverse
problems. Standard statistical formulations of the problem are provably solved
by general convex programming techniques and more practical, fast
(nearly-linear time) iterative methods. However, these latter "fast algorithms"
have previously been observed to be brittle in various real-world settings.
We investigate the brittleness of fast sparse recovery algorithms to
generative model changes through the lens of studying their robustness to a
"helpful" semi-random adversary, a framework which tests whether an algorithm
overfits to input assumptions. We consider the following basic model: let
$\mathbf{A} \in \mathbb{R}^{n \times d}$ be a measurement matrix which contains
an unknown subset of rows $\mathbf{G} \in \mathbb{R}^{m \times d}$ which are
bounded and satisfy the restricted isometry property (RIP), but is otherwise
arbitrary. Letting $x^\star \in \mathbb{R}^d$ be $s$-sparse, and given either
exact measurements $b = \mathbf{A} x^\star$ or noisy measurements $b =
\mathbf{A} x^\star + \xi$, we design algorithms recovering $x^\star$
information-theoretically optimally in nearly-linear time. We extend our
algorithm to hold for weaker generative models relaxing our planted RIP
assumption to a natural weighted variant, and show that our method's guarantees
naturally interpolate the quality of the measurement matrix to, in some
parameter regimes, run in sublinear time.
Our approach differs from prior fast iterative methods with provable
guarantees under semi-random generative models: natural conditions on a
submatrix which make sparse recovery tractable are NP-hard to verify. We design
a new iterative method tailored to the geometry of sparse recovery which is
provably robust to our semi-random model. We hope our approach opens the door
to new robust, efficient algorithms for natural statistical inverse problems.
- Abstract（参考訳）: スパース・リカバリは最も基本的でよく研究された逆問題の一つである。
この問題の標準的な統計的定式化は、一般的な凸計画法とより実用的で速い(近線形時間)反復法によって証明できる。
しかし、これらの後者の「高速アルゴリズム」は、様々な実世界の環境では不安定である。
アルゴリズムが入力仮定に過剰に適合するかどうかをテストするフレームワークである"helpful" semi-random adversaryへのロバスト性を調べるレンズを通して、高速スパースリカバリアルゴリズムの不安定性を調査した。
以下の基本的なモデルを考える: $\mathbf{a} \in \mathbb{r}^{n \times d}$ を列の未知の部分集合を含む測定行列とする。
x^\star \in \mathbb{R}^d$ を $s$-sparse とし、正確な測定値 $b = \mathbf{A} x^\star$ またはノイズ測定値 $b = \mathbf{A} x^\star + \xi$ を与えられると、ほぼ線形時間で$x^\star$ 情報を最適に復元するアルゴリズムを設計する。
提案手法は,RIP仮定を自然重み付き変種に緩和する弱い生成モデルを保持するためにアルゴリズムを拡張し,測定行列の品質を自然に補間し,パラメータ状態によってはサブ線形時間で実行することを示す。
本手法は,半ランダム生成モデル下での証明可能な保証付き高速反復法と異なり,スパースリカバリを抽出可能なサブマトリクス上の自然条件はNPハードである。
半ランダムモデルに対して確実に堅牢なスパースリカバリの幾何学に適合した新しい反復法を設計する。
我々のアプローチが、自然統計逆問題に対する新しい堅牢で効率的なアルゴリズムの扉を開くことを願っている。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method [10.742859956268655]
本稿では,レバレッジスコア勾配から固有モデルパラメータを復元することを目的とする。
具体的には、レバレッジスコア勾配の逆転を$g(x)$として精査する。
論文 参考訳（メタデータ） (2024-08-21T01:39:42Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。
提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。
我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
論文 参考訳（メタデータ） (2021-06-15T02:23:07Z) - Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。
ProxRR と FedRR は複合凸有限和最小化問題を解く。
ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文 参考訳（メタデータ） (2021-02-12T18:59:24Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳（メタデータ） (2020-03-03T18:46:34Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。