論文の概要: Improved Projection-free Online Continuous Submodular Maximization
- arxiv url: http://arxiv.org/abs/2305.18442v1
- Date: Mon, 29 May 2023 02:54:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 21:06:00.550009
- Title: Improved Projection-free Online Continuous Submodular Maximization
- Title（参考訳）: プロジェクションフリーオンライン連続サブモジュラー最大化の改善
- Authors: Yucheng Liao and Yuanyu Wan and Chang Yao and Mingli Song
- Abstract要約: 単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。
同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
- 参考スコア（独自算出の注目度）: 35.324719857218014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the problem of online learning with monotone and continuous
DR-submodular reward functions, which has received great attention recently. To
efficiently handle this problem, especially in the case with complicated
decision sets, previous studies have proposed an efficient projection-free
algorithm called Mono-Frank-Wolfe (Mono-FW) using $O(T)$ gradient evaluations
and linear optimization steps in total. However, it only attains a
$(1-1/e)$-regret bound of $O(T^{4/5})$. In this paper, we propose an improved
projection-free algorithm, namely POBGA, which reduces the regret bound to
$O(T^{3/4})$ while keeping the same computational complexity as Mono-FW.
Instead of modifying Mono-FW, our key idea is to make a novel combination of a
projection-based algorithm called online boosting gradient ascent, an
infeasible projection technique, and a blocking technique. Furthermore, we
consider the decentralized setting and develop a variant of POBGA, which not
only reduces the current best regret bound of efficient projection-free
algorithms for this setting from $O(T^{4/5})$ to $O(T^{3/4})$, but also reduces
the total communication complexity from $O(T)$ to $O(\sqrt{T})$.
- Abstract（参考訳）: 近年注目されているモノトーンおよび連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
この問題を、特に複雑な決定集合の場合において効率的に解決するために、以前の研究では、$O(T)$グラデーション評価と合計線形最適化ステップを用いて、Mono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムを提案した。
ただし、$(1-1/e)$-regret bound of $O(T^{4/5})$である。
本稿では,Mono-FWと同じ計算量を維持しつつ,$O(T^{3/4})$に制限された後悔を低減させる改良されたプロジェクションフリーアルゴリズム,すなわちPOBGAを提案する。
Mono-FWを変更する代わりに、オンラインブースティング勾配上昇というプロジェクションベースの新しいアルゴリズムと、実現不可能なプロジェクションテクニック、ブロッキングテクニックを組み合わせることが必要です。
さらに、分散された設定を考慮し、この設定に対する効率的なプロジェクションフリーアルゴリズムの現在の最大の後悔境界を$O(T^{4/5})$から$O(T^{3/4})$に下げるだけでなく、通信の総複雑性を$O(T)$から$O(\sqrt{T})$に下げる。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳（メタデータ） (2022-11-22T23:53:06Z) - Communication-Efficient Decentralized Online Continuous DR-Submodular
Maximization [11.889570525184801]
単調連続DR-submodular-Frank問題に対する2つの分散オンラインアルゴリズムを提案する。
1つはOne-shot Decentralized Meta-Wolfe (Mono-DMFW)で、1-1/e)$regret bound $O(T4/5)$を達成している。
次に,非公開ブースティング関数citepzhang2022 に着想を得て,分散オンラインブースティング・グラディエント・アセンジ(DOBGA)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-18T07:32:28Z) - Online Learning for Non-monotone Submodular Maximization: From Full
Information to Bandit Feedback [12.914842850902456]
本稿では, 閉鎖凸集合上でのオンライン非単調連続DR-サブモジュラー問題を再検討する。
メタ-MFWアルゴリズムは$O(sqrtT)$の1/e$-regret境界を達成する。
次に、Mono-MFWを帯域設定に拡張し、$O(T8/9)の1/e$-regretバウンダリのBandit-MFWアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-16T09:32:37Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳（メタデータ） (2022-02-09T20:56:16Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Reusing Combinatorial Structure: Faster Iterative Projections over
Submodular Base Polytopes [7.734726150561089]
離散的視点と連続的な視点の両方を用いて投影の計算を高速化するツールキットを開発した。
基数に基づく部分モジュラーポリトープの特別の場合、あるブレグマン射影の計算ランタイムを$Omega(n/log(n))$の係数で改善する。
論文 参考訳（メタデータ） (2021-06-22T17:29:24Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。