論文の概要: Composable Coresets for Determinant Maximization: Greedy is Almost
Optimal
- arxiv url: http://arxiv.org/abs/2309.15286v1
- Date: Tue, 26 Sep 2023 21:46:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 17:27:10.162093
- Title: Composable Coresets for Determinant Maximization: Greedy is Almost
Optimal
- Title（参考訳）: 行列最大化のための構成可能なコアセット:グリーディはほぼ最適である
- Authors: Siddharth Gollapudi, Sepideh Mahabadi, Varun Sivashankar
- Abstract要約: a set of $n$ in $mathbbRd$, the emphdeterminant problem of the emphdeterminant problem to pick $k$ vectors with the maximum volume。
広く使われているGreedyアルゴリズムは、O(k)3k$の近似係数がほぼ最適である構成可能なコアセットも提供する。
- 参考スコア（独自算出の注目度）: 2.849878266188877
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the
\emph{determinant maximization} problem is to pick $k$ vectors with the maximum
volume. Determinant maximization is the MAP-inference task for determinantal
point processes (DPP) and has recently received considerable attention for
modeling diversity. As most applications for the problem use large amounts of
data, this problem has been studied in the relevant \textit{composable coreset}
setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19]
showed that one can get composable coresets with optimal approximation factor
of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves
an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show
that the widely-used Greedy algorithm also provides composable coresets with an
almost optimal approximation factor of $O(k)^{3k}$, which improves over the
previously known guarantee of $C^{k^2}$, and supports the prior experimental
results showing the practicality of the greedy algorithm as a coreset. Our main
result follows by showing a local optimality property for Greedy: swapping a
single point from the greedy solution with a vector that was not picked by the
greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$.
This is tight up to the additive constant $1$. Finally, our experiments show
that the local optimality of the greedy algorithm is even lower than the
theoretical bound on real data sets.
- Abstract（参考訳）: $\mathbb{R}^d$ における$n$ベクトルの集合が与えられたとき、 \emph{determinant maximization} 問題の目標は最大体積を持つ$k$ベクトルを選ぶことである。
決定的最大化(Determinant maximization)は、決定的ポイントプロセス(DPP)のためのMAP推論タスクであり、近年、モデリングの多様性に対して大きな注目を集めている。
問題のほとんどのアプリケーションは大量のデータを使用するため、この問題は関連する \textit{composable coreset} 設定で研究されている。
特に [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] は、この問題に対して最適近似係数が$\tilde O(k)^k$で構成可能なコアセットを得ることができ、局所探索アルゴリズムが$O(k)^{2k}$でほぼ最適な近似を保証することを示した。
本研究では,広く用いられているグリーディアルゴリズムが,従来知られていた$c^{k^2}$の保証よりも向上するほぼ最適近似係数である$o(k)^{3k}$の合成可能なコアセットを提供するとともに,グリーディアルゴリズムをコアセットとして実用性を示す先行実験結果をサポートすることを示す。
我々の主な結果は、グリーディの局所最適性を示すことによる: グリーディの解から、グリーディのアルゴリズムが選ばなかったベクトルに1点を置き換えることで、少なくとも1+\sqrt{k})$の係数で体積を増大させることができる。
これは加法定数が$$$の値に固まる。
最後に, 実験により, グリーディアルゴリズムの局所最適性は, 実データ集合上の理論的境界よりも低いことを示した。
関連論文リスト
- Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity [0.0]
我々は最も高速な決定論的アルゴリズムの近似係数を6+epsilon$から5+epsilon$に改善する。
本手法は, しきい値のグリーディ・サブルーチンと, 候補解としての2つの解集合の構築という, 2つの成分の性能を最適化することに基づいている。
論文 参考訳（メタデータ） (2024-05-20T02:24:58Z) - Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Sparse Convex Optimization via Adaptively Regularized Hard Thresholding [17.60502131429094]
本稿では,適応正規化ハードThresholding (ARHT) アルゴリズムを提案する。
また、OMP with Replacement (OMPR) for general $f$, under the condition $s > s* frackappa24$。
論文 参考訳（メタデータ） (2020-06-25T17:16:21Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。