論文の概要: A new Linear Time Bi-level $\ell_{1,\infty}$ projection ; Application to the sparsification of auto-encoders neural networks
- arxiv url: http://arxiv.org/abs/2407.16293v1
- Date: Tue, 23 Jul 2024 08:51:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 18:06:10.901970
- Title: A new Linear Time Bi-level $\ell_{1,\infty}$ projection ; Application to the sparsification of auto-encoders neural networks
- Title（参考訳）: 新しい線形時間Biレベル$\ell_{1,\infty}$プロジェクション;オートエンコーダニューラルネットワークのスパース化への応用
- Authors: Michel Barlaud, Guillaume Perez, Jean-Paul Marmorat,
- Abstract要約: 我々は、$ell_1,infty$ノルムの時間複雑性が、行列 $ntimes m$ に対して$mathcalObig(n m big)$ であることを示す。
実験によると、我々の2レベル$ell_1,infty$プロジェクションは、実際の最速アルゴリズムよりも2.5ドル速い。
- 参考スコア（独自算出の注目度）: 2.014710510332479
- 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 $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 $n\times m$. Moreover, we provide a new $\ell_{1,\infty}$ identity with mathematical proof and experimental validation. Experiments show that our bi-level $\ell_{1,\infty}$ projection is $2.5$ times faster than the actual fastest algorithm and provides the best sparsity while keeping the same accuracy in classification applications.
- Abstract（参考訳）: $\ell_{1,\infty}$ノルムは効率的な構造的射影であるが、最良のアルゴリズムの複雑さは、残念ながら$\mathcal{O}\big(n m \log(n m)\big)$ for a matrix $n\times m$である。
この論文では、$\ell_{1,\infty}$ノルムの時間複雑性は、行列$n\times m$に対して$\mathcal{O}\big(n m \big)$のみであることを示す新しい二値射影法を提案する。
さらに、数学的証明と実験的検証を備えた新しい$\ell_{1,\infty}$恒等式を提供する。
実験により、我々の2レベル$\ell_{1,\infty}$プロジェクションは、実際の最速アルゴリズムよりも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) - Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks [2.264332709661011]
ell_1,infty$ノルムの時間複雑性は、$mathbbRntimes m$の行列に対して$mathcalObig(n m big)$のみであることを示す。
実験により、我々の予測は、実際の最速のユークリッドアルゴリズムの2倍高速であることが示されている。
論文 参考訳（メタデータ） (2024-05-03T13:21:49Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Near-Linear Time Projection onto the $\ell_{1,\infty}$ Ball; Application
to Sparse Autoencoders [12.010310883787911]
本稿では,$ell_1,infty$ norm ballに対する新しいプロジェクションアルゴリズムを提案する。
また,本手法が最高速であることは,生物学的ケースにおいても,一般の場合においても明らかである。
論文 参考訳（メタデータ） (2023-07-19T08:47:41Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Randomized and Deterministic Attention Sparsification Algorithms for
Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。
超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文 参考訳（メタデータ） (2023-04-10T05:52:38Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳（メタデータ） (2023-02-26T02:42:39Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。