論文の概要: Non-Convex Bilevel Optimization with Time-Varying Objective Functions

• arxiv url: http://arxiv.org/abs/2308.03811v2
• Date: Wed, 8 Nov 2023 23:59:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-10 18:00:39.153294
• Title: Non-Convex Bilevel Optimization with Time-Varying Objective Functions
• Title（参考訳）: 時変目的関数を用いた非凸双レベル最適化
• Authors: Sen Lin, Daouda Sow, Kaiyi Ji, Yingbin Liang, Ness Shroff
• Abstract要約: 本稿では,時間変化の可能なオンライン二段階最適化を提案し,エージェントがオンラインデータを用いて決定を継続的に更新する。 既存のアルゴリズムと比較して、SOBOWは計算効率が良く、以前の関数を知る必要がない。 軽度条件下では,SOBOWはサブリニアな局所的後悔を達成できることを示す。
• 参考スコア（独自算出の注目度）: 57.299128109226025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.
• Abstract（参考訳）: バイレベル最適化は、幅広い機械学習問題において強力なツールとなっている。 しかし、現在のnonconvex bilevel optimizationでは、オフラインデータセットと静的関数が検討されており、ストリーミングデータと時変関数を備えた新興オンラインアプリケーションではうまく動作しない可能性がある。 本研究は,オンラインの双方向最適化(OBO)について検討し,時間変化が可能であるとともに,エージェントがオンラインストリーミングデータを用いて決定を継続的に更新する。 本稿では,booにおける真のハイパーグレードの関数のばらつきと可利用性に対処するために,メモリに格納されている最新のハイパーグレード推定のウィンドウ平均に基づいて外層決定を更新するウィンドウ平均化(sobow)を備えたシングルループオンラインバイレベルオプティマイザを提案する。 既存のアルゴリズムと比較して、SOBOWは計算効率が良く、以前の関数を知る必要がない。 OBOの単一ループ更新と関数変動に根ざした技術的難しさに対処するため,決定変数間の複雑な結合を解消し,過次推定誤差を慎重に制御する新しい解析手法を開発した。 軽度条件下では,SOBOWはサブリニアな局所的後悔を達成できることを示す。 複数の領域にわたる大規模な実験は、SOBOWの有効性を裏付ける。

関連論文リスト

• Online Nonconvex Bilevel Optimization with Bregman Divergences [3.237380113935023]
  本稿では,近年の変動率の平均値を用いて,外部変数を更新するオンラインバイレベル(SOB)手法を提案する。 このアプローチは、ハイパーレベルベンチマークのレートが優れたパフォーマンスと効率を強調するため、オフラインバイレベル設定(OBO)よりも優れている。
  論文  参考訳（メタデータ） (2024-09-16T17:01:27Z)
• Reinforced In-Context Black-Box Optimization [64.25546325063272]
  RIBBOは、オフラインデータからエンドツーエンドでBBOアルゴリズムを強化学習する手法である。 RIBBOは、複数の動作アルゴリズムとタスクによって生成される最適化履歴を学習するために、表現的なシーケンスモデルを使用している。 提案手法の中心となるのは,テキストレグレット・ツー・ゴートークンによる最適化履歴の増大である。
  論文  参考訳（メタデータ） (2024-02-27T11:32:14Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。 メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
  論文  参考訳（メタデータ） (2023-10-27T23:24:37Z)
• On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
  双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。 本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。 ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
  論文  参考訳（メタデータ） (2022-12-28T18:57:46Z)
• Asynchronous Distributed Bilevel Optimization [20.074079852690048]
  本稿では,双方向最適化問題に対処するため,非同期分散双レベル(ADBO)アルゴリズムを提案する。 ADBOが$epsilon$-定常点を得る複雑さは$mathcalO(frac1epsilon 2)$によって上界される。
  論文  参考訳（メタデータ） (2022-12-20T07:44:48Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  統計的決定論の研究からシャノンエントロピーの一般化を考える。 まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。 次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
  論文  参考訳（メタデータ） (2022-10-04T04:43:58Z)
• Computationally Efficient High-Dimensional Bayesian Optimization via Variable Selection [0.5439020425818999]
  本稿では,変数選択を利用した計算効率の高い高次元BO法を提案する。 提案手法では,選択変数を含む空間を軸整列した部分空間を自動的に学習することができる。 我々は,いくつかの合成および実問題に対する本手法の有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-09-20T01:55:43Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• JUMBO: Scalable Multi-task Bayesian Optimization using Offline Data [86.8949732640035]
  追加データをクエリすることで制限をサイドステップするMBOアルゴリズムであるJUMBOを提案する。 GP-UCBに類似した条件下では, 応答が得られないことを示す。 実世界の2つの最適化問題に対する既存手法に対する性能改善を実証的に示す。
  論文  参考訳（メタデータ） (2021-06-02T05:03:38Z)

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

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