論文の概要: Computational Complexity of Detecting Proximity to Losslessly
Compressible Neural Network Parameters
- arxiv url: http://arxiv.org/abs/2306.02834v1
- Date: Mon, 5 Jun 2023 12:29:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 15:12:06.753039
- Title: Computational Complexity of Detecting Proximity to Losslessly
Compressible Neural Network Parameters
- Title(参考訳): ロスレス圧縮性ニューラルネットワークパラメータの近接検出の計算複雑性
- Authors: Matthew Farrugia-Roberts (The University of Melbourne)
- Abstract要約: 単層双曲型タンジェントネットワークの設定において、最適ロスレス圧縮のための効率的な公式アルゴリズムを提案する。
近似ランクの有界化はNP完全問題であることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To better understand complexity in neural networks, we theoretically
investigate the idealised phenomenon of lossless network compressibility,
whereby an identical function can be implemented with a smaller network. We
give an efficient formal algorithm for optimal lossless compression in the
setting of single-hidden-layer hyperbolic tangent networks. To measure lossless
compressibility, we define the rank of a parameter as the minimum number of
hidden units required to implement the same function. Losslessly compressible
parameters are atypical, but their existence has implications for nearby
parameters. We define the proximate rank of a parameter as the rank of the most
compressible parameter within a small $L^\infty$ neighbourhood. Unfortunately,
detecting nearby losslessly compressible parameters is not so easy: we show
that bounding the proximate rank is an NP-complete problem, using a reduction
from Boolean satisfiability via a geometric problem involving covering points
in the plane with small squares. These results underscore the computational
complexity of measuring neural network complexity, laying a foundation for
future theoretical and empirical work in this direction.
- Abstract(参考訳): ニューラルネットワークの複雑性をよりよく理解するために、損失のないネットワーク圧縮の理想的な現象を理論的に検討し、より小さなネットワークで同じ機能を実装できる。
単層双曲型ネットワークの設定において、最適ロスレス圧縮のための効率的な形式的アルゴリズムを与える。
損失のない圧縮性を測定するために、パラメータのランクを同じ関数を実装するのに必要な隠れ単位の最小数と定義する。
ロスレス圧縮可能なパラメータは非典型的であるが、その存在は近隣のパラメータに影響を及ぼす。
パラメータの近位階を、小さな$l^\infty$近傍における最も圧縮可能なパラメータのランクとして定義する。
残念なことに、近傍の非圧縮的パラメータの検出はそれほど簡単ではない: 近似ランクの有界化はNP完全問題であり、小さな正方形を持つ平面の被覆点を含む幾何学的問題によってブール満足度から減少することを示した。
これらの結果は、ニューラルネットワークの複雑さを測定することの計算複雑性を強調し、この方向への将来の理論的かつ実証的な研究の基礎を築いた。
関連論文リスト
- Compression of Structured Data with Autoencoders: Provable Benefit of
Nonlinearities and Depth [83.15263499262824]
勾配勾配勾配は入力のスパース構造を完全に無視する解に収束することを示す。
浅層構造にデノナイジング関数を付加することにより,スパースデータの圧縮におけるガウス性能の改善方法を示す。
CIFAR-10 や MNIST などの画像データセットに対して,本研究の成果を検証した。
論文 参考訳(メタデータ) (2024-02-07T16:32:29Z) - The Implicit Bias of Minima Stability in Multivariate Shallow ReLU
Networks [53.95175206863992]
本研究では,2次損失を持つ1層多変量ReLUネットワークをトレーニングする際に,勾配勾配勾配が収束する解のタイプについて検討する。
我々は、浅いReLUネットワークが普遍近似器であるにもかかわらず、安定した浅層ネットワークは存在しないことを証明した。
論文 参考訳(メタデータ) (2023-06-30T09:17:39Z) - On Model Compression for Neural Networks: Framework, Algorithm, and
Convergence Guarantee [10.783153208561469]
本稿では,低ランク近似と重み近似の2つのモデル圧縮手法に焦点を当てた。
本稿では,非最適化の新たな視点から,モデル圧縮のための全体論的なフレームワークを提案する。
論文 参考訳(メタデータ) (2023-03-13T02:14:42Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - The (Un)Scalability of Heuristic Approximators for NP-Hard Search
Problems [25.641418039598587]
A*アルゴリズムはNP-ハード最適化問題の解法として一般的に用いられる。
このような問題の多くに対する正確な近似もNPハードであることを示す。
論文 参考訳(メタデータ) (2022-09-07T18:02:02Z) - A Theoretical Understanding of Neural Network Compression from Sparse
Linear Approximation [37.525277809849776]
モデル圧縮の目標は、同等のパフォーマンスを維持しながら、大きなニューラルネットワークのサイズを減らすことだ。
圧縮性を特徴付けるためにスペーサ感度$ell_q$-normを使用し、ネットワーク内の重みの柔らかいスペーサと圧縮度の関係を提供する。
また,ネットワーク上で各ニューロンを切断する適応アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-11T20:10:35Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳(メタデータ) (2021-07-28T04:28:55Z) - Compressing Neural Networks: Towards Determining the Optimal Layer-wise
Decomposition [62.41259783906452]
本稿では,ディープニューラルネットワークのための新しいグローバル圧縮フレームワークを提案する。
各層を自動的に解析し、最適な層間圧縮比を特定する。
我々の結果は、現代のニューラルネットワークのグローバルなパフォーマンス-サイズトレードオフに関する将来の研究のための新たな道を開く。
論文 参考訳(メタデータ) (2021-07-23T20:01:30Z) - Achieving Small Test Error in Mildly Overparameterized Neural Networks [30.664282759625948]
時間内にこれらの点の1つを見つけるアルゴリズムを示す。
さらに、我々は、完全に接続されたニューラルネットワークのために、データ分布に追加の仮定で、時間アルゴリズムがあることを証明します。
論文 参考訳(メタデータ) (2021-04-24T06:47:20Z) - Random Vector Functional Link Networks for Function Approximation on Manifolds [8.535815777849786]
ランダムな入力-隠蔽層重みとバイアスを持つ単一層ニューラルネットが実際に成功していることを示す。
さらに、このランダム化されたニューラルネットワークアーキテクチャをユークリッド空間の滑らかでコンパクトな部分多様体上の近似関数に適用する。
論文 参考訳(メタデータ) (2020-07-30T23:50:44Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳(メタデータ) (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。