論文の概要: First-order penalty methods for bilevel optimization
- arxiv url: http://arxiv.org/abs/2301.01716v1
- Date: Wed, 4 Jan 2023 17:29:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-05 15:31:45.973866
- Title: First-order penalty methods for bilevel optimization
- Title（参考訳）: 2レベル最適化のための1次ペナルティ法
- Authors: Zhaosong Lu and Sanyou Mei
- Abstract要約: 本研究では,下層部が凸問題である非制約二段階最適化問題について検討する。
特に,avarレベルの問題を解くためのペナルティ手法を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- 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 part is a convex optimization
problem, while the upper-level part is possibly a nonconvex optimization
problem. In particular, we propose penalty methods for solving them, whose
subproblems turn out to be a structured minimax problem and are suitably solved
by a first-order method developed in this paper. Under some suitable
assumptions, an \emph{operation complexity} of ${\cal
O}(\varepsilon^{-4}\log\varepsilon^{-1})$ and ${\cal
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. To the best of our knowledge, the
methodology and results in this paper are new.
- Abstract（参考訳）: 本稿では,下層部が凸最適化問題,上層部が非凸最適化問題,下層部が凸最適化問題,下層部が非凸最適化問題という2次最適化問題のクラスについて検討する。
特に,サブプロブレムが構造化されたミニマックス問題であることが判明し,本論文で開発した一階法で最適に解決できるペナルティ法を提案する。
いくつかの適切な仮定の下で、制約のない双レベル最適化問題の$\varepsilon$-KKTソリューションを見つけるための提案されたペナルティ法に対して、${\cal O}(\varepsilon^{-4}\log\varepsilon^{-1})$と${\cal O}(\varepsilon^{-7}\log\varepsilon^{-1})$の \emph{operation complexity} が確立されている。
我々の知る限りでは、本論文の方法論と成果は新しいものである。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。