論文の概要: Online Bilevel Optimization: Regret Analysis of Online Alternating
Gradient Methods
- arxiv url: http://arxiv.org/abs/2207.02829v1
- Date: Wed, 6 Jul 2022 17:36:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-07 15:06:22.886319
- Title: Online Bilevel Optimization: Regret Analysis of Online Alternating
Gradient Methods
- Title(参考訳): オンラインバイレベル最適化:オンライン交互勾配法の後悔分析
- Authors: Davoud Ataee Tarzanagh and Laura Balzano
- Abstract要約: 本稿では,オンラインの2段階最適化手法について検討し,時間変化の2段階問題を次々に明らかにする手法を提案する。
具体的には,2段階の後悔という新たな概念を導入し,スムーズさを生かしたオンラインの時間平均勾配法を開発し,内部および外部の最小化シーケンスのパス長による後悔境界を提供する。
- 参考スコア(独自算出の注目度): 11.023443997688227
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Online optimization is a well-established optimization paradigm that aims to
make a sequence of correct decisions given knowledge of the correct answer to
previous decision tasks. Bilevel programming involves a hierarchical
optimization problem where the feasible region of the so-called outer problem
is restricted by the graph of the solution set mapping of the inner problem.
This paper brings these two ideas together and studies an online bilevel
optimization setting in which a sequence of time-varying bilevel problems are
revealed one after the other. We extend the known regret bounds for
single-level online algorithms to the bilevel setting. Specifically, we
introduce new notions of bilevel regret, develop an online alternating
time-averaged gradient method that is capable of leveraging smoothness, and
provide regret bounds in terms of the path-length of the inner and outer
minimizer sequences.
- Abstract(参考訳): オンライン最適化は、以前の意思決定タスクに対する正しい答えの知識を前提として、正しい意思決定の連続を目標とする、確立した最適化パラダイムである。
双レベルプログラミングは、内部問題の解集合写像のグラフによって、いわゆる外問題の実現可能な領域が制限される階層的最適化問題を含む。
本稿では、これらの2つのアイデアをまとめて、時間変化の両レベル問題の連続を次々に明らかにするオンラインの双レベル最適化設定について研究する。
我々は、シングルレベルオンラインアルゴリズムの既知の後悔の限界を二レベル設定に拡張する。
具体的には,2段階の後悔という新たな概念を導入し,スムーズさを生かしたオンラインの時間平均勾配法を開発し,内部および外部の最小化シーケンスのパス長による後悔境界を提供する。
関連論文リスト
- Universal Online Learning with Gradient Variations: A Multi-layer Online
Ensemble Approach [65.10444843694003]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $widehatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳(メタデータ) (2023-07-17T09:55:35Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳(メタデータ) (2023-06-04T17:54:11Z) - Minimizing Dynamic Regret on Geodesic Metric Spaces [20.353993251916982]
測地線距離空間に適用可能な「最適」オンライン学習アルゴリズムを開発した。
これは、一般的な動的後悔を考慮し、「最適」オンライン学習アルゴリズムを開発する最初の作品である。
論文 参考訳(メタデータ) (2023-02-17T02:03:29Z) - On Penalty-based Bilevel Gradient Descent Method [40.27047651949238]
我々はペナルティ法のレンズを通して二段階問題に取り組む。
ペナルティに基づく二段階勾配勾配法(PBGD)アルゴリズムを提案する。
実験では提案したPBGDアルゴリズムの有効性を示す。
論文 参考訳(メタデータ) (2023-02-10T11:30:19Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.71361250701075]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応するのは, 既往の結果よりも厳密であり, 最悪の場合, 同一の値が保証されるためである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳(メタデータ) (2021-10-24T22:43:15Z) - Regret minimization in stochastic non-convex learning via a
proximal-gradient approach [80.59047515124198]
機械学習やオペレーションの応用によって動機づけられた私たちは、オンラインで制約された問題を最小化するために、一階のオラクルフィードバックを後悔しています。
我々は、近位複雑性低減技術を保証する新しいプロキシグレードを開発する。
論文 参考訳(メタデータ) (2020-10-13T09:22:21Z) - Online Boosting with Bandit Feedback [36.33990847170534]
学習者が限られた情報しか入手できない場合、回帰タスクのオンライン強化の問題を考える。
ノイズの多いマルチポイント帯域フィードバックを持つオンラインブースティングアルゴリズムと、勾配のある新しいオンライン凸最適化アルゴリズムという、2つの意味を持つ効率的な後悔の最小化法を提案する。
論文 参考訳(メタデータ) (2020-07-23T12:40:57Z) - Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。
我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
論文 参考訳(メタデータ) (2020-02-06T03:32:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。