論文の概要: Adaptive Sampling for Fast Constrained Maximization of Submodular
Function
- arxiv url: http://arxiv.org/abs/2102.06486v1
- Date: Fri, 12 Feb 2021 12:38:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-15 13:03:15.096637
- Title: Adaptive Sampling for Fast Constrained Maximization of Submodular
Function
- Title（参考訳）: サブモジュラ関数の高速制約最大化のための適応サンプリング
- Authors: Francesco Quinzan and Vanja Dosko\v{c} and Andreas G\"obel and Tobias
Friedrich
- Abstract要約: 非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
- 参考スコア（独自算出の注目度）: 8.619758302080891
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several large-scale machine learning tasks, such as data summarization, can
be approached by maximizing functions that satisfy submodularity. These
optimization problems often involve complex side constraints, imposed by the
underlying application. In this paper, we develop an algorithm with
poly-logarithmic adaptivity for non-monotone submodular maximization under
general side constraints. The adaptive complexity of a problem is the minimal
number of sequential rounds required to achieve the objective.
Our algorithm is suitable to maximize a non-monotone submodular function
under a $p$-system side constraint, and it achieves a $(p +
O(\sqrt{p}))$-approximation for this problem, after only poly-logarithmic
adaptive rounds and polynomial queries to the valuation oracle function.
Furthermore, our algorithm achieves a $(p + O(1))$-approximation when the given
side constraint is a $p$-extendible system.
This algorithm yields an exponential speed-up, with respect to the
adaptivity, over any other known constant-factor approximation algorithm for
this problem. It also competes with previous known results in terms of the
query complexity. We perform various experiments on various real-world
applications. We find that, in comparison with commonly used heuristics, our
algorithm performs better on these instances.
- Abstract（参考訳）: データ要約のような大規模機械学習タスクは、サブモジュラリティを満たす関数を最大化することでアプローチすることができる。
これらの最適化問題は、しばしば基礎となるアプリケーションによって課される複雑な側制約を伴う。
本稿では,非単調部分モジュラー最大化に対する多対数適応性を持つアルゴリズムを一般制約下で開発する。
問題の適応的複雑性は、目的を達成するのに必要な逐次ラウンドの最小数である。
このアルゴリズムは、$p$-system側制約の下で非単調なサブモジュラ関数を最大化するのに適しており、評価オーラクル関数に対する多対数適応ラウンドと多項式クエリのみの後、この問題に対する$(p + O(\sqrt{p})$-近似を実現する。
さらに,提案アルゴリズムは,与えられた側制約が$p$-extendibleシステムである場合に,$(p + O(1))$-approximationを達成する。
このアルゴリズムは、適応性に関して、この問題に対する既知の任意の定数近似アルゴリズムよりも指数的なスピードアップをもたらす。
また、クエリの複雑さの観点から、以前の既知の結果と競合する。
我々は様々な実世界のアプリケーションで様々な実験を行う。
一般的なヒューリスティックと比較すると、アルゴリズムはこれらのインスタンスでより良いパフォーマンスを発揮します。
関連論文リスト
- Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint [0.0]
本研究は,knapsack制約下での非モジュラーサイズに対する効率的な並列アルゴリズムを提案する。
我々のアルゴリズムは, 既存の並列処理を 8+epsilon$ から 7+epsilon$ に改良し, 適応複雑性を$O(log n)$ にする。
論文 参考訳（メタデータ） (2024-09-06T17:17:52Z) - Practical Parallel Algorithms for Non-Monotone Submodular Maximization [20.13836086815112]
Submodularは、人工知能の分野における様々な分野に広く応用されている。
部分モジュラーアルゴリズムの並列化可能性の1つは適応的な複雑性であり、これは対象関数に対する多数のクエリを並列に実行できるラウンドの数を示している。
証明可能な近似比と非単調なサブモジュラー問題に対するサブ適応複雑性をともに持つ最初のアルゴリズムを$k$-systemに提案する。
論文 参考訳（メタデータ） (2023-08-21T11:48:34Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。