論文の概要: Debiasing a First-order Heuristic for Approximate Bi-level Optimization
- arxiv url: http://arxiv.org/abs/2106.02487v1
- Date: Fri, 4 Jun 2021 13:46:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-07 14:57:11.847887
- Title: Debiasing a First-order Heuristic for Approximate Bi-level Optimization
- Title(参考訳): 近似バイレベル最適化のための1次ヒューリスティックのデバイアス
- Authors: Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared
Davis, Adrian Weller
- Abstract要約: 近似バイレベル最適化(ABLO)は、数値的な(インナーレベルの)最適化ループを含む(外部レベルの)最適化問題からなる。
FOMの収束性に関する理論的理解の欠如がある。
本稿では,メモリの複雑さを一定に保った非バイアスなFOMを$r$の関数として提案する。
- 参考スコア(独自算出の注目度): 38.068090269482425
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Approximate bi-level optimization (ABLO) consists of (outer-level)
optimization problems, involving numerical (inner-level) optimization loops.
While ABLO has many applications across deep learning, it suffers from time and
memory complexity proportional to the length $r$ of its inner optimization
loop. To address this complexity, an earlier first-order method (FOM) was
proposed as a heuristic that omits second derivative terms, yielding
significant speed gains and requiring only constant memory. Despite FOM's
popularity, there is a lack of theoretical understanding of its convergence
properties. We contribute by theoretically characterizing FOM's gradient bias
under mild assumptions. We further demonstrate a rich family of examples where
FOM-based SGD does not converge to a stationary point of the ABLO objective. We
address this concern by proposing an unbiased FOM (UFOM) enjoying constant
memory complexity as a function of $r$. We characterize the introduced
time-variance tradeoff, demonstrate convergence bounds, and find an optimal
UFOM for a given ABLO problem. Finally, we propose an efficient adaptive UFOM
scheme.
- Abstract(参考訳): 近似二レベル最適化(ablo)は、数値(インナーレベル)最適化ループを含む(外部レベル)最適化問題からなる。
ABLOはディープラーニングにまたがる多くのアプリケーションを持っているが、時間とメモリの複雑さは内部最適化ループの$r$に比例する。
この複雑さに対処するため、初期の1次法(FOM)は2次微分項を省略し、大きな速度ゲインをもたらし、メモリを一定に保つヒューリスティックとして提案された。
FOMの人気にもかかわらず、収束性に関する理論的理解が欠けている。
我々は,FOMの勾配バイアスを軽度仮定の下で理論的に特徴づけることにより寄与する。
さらに、FOMをベースとしたSGDがABLO目標の定常点に収束しないような、豊富な例の族を示す。
この懸念に対処するために、不偏のFOM(UFOM)を$r$の関数として一定のメモリ複雑性を享受することを提案する。
導入した時間分散トレードオフを特徴付け、収束境界を示し、与えられたABLO問題に対して最適なUFOMを求める。
最後に,効率的な適応ufomスキームを提案する。
関連論文リスト
- Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed
Smoothness Conditions [9.518010235273785]
両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。
我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
論文 参考訳(メタデータ) (2023-06-21T07:32:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - 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) - Global convergence of optimized adaptive importance samplers [0.0]
我々は,モンテカルロを一般提案と統合するために最適化された適応的重要度サンプリング器 (OAIS) を解析した。
我々は、提案に対する$chi2$-divergenceの大域的勾配に対する漸近的境界を導出する。
論文 参考訳(メタデータ) (2022-01-02T19:56:36Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳(メタデータ) (2021-07-06T21:59:49Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Approximate Inference for Spectral Mixture Kernel [25.087829816206813]
スペクトル混合核に対する近似ベイズ推定を提案する。
抽出されたエビデンス下界(ELBO)推定器にサンプリングベース変分推定を適用することにより,変分パラメータを最適化する。
提案した推論と2つの戦略が組み合わさってパラメータの収束を加速し、より良いパラメータをもたらす。
論文 参考訳(メタデータ) (2020-06-12T09:39:29Z) - 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) - UFO-BLO: Unbiased First-Order Bilevel Optimization [42.49533978193117]
我々は,この収束を理論的に保証できる,新しいFOBLOに基づく外層勾配の非バイアス推定法を提案する。
この結果はOmniglotとMini-ImageNet,人気の数ショットメタラーニングベンチマークの実験結果によって裏付けられている。
論文 参考訳(メタデータ) (2020-06-05T18:53:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。