論文の概要: Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity
- arxiv url: http://arxiv.org/abs/2108.08758v1
- Date: Thu, 19 Aug 2021 15:50:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-20 16:45:15.165664
- Title: Parallel Quasi-concave set optimization: A new frontier that scales
without needing submodularity
- Title（参考訳）: parallel quasi-concave set optimization: submodularityを必要とせずにスケールする新しいフロンティア
- Authors: Praneeth Vepakomma, Yulia Kempner, Ramesh Raskar
- Abstract要約: 擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。
我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
- 参考スコア（独自算出の注目度）: 14.93584434176082
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Classes of set functions along with a choice of ground set are a bedrock to
determine and develop corresponding variants of greedy algorithms to obtain
efficient solutions for combinatorial optimization problems. The class of
approximate constrained submodular optimization has seen huge advances at the
intersection of good computational efficiency, versatility and approximation
guarantees while exact solutions for unconstrained submodular optimization are
NP-hard. What is an alternative to situations when submodularity does not hold?
Can efficient and globally exact solutions be obtained? We introduce one such
new frontier: The class of quasi-concave set functions induced as a dual class
to monotone linkage functions. We provide a parallel algorithm with a time
complexity over $n$ processors of $\mathcal{O}(n^2g)
+\mathcal{O}(\log{\log{n}})$ where $n$ is the cardinality of the ground set and
$g$ is the complexity to compute the monotone linkage function that induces a
corresponding quasi-concave set function via a duality. The complexity reduces
to $\mathcal{O}(gn\log(n))$ on $n^2$ processors and to $\mathcal{O}(gn)$ on
$n^3$ processors. Our algorithm provides a globally optimal solution to a
maxi-min problem as opposed to submodular optimization which is approximate. We
show a potential for widespread applications via an example of diverse feature
subset selection with exact global maxi-min guarantees upon showing that a
statistical dependency measure called distance correlation can be used to
induce a quasi-concave set function.
- Abstract（参考訳）: 集合関数のクラスと基底集合の選択は、組合せ最適化問題の効率的な解を得るためのグレディアルゴリズムの対応する変種を決定・開発するための基盤岩である。
近似的制約付き部分モジュラ最適化のクラスは、優れた計算効率、汎用性、近似保証の交差において大きな進歩を経験し、制約なし部分モジュラ最適化の正確な解はNPハードである。
サブモジュラリティが持たない状況の代替となるものは何か?
効率的でグローバルな解が得られますか?
双対クラスとして誘導される準凸集合関数のクラスを単調結合関数へ導入する。
ここでは、$n$は基底集合の濃度であり、$g$は対応する準凸集合関数を双対性を通して誘導する単調結合関数を計算する複雑さである。
複雑さは$n^2$プロセッサで$\mathcal{O}(gn\log(n))$、$n^3$プロセッサで$\mathcal{O}(gn)$に減少する。
我々のアルゴリズムは、近似的な部分モジュラー最適化とは対照的に、極大分問題に対する大域的最適解を提供する。
本研究では,完全大域的マクシミン保証を持つ多種多様な特徴集合選択の例を用いて,距離相関と呼ばれる統計的依存測度を用いて準凸集合関数を誘導できることを示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
論文 参考訳（メタデータ） (2023-08-21T11:48:34Z) - Linear Query Approximation Algorithms for Non-monotone Submodular
Maximization under Knapsack Constraint [16.02833173359407]
この研究は、2つの定数係数近似アルゴリズムを導入し、クナップサック制約の基底集合に対して非単調な部分モジュラーに対して線形なクエリ複雑性を持つ。
$mathsfDLA$は6+epsilon$の近似係数を提供する決定論的アルゴリズムであり、$mathsfRLA$は4+epsilon$の近似係数を持つランダム化アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-17T15:27:33Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。