論文の概要: Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization
- arxiv url: http://arxiv.org/abs/2111.07990v1
- Date: Mon, 15 Nov 2021 18:53:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-16 14:56:08.664906
- Title: Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization
- Title（参考訳）: 単調DR-サブモジュラー最大化のための高速1次アルゴリズム
- Authors: Omid Sadeghi, Maryam Fazel
- Abstract要約: 連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 11.919431962501479
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Continuous DR-submodular functions are a class of generally
non-convex/non-concave functions that satisfy the Diminishing Returns (DR)
property, which implies that they are concave along non-negative directions.
Existing work has studied monotone continuous DR-submodular maximization
subject to a convex constraint and provided efficient algorithms with
approximation guarantees. In many applications, such as computing the stability
number of a graph, the monotone DR-submodular objective function has the
additional property of being strongly concave along non-negative directions
(i.e., strongly DR-submodular). In this paper, we consider a subclass of
$L$-smooth monotone DR-submodular functions that are strongly DR-submodular and
have a bounded curvature, and we show how to exploit such additional structure
to obtain faster algorithms with stronger guarantees for the maximization
problem. We propose a new algorithm that matches the provably optimal
$1-\frac{c}{e}$ approximation ratio after only $\lceil\frac{L}{\mu}\rceil$
iterations, where $c\in[0,1]$ and $\mu\geq 0$ are the curvature and the strong
DR-submodularity parameter. Furthermore, we study the Projected Gradient Ascent
(PGA) method for this problem, and provide a refined analysis of the algorithm
with an improved $\frac{1}{1+c}$ approximation ratio (compared to $\frac{1}{2}$
in prior works) and a linear convergence rate. Experimental results illustrate
and validate the efficiency and effectiveness of our proposed algorithms.
- Abstract（参考訳）: 連続DR-部分モジュラ函数は、一般に非凸/非凹関数のクラスであり、Dimishing Returns (DR) の性質を満たす。
既存の研究は、凸制約を受ける単調連続DR-部分モジュラー最大化を研究し、近似保証付き効率的なアルゴリズムを提供した。
グラフの安定性数を計算するような多くの応用において、単調DR-部分モジュラー目的関数は非負方向(すなわち強DR-部分モジュラー)に沿って強く凹むという付加的性質を持つ。
本稿では、DR-部分モジュラー関数が強く、有界曲率を持つ$L$-smooth monotone DR-submodular関数のサブクラスを考察し、そのような付加構造を利用して、最大化問題に対するより強力な保証付き高速なアルゴリズムを得る方法を示す。
証明可能な最適な1-\frac{c}{e}$近似比を,$c\in[0,1]$および$\mu\geq 0$が曲率であり,DR-部分モジュラリティパラメータが強い場合,$\lceil\frac{L}{\mu}\rceil$ iterationsのみに一致する新しいアルゴリズムを提案する。
さらに,この問題に対するpga法の検討を行い,改良された$\frac{1}{1+c}$近似比(先行研究では$\frac{1}{2}$)と線形収束率(線形収束率)を用いて,アルゴリズムの精巧な解析を行う。
実験結果は,提案アルゴリズムの有効性と有効性を示すものである。
関連論文リスト
- Boosting Gradient Ascent for Continuous DR-submodular Maximization [18.040022136474114]
Projected Gradient Ascent (PGA)は、機械学習および運用研究分野で最もよく使われている最適化スキームである。
本稿では,目的関数にわずかな変更を加えるだけで,標準PGAの近似保証を最適に向上できるブースティング手法を提案する。
得られたPGAの変動は、近似比や効率などのいくつかの面で、以前の標準PGAを上回りました。
論文 参考訳（メタデータ） (2024-01-16T12:49:10Z) - 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) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - 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) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳（メタデータ） (2020-06-24T04:37:31Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。