Fugu-MT 論文翻訳(概要): A Note On Deterministic Submodular Maximization With Bounded Curvature

論文の概要: A Note On Deterministic Submodular Maximization With Bounded Curvature

arxiv url: http://arxiv.org/abs/2409.02943v1
Date: Sun, 25 Aug 2024 01:16:30 GMT
ステータス: 処理完了
システム内更新日: 2024-09-08 14:53:30.133249
Title: A Note On Deterministic Submodular Maximization With Bounded Curvature
Title（参考訳）: 境界曲率による決定論的部分モジュラー最大化の一考察
Authors: Wenxin Li,
Abstract要約: Buchbinder と Feldman, FOCS'24] の最近のブレークスルー結果は,行列制約下での曲率 $kappa_f$ で部分モジュラ函数を最大化するための決定論的 $ (1-kappa_f/e-varepsilon)$-approximate アルゴリズムにさらに繋がることを示した。
参考スコア（独自算出の注目度）: 1.1717204003050075
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We show that the recent breakthrough result of [Buchbinder and Feldman, FOCS'24] could further lead to a deterministic $(1-\kappa_{f}/e-\varepsilon)$-approximate algorithm for maximizing a submodular function with curvature $\kappa_{f}$ under matroid constraint.
Abstract（参考訳）: Buchbinder and Feldman, FOCS'24] の最近のブレークスルーの結果は、行列制約の下で曲率$\kappa_{f}$で部分モジュラ函数を最大化するための決定論的 $(1-\kappa_{f}/e-\varepsilon)$-approximate アルゴリズムにさらに繋がることを示した。

関連論文リスト

Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文参考訳（メタデータ） (2023-03-17T13:32:33Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
論文参考訳（メタデータ） (2022-01-03T15:10:17Z)
Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文参考訳（メタデータ） (2021-06-09T01:59:55Z)
Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文参考訳（メタデータ） (2021-02-17T18:54:08Z)
Submodular Maximization via Taylor Series Approximation [16.682504954615922]
マトロイド制約を用いた部分モジュラー決定論的問題について検討する。この形式のために、いわゆる連続関数グリーディアルゴリズムは、テイラー級数近似を用いて、およそ 0.63$ 以前の$(1-1/e) に近い比率を得る。
論文参考訳（メタデータ） (2021-01-19T02:41:45Z)
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。最適なデータ依存上界を導出する。また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文参考訳（メタデータ） (2020-08-12T15:40:21Z)
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)
Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-09T12:32:14Z)

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