論文の概要: 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に対する最初の非自明な下界を証明し、独立な興味を持ち、既存の上界を改善することができる。
オンラインリニアコントロールやオンラインパフォーマンス予測など,さまざまなオンライン学習問題に対して,後悔境界の導出と既存の後悔境界導出を改善し,単純化することにより,フレームワークの広範な適用性を示す。
関連論文リスト
- LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。
我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-12T17:08:31Z) - Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。
これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
論文 参考訳（メタデータ） (2024-06-20T23:00:25Z) - A Theory of Learnability for Offline Decision Making [0.1227734309612871]
本稿では,学習目標に部分的に相関したデータセットから決定を学習することに焦点を当てたオフライン意思決定の問題について検討する。
オフラインフィードバックを用いた意思決定(Decision Making with Offline Feedback, DMOF)と呼ばれる統合フレームワークを導入する。
我々はまた、インスタンス依存上界とミニマックス上界の両方を確立する、EDD(Empirical Decision with Divergence)と呼ばれるアルゴリズムも導入した。
論文 参考訳（メタデータ） (2024-06-03T14:42:31Z) - Second Order Methods for Bandit Optimization and Control [34.51425758864638]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳（メタデータ） (2024-02-14T04:03:38Z) - 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 [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。