Fugu-MT 論文翻訳(概要): Submodular Maximization via Taylor Series Approximation

論文の概要: Submodular Maximization via Taylor Series Approximation

arxiv url: http://arxiv.org/abs/2101.07423v1
Date: Tue, 19 Jan 2021 02:41:45 GMT
ステータス: 処理完了
システム内更新日: 2021-03-26 09:10:06.522900
Title: Submodular Maximization via Taylor Series Approximation
Title（参考訳）: テイラー級数近似による部分モジュラー最大化
Authors: G\"ozde \"Ozcan, Armin Moharrer, Stratis Ioannidis
Abstract要約: マトロイド制約を用いた部分モジュラー決定論的問題について検討する。この形式のために、いわゆる連続関数グリーディアルゴリズムは、テイラー級数近似を用いて、およそ 0.63$ 以前の$(1-1/e) に近い比率を得る。
参考スコア（独自算出の注目度）: 16.682504954615922
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study submodular maximization problems with matroid constraints, in particular, problems where the objective can be expressed via compositions of analytic and multilinear functions. We show that for functions of this form, the so-called continuous greedy algorithm attains a ratio arbitrarily close to $(1-1/e) \approx 0.63$ using a deterministic estimation via Taylor series approximation. This drastically reduces execution time over prior art that uses sampling.
Abstract（参考訳）: 本研究では,マトロイド制約を伴う部分モジュラー最大化問題,特に,対象を解析関数と多線形関数の合成によって表現できる問題について検討する。この形式の関数に対して、いわゆる連続 greedy アルゴリズムはテイラー級数近似による決定論的推定を用いて、任意に$(1-1/e) に近い約 0.63$ の比率を得る。これにより、サンプリングを使用する先行技術よりも実行時間が大幅に短縮される。

関連論文リスト

Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文参考訳（メタデータ） (2023-03-17T13:32:33Z)
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文参考訳（メタデータ） (2023-01-10T12:18:47Z)
Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。我々の理論解析は数値実験によってさらに検証される。
論文参考訳（メタデータ） (2021-09-08T18:00:05Z)
Sparse Approximate Solutions to Max-Plus Equations with Application to Multivariate Convex Regression [34.99564569478268]
我々は,任意の$ell_p$近似誤差に対して,そのような解を効率よく最小時間で得る方法を示す。本稿では, 凸関数を一括フィッティングする手法を提案し, 最適性を保証するとともに, 略スパースアフィン領域を提案する。
論文参考訳（メタデータ） (2020-11-06T15:17:00Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文参考訳（メタデータ） (2020-07-07T21:26:35Z)
Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文参考訳（メタデータ） (2020-06-28T23:18:58Z)
Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文参考訳（メタデータ） (2020-06-16T17:06:45Z)
Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。予測勾配降下アルゴリズムのランダム化近似を考察する。その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文参考訳（メタデータ） (2020-06-14T10:42:23Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)
Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-09T12:32:14Z)

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