論文の概要: On the Iteration Complexity of Hypergradient Computation

• arxiv url: http://arxiv.org/abs/2006.16218v2
• Date: Fri, 10 Jul 2020 17:28:22 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-15 13:55:42.094490
• Title: On the Iteration Complexity of Hypergradient Computation
• Title（参考訳）: 超勾配計算の反復複雑性について
• Authors: Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, Saverio Salzo
• Abstract要約: 機械学習では、上層目標(過度)の勾配は、正確に計算するのは難しいか、あるいは不可能である。 逆モード反復微分と近似的暗黙的微分に基づく過次微分を計算するための一般的なアプローチについて検討する。 この分析は, 共役勾配に基づく近似的暗黙差を最良とする, 上記の手法の計算効率の階層性を示す。
• 参考スコア（独自算出の注目度）: 38.409444179509705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a general class of bilevel problems, consisting in the minimization of an upper-level objective which depends on the solution to a parametric fixed-point equation. Important instances arising in machine learning include hyperparameter optimization, meta-learning, and certain graph and recurrent neural networks. Typically the gradient of the upper-level objective (hypergradient) is hard or even impossible to compute exactly, which has raised the interest in approximation methods. We investigate some popular approaches to compute the hypergradient, based on reverse mode iterative differentiation and approximate implicit differentiation. Under the hypothesis that the fixed point equation is defined by a contraction mapping, we present a unified analysis which allows for the first time to quantitatively compare these methods, providing explicit bounds for their iteration complexity. This analysis suggests a hierarchy in terms of computational efficiency among the above methods, with approximate implicit differentiation based on conjugate gradient performing best. We present an extensive experimental comparison among the methods which confirm the theoretical findings.
• Abstract（参考訳）: パラメトリック不動点方程式の解に依存する上層目標の最小化から成り立つ2段階問題の一般的なクラスについて検討する。 機械学習で発生する重要なインスタンスには、ハイパーパラメータ最適化、メタラーニング、特定のグラフとリカレントニューラルネットワークがある。 通常、上層の目標(高度)の勾配は正確に計算することは困難か不可能であり、近似法への関心が高まっている。 逆モード反復微分と近似的暗黙的微分に基づく過次微分を計算するための一般的なアプローチについて検討する。 固定点方程式は縮尺写像によって定義されるという仮説の下で、これらの手法を定量的に比較し、その反復複雑性に対して明示的な境界を与える統一解析を提案する。 この分析は, 共役勾配に基づく近似的暗黙差を最良とする, 上記の手法の計算効率の階層性を示す。 本研究は, 理論的な知見を裏付ける方法の広範囲な実験比較を行う。

関連論文リスト

• Stochastic Gradient Descent for Gaussian Processes Done Right [86.83678041846971]
  emphdone right -- 最適化とカーネルコミュニティからの具体的な洞察を使用するという意味で -- が、勾配降下は非常に効果的であることを示している。 本稿では,直感的に設計を記述し,設計選択について説明する。 本手法は,分子結合親和性予測のための最先端グラフニューラルネットワークと同程度にガウス過程の回帰を配置する。
  論文  参考訳（メタデータ） (2023-10-31T16:15:13Z)
• Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
  そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。 我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。 本実験は, 勾配法よりも近似分散還元法の利点を実証する。
  論文  参考訳（メタデータ） (2023-08-18T05:11:50Z)
• Analyzing Inexact Hypergradients for Bilevel Learning [0.09669369645900441]
  暗黙の関数定理と自動微分/バックプロパゲーションに基づいて既存の手法を一般化する過次計算のための統一的なフレームワークを提案する。 計算結果から,高次アルゴリズムの選択は低次解法の選択と同等に重要であることが明らかとなった。
  論文  参考訳（メタデータ） (2023-01-11T23:54:27Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。 分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
  論文  参考訳（メタデータ） (2022-02-28T13:01:04Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Convergence Properties of Stochastic Hypergradients [38.64355126221992]
  大規模データセットにおける低レベルの問題が経験的リスクである場合に重要となる過勾配の近似スキームについて検討する。 本研究では,理論解析を支援する数値実験を行い,実際にハイパーグラディエントを用いることの利点を示す。
  論文  参考訳（メタデータ） (2020-11-13T20:50:36Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。 我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。 一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-23T20:02:00Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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