論文の概要: Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
- arxiv url: http://arxiv.org/abs/2601.00611v1
- Date: Fri, 02 Jan 2026 08:44:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-01-05 15:04:33.542506
- Title: Stronger Approximation Guarantees for Non-Monotone γ-Weakly DR-Submodular Maximization
- Title（参考訳）: 非モノトンγ-弱DR-サブモジュラー最大化のためのより強い近似保証
- Authors: Hareshkumar Jadav, Ranveer Singh, Vaneet Aggarwal,
- Abstract要約: 閉鎖凸体上の非単調な$$$-weakly DR-submodular関数について検討した。
我々のアプローチは、Frank-Wolfe指導の継続的機械学習フレームワークと$-greedyのステップを組み合わせています。
これにより、非単調な$$-weakly DR-submodular over down-closed convex bodyに対する最先端の保証が得られる。
- 参考スコア（独自算出の注目度）: 42.50444156527582
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Maximizing submodular objectives under constraints is a fundamental problem in machine learning and optimization. We study the maximization of a nonnegative, non-monotone $γ$-weakly DR-submodular function over a down-closed convex body. Our main result is an approximation algorithm whose guarantee depends smoothly on $γ$; in particular, when $γ=1$ (the DR-submodular case) our bound recovers the $0.401$ approximation factor, while for $γ<1$ the guarantee degrades gracefully and, it improves upon previously reported bounds for $γ$-weakly DR-submodular maximization under the same constraints. Our approach combines a Frank-Wolfe-guided continuous-greedy framework with a $γ$-aware double-greedy step, yielding a simple yet effective procedure for handling non-monotonicity. This results in state-of-the-art guarantees for non-monotone $γ$-weakly DR-submodular maximization over down-closed convex bodies.
- Abstract（参考訳）: 制約下でのサブモジュール目標の最大化は、機械学習と最適化の基本的な問題である。
閉鎖凸体上の非負の非単トン$γ$-弱弱DR-部分モジュラ函数の最大化について検討した。
我々の主な結果は、保証が$γ$に滑らかに依存する近似アルゴリズムであり、特に、$γ=1$ (DR-submodular case) が$0.401$の近似係数を回復する一方で、$γ<1$の保証は優雅に低下し、同じ制約の下で$γ$-weakly DR-submodular maximization(英語版)に対して以前に報告された境界により改善される。
提案手法は,フランク=ウルフ誘導型連続グリーディフレームワークと$γ$-awareのダブルグリーディステップを組み合わせることで,非単調性を扱うための単純かつ効果的な手順を導出する。
これにより、非単調な$γ$-弱弱弱めのDR-サブモジュラー極大化が、閉鎖凸体上での最先端の保証となる。
関連論文リスト
- Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。
1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。
第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
論文 参考訳（メタデータ） (2025-09-26T17:16:34Z) - FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。
Low-Rank Adaptation (LoRA) は、学習における言語モデルの効率的な微調整に広く用いられている。
論文 参考訳（メタデータ） (2025-05-19T07:32:56Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Boosting Gradient Ascent for Continuous DR-submodular Maximization [18.040022136474114]
Projected Gradient Ascent (PGA)は、機械学習および運用研究分野で最もよく使われている最適化スキームである。
本稿では,目的関数にわずかな変更を加えるだけで,標準PGAの近似保証を最適に向上できるブースティング手法を提案する。
得られたPGAの変動は、近似比や効率などのいくつかの面で、以前の標準PGAを上回りました。
論文 参考訳（メタデータ） (2024-01-16T12:49:10Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。