論文の概要: Adaptive Mirror Descent Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2311.04520v1
- Date: Wed, 8 Nov 2023 08:17:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-09 16:40:03.364966
- Title: Adaptive Mirror Descent Bilevel Optimization
- Title（参考訳）: 適応ミラー降下二レベル最適化
- Authors: Feihu Huang
- Abstract要約: 非二段階最適化のためのミラー降下に基づく適応的二段階最適化手法のクラスを提案する。
いくつかの条件下でメソッドを解析し、メソッドが高速なイテレーション数を持つことを証明します。
- 参考スコア（独自算出の注目度）: 25.438298531555468
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In the paper, we propose a class of efficient adaptive bilevel methods based
on mirror descent for nonconvex bilevel optimization, where its upper-level
problem is nonconvex possibly with nonsmooth regularization, and its
lower-level problem is also nonconvex while satisfies Polyak-{\L}ojasiewicz
(PL) condition. To solve these deterministic bilevel problems, we present an
efficient adaptive projection-aid gradient (i.e., AdaPAG) method based on
mirror descent, and prove that it obtains the best known gradient complexity of
$O(\epsilon^{-1})$ for finding an $\epsilon$-stationary solution of nonconvex
bilevel problems. To solve these stochastic bilevel problems, we propose an
efficient adaptive stochastic projection-aid gradient (i.e., AdaVSPAG) methods
based on mirror descent and variance-reduced techniques, and prove that it
obtains the best known gradient complexity of $O(\epsilon^{-3/2})$ for finding
an $\epsilon$-stationary solution. Since the PL condition relaxes the strongly
convex, our algorithms can be used to nonconvex strongly-convex bilevel
optimization. Theoretically, we provide a useful convergence analysis framework
for our methods under some mild conditions, and prove that our methods have a
fast convergence rate of $O(\frac{1}{T})$, where $T$ denotes the number of
iterations.
- Abstract（参考訳）: 本稿では,非凸二レベル最適化のミラー降下に基づく効率的な適応的二レベル手法のクラスを提案し,その上層問題は非滑らかな正規化を伴う可能性があり,下層問題もまた非凸であり,Polyak-{\L}ojasiewicz (PL) 条件を満たす。
これらの決定論的双レベル問題を解くために、鏡面降下に基づく効率的な適応射影支援勾配(AdaPAG)法を提案し、非凸双レベル問題の$\epsilon$-stationary解を求めるために$O(\epsilon^{-1})$の最もよく知られた勾配複雑性を求める。
これらの確率的双レベル問題を解決するために,鏡面降下法と分散還元法に基づく適応確率的射影支援勾配(AdaVSPAG)法を提案し,$O(\epsilon^{-3/2})$を$\epsilon$-stationary解を求めるために最もよく知られた勾配複雑性を求める。
PL条件は強凸を緩和するので、我々のアルゴリズムは強凸二値最適化に利用できる。
理論的には、いくつかの穏やかな条件下での方法に対して有用な収束解析フレームワークを提供し、この手法がより高速な収束率である $o(\frac{1}{t})$ を示し、ここで$t$ は反復数を表す。
関連論文リスト
- Optimal Hessian/Jacobian-Free Nonconvex-PL Bilevel Optimization [25.438298531555468]
双レベル最適化は、ハイパーラーニング、メタラーニング、強化ラーニングなど、多くの機械学習タスクに広く適用されている。
最適収束$frac1TT(Hessian/BiO法)を軽度条件下で提案する。
バイレベルゲーム超定常数値収束に関するいくつかの実験を行う。
論文 参考訳（メタデータ） (2024-07-25T07:25:06Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳（メタデータ） (2023-06-04T17:54:11Z) - On Momentum-Based Gradient Methods for Bilevel Optimization with
Nonconvex Lower-Level [25.438298531555468]
バイレベル最適化は機械学習タスクで一般的なプロセスである。
本稿では,両レベルPLゲームにおける非表現問題について検討する。
我々は,既存の最良の結果を$tO(Enabla F(x)leq epsilon$)の係数で改善することを示す。
論文 参考訳（メタデータ） (2023-03-07T14:55:05Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。