Fugu-MT 論文翻訳(概要): Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

論文の概要: Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization

arxiv url: http://arxiv.org/abs/2403.10063v2
Date: Fri, 26 Apr 2024 21:05:00 GMT
ステータス: 処理完了
システム内更新日: 2024-04-30 23:16:19.305112
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-サブモジュラー最適化のための半帯域フィードバックと帯域フィードバックについて検討し,この最適化領域の理解を推し進める。

関連論文リスト

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文参考訳（メタデータ） (2024-05-28T19:02:30Z)
Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
論文参考訳（メタデータ） (2024-05-24T04:11:58Z)
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)
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)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。