論文の概要: Polynomial-time sparse measure recovery

• arxiv url: http://arxiv.org/abs/2204.07879v1
• Date: Sat, 16 Apr 2022 22:12:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-19 14:05:48.216116
• Title: Polynomial-time sparse measure recovery
• Title（参考訳）: 多項式時間スパース測度の回復
• Authors: Hadi Daneshmand and Francis Bach
• Abstract要約: 慎重に設計したモーメントから最初のポリ時間回復法を提案する。 この方法は、2次元入力、有限幅、ゼロワンアクティベーションを備えた植込み2層ニューラルネットワークの回復に依存する。
• 参考スコア（独自算出の注目度）: 2.0951285993543642
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: How to recover a probability measure with sparse support from particular moments? This problem has been the focus of research in theoretical computer science and neural computing. However, there is no polynomial-time algorithm for the recovery. The best algorithm for the recovery requires $O(2^{\text{poly}(1/\epsilon)})$ for $\epsilon$-accurate recovery. We propose the first poly-time recovery method from carefully designed moments that only requires $O(\log(1/\epsilon)/\epsilon^2)$ computations for an $\epsilon$-accurate recovery. This method relies on the recovery of a planted two-layer neural network with two-dimensional inputs, a finite width, and zero-one activation. For such networks, we establish the first global convergence of gradient descent and demonstrate its application in sparse measure recovery.
• Abstract（参考訳）: 特定の瞬間からスパース支援を伴う確率測度を回復する方法? この問題は理論計算機科学とニューラルコンピューティングの研究の焦点となっている。 しかし、回復のための多項式時間アルゴリズムは存在しない。 回復に最適なアルゴリズムは、$O(2^{\text{poly}(1/\epsilon)})$ for $\epsilon$-accurate recoveryである。 我々は,$O(\log(1/\epsilon)/\epsilon^2)$の計算しか必要としない,慎重に設計されたモーメントからの最初のポリ時間回復法を提案する。 この方法は、2次元入力、有限幅、ゼロワンアクティベーションを持つ植込み型2層ニューラルネットワークの回復に依存している。 このようなネットワークに対して, 勾配降下のグローバル収束を初めて確立し, スパース測度回復への応用を実証する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。 また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
  論文  参考訳（メタデータ） (2023-03-03T18:03:49Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Improved Support Recovery in Universal One-bit Compressed Sensing [37.5349071806395]
  1ビット圧縮(1bCS)は、極端に量子化された信号取得法である。 本論文の焦点は、しばしば近似的な信号回復を促進するサポートリカバリである。 まず, $tildeO(k/epsilon), $tildeO(maxk/epsilon,k3/2), $tildeO(maxk/epsilon,k3/2)$測定を行う。
  論文  参考訳（メタデータ） (2022-10-29T17:43:14Z)
• Semi-Random Sparse Recovery in Nearly-Linear Time [37.61139884826181]
  生成モデル変更に対する高速スパース回収アルゴリズムの脆性について検討する。 提案手法は,半ランダム生成モデルに基づく証明可能な保証付き高速反復法とは異なる。 半ランダムモデルに対して確実に堅牢なスパースリカバリの幾何学に適合した新しい反復法を設計する。
  論文  参考訳（メタデータ） (2022-03-08T10:56:46Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Training (Overparametrized) Neural Networks in Near-Linear Time [21.616949485102342]
  本稿では,ReparamLUネットワークをトレーニングするための[CGH+1]アルゴリズムの高速化について述べる。 我々のアルゴリズムの中心はガウスニュートンを$ell$-reconditionとして再構成することである。
  論文  参考訳（メタデータ） (2020-06-20T20:26:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。