論文の概要: Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks
- arxiv url: http://arxiv.org/abs/2405.02086v1
- Date: Fri, 3 May 2024 13:21:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-06 12:46:03.851449
- Title: Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks
- Title（参考訳）: 指数パラレルスピードアップを用いたマルチレベルプロジェクション : スパースオートエンコーダニューラルネットワークへの応用
- Authors: Guillaume Perez, Michel Barlaud,
- Abstract要約: ell_1,infty$ノルムの時間複雑性は、$mathbbRntimes m$の行列に対して$mathcalObig(n m big)$のみであることを示す。
実験によると、我々の2レベル$ell_1,infty$プロジェクションは、実際の最速アルゴリズムよりも2.5ドル速い。
- 参考スコア（独自算出の注目度）: 2.264332709661011
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $\ell_{1,\infty}$ norm is an efficient structured projection but the complexity of the best algorithm is unfortunately $\mathcal{O}\big(n m \log(n m)\big)$ for a matrix in $\mathbb{R}^{n\times m}$. In this paper, we propose a new bi-level projection method for which we show that the time complexity for the $\ell_{1,\infty}$ norm is only $\mathcal{O}\big(n m \big)$ for a matrix in $\mathbb{R}^{n\times m}$, and $\mathcal{O}\big(n + m \big)$ with full parallel power. We generalize our method to tensors and we propose a new multi-level projection, having an induced decomposition that yields a linear parallel speedup up to an exponential speedup factor, resulting in a time complexity lower-bounded by the sum of the dimensions. Experiments show that our bi-level $\ell_{1,\infty}$ projection is $2.5$ times faster than the actual fastest algorithm provided by \textit{Chu et. al.} while providing same accuracy and better sparsity in neural networks applications.
- Abstract（参考訳）: $\ell_{1,\infty}$ノルムは効率的な構造化射影であるが、最良のアルゴリズムの複雑さは、$\mathbb{R}^{n\times m}$の行列に対して$\mathcal{O}\big(n m \log(n m)\big)$である。
本稿では,$\ell_{1,\infty}$ノルムの時間的複雑さが$\mathcal{O}\big(n m \big)$,$\mathbb{R}^{n\times m}$,$\mathcal{O}\big(n + m \big)$の行列に対してのみであることを示す新しい二値射影法を提案する。
本手法をテンソルに一般化し,指数的スピードアップ係数までの線形並列スピードアップを誘導分解し,次元の和によって時間的複雑さを低くする,新しい多層射影法を提案する。
実験の結果、我々の二段階の$\ell_{1,\infty}$プロジェクションは、 \textit{Chu et al } が提供する実際の最速アルゴリズムの2.5ドル高速であり、ニューラルネットワークアプリケーションでは、同じ精度とより親密性を提供する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - A new Linear Time Bi-level $\ell_{1,\infty}$ projection ; Application to the sparsification of auto-encoders neural networks [2.014710510332479]
我々は、$ell_1,infty$ノルムの時間複雑性が、行列 $ntimes m$ に対して$mathcalObig(n m big)$ であることを示す。
実験によると、我々の2レベル$ell_1,infty$プロジェクションは、実際の最速アルゴリズムよりも2.5ドル速い。
論文 参考訳（メタデータ） (2024-07-23T08:51:29Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
EigenDecomposition (ED)は多くのコンピュータビジョンアルゴリズムとアプリケーションの中心にある。
本稿では,コンピュータビジョンの応用シナリオに特化したQRベースのED手法を提案する。
論文 参考訳（メタデータ） (2022-07-09T09:14:12Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。
我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
論文 参考訳（メタデータ） (2020-10-01T22:41:41Z) - Training (Overparametrized) Neural Networks in Near-Linear Time [21.616949485102342]
本稿では,ReparamLUネットワークをトレーニングするための[CGH+1]アルゴリズムの高速化について述べる。
我々のアルゴリズムの中心はガウスニュートンを$ell$-reconditionとして再構成することである。
論文 参考訳（メタデータ） (2020-06-20T20:26:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。