論文の概要: Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
- arxiv url: http://arxiv.org/abs/2403.10063v1
- Date: Fri, 15 Mar 2024 07:05:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 18:19:27.874408
- Title: Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
- Title(参考訳): 逆DR-サブモジュール最適化のための統一射影自由アルゴリズム
- Authors: Mohammad Pedramfar, Yididiya Y. Nadew, Christopher J. Quinn, Vaneet Aggarwal,
- Abstract要約: 本稿では,DR-サブモジュラー最適化のための統合プロジェクションフリーのFrank-Wolfe型アルゴリズムを提案する。
非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明されたサブ線形$alpha$-regret境界を持つ最初のものであるか、あるいは、最先端よりもより優れた$alpha$-regret境界を持つかのいずれかである。
- 参考スコア(独自算出の注目度): 28.598226670015315
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces unified projection-free Frank-Wolfe type algorithms for adversarial continuous DR-submodular optimization, spanning scenarios such as full information and (semi-)bandit feedback, monotone and non-monotone functions, different constraints, and types of stochastic queries. For every problem considered in the non-monotone setting, the proposed algorithms are either the first with proven sub-linear $\alpha$-regret bounds or have better $\alpha$-regret bounds than the state of the art, where $\alpha$ is a corresponding approximation bound in the offline setting. In the monotone setting, the proposed approach gives state-of-the-art sub-linear $\alpha$-regret bounds among projection-free algorithms in 7 of the 8 considered cases while matching the result of the remaining case. Additionally, this paper addresses semi-bandit and bandit feedback for adversarial DR-submodular optimization, advancing the understanding of this optimization area.
- Abstract(参考訳): 本稿では,予測自由なFrank-Wolfe型アルゴリズムを導入し,全情報や半帯域フィードバック,モノトーンおよび非モノトーン関数,制約の相違,確率的クエリのタイプといったシナリオを網羅する。
非単調な設定で考慮されたすべての問題に対して、提案アルゴリズムは、証明済みのサブ線形$\alpha$-regret境界を持つか、あるいは、オフライン設定における対応する近似である$\alpha$-regret境界を持つよりも良い$\alpha$-regret境界を持つかのいずれかである。
モノトーン設定では、提案手法は、残りのケースの結果と一致しながら、提案した8つのケースのうち7つのプロジェクションフリーアルゴリズムにおいて、最先端のサブ線形$\alpha$-regret境界を与える。
さらに,逆DR-サブモジュラー最適化のための半帯域フィードバックと帯域フィードバックについて検討し,この最適化領域の理解を推し進める。
関連論文リスト
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization [33.38582292895673]
一般的なメタアルゴリズムは、凹凸/四角形関数を四角形設定を最適化するものに変換する。
新しいプロジェクションアルゴリズムは、Follow The Perturbed Leaderフレームワークを使って導出される。
特に,本論文では,既存の最先端結果と比較して,これらの設定を少ない仮定で達成している。
論文 参考訳(メタデータ) (2024-04-27T06:19:30Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳(メタデータ) (2023-01-28T12:09:58Z) - Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models [17.462968952951883]
MapReduce(MR)モデルのサブモジュラー関数は注目されている。
MR設定において,複数のサブ線形適応アルゴリズムが動作に必要な整合性を満たすことを示す。
論文 参考訳(メタデータ) (2022-06-20T04:17:32Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-11-15T18:53:14Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳(メタデータ) (2021-07-09T16:04:24Z) - Bregman Gradient Policy Optimization [97.73041344738117]
本稿では,Bregmanの発散と運動量に基づく強化学習のためのBregmanグラデーションポリシーの最適化を設計する。
VR-BGPOは、各イテレーションで1つの軌道のみを必要とする$epsilon$stationaryポイントを見つけるために、$tilde(epsilon-3)$で最高の複雑性に達する。
論文 参考訳(メタデータ) (2021-06-23T01:08:54Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。