論文の概要: Near-Linear Time Projection onto the $\ell_{1,\infty}$ Ball; Application
to Sparse Autoencoders
- arxiv url: http://arxiv.org/abs/2307.09836v1
- Date: Wed, 19 Jul 2023 08:47:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-20 14:47:26.077086
- Title: Near-Linear Time Projection onto the $\ell_{1,\infty}$ Ball; Application
to Sparse Autoencoders
- Title（参考訳）: $\ell_{1,\infty}$ Ball 上の準線形時間射影 : スパースオートエンコーダへの応用
- Authors: Guillaume Perez and Laurent Condat and Michel Barlaud
- Abstract要約: 本稿では,$ell_1,infty$ norm ballに対する新しいプロジェクションアルゴリズムを提案する。
また,本手法が最高速であることは,生物学的ケースにおいても,一般の場合においても明らかである。
- 参考スコア（独自算出の注目度）: 12.010310883787911
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Looking for sparsity is nowadays crucial to speed up the training of
large-scale neural networks. Projections onto the $\ell_{1,2}$ and
$\ell_{1,\infty}$ are among the most efficient techniques to sparsify and
reduce the overall cost of neural networks. In this paper, we introduce a new
projection algorithm for the $\ell_{1,\infty}$ norm ball. The worst-case time
complexity of this algorithm is $\mathcal{O}\big(nm+J\log(nm)\big)$ for a
matrix in $\mathbb{R}^{n\times m}$. $J$ is a term that tends to 0 when the
sparsity is high, and to $nm$ when the sparsity is low. Its implementation is
easy and it is guaranteed to converge to the exact solution in a finite time.
Moreover, we propose to incorporate the $\ell_{1,\infty}$ ball projection while
training an autoencoder to enforce feature selection and sparsity of the
weights. Sparsification appears in the encoder to primarily do feature
selection due to our application in biology, where only a very small part
($<2\%$) of the data is relevant. We show that both in the biological case and
in the general case of sparsity that our method is the fastest.
- Abstract（参考訳）: 大規模なニューラルネットワークのトレーニングをスピードアップするためには、スパシティを探すことが重要なのです。
$\ell_{1,2}$ と $\ell_{1,\infty}$ の投射は、ニューラルネットワーク全体のコストを軽減し、削減するための最も効率的な技術の一つである。
本稿では,$\ell_{1,\infty}$標準球に対する新しい射影アルゴリズムを提案する。
このアルゴリズムの最悪の時間は、$\mathcal{O}\big(nm+J\log(nm)\big)$ for a matrix in $\mathbb{R}^{n\times m}$である。
J$ は、空間が高ければ 0 になり、空間が低ければ $nm$ になるような用語である。
その実装は簡単であり、有限時間で正確な解に収束することが保証される。
さらに,重みの特徴選択と疎度を強制するオートエンコーダを訓練しながら,$\ell_{1,\infty}$ボールプロジェクションを導入することを提案する。
エンコーダでは、データのごく一部(<2\%$)しか関係しない、生物学における我々の応用により、主に特徴選択を行うためにスパーシフィケーションが現れる。
また,本手法が最高速であることは,生物学的ケースにおいても,一般の場合においても明らかである。
関連論文リスト
- 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) - 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) - A Smoothing Algorithm for l1 Support Vector Machines [0.07499722271664144]
ソフトマージン支援ベクトルマシン(SVM)最適化問題を$ell1$ペナルティで解くためのスムーシングアルゴリズムを提案する。
このアルゴリズムはヒンジロス関数のスムース化と$ell1$ペナルティのアクティブなセットアプローチを使用する。
実験により,本アルゴリズムはトレーニング速度を犠牲にすることなく,試験精度を向上できることが示された。
論文 参考訳（メタデータ） (2023-12-17T00:54:56Z) - Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳（メタデータ） (2023-10-30T19:52:43Z) - 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) - Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces [2.7195102129095003]
ReLU活性化関数を持つディープニューラルネットワークは、ソボレフ空間$Ws(L_q(Omega))$とBesov空間$Bs_r(L_q(Omega))$の関数を近似することができる。
この問題は、様々な分野におけるニューラルネットワークの適用を研究する際に重要である。
論文 参考訳（メタデータ） (2022-11-25T23:32:26Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Training (Overparametrized) Neural Networks in Near-Linear Time [21.616949485102342]
本稿では,ReparamLUネットワークをトレーニングするための[CGH+1]アルゴリズムの高速化について述べる。
我々のアルゴリズムの中心はガウスニュートンを$ell$-reconditionとして再構成することである。
論文 参考訳（メタデータ） (2020-06-20T20:26:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。