論文の概要: Second-Order Sensitivity Analysis for Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2205.02329v1
- Date: Wed, 4 May 2022 21:16:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-07 09:31:08.384280
- Title: Second-Order Sensitivity Analysis for Bilevel Optimization
- Title（参考訳）: バイレベル最適化のための2次感度解析
- Authors: Robert Dyro, Edward Schmerling, Nikos Arechiga, Marco Pavone
- Abstract要約: 感度解析を拡張し、より低い問題の2階微分情報を提供する。
我々は、IFT勾配を生成するために既に使われている計算の多くが、IFTヘッセンのために再利用可能であることを示す。
- 参考スコア（独自算出の注目度）: 26.17470185675129
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work we derive a second-order approach to bilevel optimization, a
type of mathematical programming in which the solution to a parameterized
optimization problem (the "lower" problem) is itself to be optimized (in the
"upper" problem) as a function of the parameters. Many existing approaches to
bilevel optimization employ first-order sensitivity analysis, based on the
implicit function theorem (IFT), for the lower problem to derive a gradient of
the lower problem solution with respect to its parameters; this IFT gradient is
then used in a first-order optimization method for the upper problem. This
paper extends this sensitivity analysis to provide second-order derivative
information of the lower problem (which we call the IFT Hessian), enabling the
usage of faster-converging second-order optimization methods at the upper
level. Our analysis shows that (i) much of the computation already used to
produce the IFT gradient can be reused for the IFT Hessian, (ii) errors bounds
derived for the IFT gradient readily apply to the IFT Hessian, (iii) computing
IFT Hessians can significantly reduce overall computation by extracting more
information from each lower level solve. We corroborate our findings and
demonstrate the broad range of applications of our method by applying it to
problem instances of least squares hyperparameter auto-tuning, multi-class SVM
auto-tuning, and inverse optimal control.
- Abstract（参考訳）: 本研究では、パラメータ化最適化問題("より低い"問題)に対する解が、パラメータの関数として("上"問題において)最適化される数学的プログラミングの一種である、二階最適化に対する二階最適化のアプローチを導出する。
従来の2段階最適化手法の多くは、暗黙の関数定理(IFT)に基づく1次感度解析を用いており、下位問題のパラメータに対する下位問題の解の勾配を導出する。
本稿では,この感度解析を拡張し,下層問題(ift hessian と呼ぶ)の2次微分情報を提供し,上位層での高速収束2次最適化手法の利用を可能にした。
私たちの分析は
i) IFT勾配を生成するために既に使われている計算の多くは、IFTヘッセンのために再利用することができる。
(ii)IFT勾配から導出される誤差境界はIFTヘッセンにも容易に適用できる。
3) IFTヘシアン計算は, 各下層解からより多くの情報を抽出することにより, 全体計算を大幅に削減することができる。
我々は,最小2乗超パラメータオートチューニング,マルチクラスSVMオートチューニング,逆最適制御といった問題事例に適用し,本手法の幅広い応用を実証する。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - Enhancing Hypergradients Estimation: A Study of Preconditioning and
Reparameterization [49.73341101297818]
双レベル最適化は、内部最適化問題の解に依存する外的目的関数を最適化することを目的としている。
外部問題の過次性を計算する従来の方法は、Implicit Function Theorem (IFT) を使うことである。
IFT法の誤差について検討し,この誤差を低減するための2つの手法を解析した。
論文 参考訳（メタデータ） (2024-02-26T17:09:18Z) - Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions [9.518010235273785]
両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。
我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
論文 参考訳（メタデータ） (2023-06-21T07:32:29Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。
本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。
ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
論文 参考訳（メタデータ） (2022-12-28T18:57:46Z) - Versatile Single-Loop Method for Gradient Estimator: First and Second
Order Optimality, and its Application to Federated Learning [45.78238792836363]
本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。
既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
論文 参考訳（メタデータ） (2022-09-01T11:05:26Z) - A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and
Nonsmooth Bi-level Optimization [26.68351521813062]
既存のバイレベルアルゴリズムは、非滑らかまたは超滑らかな正規化器を扱えない。
本稿では,包括的機械学習アプリケーションを高速化するために,暗黙差分法(AID)が有効であることを示す。
論文 参考訳（メタデータ） (2022-03-30T18:53:04Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - A Primer on Zeroth-Order Optimization in Signal Processing and Machine
Learning [95.85269649177336]
ZO最適化は、勾配推定、降下方向、ソリューション更新の3つの主要なステップを反復的に実行する。
我々は,ブラックボックス深層学習モデルによる説明文の評価や生成,効率的なオンラインセンサ管理など,ZO最適化の有望な応用を実証する。
論文 参考訳（メタデータ） (2020-06-11T06:50:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。