論文の概要: On Penalty Methods for Nonconvex Bilevel Optimization and First-Order
Stochastic Approximation
- arxiv url: http://arxiv.org/abs/2309.01753v2
- Date: Sun, 11 Feb 2024 08:10:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-13 22:31:20.455471
- Title: On Penalty Methods for Nonconvex Bilevel Optimization and First-Order
Stochastic Approximation
- Title（参考訳）: 非凸双レベル最適化のペナルティ法と一階確率近似について
- Authors: Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, Robert Nowak
- Abstract要約: 両レベル最適化問題の1次解法について述べる。
特に,ペナルティ関数と超目的物との間に強い関連性を示す。
その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
- 参考スコア（独自算出の注目度）: 13.813242559935732
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study first-order algorithms for solving Bilevel
Optimization (BO) where the objective functions are smooth but possibly
nonconvex in both levels and the variables are restricted to closed convex
sets. As a first step, we study the landscape of BO through the lens of penalty
methods, in which the upper- and lower-level objectives are combined in a
weighted sum with penalty parameter $\sigma > 0$. In particular, we establish a
strong connection between the penalty function and the hyper-objective by
explicitly characterizing the conditions under which the values and derivatives
of the two must be $O(\sigma)$-close. A by-product of our analysis is the
explicit formula for the gradient of hyper-objective when the lower-level
problem has multiple solutions under minimal conditions, which could be of
independent interest. Next, viewing the penalty formulation as
$O(\sigma)$-approximation of the original BO, we propose first-order algorithms
that find an $\epsilon$-stationary solution by optimizing the penalty
formulation with $\sigma = O(\epsilon)$. When the perturbed lower-level problem
uniformly satisfies the small-error proximal error-bound (EB) condition, we
propose a first-order algorithm that converges to an $\epsilon$-stationary
point of the penalty function, using in total $O(\epsilon^{-3})$ and
$O(\epsilon^{-7})$ accesses to first-order (stochastic) gradient oracles when
the oracle is deterministic and oracles are noisy, respectively. Under an
additional assumption on stochastic oracles, we show that the algorithm can be
implemented in a fully {\it single-loop} manner, i.e., with $O(1)$ samples per
iteration, and achieves the improved oracle-complexity of $O(\epsilon^{-3})$
and $O(\epsilon^{-5})$, respectively.
- Abstract（参考訳）: 本研究では,目的関数が両レベルにおいて滑らかだが非凸であり,変数が閉凸集合に制限される2次最適化(bo)を解くための一階アルゴリズムについて検討する。
第一段階として,上層目標と下層目標の重み付き和とペナルティパラメータ $\sigma > 0$ とを組み合わせたペナルティ法のレンズを通してboのランドスケープを考察する。
特に、ペナルティ関数と超目的関数の間には、2つの値と微分が$o(\sigma)$-close でなければならない条件を明示的に特徴付けることによって強い関係が確立される。
我々の分析の副産物は、低レベル問題が最小条件下で複数の解を持つ場合に、超目的の勾配の明示的な公式である。
次に、ペナルティ定式化を元のBOの$O(\sigma)$-approximationとみなして、$\epsilon$-stationary Solution を求める一階アルゴリズムを提案し、$\sigma = O(\epsilon)$でペナルティ定式化を最適化する。
摂動下層問題は小誤差近位誤差結合(EB)条件を均一に満たす場合、各オラクルが決定論的でオラクルがうるさいときの1次勾配オラクルへのアクセスを合計$O(\epsilon^{-3})$と$O(\epsilon^{-7})$を用いて、ペナルティ関数の$\epsilon$定常点に収束する1次アルゴリズムを提案する。
確率的オラクルに関する追加の仮定の下で、このアルゴリズムは全単ループで実装可能であること、すなわち、1イテレーションあたり$O(1)$サンプルで、それぞれ$O(\epsilon^{-3})$と$O(\epsilon^{-5})$の改善されたオラクル複雑度を達成する。
関連論文リスト
- First-Order Methods for Linearly Constrained Bilevel Optimization [38.19659447295665]
本稿では,高次ヘッセン計算に対する一階線形制約最適化手法を提案する。
線形不等式制約に対しては、$widetildeO(ddelta-1 epsilon-3)$ gradient oracle callにおいて$(delta,epsilon)$-Goldstein固定性を得る。
論文 参考訳（メタデータ） (2024-06-18T16:41:21Z) - Projection-Free Methods for Stochastic Simple Bilevel Optimization with
Convex Lower-level Problem [16.9187409976238]
凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。
低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
論文 参考訳（メタデータ） (2023-08-15T02:37:11Z) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - Projection-Free Algorithm for Stochastic Bi-level Optimization [17.759493152879013]
本研究は、目的関数が他の最適化問題に依存する二段階最適化問題を解く最初のプロジェクションフリーアルゴリズムを示す。
提案されている$textbfStochastic $textbfF$rank-$textbfW$olfe ($textbfSCFW$)は、凸目的に対して$mathcalO(epsilon-2)$のサンプル複雑性を実現するために示されている。
論文 参考訳（メタデータ） (2021-10-22T11:49:15Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。