論文の概要: Amortized Implicit Differentiation for Stochastic Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2111.14580v2
- Date: Tue, 30 Nov 2021 04:43:47 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-01 11:46:17.722360
- Title: Amortized Implicit Differentiation for Stochastic Bilevel Optimization
- Title（参考訳）: 確率的二値最適化のための暗黙差分法
- Authors: Michael Arbel and Julien Mairal
- Abstract要約: 決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
- 参考スコア（独自算出の注目度）: 53.12363770169761
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a class of algorithms for solving bilevel optimization problems in
both stochastic and deterministic settings when the inner-level objective is
strongly convex. Specifically, we consider algorithms based on inexact implicit
differentiation and we exploit a warm-start strategy to amortize the estimation
of the exact gradient. We then introduce a unified theoretical framework
inspired by the study of singularly perturbed systems (Habets, 1974) to analyze
such amortized algorithms. By using this framework, our analysis shows these
algorithms to match the computational complexity of oracle methods that have
access to an unbiased estimate of the gradient, thus outperforming many
existing results for bilevel optimization. We illustrate these findings on
synthetic experiments and demonstrate the efficiency of these algorithms on
hyper-parameter optimization experiments involving several thousands of
variables.
- Abstract（参考訳）: 本研究では,内部レベルの目標が強凸である場合,確率的および決定論的設定の両方において,二階最適化問題を解決するアルゴリズムのクラスについて検討する。
具体的には, 暗黙的微分に基づくアルゴリズムを考察し, 正確な勾配の推定を償却するためにウォームスタート戦略を利用する。
次に,特異摂動系(habets, 1974)の研究に触発された統一的理論的枠組みを導入し,そのような不定形化アルゴリズムを解析した。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセスできるオラクルメソッドの計算複雑性と一致し、2段階最適化のための既存の多くの結果より優れていることを示す。
これらの結果を合成実験で示し,数千変数を含む超パラメータ最適化実験におけるアルゴリズムの有効性を実証する。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Towards Differentiable Multilevel Optimization: A Gradient-Based Approach [1.6114012813668932]
本稿では,多レベル最適化のための新しい勾配に基づくアプローチを提案する。
本手法は解の精度と収束速度を両立させながら計算複雑性を著しく低減する。
私たちの知る限りでは、これは暗黙の微分の一般的なバージョンを提供する最初のアルゴリズムの1つである。
論文 参考訳（メタデータ） (2024-10-15T06:17:59Z) - One-step differentiation of iterative algorithms [7.9495796547433395]
本稿では, 自動微分法としての一段階微分法, あるいはジャコビアンフリーバックプロパゲーションについて検討する。
両レベル最適化の結果とともに, 具体例を用いた完全理論的近似解析を行う。
論文 参考訳（メタデータ） (2023-05-23T07:32:37Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-07-31T22:05:47Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。