論文の概要: Online Submodular Maximization via Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2309.04339v1
- Date: Fri, 8 Sep 2023 14:08:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-11 13:24:53.333127
- Title: Online Submodular Maximization via Online Convex Optimization
- Title（参考訳）: オンライン凸最適化によるオンラインサブモジュラー最大化
- Authors: T. Si-Salem, G. \"Ozcan, I. Nikolaou, E. Terzi, S. Ioannidis
- Abstract要約: 我々は、ポテンシャル関数、すなわちポテンシャル関数の大規模なクラスがしきい値凸最適化(OCO)に還元されることを証明した。
我々は,オンライン学習問題において,動的後悔,盗賊,楽観的な学習設定など,多くの異なるバージョンに縮小が及んでいることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study monotone submodular maximization under general matroid constraints
in the online setting. We prove that online optimization of a large class of
submodular functions, namely, weighted threshold potential functions, reduces
to online convex optimization (OCO). This is precisely because functions in
this class admit a concave relaxation; as a result, OCO policies, coupled with
an appropriate rounding scheme, can be used to achieve sublinear regret in the
combinatorial setting. We show that our reduction extends to many different
versions of the online learning problem, including the dynamic regret, bandit,
and optimistic-learning settings.
- Abstract（参考訳）: 一般マトロイド制約下でのモノトン部分モジュラー最大化をオンライン環境で検討する。
重み付けされたしきい値ポテンシャル関数のオンライン最適化は,オンライン凸最適化(OCO)に還元されることを示す。
これは、このクラスの関数が凹凸緩和(concave relaxation)を許容するためであり、結果として、OCOポリシーと適切な丸めのスキームが組み合わさって、組合せ設定におけるサブ線形後悔を達成できる。
我々は,オンライン学習問題において,動的後悔,盗賊,楽観的な学習設定など,多くの異なるバージョンに縮小が及んでいることを示す。
関連論文リスト
- Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
本稿では,モノトーン非線型やDR-サブモジュラリティなど,様々な環境での凹凸とDR-サブモジュラリティの概念を紹介する。
一般的なメタアルゴリズムは、線形/四進関数を上線形/四進関数を最適化するものに変換する。
論文 参考訳（メタデータ） (2024-04-27T06:19:30Z) - Bridging the Gap Between General and Down-Closed Convex Sets in
Submodular Maximization [8.225819874406238]
Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。
本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。
また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
論文 参考訳（メタデータ） (2024-01-17T14:56:42Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳（メタデータ） (2023-07-05T13:52:10Z) - Online Dynamic Submodular Optimization [0.0]
オンラインバイナリ最適化のための証明可能な性能を持つ新しいアルゴリズムを提案する。
高速な需要応答とリアルタイム分散ネットワーク再構成という2つのパワーシステムアプリケーションでアルゴリズムを数値的にテストする。
論文 参考訳（メタデータ） (2023-06-19T10:37:15Z) - Universal Online Optimization in Dynamic Environments via Uniclass
Prediction [0.0]
動的環境におけるユニバーサルオンライン最適化のための新しい直感的なフレームワークを提案する。
私たちの戦略は、専門家のセットと付随するメタアルゴリズムの構築に依存していません。
これは、一般凸コスト関数に対しても、最先端の動的後悔保証を伴う普遍的アプローチを提案する最初の論文である。
論文 参考訳（メタデータ） (2023-02-13T03:00:45Z) - Online Nonsubmodular Minimization with Delayed Costs: From Full
Information to Bandit Feedback [98.7678704343537]
我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。
我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
論文 参考訳（メタデータ） (2022-05-15T08:27:12Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Boosting for Online Convex Optimization [64.15578413206715]
多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。
弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。
ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-02-18T12:30:49Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。