論文の概要: Resolving the Approximability of Offline and Online Non-monotone
DR-Submodular Maximization over General Convex Sets
- arxiv url: http://arxiv.org/abs/2210.05965v1
- Date: Wed, 12 Oct 2022 07:04:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 15:59:51.386644
- Title: Resolving the Approximability of Offline and Online Non-monotone
DR-Submodular Maximization over General Convex Sets
- Title（参考訳）: 一般凸集合上のオフラインおよびオンライン非単調DR-サブモジュラー最大化の近似可能性の解消
- Authors: Loay Mualem and Moran Feldman
- Abstract要約: DR-サブモジュラー連続関数は、機械学習、通信システム、研究、経済学の分野において多くの実世界の応用を持つ。
tfrac14 (1 - m)$-the-art offline algorithmと一致する時間オンラインアルゴリズムを提示する。
また、我々のアルゴリズムとDuの(2022)オフラインはどちらも強い意味で最適であることを示す。
- 参考スコア（独自算出の注目度）: 13.23676270963484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent years, maximization of DR-submodular continuous functions became an
important research field, with many real-worlds applications in the domains of
machine learning, communication systems, operation research and economics. Most
of the works in this field study maximization subject to down-closed convex set
constraints due to an inapproximability result by Vondr\'ak (2013). However,
Durr et al. (2021) showed that one can bypass this inapproximability by proving
approximation ratios that are functions of $m$, the minimum
$\ell_{\infty}$-norm of any feasible vector. Given this observation, it is
possible to get results for maximizing a DR-submodular function subject to
general convex set constraints, which has led to multiple works on this
problem. The most recent of which is a polynomial time $\tfrac{1}{4}(1 -
m)$-approximation offline algorithm due to Du (2022). However, only a
sub-exponential time $\tfrac{1}{3\sqrt{3}}(1 - m)$-approximation algorithm is
known for the corresponding online problem. In this work, we present a
polynomial time online algorithm matching the $\tfrac{1}{4}(1 -
m)$-approximation of the state-of-the-art offline algorithm. We also present an
inapproximability result showing that our online algorithm and Du's (2022)
offline algorithm are both optimal in a strong sense. Finally, we study the
empirical performance of our algorithm and the algorithm of Du (which was only
theoretically studied previously), and show that they consistently outperform
previously suggested algorithms on revenue maximization, location summarization
and quadratic programming applications.
- Abstract（参考訳）: 近年、dr-サブモジュラー連続関数の最大化は重要な研究分野となり、機械学習、通信システム、運用研究、経済学の領域で多くの実世界の応用が行われている。
この分野の研究の多くは、Vondr\'ak (2013) による不適応性による下閉凸集合の制約によって最大化される。
しかし、dur et al. (2021) は、任意の可算ベクトルの最小$\ell_{\infty}$-norm の関数である近似比を証明して、この近似可能性を回避することができることを示した。
この観察から、一般凸集合制約を受けるDR-部分モジュラ函数を最大化するための結果を得ることができ、この問題に関して複数の研究がなされている。
直近の多項式時間 $\tfrac{1}{4}(1m)$-approximation オフラインアルゴリズムは du (2022) によるものである。
しかし、対応するオンライン問題では、サブ指数時間 $\tfrac{1}{3\sqrt{3}}(1 - m)$-approximation アルゴリズムのみが知られている。
本研究では,最先端オフラインアルゴリズムの$\tfrac{1}{4}(1m)$を近似した多項式時間オンラインアルゴリズムを提案する。
また,我々のオンラインアルゴリズムとdu(2022)オフラインアルゴリズムがどちらも強い意味で最適であることを示す近似可能性結果を示す。
最後に,我々のアルゴリズムとduのアルゴリズム(理論上は以前にしか研究されていなかった)の実証的性能について検討し,収益の最大化,位置要約,二次プログラミングアプリケーションにおいて,従来提案していたアルゴリズムを一貫して上回っていることを示す。
関連論文リスト
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint [18.290666675596984]
非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。
既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。
我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-22T20:56:57Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Adaptive Sampling for Fast Constrained Maximization of Submodular
Function [8.619758302080891]
非モノトーンサブモジュラに対する多対数適応性を有するアルゴリズムを一般側制約下で開発する。
本アルゴリズムは,$p$-system 側制約下での非単調部分モジュラ関数の最大化に適している。
論文 参考訳（メタデータ） (2021-02-12T12:38:03Z) - Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time [16.346069386394703]
単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
論文 参考訳（メタデータ） (2020-09-10T16:35:54Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Linear-Time Algorithms for Adaptive Submodular Maximization [17.19443570570189]
まず, 濃度制約を考慮した適応的部分モジュラー問題を提案する。
第二に、完全適応部分モジュラリティの概念を導入する。
提案アルゴリズムは,O(nlogfrac1epsilon)$関数の評価値のみを用いて,$frac1-1/e-epsilon4-2/e-2epsilon$近似比を実現する。
論文 参考訳（メタデータ） (2020-07-08T15:54:28Z) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳（メタデータ） (2020-06-16T17:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。