論文の概要: Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization
- arxiv url: http://arxiv.org/abs/2107.03356v2
- Date: Thu, 8 Jul 2021 08:40:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-09 11:04:34.751647
- Title: Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization
- Title（参考訳）: 二階情報の効率的な行列フリー近似と刈り取りと最適化への応用
- Authors: Elias Frantar, Eldar Kurtic, Dan Alistarh
- Abstract要約: Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。
これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
- 参考スコア（独自算出の注目度）: 16.96639526117016
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Efficiently approximating local curvature information of the loss function is
a key tool for optimization and compression of deep neural networks. Yet, most
existing methods to approximate second-order information have high
computational or storage costs, which can limit their practicality. In this
work, we investigate matrix-free, linear-time approaches for estimating
Inverse-Hessian Vector Products (IHVPs) for the case when the Hessian can be
approximated as a sum of rank-one matrices, as in the classic approximation of
the Hessian by the empirical Fisher matrix. We propose two new algorithms as
part of a framework called M-FAC: the first algorithm is tailored towards
network compression and can compute the IHVP for dimension $d$, if the Hessian
is given as a sum of $m$ rank-one matrices, using $O(dm^2)$ precomputation,
$O(dm)$ cost for computing the IHVP, and query cost $O(m)$ for any single
element of the inverse Hessian. The second algorithm targets an optimization
setting, where we wish to compute the product between the inverse Hessian,
estimated over a sliding window of optimization steps, and a given gradient
direction, as required for preconditioned SGD. We give an algorithm with cost
$O(dm + m^2)$ for computing the IHVP and $O(dm + m^3)$ for adding or removing
any gradient from the sliding window. These two algorithms yield
state-of-the-art results for network pruning and optimization with lower
computational overhead relative to existing second-order methods.
Implementations are available at [10] and [18].
- Abstract（参考訳）: 損失関数の局所曲率情報を効率的に近似することは、ディープニューラルネットワークの最適化と圧縮の鍵となるツールである。
しかし、既存の2次情報を近似する手法の多くは計算コストやストレージコストが高く、実用性を制限できる。
本研究では,経験的フィッシャー行列によるヘッシアンの古典的な近似のように,ヘッシアンをランク1の行列の和として近似できる場合の逆ヘッシアンベクトル積(ihvps)を推定するための行列フリーな線形時間アプローチについて検討する。
M-FACと呼ばれるフレームワークの一部として、2つの新しいアルゴリズムを提案する: 最初のアルゴリズムはネットワーク圧縮に最適化され、逆 Hessian の任意の要素に対して$O(dm^2)$プリ計算、$O(dm)$計算、$O(dm)$クエリコスト$O(m)$で階数1の行列の和として与えられる場合、次元$d$で IHVPを計算できる。
第2のアルゴリズムは最適化設定を目標とし,最適化ステップのスライディングウィンドウ上で推定される逆ヘシアンと,事前条件付きSGDに必要な勾配方向との間の積の計算を行う。
IHVPの計算に$O(dm + m^2)$と$O(dm + m^3)$を、スライディングウィンドウから勾配を追加したり取り除いたりするためのアルゴリズムを与える。
これら2つのアルゴリズムは、既存の二階法に比べて計算オーバーヘッドの少ないネットワークプルーニングと最適化に最先端の結果をもたらす。
実装は[10]と[18]で利用可能です。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - AdaSub: Stochastic Optimization Using Second-Order Information in
Low-Dimensional Subspaces [0.0]
本稿では,低次元部分空間における2階情報に基づく探索方向の探索アルゴリズムであるAdaSubを紹介する。
一階法と比較して、二階法は収束特性が優れているが、繰り返しごとにヘッセン行列を計算する必要があるため、計算コストが過大になる。
予備的な数値結果から、AdaSubは所定の精度に達するのに必要なイテレーションの時間と回数で、一般的なイテレーションを超越していることが示される。
論文 参考訳（メタデータ） (2023-10-30T22:24:23Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Representing Additive Gaussian Processes by Sparse Matrices [18.618437338490487]
Mat'ern Gaussian Processes (GP) は、最も人気のあるスケーラブルな高次元問題の一つである。
バックフィッティングアルゴリズムは、後進平均の計算時間の複雑さを$O(n3)$から$O(nlog n)$ timeに減らすことができる。
後方分散と最大対数類似度を効率的に計算するためにこれらのアルゴリズムを一般化することは、未解決の問題である。
論文 参考訳（メタデータ） (2023-04-29T18:53:42Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - 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 Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳（メタデータ） (2022-04-14T19:56:36Z) - 2nd-order Updates with 1st-order Complexity [0.0]
関数の2次情報を効率よく計算し(f$)、数値近似を支援することが長年の目標であった。
ここでは、基礎物理学と数値近似のみを用いて、そのような情報を$cal O(N)$ complexityのコストで正確に得る方法を示す。
論文 参考訳（メタデータ） (2021-05-24T17:47:51Z) - Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。
実験ではハッチンソン法を著しく上回る結果を得た。
論文 参考訳（メタデータ） (2020-10-19T16:45:37Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。