Fugu-MT 論文翻訳(概要): Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

論文の概要: Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

arxiv url: http://arxiv.org/abs/2405.14995v1
Date: Thu, 23 May 2024 18:56:46 GMT
ステータス: 処理完了
システム内更新日: 2024-05-27 19:17:31.806116
Title: Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
Title（参考訳）: 適応的部分モジュラカバーのグリーディ近似比に対する下界
Authors: Blake Harris, Viswanath Nagarajan,
Abstract要約: 適応部分モジュラー被覆のグリーディアルゴリズムは、少なくとも1.3*(1+ln Q)の近似比を持つことを示す。同じアルゴリズムに対して (1+ln2 近似比) を主張する先行結果を無効化する。
参考スコア（独自算出の注目度）: 5.26062227842158
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We show that the greedy algorithm for adaptive-submodular cover has approximation ratio at least 1.3*(1+ln Q). Moreover, the instance demonstrating this gap has Q=1. So, it invalidates a prior result in the paper ``Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization'' by Golovin-Krause, that claimed a (1+ln Q)^2 approximation ratio for the same algorithm.
Abstract（参考訳）: 適応部分モジュラー被覆のグリーディアルゴリズムは、少なくとも1.3*(1+ln Q)の近似比を持つことを示す。さらに、このギャップを示す例はQ=1である。そのため、Golovin-Krause の論文 ‘Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization' において、同じアルゴリズムの (1+ln Q)^2 近似比を主張する以前の結果を無効にしている。

関連論文リスト

On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms [4.307128674848627]
AdaPG$q,r$は、より大きな段階的なポリシーと改善された下位境界を提供することで、既存の結果を統一し、拡張するフレームワークである。パラメータの$q$と$r$の異なる選択について論じ、数値シミュレーションにより結果の有効性を実証する。
論文参考訳（メタデータ） (2023-11-30T10:29:43Z)
Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T17:26:39Z)
Partial-Monotone Adaptive Submodular Maximization [19.29174615532181]
サンプリングベースのポリシが近似比$(m+1)/10$ユーティリティ関数が$m$適応単調かつ適応部分モジュラーであることを示す。これにより、ユーティリティ機能がほぼ適応的なモノトンである多くの機械学習アプリケーションのバウンダリが改善される。
論文参考訳（メタデータ） (2022-07-26T12:16:12Z)
Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文参考訳（メタデータ） (2022-01-07T13:33:28Z)
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文参考訳（メタデータ） (2021-06-08T15:54:44Z)
Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。最適なデータ依存上界を導出する。また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文参考訳（メタデータ） (2020-08-12T15:40:21Z)
Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time [17.19443570570189]
濃度制約を受ける非単調適応部分モジュラー問題について検討する。適応的ランダムグリードアルゴリズムは適応的部分モジュラリティの下で1/e$の近似比を達成することを示す。我々は,$O(nepsilon-2log epsilon-1)$値オラクルクエリを期待して,1-1/e-epsilon$近似比を高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-08-11T21:06:52Z)
Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。第二に、完全適応部分モジュラリティの概念を導入する。提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文参考訳（メタデータ） (2020-07-08T15:54:28Z)
Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文参考訳（メタデータ） (2020-06-24T06:01:24Z)
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)

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