論文の概要: First-order penalty methods for bilevel optimization
- arxiv url: http://arxiv.org/abs/2301.01716v2
- Date: Thu, 7 Mar 2024 15:42:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-08 18:37:00.160283
- Title: First-order penalty methods for bilevel optimization
- Title（参考訳）: 2レベル最適化のための1次ペナルティ法
- Authors: Zhaosong Lu and Sanyou Mei
- Abstract要約: 制約のない二段階最適化問題に対して、$varepsilon$ complexity Solutionのクラスを示す。
また,制約のない二段階問題に対して,$epsilon$KKTの解を求める一次ペナルティ法を提案する。
- 参考スコア（独自算出の注目度）: 1.2691047660244337
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study a class of unconstrained and constrained bilevel
optimization problems in which the lower level is a possibly nonsmooth convex
optimization problem, while the upper level is a possibly nonconvex
optimization problem. We introduce a notion of $\varepsilon$-KKT solution for
them and show that an $\varepsilon$-KKT solution leads to an
$O(\sqrt{\varepsilon})$- or $O(\varepsilon)$-hypergradient based stionary point
under suitable assumptions. We also propose first-order penalty methods for
finding an $\varepsilon$-KKT solution of them, whose subproblems turn out to be
a structured minimax problem and can be suitably solved by a first-order method
recently developed by the authors. Under suitable assumptions, an
\emph{operation complexity} of $O(\varepsilon^{-4}\log\varepsilon^{-1})$ and
$O(\varepsilon^{-7}\log\varepsilon^{-1})$, measured by their fundamental
operations, is established for the proposed penalty methods for finding an
$\varepsilon$-KKT solution of the unconstrained and constrained bilevel
optimization problems, respectively. Preliminary numerical results are
presented to illustrate the performance of our proposed methods. To the best of
our knowledge, this paper is the first work to demonstrate that bilevel
optimization can be approximately solved as minimax optimization, and moreover,
it provides the first implementable method with complexity guarantees for such
sophisticated bilevel optimization.
- Abstract（参考訳）: 本稿では,下層が非滑らかな凸最適化問題であり,上層が非凸最適化問題であるような,制約のない二段階最適化問題のクラスについて検討する。
我々は,これらに対して$\varepsilon$-kkt の解の概念を導入し,$\varepsilon$-kkt の解が適切な仮定の下で $o(\sqrt{\varepsilon})$- または $o(\varepsilon)$-hypergradient based stionary point となることを示す。
また,そのサブプロブレムが構造化されたミニマックス問題となり,著者らによって最近開発された一階法で適切に解けるような,$\varepsilon$-KKTの解を求める一階法を提案する。
適切な仮定の下では、その基本演算によって測定された$O(\varepsilon^{-4}\log\varepsilon^{-1})$と$O(\varepsilon^{-7}\log\varepsilon^{-1})$の \emph{operation complexity} が、制約のない二段階最適化問題の$\varepsilon$-KTソリューションを見つけるための提案されたペナルティ法に対して確立される。
提案手法の性能を示すための予備的な数値結果を示す。
本稿では,この2レベル最適化をミニマックス最適化として大まかに解くことができることを示す最初の研究であり,さらに,このような洗練された2レベル最適化の複雑性を保証する,最初の実装可能な手法を提供する。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。
また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文 参考訳（メタデータ） (2023-06-30T20:36:44Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - Optimal Stochastic Non-smooth Non-convex Optimization through
Online-to-Non-convex Conversion [56.92236659731376]
本稿では,新しい解析手法を用いて,未知の非平滑な目的を最適化するアルゴリズムを提案する。
決定論的二階スムーズな目的のために、先進的な楽観的なオンライン学習技術を適用することで、新しい$O(delta0.5)All$が最適または最もよく知られた結果の回復を可能にする。
論文 参考訳（メタデータ） (2023-02-07T22:09:20Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - A Conditional Gradient-based Method for Simple Bilevel Optimization with
Convex Lower-level Problem [18.15207779559351]
そこで本稿では, 切削平面による下層問題の解集合を局所的に近似する二段階最適化手法を提案する。
本手法は,二段階問題のクラスについて,最もよく知られた仮定を導出する。
論文 参考訳（メタデータ） (2022-06-17T16:12:47Z) - Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient [0.0]
まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。
提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。
提案手法の性能を実証するために,予備的な数値計算結果を示す。
論文 参考訳（メタデータ） (2022-06-02T10:34:26Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。