論文の概要: Boosting Gradient Ascent for Continuous DR-submodular Maximization

• arxiv url: http://arxiv.org/abs/2401.08330v2
• Date: Wed, 24 Jul 2024 08:13:26 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-25 19:30:34.783417
• Title: Boosting Gradient Ascent for Continuous DR-submodular Maximization
• Title（参考訳）: 連続DRサブモジュラー最大化のためのブースティンググラジエント上昇
• Authors: Qixin Zhang, Zongqi Wan, Zengde Deng, Zaiyi Chen, Xiaoming Sun, Jialin Zhang, Yu Yang,
• Abstract要約: Projected Gradient Ascent (PGA)は、機械学習および運用研究分野で最もよく使われている最適化スキームである。 本稿では,目的関数にわずかな変更を加えるだけで,標準PGAの近似保証を最適に向上できるブースティング手法を提案する。 得られたPGAの変動は、近似比や効率などのいくつかの面で、以前の標準PGAを上回りました。
• 参考スコア（独自算出の注目度）: 18.040022136474114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Projected Gradient Ascent (PGA) is the most commonly used optimization scheme in machine learning and operations research areas. Nevertheless, numerous studies and examples have shown that the PGA methods may fail to achieve the tight approximation ratio for continuous DR-submodular maximization problems. To address this challenge, we present a boosting technique in this paper, which can efficiently improve the approximation guarantee of the standard PGA to \emph{optimal} with only small modifications on the objective function. The fundamental idea of our boosting technique is to exploit non-oblivious search to derive a novel auxiliary function $F$, whose stationary points are excellent approximations to the global maximum of the original DR-submodular objective $f$. Specifically, when $f$ is monotone and $\gamma$-weakly DR-submodular, we propose an auxiliary function $F$ whose stationary points can provide a better $(1-e^{-\gamma})$-approximation than the $(\gamma^2/(1+\gamma^2))$-approximation guaranteed by the stationary points of $f$ itself. Similarly, for the non-monotone case, we devise another auxiliary function $F$ whose stationary points can achieve an optimal $\frac{1-\min_{\boldsymbol{x}\in\mathcal{C}}\|\boldsymbol{x}\|_{\infty}}{4}$-approximation guarantee where $\mathcal{C}$ is a convex constraint set. In contrast, the stationary points of the original non-monotone DR-submodular function can be arbitrarily bad~\citep{chen2023continuous}. Furthermore, we demonstrate the scalability of our boosting technique on four problems. In all of these four problems, our resulting variants of boosting PGA algorithm beat the previous standard PGA in several aspects such as approximation ratio and efficiency. Finally, we corroborate our theoretical findings with numerical experiments, which demonstrate the effectiveness of our boosting PGA methods.
• Abstract（参考訳）: Projected Gradient Ascent (PGA)は、機械学習および運用研究分野で最もよく使われている最適化スキームである。 しかしながら、多くの研究や例により、PGA法は連続DR-部分モジュラー最大化問題に対する厳密な近似比を達成できない可能性があることが示されている。 この課題に対処するため,本論文では,目的関数に小さな変更を加えるだけで,標準 PGA の \emph{optimal} への近似保証を効率よく改善する手法を提案する。 本手法の基本的な考え方は,従来のDR-submodular objective $f$の大域的最大値に対する固定点の近似が優れている新しい補助関数$F$を導出するために,非公約探索を利用することである。 具体的には、$f$が単調で$\gamma$-weakly DR-submodularなとき、固定点が $f$ の定常点によって保証される $(\gamma^2/(1+\gamma^2))$-approximation よりも良い$(1-e^{-\gamma})$-approximation を提供するような補助関数 $F$ を提案する。 同様に、単調でない場合には、固定点が最適$\frac{1-\min_{\boldsymbol{x}\in\mathcal{C}}\|\boldsymbol{x}\|_{\infty}}{4}$-approximation guarantee ここで$\mathcal{C}$は凸制約集合である。 対照的に、元の非単調DR-部分モジュラ函数の定常点は、任意に悪い~\citep{chen2023continuous} となる。 さらに,提案手法のスケーラビリティを4つの問題に適用した。 これら4つの問題すべてにおいて、我々の結果のPGAアルゴリズムの変種は、近似比や効率などのいくつかの面で以前の標準PGAを上回った。 最後に,PGA法の有効性を示す数値実験と理論的な結果の相関について検討した。

関連論文リスト

• Fair Submodular Cover [18.37610521373708]
  フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。 まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。 次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
  論文  参考訳（メタデータ） (2024-07-05T18:37:09Z)
• Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
  任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。 この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
  論文  参考訳（メタデータ） (2023-03-06T17:54:33Z)
• 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)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。 係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。 オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
  論文  参考訳（メタデータ） (2022-01-03T15:10:17Z)
• 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)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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