論文の概要: Online Convex Optimization with Unbounded Memory
- arxiv url: http://arxiv.org/abs/2210.09903v4
- Date: Sat, 28 Oct 2023 01:15:57 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 23:40:10.807776
- Title: Online Convex Optimization with Unbounded Memory
- Title(参考訳): unbounded memoryを用いたオンライン凸最適化
- Authors: Raunak Kumar, Sarah Dean, and Robert Kleinberg
- Abstract要約: 我々は,過去の意思決定に対する長期的依存を捉えたOCOフレームワークの一般化を紹介する。
ポリシーの後悔に対して$O(sqrtH_p T)$上界とマッチング(Worst-case)下界を証明します。
我々は、このフレームワークの広範な適用性を、後悔境界の導出に利用し、既存の後悔境界の導出を改善し、単純化することで実証する。
- 参考スコア(独自算出の注目度): 10.292080338245812
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online convex optimization (OCO) is a widely used framework in online
learning. In each round, the learner chooses a decision in a convex set and an
adversary chooses a convex loss function, and then the learner suffers the loss
associated with their current decision. However, in many applications the
learner's loss depends not only on the current decision but on the entire
history of decisions until that point. The OCO framework and its existing
generalizations do not capture this, and they can only be applied to many
settings of interest after a long series of approximation arguments. They also
leave open the question of whether the dependence on memory is tight because
there are no non-trivial lower bounds. In this work we introduce a
generalization of the OCO framework, ``Online Convex Optimization with
Unbounded Memory'', that captures long-term dependence on past decisions. We
introduce the notion of $p$-effective memory capacity, $H_p$, that quantifies
the maximum influence of past decisions on present losses. We prove an
$O(\sqrt{H_p T})$ upper bound on the policy regret and a matching (worst-case)
lower bound. As a special case, we prove the first non-trivial lower bound for
OCO with finite memory~\citep{anavaHM2015online}, which could be of independent
interest, and also improve existing upper bounds. We demonstrate the broad
applicability of our framework by using it to derive regret bounds, and to
improve and simplify existing regret bound derivations, for a variety of online
learning problems including online linear control and an online variant of
performative prediction.
- Abstract(参考訳): online convex optimization(oco)は、オンライン学習において広く使われているフレームワークである。
各ラウンドにおいて、学習者は凸集合における決定を選択し、敵は凸損失関数を選択し、その後、学習者は現在の決定に関連する損失を被る。
しかし、多くのアプリケーションでは、学習者の損失は現在の決定だけでなく、その時点まですべての決定の歴史に依存する。
ocoフレームワークとその既存の一般化は、これを捉えておらず、長い一連の近似引数の後、多くの関心の設定にしか適用できない。
彼らはまた、非自明な下限がないため、メモリ依存がきついかどうかという疑問も残している。
本稿では,OCOフレームワークの一般化である ``Online Convex Optimization with Unbounded Memory'' を紹介する。
我々は,現在の損失に対する過去の決定の最大影響を定量化するメモリ容量$p$,$h_p$の概念を導入する。
o(\sqrt{h_p t})$ upperbound on the policy regret and a matching (worst-case) lowerbound を証明します。
特別な場合として、有限メモリを持つocoに対する最初の非自明な下界を証明し、独立な興味を持ち、既存の上界を改善することができる。
オンラインリニアコントロールやオンラインパフォーマンス予測など,さまざまなオンライン学習問題に対して,後悔境界の導出と既存の後悔境界導出を改善し,単純化することにより,フレームワークの広範な適用性を示す。
関連論文リスト
- Second Order Methods for Bandit Optimization and Control [37.70434692823672]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳(メタデータ) (2024-02-14T04:03:38Z) - Playing in the Dark: No-regret Learning with Adversarial Constraints [20.077237398506536]
本稿では,従来のオンライン凸最適化(OCO)フレームワークの長期的制約を考慮した一般化について検討する。
我々は,任意のOCOポリシを用いて代理問題を解くことで,最適な性能境界を実現することができることを示す。
新たなリャプノフに基づく証明手法が提示され、後悔と特定の逐次不等式の間の関係を明らかにする。
論文 参考訳(メタデータ) (2023-10-29T09:55:41Z) - Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making [73.48977854003697]
この研究は、複雑性という新しい概念、一般化ブラケット数を導入し、空間の大きさに対する敵の制約を結婚させる。
次に、オンライン予測や断片的連続関数の計画など、関心のあるいくつかの問題で境界をインスタンス化する。
論文 参考訳(メタデータ) (2023-02-10T18:45:52Z) - Online Convex Optimization with Long Term Constraints for Predictable
Sequences [5.964436882344728]
我々は,長期的制約を伴うOCOと呼ばれるOCOの特定の枠組みについて検討する。
長期的制約は、オンライン最適化における更新ステップ毎に、プロジェクションの複雑さを減らす代替手段として導入される。
我々は,次の関数の情報をシーケンスで供給できる予測器を用いて,予測なしで達成できる率よりも厳密に少ない,全体的な後悔と制約違反率を達成することができることを示した。
論文 参考訳(メタデータ) (2022-10-30T03:50:53Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳(メタデータ) (2022-09-15T16:59:19Z) - Universal Caching [8.208569626646034]
オンラインキャッシュ問題の文脈において,後悔の最小化というより強い概念を考察する。
適応的なサブ線形後悔境界を持つ効率的なオンラインキャッシュポリシーを提案する。
私たちの知る限りでは、ユニバーサルキャッシング問題で知られている最初のデータ依存の後悔だ。
論文 参考訳(メタデータ) (2022-05-10T13:00:10Z) - First-Order Regret in Reinforcement Learning with Linear Function
Approximation: A Robust Estimation Approach [57.570201404222935]
我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。
この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
論文 参考訳(メタデータ) (2021-12-07T00:29:57Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳(メタデータ) (2021-11-24T07:14:57Z) - Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds
for Episodic Reinforcement Learning [50.44564503645015]
有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。
楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
論文 参考訳(メタデータ) (2021-07-02T20:36:05Z) - Projection-free Online Learning over Strongly Convex Sets [27.875251633343666]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受していることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳(メタデータ) (2020-10-16T05:42:50Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳(メタデータ) (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。