論文の概要: 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完全問題であり、小さな正方形を持つ平面の被覆点を含む幾何学的問題によってブール満足度から減少することを示した。 これらの結果は、ニューラルネットワークの複雑さを測定することの計算複雑性を強調し、この方向への将来の理論的かつ実証的な研究の基礎を築いた。

関連論文リスト

• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。 このような問題は医学、物理学、機械学習で発生する。 両種類の雑音下で提案アルゴリズムの収束保証を行う。
  論文  参考訳（メタデータ） (2024-11-21T10:26:17Z)
• Trainability Barriers in Low-Depth QAOA Landscapes [0.0]
  QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための変分量子アルゴリズムである。 以前の結果から、小さなパラメータの固定数の解析性能が保証された。 本研究は,近年の数値研究の焦点である中間体制における訓練の難しさについて考察する。
  論文  参考訳（メタデータ） (2024-02-15T18:45:30Z)
• How Free is Parameter-Free Stochastic Optimization? [29.174036532175855]
  パラメータフリー最適化の問題について検討し、パラメータフリーな手法が存在するかどうかを問う。 既存の手法は、真の問題パラメータに関するいくつかの非自明な知識を必要とするため、部分的にはパラメータフリーとみなすことができる。 単純なハイパーサーチ手法により、より洗練された最先端アルゴリズムより優れたパラメータフリーな手法が実現できることを実証する。
  論文  参考訳（メタデータ） (2024-02-05T15:51:49Z)
• Parameter-Agnostic Optimization under Relaxed Smoothness [25.608968462899316]
  本研究では,モメンタムを用いた正規化グラディエントDescence (NSGD-M) が,問題パラメータの事前知識を必要とせずに,速度-最適の複雑性を実現できることを示す。 決定論的設定では、指数係数は、バックトラックラインサーチによるグラディエント・ディクスト(Gradient Descent)を用いることで、中和することができる。
  論文  参考訳（メタデータ） (2023-11-06T16:39:53Z)
• Online Continuous Hyperparameter Optimization for Generalized Linear Contextual Bandits [55.03293214439741]
  文脈的包帯では、エージェントは過去の経験に基づいた時間依存アクションセットから順次アクションを行う。 そこで本稿では,文脈的包帯のためのオンライン連続型ハイパーパラメータチューニングフレームワークを提案する。 理論上はサブ線形の後悔を達成でき、合成データと実データの両方において既存のすべての手法よりも一貫して優れた性能を発揮することを示す。
  論文  参考訳（メタデータ） (2023-02-18T23:31:20Z)
• A relaxed proximal gradient descent algorithm for convergent plug-and-play with proximal denoiser [6.2484576862659065]
  本稿では,新しいコンバーゼントなPlug-and-fidelity Descent (Play)アルゴリズムを提案する。 このアルゴリズムは、より広い範囲の通常の凸化パラメータに収束し、画像のより正確な復元を可能にする。
  論文  参考訳（メタデータ） (2023-01-31T16:11:47Z)
• Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
  パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。 そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。 後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
  論文  参考訳（メタデータ） (2022-03-19T13:39:49Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。 非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
  論文  参考訳（メタデータ） (2020-01-15T16:11:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。