論文の概要: One-step differentiation of iterative algorithms
- arxiv url: http://arxiv.org/abs/2305.13768v1
- Date: Tue, 23 May 2023 07:32:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 18:15:03.519819
- Title: One-step differentiation of iterative algorithms
- Title（参考訳）: 反復アルゴリズムの一段階微分
- Authors: J\'er\^ome Bolte, Edouard Pauwels, Samuel Vaiter
- Abstract要約: 本稿では, 自動微分法としての一段階微分法, あるいはジャコビアンフリーバックプロパゲーションについて検討する。
両レベル最適化の結果とともに, 具体例を用いた完全理論的近似解析を行う。
- 参考スコア（独自算出の注目度）: 7.9495796547433395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In appropriate frameworks, automatic differentiation is transparent to the
user at the cost of being a significant computational burden when the number of
operations is large. For iterative algorithms, implicit differentiation
alleviates this issue but requires custom implementation of Jacobian
evaluation. In this paper, we study one-step differentiation, also known as
Jacobian-free backpropagation, a method as easy as automatic differentiation
and as performant as implicit differentiation for fast algorithms (e.g.,
superlinear optimization methods). We provide a complete theoretical
approximation analysis with specific examples (Newton's method, gradient
descent) along with its consequences in bilevel optimization. Several numerical
examples illustrate the well-foundness of the one-step estimator.
- Abstract（参考訳）: 適切なフレームワークでは、操作数が大きければ計算量を大幅に負担するコストがかかるため、自動微分はユーザに透過的である。
反復アルゴリズムでは、暗黙の微分がこの問題を緩和するが、ジャコビアン評価のカスタム実装が必要である。
本稿では,高速アルゴリズム(超線形最適化法など)における一段階微分,すなわちジャコビアンフリーバックプロパゲーション,自動微分と同様に容易で,暗黙的微分としての性能について検討する。
両レベル最適化の結果とともに,特定の例(ニュートン法,勾配降下法)を用いた完全理論近似解析を行う。
いくつかの数値的な例は、ワンステップ推定器の確立性を示している。
関連論文リスト
- Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
本稿では,多レベル最適化のための新しい勾配に基づくアプローチを提案する。
本手法は解の精度と収束速度を両立させながら計算複雑性を著しく低減する。
私たちの知る限りでは、これは暗黙の微分の一般的なバージョンを提供する最初のアルゴリズムの1つである。
論文 参考訳（メタデータ） (2024-10-15T06:17:59Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳（メタデータ） (2022-09-27T09:27:29Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Efficient and Modular Implicit Differentiation [68.74748174316989]
最適化問題の暗黙的な微分のための統一的で効率的かつモジュール化されたアプローチを提案する。
一見単純な原理は、最近提案された多くの暗黙の微分法を復元し、新しいものを簡単に作成できることを示している。
論文 参考訳（メタデータ） (2021-05-31T17:45:58Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Super-efficiency of automatic differentiation for functions defined as a
minimum [16.02151272607889]
min-min最適化では、最小値として定義される関数の勾配を計算する必要がある。
本稿では,これらの推定器による誤差を最適化誤差の関数として検討する。
論文 参考訳（メタデータ） (2020-02-10T13:23:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。