論文の概要: On Stability and Generalization of Bilevel Optimization Problem

• arxiv url: http://arxiv.org/abs/2210.01063v2
• Date: Wed, 5 Oct 2022 18:36:15 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 14:59:24.616818
• Title: On Stability and Generalization of Bilevel Optimization Problem
• Title（参考訳）: 双レベル最適化問題の安定性と一般化について
• Authors: Meng Ding, Mingxi Lei, Yunwen Lei, Di Wang, Jinhui Xu
• Abstract要約: (確率的)バイレベル最適化は、幅広いアプリケーションを持つ機械学習において頻繁に発生する問題である。 まず、安定性とエラーを異なる形で関連付けることで、前のベストな結果を改善する高い確率を与える。 次に、両外層パラメータが連続している場合に、外層パラメータのみを更新できるのに対して、第1の安定性を提供する。
• 参考スコア（独自算出の注目度）: 39.662459636180174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: (Stochastic) bilevel optimization is a frequently encountered problem in machine learning with a wide range of applications such as meta-learning, hyper-parameter optimization, and reinforcement learning. Most of the existing studies on this problem only focused on analyzing the convergence or improving the convergence rate, while little effort has been devoted to understanding its generalization behaviors. In this paper, we conduct a thorough analysis on the generalization of first-order (gradient-based) methods for the bilevel optimization problem. We first establish a fundamental connection between algorithmic stability and generalization error in different forms and give a high probability generalization bound which improves the previous best one from $\bigO(\sqrt{n})$ to $\bigO(\log n)$, where $n$ is the sample size. We then provide the first stability bounds for the general case where both inner and outer level parameters are subject to continuous update, while existing work allows only the outer level parameter to be updated. Our analysis can be applied in various standard settings such as strongly-convex-strongly-convex (SC-SC), convex-convex (C-C), and nonconvex-nonconvex (NC-NC). Our analysis for the NC-NC setting can also be extended to a particular nonconvex-strongly-convex (NC-SC) setting that is commonly encountered in practice. Finally, we corroborate our theoretical analysis and demonstrate how iterations can affect the generalization error by experiments on meta-learning and hyper-parameter optimization.
• Abstract（参考訳）: (確率的)双レベル最適化は、メタラーニング、ハイパーパラメータ最適化、強化学習といった幅広い応用を持つ機械学習において頻繁に発生する問題である。 この問題に関する既存の研究のほとんどは収束率の分析と収束率の向上にのみ焦点を合わせているが、その一般化の振る舞いを理解することにはほとんど努力していない。 本稿では,二段階最適化問題に対する一階法(漸進法)の一般化を徹底的に分析する。 まずアルゴリズムの安定性と異なる形式における一般化誤差の基本的な関係を定め、以前のベストを$\bigo(\sqrt{n})$から$\bigo(\log n)$に改善する高い確率一般化境界を与え、ここで$n$をサンプルサイズとする。 次に、内層パラメータと外層パラメータの両方が連続的な更新を受ける場合の一般の場合の第一の安定性境界を、既存の作業では外層パラメータのみを更新できる。 本分析は, 強凸凸(SC-SC), 凸凸(C-C), 非凸凸(NC-NC)などの各種標準設定に適用できる。 NC-NC設定に対する我々の分析は、実際によく見られる特定の非凸強凸(NC-SC)設定にまで拡張することができる。 最後に,我々は,メタラーニングとハイパーパラメータ最適化の実験により,反復が一般化誤差に与える影響を実証する。

関連論文リスト

• PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates [17.777466668123886]
  PROMISE ($textbfPr$econditioned $textbfO$ptimization $textbfM$ethods by $textbfI$ncorporating $textbfS$calable Curvature $textbfE$stimates)はスケッチベースの事前条件勾配アルゴリズムである。 PROMISEには、SVRG、SAGA、およびKatyushaのプレコンディション版が含まれている。
  論文  参考訳（メタデータ） (2023-09-05T07:49:10Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems [34.68590236021379]
  本稿では,アルゴリズム的安定度と定量的勾配と人口間のギャップについて述べる。 これらのアルゴリズムを、暗黙の規則的な反復ステップサイズと適応勾配勾配を達成するためにどのように適用するかを示す。
  論文  参考訳（メタデータ） (2022-06-14T18:14:30Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。