論文の概要: Contextual Stochastic Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2310.18535v1
• Date: Fri, 27 Oct 2023 23:24:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-31 18:09:55.922614
• Title: Contextual Stochastic Bilevel Optimization
• Title（参考訳）: 文脈的確率的二レベル最適化
• Authors: Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, Daniel Kuhn
• Abstract要約: 文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。 メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
• 参考スコア（独自算出の注目度）: 50.36775806399861
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This framework extends classical stochastic bilevel optimization when the lower-level decision maker responds optimally not only to the decision of the upper-level decision maker but also to some side information and when there are multiple or even infinite many followers. It captures important applications such as meta-learning, personalized federated learning, end-to-end learning, and Wasserstein distributionally robust optimization with side information (WDRO-SI). Due to the presence of contextual information, existing single-loop methods for classical stochastic bilevel optimization are unable to converge. To overcome this challenge, we introduce an efficient double-loop gradient method based on the Multilevel Monte-Carlo (MLMC) technique and establish its sample and computational complexities. When specialized to stochastic nonconvex optimization, our method matches existing lower bounds. For meta-learning, the complexity of our method does not depend on the number of tasks. Numerical experiments further validate our theoretical results.
• Abstract（参考訳）: 文脈的確率的二レベル最適化(csbo) - いくつかの文脈情報と上位レベルの決定変数に基づく期待条件を最小化する低レベル問題を伴う確率的二レベル最適化フレームワーク。 このフレームワークは、下層の意思決定者が上層の意思決定者だけでなく、何らかの側の情報や複数のあるいは無限のフォロワーが存在する場合にも、古典的な確率的二段階最適化を拡張する。 メタラーニング、パーソナライズド・フェデレーション・ラーニング、エンドツーエンド・ラーニング、wasserstein distributionally robust optimization with side information (wdro-si)といった重要な応用を捉えている。 文脈情報が存在するため、従来の確率的二段階最適化のための単一ループ法は収束できない。 この課題を克服するために,マルチレベルモンテカルロ(MLMC)技術に基づく効率的な二重ループ勾配法を導入し,そのサンプルおよび計算複雑性を確立する。 確率的非凸最適化に特化した場合,本手法は既存の下限に適合する。 メタラーニングでは,提案手法の複雑さはタスク数に依存しない。 数値実験は我々の理論結果をさらに検証する。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Pareto Set Prediction Assisted Bilevel Multi-objective Optimization [2.3293561091456283]
  両レベルにおいて複数目的(BLMOP)の問題に対処する。 提案されたアプローチは、欺くことと非欺くことの両方を含む、さまざまな問題で競合する。
  論文  参考訳（メタデータ） (2024-09-05T08:04:11Z)
• Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
  従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。 両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。 $(textFG)2textU$は本質的に並列コンピューティングをサポートするように設計されており、大規模分散コンピューティングシステムを効果的に活用することができる。
  論文  参考訳（メタデータ） (2024-06-20T08:21:52Z)
• SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity [5.046146134689904]
  SPABAを実装する際には,双レベル最適化と単レベル最適化の間に複雑性解析のギャップがないことが示されている。 本稿では,複雑性解析の状況を改善するために,他の2ループあるいはネストした2レベルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-29T05:36:03Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• A Gradient Method for Multilevel Optimization [8.80899367147235]
  我々は、Franceschiらのアイデアに基づいて、多レベル$n$レベルの勾配に基づくアルゴリズムを開発した。 私たちの知る限り、これはマルチレベル最適化の理論的保証を持つ最初のアルゴリズムの1つである。
  論文  参考訳（メタデータ） (2021-05-28T16:22:10Z)
• A Single-Timescale Stochastic Bilevel Optimization Method [34.868681953242934]
  本稿では,Single-Timescale stochAstic BiEl Optimization (STABLE) と呼ばれる二段階問題に対する新しい手法を提案する。 双レベル問題において、$epsilon$-stationaryポイントを達成するためには、合計$cal O(epsilon-2)$サンプルが必要であり、強凸の場合、$epsilon$-Optimalソリューションを達成するには$cal O(epsilon-1)$サンプルが必要である。
  論文  参考訳（メタデータ） (2021-02-09T06:35:30Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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