論文の概要: 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層ニューラルネットワークの回復に依存している。
このようなネットワークに対して, 勾配降下のグローバル収束を初めて確立し, スパース測度回復への応用を実証する。
関連論文リスト
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time [54.01594785269913]
本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - 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) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-14T16:51:14Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。