論文の概要: Online Learning for Non-monotone Submodular Maximization: From Full
Information to Bandit Feedback
- arxiv url: http://arxiv.org/abs/2208.07632v1
- Date: Tue, 16 Aug 2022 09:32:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-17 13:01:07.513711
- Title: Online Learning for Non-monotone Submodular Maximization: From Full
Information to Bandit Feedback
- Title（参考訳）: 非単調サブモジュラー最大化のためのオンライン学習:フル情報からバンディットフィードバックへ
- Authors: Qixin Zhang, Zengde Deng, Zaiyi Chen, Kuangqi Zhou, Haoyuan Hu, Yu
Yang
- Abstract要約: 本稿では, 閉鎖凸集合上でのオンライン非単調連続DR-サブモジュラー問題を再検討する。
メタ-MFWアルゴリズムは$O(sqrtT)$の1/e$-regret境界を達成する。
次に、Mono-MFWを帯域設定に拡張し、$O(T8/9)の1/e$-regretバウンダリのBandit-MFWアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 12.914842850902456
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we revisit the online non-monotone continuous DR-submodular
maximization problem over a down-closed convex set, which finds wide real-world
applications in the domain of machine learning, economics, and operations
research. At first, we present the Meta-MFW algorithm achieving a $1/e$-regret
of $O(\sqrt{T})$ at the cost of $T^{3/2}$ stochastic gradient evaluations per
round. As far as we know, Meta-MFW is the first algorithm to obtain
$1/e$-regret of $O(\sqrt{T})$ for the online non-monotone continuous
DR-submodular maximization problem over a down-closed convex set. Furthermore,
in sharp contrast with ODC algorithm \citep{thang2021online}, Meta-MFW relies
on the simple online linear oracle without discretization, lifting, or rounding
operations. Considering the practical restrictions, we then propose the
Mono-MFW algorithm, which reduces the per-function stochastic gradient
evaluations from $T^{3/2}$ to 1 and achieves a $1/e$-regret bound of
$O(T^{4/5})$. Next, we extend Mono-MFW to the bandit setting and propose the
Bandit-MFW algorithm which attains a $1/e$-regret bound of $O(T^{8/9})$. To the
best of our knowledge, Mono-MFW and Bandit-MFW are the first sublinear-regret
algorithms to explore the one-shot and bandit setting for online non-monotone
continuous DR-submodular maximization problem over a down-closed convex set,
respectively. Finally, we conduct numerical experiments on both synthetic and
real-world datasets to verify the effectiveness of our methods.
- Abstract（参考訳）: 本稿では,オンラインの非単調連続DR-サブモジュラー最大化問題を再検討し,機械学習,経済学,オペレーション研究の分野における幅広い実世界の応用を見出す。
まず,O(\sqrt{T})$の1/e$-regretを1ラウンドあたり$T^{3/2}$確率勾配評価で達成するメタ-MFWアルゴリズムを提案する。
われわれが知る限り、Meta-MFWはオンラインの非単調連続DR-部分モジュラー最大化問題に対して$O(\sqrt{T})$$1/e$-regretを得る最初のアルゴリズムである。
さらに、ODCアルゴリズム \citep{thang2021online} とは対照的に、Meta-MFW は離散化、昇降、丸め操作をせずに単純なオンライン線形オラクルに依存している。
実用的制約を考慮すると,関数ごとの確率勾配の評価をT^{3/2}$から1に減らし,O(T^{4/5})$の1/e$-regretバウンダリを達成できるMono-MFWアルゴリズムを提案する。
次に、Mono-MFWを帯域設定に拡張し、$O(T^{8/9})$の1/e$-regretバウンダリを実現するBandit-MFWアルゴリズムを提案する。
我々の知る限り、Mono-MFWとBandit-MFWは、オンラインの非単調連続DR-サブモジュラー最大化問題に対して、それぞれダウンクロースされた凸集合上のワンショットおよびバンディット設定を探索する最初のサブ線形回帰アルゴリズムである。
最後に,本手法の有効性を検証するために,合成データと実世界データの両方について数値実験を行った。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。
同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
論文 参考訳（メタデータ） (2023-05-29T02:54:31Z) - Bandit Multi-linear DR-Submodular Maximization and Its Applications on
Adversarial Submodular Bandits [21.54858035450694]
分割マトロイド制約を持つ部分モジュラー帯域に対するサブ線形後悔アルゴリズムを提案する。
バンドイットの逐次部分モジュラーに対して、既存の研究はO(T2/3)$ regret を証明し、近似比は1/2$である。
論文 参考訳（メタデータ） (2023-05-21T08:51:55Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Resolving the Approximability of Offline and Online Non-monotone
DR-Submodular Maximization over General Convex Sets [13.23676270963484]
DR-サブモジュラー連続関数は、機械学習、通信システム、研究、経済学の分野において多くの実世界の応用を持つ。
tfrac14 (1 - m)$-the-art offline algorithmと一致する時間オンラインアルゴリズムを提示する。
また、我々のアルゴリズムとDuの(2022)オフラインはどちらも強い意味で最適であることを示す。
論文 参考訳（メタデータ） (2022-10-12T07:04:24Z) - 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) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。