論文の概要: How Do You Want Your Greedy: Simultaneous or Repeated?
- arxiv url: http://arxiv.org/abs/2009.13998v2
- Date: Tue, 13 Jul 2021 18:02:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-13 07:21:19.561397
- Title: How Do You Want Your Greedy: Simultaneous or Repeated?
- Title（参考訳）: 欲しがる理由 - 同時に繰り返すか、繰り返すか?
- Authors: Moran Feldman, Christopher Harshaw, Amin Karbasi
- Abstract要約: 制約付き部分モジュラーユリアに対する決定論的アルゴリズムであるSimultaneousGreedysを提案する。
また、これらのアルゴリズムを実装するパッケージであるSubmodularGreedyも提示する。
- 参考スコア（独自算出の注目度）: 41.440943886672855
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present SimultaneousGreedys, a deterministic algorithm for constrained
submodular maximization. At a high level, the algorithm maintains $\ell$
solutions and greedily updates them in a simultaneous fashion.
SimultaneousGreedys achieves the tightest known approximation guarantees for
both $k$-extendible systems and the more general $k$-systems, which are
$(k+1)^2/k = k + \mathcal{O}(1)$ and $(1 + \sqrt{k+2})^2 = k +
\mathcal{O}(\sqrt{k})$, respectively. This is in contrast to previous
algorithms, which are designed to provide tight approximation guarantees in one
setting, but not both. We also improve the analysis of RepeatedGreedy, showing
that it achieves an approximation ratio of $k + \mathcal{O}(\sqrt{k})$ for
$k$-systems when allowed to run for $\mathcal{O}(\sqrt{k})$ iterations, an
improvement in both the runtime and approximation over previous analyses. We
demonstrate that both algorithms may be modified to run in nearly linear time
with an arbitrarily small loss in the approximation.
Both SimultaneousGreedys and RepeatedGreedy are flexible enough to
incorporate the intersection of $m$ additional knapsack constraints, while
retaining similar approximation guarantees: both algorithms yield an
approximation guarantee of roughly $k + 2m + \mathcal{O}(\sqrt{k+m})$ for
$k$-systems and SimultaneousGreedys enjoys an improved approximation guarantee
of $k+2m + \mathcal{O}(\sqrt{m})$ for $k$-extendible systems. To complement our
algorithmic contributions, we provide a hardness result which states that no
algorithm making polynomially many oracle queries can achieve an approximation
better than $k + 1/2 + \varepsilon$. We also present SubmodularGreedy.jl, a
Julia package which implements these algorithms and may be downloaded at
https://github.com/crharshaw/SubmodularGreedy.jl . Finally, we test the
effectiveness of these algorithms on real datasets.
- Abstract（参考訳）: 我々は制約付き部分モジュラー最大化のための決定論的アルゴリズムであるSimultaneousGreedysを提案する。
高いレベルでは、アルゴリズムは$\ell$ソリューションを維持し、それらを同時に更新する。
同時にGreedysは、$k$-extendibleシステムとより一般的な$k$-systemsの両方に対して最も厳密な近似保証を達成し、それぞれ$(k+1)^2/k = k + \mathcal{O}(1)$と$(1 + \sqrt{k+2})^2 = k + \mathcal{O}(\sqrt{k})$である。
これは、1つの設定で厳密な近似を保証するように設計されているが、両方ではない以前のアルゴリズムとは対照的である。
また, 反復感情の分析も改善し, $k + \mathcal{o}(\sqrt{k})$ に対して$k$-systems に対して$k + \mathcal{o}(\sqrt{k})$ の近似比を達成できることを示した。
両アルゴリズムがほぼ線形時間で動作するように修正されることを実証し,近似の損失を任意に小さくすることを示した。
両方のアルゴリズムは、約$k + 2m + \mathcal{O}(\sqrt{k+m})$ for $k$-systems と SimultaneousGreedys は、$k+2m + \mathcal{O}(\sqrt{m})$ for $k$-extendible systems の近似を保証する。
アルゴリズムによるコントリビューションを補完するために、多項式的に多くのオラクルクエリを生成するアルゴリズムが$k + 1/2 + \varepsilon$よりも良い近似を達成できないという難しさの結果を提供する。
SubmodularGreedy.jlは、これらのアルゴリズムを実装したJuliaパッケージで、https://github.com/crharshaw/SubmodularGreedy.jlでダウンロードできる。
最後に,これらのアルゴリズムの有効性を実際のデータセット上で検証する。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。
次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。
Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
論文 参考訳（メタデータ） (2020-06-21T06:57:59Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。