論文の概要: 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)技術に基づく効率的な二重ループ勾配法を導入し,そのサンプルおよび計算複雑性を確立する。
確率的非凸最適化に特化した場合,本手法は既存の下限に適合する。
メタラーニングでは,提案手法の複雑さはタスク数に依存しない。
数値実験は我々の理論結果をさらに検証する。
関連論文リスト
- Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
本稿では,時間変化の可能なオンライン二段階最適化を提案し,エージェントがオンラインデータを用いて決定を継続的に更新する。
既存のアルゴリズムと比較して、SOBOWは計算効率が良く、以前の関数を知る必要がない。
軽度条件下では,SOBOWはサブリニアな局所的後悔を達成できることを示す。
論文 参考訳(メタデータ) (2023-08-07T06:27:57Z) - On Implicit Bias in Overparameterized Bilevel Optimization [38.11483853830913]
双レベル問題は、それぞれ外問題と内問題と呼ばれる、ネストした2つのサブプロブレムから構成される。
本稿では,2レベル最適化のための勾配に基づくアルゴリズムの暗黙バイアスについて検討する。
ウォームスタートBLOによって得られる内部解は、外的目的に関する驚くべき量の情報を符号化できることを示す。
論文 参考訳(メタデータ) (2022-12-28T18:57:46Z) - Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。
AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。
AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
論文 参考訳(メタデータ) (2022-11-02T13:55:47Z) - FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
多くの現代のML問題は、ミニマックスと合成最適化を仮定したネストされた双レベルプログラミングに該当する。
我々は、一般的なネスト問題に対処するフェデレーション付き交互勾配法を提案する。
論文 参考訳(メタデータ) (2022-05-04T17:48:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。