論文の概要: Submodular + Concave

• arxiv url: http://arxiv.org/abs/2106.04769v1
• Date: Wed, 9 Jun 2021 01:59:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-11 07:52:53.692888
• Title: Submodular + Concave
• Title（参考訳）: Submodular + Concave
• Authors: Siddharth Mitra, Moran Feldman, Amin Karbasi
• Abstract要約: 第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
• 参考スコア（独自算出の注目度）: 53.208470310734825
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It has been well established that first order optimization methods can converge to the maximal objective value of concave functions and provide constant factor approximation guarantees for (non-convex/non-concave) continuous submodular functions. In this work, we initiate the study of the maximization of functions of the form $F(x) = G(x) +C(x)$ over a solvable convex body $P$, where $G$ is a smooth DR-submodular function and $C$ is a smooth concave function. This class of functions is a strict extension of both concave and continuous DR-submodular functions for which no theoretical guarantee is known. We provide a suite of Frank-Wolfe style algorithms, which, depending on the nature of the objective function (i.e., if $G$ and $C$ are monotone or not, and non-negative or not) and on the nature of the set $P$ (i.e., whether it is downward closed or not), provide $1-1/e$, $1/e$, or $1/2$ approximation guarantees. We then use our algorithms to get a framework to smoothly interpolate between choosing a diverse set of elements from a given ground set (corresponding to the mode of a determinantal point process) and choosing a clustered set of elements (corresponding to the maxima of a suitable concave function). Additionally, we apply our algorithms to various functions in the above class (DR-submodular + concave) in both constrained and unconstrained settings, and show that our algorithms consistently outperform natural baselines.
• Abstract（参考訳）: 一階最適化法が凸関数の最大目的値に収束し、(非凸/非凸)連続部分モジュラ函数に対する定数因子近似の保証を提供できることはよく確立されている。 本研究では, 可解凸体上での$f(x) = g(x) +c(x)$ の関数の最大化の研究を開始する。ここでは$g$ は滑らかな dr-サブモジュラー関数であり、$c$ は滑らかな凸関数である。 このクラスの函数は、理論的な保証がないような凹凸および連続DR-部分モジュラ函数の厳密な拡張である。 目的関数の性質(例えば$G$ と $C$ が単調か非負か)と集合 $P$ の性質(下向きの閉か否かに関わらず)により、1-1/e$, $1/e$, $1/2$ の近似保証を提供するフランク・ウルフ型アルゴリズムのスイートを提供する。 次に、我々のアルゴリズムを用いて、与えられた基底集合から多様な要素の選択(決定点過程のモードに対応する)とクラスタ化された要素のセットの選択(適切な凹凸関数の最大値に対応する)を円滑に補間するフレームワークを得る。 さらに, 制約条件と制約条件の両方で, 上記のクラス(DR-submodular + concave)の様々な関数にアルゴリズムを適用し, アルゴリズムが自然ベースラインを一貫して上回ることを示す。

関連論文リスト

• 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)
• Faster First-Order Algorithms for Monotone Strongly DR-Submodular Maximization [11.919431962501479]
  連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。 そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-11-15T18:53:14Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity [14.93584434176082]
  擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。 我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:50:41Z)
• 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)
• Submodular Maximization Through Barrier Functions [32.41824379833395]
  連続最適化における障壁関数に着想を得た制約付き部分モジュラーの新しい手法を提案する。 提案するアルゴリズムを実世界の複数のアプリケーションに対して広範囲に評価する。
  論文  参考訳（メタデータ） (2020-02-10T03:32:49Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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