論文の概要: Stochastic Online Learning with Feedback Graphs: Finite-Time and
Asymptotic Optimality
- arxiv url: http://arxiv.org/abs/2206.10022v1
- Date: Mon, 20 Jun 2022 22:11:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-22 18:20:03.464057
- Title: Stochastic Online Learning with Feedback Graphs: Finite-Time and
Asymptotic Optimality
- Title（参考訳）: フィードバックグラフによる確率的オンライン学習:有限時間と漸近的最適性
- Authors: Teodor V. Marinov and Mehryar Mohri and Julian Zimmert
- Abstract要約: 意外なことに、最適有限時間後悔の概念は、この文脈で一意に定義された性質ではない。
半最適後悔を有限時間・経時的に認めるアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 39.2230418563572
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of stochastic online learning with feedback graphs,
with the goal of devising algorithms that are optimal, up to constants, both
asymptotically and in finite time. We show that, surprisingly, the notion of
optimal finite-time regret is not a uniquely defined property in this context
and that, in general, it is decoupled from the asymptotic rate. We discuss
alternative choices and propose a notion of finite-time optimality that we
argue is \emph{meaningful}. For that notion, we give an algorithm that admits
quasi-optimal regret both in finite-time and asymptotically.
- Abstract（参考訳）: フィードバックグラフを用いた確率的オンライン学習の問題を再検討し、漸近的にも有限時間的にも最適なアルゴリズムを考案することを目指している。
意外なことに、最適有限時間後悔の概念は、この文脈において一意に定義された性質ではなく、一般に、漸近速度から切り離されていることを示す。
代替選択肢を議論し、我々が議論する有限時間最適性の概念を提唱する。
その概念に対して、有限時間および漸近的に準最適後悔を認めるアルゴリズムを与える。
関連論文リスト
- Asymptotic and Non-Asymptotic Convergence of AdaGrad for Non-Convex Optimization via Novel Stopping Time-based Analysis [17.34603953600226]
我々はAdaの革新的な包括的分析を導入し、文献の既存のギャップを埋める。
AdaGradの期待は、ほぼ確実に、平均的にもたらされます。
また,既存の結果と無関係に予測された平均非a-bpt-d勾配を実証した。
論文 参考訳（メタデータ） (2024-09-08T08:29:51Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - Instance-Optimality in Interactive Decision Making: Toward a
Non-Asymptotic Theory [30.061707627742766]
適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。
本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
論文 参考訳（メタデータ） (2023-04-24T21:51:58Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds
for Episodic Reinforcement Learning [50.44564503645015]
有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。
楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
論文 参考訳（メタデータ） (2021-07-02T20:36:05Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - An Index-based Deterministic Asymptotically Optimal Algorithm for
Constrained Multi-armed Bandit Problems [0.0]
制約付きマルチアームバンディットのモデルでは、インデックスベースの決定論的最適アルゴリズムが存在することを示す。
我々は、T が地平線サイズ、A がバンディットの腕の集合であるような 1-O(|A|Te-T) として与えられる最適性の確率に制限された有限時間を与える。
論文 参考訳（メタデータ） (2020-07-29T01:54:22Z) - Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic
Optimality [25.627939043735683]
我々は後悔を最小限に抑えるために構造化された包帯について研究する。
本稿では,有限仮説に焦点をあて,有界後悔を楽しみながら最適性を達成できるかを問う。
論文 参考訳（メタデータ） (2020-06-15T20:46:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。